Codeforces Round 838

發表於 更新於 分類於 ， Disqus： 文章字數： 2.4k 所需閱讀時間 ≈ 8 分鐘
D(gcd)E(Cayley's formula)F(DP,线段树)G(构造)

https://codeforces.com/contest/1762

D. GCD Queries

交互题

有 [0…n-1] 的排列 固定但是隐藏

你最多 2n 次询问, 找到2个下标, 其中一个要是0的下标

每次可以询问 gcd(a[i],a[j]), i!=j

范围

n 2e4

3s

256mb

我的思路

筛出 2的倍数

筛出 4的倍数

这样下去就可以了

但 次数无法保证

要找2的倍数 首先得找到一个是2的倍数的, 这最坏需要 n/2 + 3 次, 再找 就需要 n - 4 次

题解

就是 删除不可能, 每次选3个

如果是 0, v1, v2 那么结果将是

gcd(0,v1) = v1

gcd(0,v2) = v2

gcd(v1,v2) = gcd(v1,v2)

v1 一定不等于 v2, 至多2个1

0 一定出现在最大 的计算中

这样看起来要3次, 但是 删除了一个以后再加入的的话, 额外只用两次

没了

我的代码

https://codeforces.com/contest/1762/submission/186044700

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;}

int n;

void ans(int x,int y){
  printf("! %d %d\n",x,y);
  fflush(stdout);
  int v;
  scanf("%d",&v);
  assert(v==1);
}

int query(int i,int j){
  printf("? %d %d\n",i,j);
  fflush(stdout);
  int v;
  scanf("%d",&v);
  return v;
}

void w(){
  n = read();
  if(n==2){
    ans(1,2);
    return ;
  }
  int v0=1;
  int v1=2;
  int g=query(v0,v1);
  rep(v,3,n+1){
    int g0v = query(v0,v);
    int g1v = query(v1,v);
    if(g > g0v && g > g1v){
      continue;
    }else if(g0v > g && g0v > g1v){
      v1 = v;
      g = g0v;
    }else { // g1v max
      v0 = v;
      g = g1v;
    }
  }
  ans(v0,v1);
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

E. Tree Sum

n 点 有边权(1/-1)树, 每个点所连边权乘积为 -1, 称做好树

求 所有好树 中1->...->n 的简单路径边权和 mod 998244353

范围

n 5e5

3s

256mb

我的思路

感觉连怎么统计好树都不会, 没啥树上统计的经验

但 只求路径权 和, 也许可以转化成贡献统计

然后注意到 1和n其实没有什么特殊的, 所以 任意两点u,v 统计出来是等价的

所以 ans = 好树 所有简单路径和 再 除以 (n-1) * n / 2

而一条边的贡献, 等于 它的权 乘上 左侧点数 乘上 右侧点数

考虑显然 叶子连的是-1

而 左侧两点 的边是 1

猜性质 边 = -1 的 一侧点的幂次

归纳, 如果 < n 成立, 那么直接连一定是奇数个奇数, 得证

所以好树 的 充要条件就是 n是偶数

依然不知道怎么统计

因为不知道能出现多少次 (1,n-1) (2,n-2)…

其实直接按贡献拆

强算?

n-1个点的有根树 方案数f(n-1), binom(n,1) * f(1) * f(n-1), 需要注意的是 (n/2,n/2) 的分割不要重复计算(通过指定1在哪侧)

f咋算?

显然 f(1)=1

?????? 有点像生成函数 不会了

题解

Hint 1 也是 n 偶数 充分要

Hint 2 给定形状 唯一权重赋值方案, 显然

一样 也是 左侧l点,右侧r=n-l点, 那么权为 -1的l次方

考虑贡献为

$\binom{n-2}{l-1} \cdot l \cdot r \cdot l^{l-2} \cdot r^{r-2}$

解释: 强制1在左侧,n在右侧

那么 除了1以外, 还有 l-1个在左侧, 所以第一个$\binom{n-2}{l-1}$ 决定了哪些点在左侧

$l^{l-2}$ 和 $r^{r-2}$ 就是 根据 Cayley’s formula 两边树的形状(但是 形状没有指定根)

所以还要指定 这个边连的哪个点(指定根) 所以还有l * r

没了

代码

https://codeforces.com/contest/1762/submission/186049033

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

ll read(){ll r;scanf("%lld",&r);return r;}

ll fac[500010]={1};
ll ifac[500010];
ll binom(int n,int m) {return (m>n or m<0)?0:(fac[n]*ifac[m]%MOD*ifac[n-m]%MOD);}
ll mypow(ll v,ll pwr){
  if(pwr==-1) return 1;
  ll r=1;
  while(pwr){
    if(pwr&1) (r*=v)%=MOD;
    (v*=v)%=MOD;
    pwr/=2;
  }
  return r;
}

int main(){
  int n=read();
  rep(i,1,n+1) fac[i]=fac[i-1]*i%MOD;
  ifac[n]=mypow(fac[n],MOD-2);
  per(i,0,n) ifac[i]=ifac[i+1]*(i+1)%MOD;
  ll ans=0;
  int neg1pwr=-1;
  rep(l,1,n){
    int r=n-l;
    (ans += neg1pwr*binom(n-2,l-1)*l%MOD*r%MOD*mypow(l,l-2)%MOD*mypow(r,r-2)%MOD)%=MOD;
    neg1pwr*=-1;
  }
  printf("%lld\n",(ans+MOD)%MOD);
  return 0;
}

F. Good Pairs

给长N数组, 问有多少对(l,r) 可以 通过中间|ai-aj|<=k (值差距不超过k 连接)

范围

n 5e5

k [0,1e5]

ai [1,1e5]

3s

256mb

我的思路

当给定l时, r可以扫描, 每次维护可达值的上下界即可

这样的话 空间 O(1), 时间O(n^2)

题解

拆 al < ar 和 al = ar 和 al < ar 来做

那么上面就变成 al < a.. < a.. < a.. < ar , 且增量在 [1,k]

这样可以建立dp[i]= i为l的r的方案数

倒着循环, 找最小的下标j > i,且 aj-ai \in [1,k]

dp[i] = dp[j] + count(a[i…] in [ai+1,aj])

搞点数据结构 就没了

G. Unequal Adjacent Elements

给点一个长n数组a

找一个 奇数项 和 偶数项 分别单调递增的[1-n]排列p

使得 a按照p排序后 相邻项均不想等 (即 a[p[i-1]]!= a[p[i]])

或 报告不存在方案

范围

n 3e5

ai [1,..,n]

2s

256mb

我的思路

说是找两个排列, 但是这里的 单增限制更像是说从 a中 顺序的提取出 n/2 个, 剩下的 n-n/2 个 和这 n/2 个交差排布, 保证相邻不等

感觉还是很构造

一个想法就是 如果最多出现的值x恰好是出现了一半, 那么正好选出它们 就能

x v0 x v1 x v2 …

而如果> 一半+1 ( 可能奇数个), 那么, 再怎么都会重复

现在问题是 小于1半的时候怎么去选

感觉会出现 aaaaabbbbbccccc 的情况, 选了a以后, 还没到n/2, 剩下的不能去选c

如果能把一些 选完,且刚好n/2 的话 也是一个方案, 但上面这样也是无法做到把 某几类选完

题解

也是 > n/2 则没有办法

hint2 也是一样, 如果一个恰好一半的,

hint3:

切割原数组, 让每个都是可以这样的, 然后反过来拼接

两个问题: 一定能切割吗? 拼接处相等怎么办?

第二个问题相对简单, 考虑到 x v0 x v1 x v2 和 v0 x v1 x v2 x 无非就是选取不同, 所以拼接处可以根据情况 取反

一定能切割吗, 比如上面这种 aaaaabbbbbccccc

这里要做的就是, 每次切出一段, 让剩余的满足 > n/2, 而切出的满足 = n/2

然后为了连接的地方合法, 这里的办法是 例如处理了 (x v0 x v1 x v2)

那么 v2 复用到接下来的处理中

这样最后一个段,可以倒过来回退, 一定能回到相等, 否则就是 n/2+1了

这样 a就是 始终可以分割的!!

代码

https://codeforces.com/contest/1762/submission/186158676

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;}

