Codeforces TypeDB Forces 2023

發表於 更新於 分類於 ， Disqus： 文章字數： 1.9k 所需閱讀時間 ≈ 6 分鐘
E(xor,贪心)F(排列,实现)G(TODO)H(TODO)I(TODO)

https://codeforces.com/contest/1787

E. The Harmonization of XOR

问 [1,2,3,…,n] 能否拆成k个非空序列(不一定连续), 且每个序列内的数字xor为x

如果可以给具体方案

范围

n 2e5

x [1,1e9]

1s

256mb

我的思路

想了很久线性基, 没啥办法, 感觉都是O(n^2)以上

然后 显然 如果 k为奇数那么 x = xor[1..n], 如果k为偶数, 0 = xor[1…n]

然后n%4==3 的时候 xor[1..n] = 0

然后n%4==0 的时候 xor[1..n] = n

然后n%4==1 的时候 xor[1..n] = 1

然后n%4==2 的时候 xor[1..n] = n+1

其中 n%4==1 很好做, 相邻取偶数和偶数+1 就能构成

n%4==0和n%4==2没有什么办法, 但是这个如果暴力出来,是可以打表的

但是n%4==3 就连打表都不行

题解

显然 3个一样的能合并成一个, 那么其实需要考虑的是最多能拆成多少个

然后是贪心 尽量 [a, a^x] 成一组, 显然 不妨设 a < a^x, 那么 a0!=a1 则 a0^x != a1^x, 所以两两不等

问题是 有没有可能 不能构成的 部分 可以 >=2 个一组得到x?

令B是x最高位bit

B一定是要存在

M = 1~n 中B是1的个数

那么 组数一定<=M (因为至少需要一个提供)

val的B位有1, 那么 val^x < val, 所以M个有1的都能找到一个比它小而且没1的, 所以剩下的一定B位都没有1, xor=0

代码

https://codeforces.com/contest/1787/submission/191286044

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
#include <bits/stdc++.h>
using namespace std;
typedef int i32;
#define rep(i,a,n) for(i32 i=(a);i<(i32)(n);i++)
#define per(i,a,n) for(i32 i=(n);i-->(i32)(a);)
i32 read(){i32 r;scanf("%d",&r);return r;}

i32 n;
void w(){
  n = read(); // 2e5
  int k=read(); // 2e5
  int x=read();
  int all = 0;
  rep(i,1,n+1) all^=i;
  if(k%2==0){
    if(all!=0) {
      printf("NO\n");
      return ;
    }
  }else{
    if(all != x) {
      printf("NO\n");
      return ;
    }
  }
  int b=0;
  per(pwr,0,20) if(x&(1<<pwr)){
    b=1<<pwr;
    break;
  }
  vector<int> used(n+1,0);
  vector< vector<int> > ans;
  if(k > 1){
    rep(i,1,n+1) if(i&b){
      used[i]=true;
      if(i==x){
        ans.push_back({i});
      }else{
        ans.push_back({x^i,i});
        used[x^i]=true;
      }
      if(k-1==(int)ans.size()) break;
    }
  }
  ans.push_back({});
  rep(i,1,n+1) if(!used[i]) ans.back().push_back(i);
  if(ans.back().size()==0) ans.pop_back();
  if((int)ans.size() != k){
    printf("NO\n");
    return;
  }
  printf("YES\n");
  for(auto &row:ans) {
    printf("%d",(int)row.size());
    for(auto v:row) printf(" %d",v);
    printf("\n");
  }
}

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

F. Inverse Transformation

给一个排列, 经过一轮就会让 a[i] = a[a[i]]

现在给你a经过k轮后的 a’

又定义 f(i) = 一个排列中第i个位置跳转几次回到自己

求一个初始a 要 sum_{i=1..n} 1/f(i) 最小

范围

n 2e5

k [1,1e9]

1s

256mb

我的思路

排列经典就是构成环, 稍微画一下就会发现, 如果当前长度是偶数, 那么 经过一轮就会被拆成两个圈(奇偶交错)

如果当前是奇数,那么只是错位圈不会被拆

而要达到最小值的就是, 1/f(i) 也就是每个点所在的圈尽量大

不可行状态就是, 一个偶圈不能向上k次偶数操作

所以找相同长度的,尽量去2的幂次个的合并, 比如7个长度3的, 那么就合并出 1个4 * 3的, 1个2 * 3的,1 个 1 * 3的

然后虽然拆环,但是结果依然是 2^k % (环长)

还原的部分 写吐了

代码

https://codeforces.com/contest/1787/submission/191295693

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for(ll i=(a);i<(ll)(n);i++)