#define all(x) x.begin(),x.end()
void w(){
  ll n=read();
  vector<ll> a(n+5),cnt(n+5,0);
  rep(i,1,n+1){
    a[i]=read();
    cnt[a[i]]++;
  }
  rep(i,1,n+1) if(cnt[i]>(n+1)/2){ // 大于一半一定不行
    printf("NO\n");
    return;
  }
  vector<ll> ans;
  int cur=1; // 下标
  while(cur<=n){ // [cur...n]
    ll val=a[cur]; // 当前切出的 需要个数 = len/2 的值,
    vector<int> v1; // 放==val的下标
    vector<int> v2; // 放!=val的下标
    while(cur<=n){
      (a[cur]==val?v1:v2).push_back(cur);

      if(v1.size()==v2.size()){ // 保证取出的合法, 但是没保证剩余的?
        rep(i,0,size(v1)){
          ans.push_back(v1[i]);
          ans.push_back(v2[i]);
        }
        ans.pop_back(); // cur 即是 分离出的结尾, 又是下一个的开头
        break;
      }
      if(cur==n){ // 最后一段 [v1[0].....n] 被拆分到了 v1, v2 里, 因为 v1长度先为1, 所以v1的长度一定大于v2
        while(!(ans.empty()||v1.size()==v2.size())){ // 总能退到v1的个数 和v2相等, 否则v1刚好n/2+1个
          (a[ans.back()]==val?v1:v2).push_back(ans.back());
          ans.pop_back();
        }
        sort(all(v1));
        sort(all(v2));
        if(v1.size()!=v2.size()){ // v1 刚好n/2+1个
          ans.push_back(v1[0]);
          v1.erase(v1.begin());
        }
        if(!v2.empty()&&!ans.empty() && a[ans.back()]==a[v2[0]]) swap(v1,v2);
        rep(i,0,v1.size()){
          ans.push_back(v2[i]);
          ans.push_back(v1[i]);
        }
        cur=n+1;
      }
      cur++;
    }
  }
  printf("YES\n");
  for(auto v:ans)printf("%lld ",v);
  printf("\n");
  return;
}
int main() {
  int t=read();
  while(t--) w();
  return 0;
}

总结

D

没有智力, 老想二分

E

哦 它这里的提示我也没看到, 提示给了Cayley’s formula, n点 有标签的 无根树有$n^{n-2}$ 个

然后这里 要在1…n的路径上, 其实就是1在一侧, n在另一测, 哎, 这都没发现好蠢, 感觉我那样一般化去算所有反而多此一举

F

我也注意到了增减 互不影响, 但没去想拆开来做, 一旦明确拆开, 剩下的就是数据结构了, 唯一需要注意就是 复用保证效率

G

这 提示里好几个都是 hint能想到部分, 但是往后推的时候 延伸不出去

后面这个构造+回退, 感觉完全学不会

参考

官方

https://en.wikipedia.org/wiki/Cayley%27s_formula