ll read(){ll r;scanf("%lld",&r);return r;}
int pow2(int y, int M) {
  ll x = 2;
  ll r= 1;
  while (y) {
    if (y & 1) (r*=x)%=M;
    (x*=x)%=M;
    y/=2;
  }
  return r % M;
}

vector<int> cyc[200010];
int nxt[200010];
int ans[200010]; // 下标无意义, 上面的连续值构成环
void w() {
  int n=read(); // 长度
  int m=read(); // 操作次数
  vector<bool> vis(n+1,0);
  rep(i,1,n+1) cyc[i]={}; // cyc[长度] = {圈头}
  rep(i,1,n+1) nxt[i]=read();
  rep(i,1,n+1) if(!vis[i]){
    int j = i;
    int z = 0;
    do {
      ++z;
      vis[j] = 1;
      j = nxt[j];
    } while (j != i);
    cyc[z].push_back(i);
  }
  int lim = pow2(min(m, 20), 1e9); // 2^{min(m,20)} < 1e9, 保证超过n时
  rep(i,1,n+1) if (cyc[i].size()){
    if (i % 2 == 0 and cyc[i].size() % lim) { // 是偶数, 则至少需要可以反向合并lim次
      printf("NO\n");
      return;
    }
    for(int j = lim; j > 0; j /= 2) {
      while((int) cyc[i].size() >= j) { // 不要if 可能本来次数就小
        vector tmp(i*j,0);
        rep(k,0,j){
          int idx = k; // [0~i*j)
          int o = cyc[i].back(); // 环的头
          do {
            tmp[idx] = o; // 计算正向转移idx记录在
            (idx += pow2(m, i*j))%=(i*j); // +2^m % (i*j)
            o = nxt[o];
          } while (o != cyc[i].back());
          cyc[i].pop_back();
        }
        rep(k,0,i*j) ans[tmp[k]] = tmp[(k+1)%(i*j)];
      }
    }
  }
  printf("YES\n");
  rep(i,1,n+1) printf("%d%c",ans[i], " \n"[i == n]);
}

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

G. Colorful Tree Again

n点,有边权wi的树, 每个边有颜色ci, 每个点可以是 block/unblocked, 初始都unblocked

path length = 简单路径边权和

good path 边同色 + 点全部unblocked, (且所有这个颜色的都在这个path上)

q个询问, 需要处理2种操作

  1. block点

  2. unblock点

每次操作后, 返回最大good path

如果没有good path ,返回0

范围

n 2e5

q 2e5

w,ci 2e5

2s

512mb

我的思路

读错题了

颜色不会变, 所以对于同色的联通块 单独考虑

每个边属于一个连通块, 每条边最多两个点, 所以最多2(n-1)个点

那么问题变成 在某个联通块的某个 点block/unblock 以后最长的变化

但这里有问题在于, 不同色的边可以共点, 于是上面的点操作就可能一次影响很多个联通块

先考虑说一个联通块里增加block/unblock 怎么办

如果 当前最长的和点无关, 那么block不影响, 否则需要重新计算? 重新计算就是 算分割后的几个块的直径

如果是树状dp

f[u] 表示子树到u 最长的距离

dp[u] = 子数u中最长的路径

dp[u] = max(dp[v0,v1,v2], f[vi]+f[vj]+1)

要求的的dp[root]

那么每次block 一个点

就是它的子树不影响

f[u] = 0

dp[u] = max(dp[v0,v1,v2])

然后向上所有它提供的 dp都要改,感觉会影响一条到root的链(但是注意到它在变小,所以如果没有影响最长可以提前break,但是对于造数据可以影响来说没有意义)

题解

好家伙, 读错题了, 题目里有一个所有颜色也在这个path上的

那么也就是 所有能成为good path的需要成一条线

而所有good path不会变长度,只会选中和不选

那么block一个点, 就是这个点上所有颜色 都变为不选计数+1

unblock 一个点, 就是 所有这个点上的颜色 不选的计数-1, 不选计数为0的才会选

总结

E

想过贪心, 但是一眼不知道怎么证明

感觉是xor相关的性质不熟悉,数学推理也拉跨, 我看noimi只用了9min 就做了E

F

赛内看题晚+编码慢,但是想出了解法, 本身从逻辑上没任何难度(比E需要数学证明一下 简单太多), 就是写着恶心, noimi妹妹写了1小时零5分钟, 虽然jiangly和tourist只花了不到20min

看来以后打Div1可能要是要先读一下后面的题, 过了F也不至于掉分

参考

官方