YeXiaoRain Blog(hexo的搜索高亮会破坏latex)

發表於 更新於 分類於 ， Disqus： 文章字數： 950 所需閱讀時間 ≈ 3 分鐘
D(树的边与点,贡献统计,DP,特殊题目条件)

题目

https://atcoder.jp/contests/arc140/tasks/arc140_d

初始有 n 个点，给定一个长度为 n 的数组 ai，若 ai≠−1，则有无向边 (i,ai)，若 ai=−1，则点 i 可以连向 1∼n 任意点，求所有图的联通块个数之和

n 2e3

答案mod 998244353

题解

考虑G中一个联通分量

如果它有N点,N个边,那么它恰好有一个环

这关键就在题目的特殊性上,因为(i->ai),即每个点连出一条边,所以n个点组成的联通分量一定恰好N个边, 题目条件特点!

因此 题目变成统计环的 而不是统计联通分量

然后先考虑 非-1的部分已经构成的环, 这部分如果再和其它相连,那么额外连的部分一定不会再有环,是个树,所以其它和它连的部分一定不会再贡献,

所以在考虑-1构成环的话不会考虑已经初始有环的联通分量

对于目前剩余没有环的联通分量是树,把这些树标号从1到k,并且b[i]表示这些树的点的个数, 注意到它一定只有一条未连接的边

现在考虑一个环的构成, 一定是由一些树连成的

树1->树2->树3->树k->树1

我们不考虑没有参与到环中的其它树,即使它从联通分量角度连进来了, 我们之考虑对环的构成直接有贡献的树

那么 如果是由 k个构成的,每一个的树的出点是固定的,但是入点的选择是上一个树的点的个数, 而它们排成环的方案是(k-1)!

所以环的构成是$(k-1)! \times \prod_{i=1}^{k} B_{x_i}$

n 很小 n方 可以接受可以DP

说是分治计算$\prod_{i=1}^{K} (1 + B_ix)$可以做到 n log(n)

代码

https://atcoder.jp/contests/arc140/submissions/31923069

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
71
72
73
74
75
76
77
78
79
80
81
#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;)
#define pb push_back

int n;
int a[2010];// 读入
int fa[2010]; // 并查集父节点
int sz[2010]; // 点个数
bool cir[2010]; // 是否有环

int getfa(int x){
  return x == fa[x]?x:(fa[x] = getfa(fa[x]));
}

void link(int u,int v){
  int fu = getfa(u);
  int fv = getfa(v);
  if(fu == fv){
    cir[fu] = true; // 有环
    return;
  }
  sz[fv] += sz[fu]; // 大小
  cir[fv] |= cir[fu]; // 环
  fa[fu] = fv;
}

ll mypow(ll v,int pwr){
  ll r = 1;
  while(pwr){
    if(pwr%2)(r*=v)%=MOD;
    (v*=v)%=MOD;
    pwr/=2;
  }
  return r;
}
ll fac[2010] = {1}; // 阶乘

int main(){
  cin>>n;
  int freecnt = 0; // 自由度 -1 个数
  rep(i,1,n+1){
    fa[i] = i;
    sz[i] = 1;
    fac[i] = fac[i-1]*i%MOD;
    scanf("%d",a+i);
    freecnt += a[i] == -1;
  }
  rep(i,1,n+1){
    if(a[i] == -1)continue;
    link(i,a[i]);
  }
  vector<int> arr ;
  int circnt = 0;
  rep(i,1,n+1){
    if(fa[i] != i)continue; // 非联通块根
    if(cir[i]){ // 环
      circnt++;
      continue;
    }
    arr.push_back(sz[i]); // 树 有一个自由度
  }
  ll ans = circnt * mypow(n,freecnt) % MOD; // 本身就是环的贡献
  vector<ll> mulsum(n+10,0); // dp mulsum[树的个数] = sz乘积和
  mulsum[0] = 1;
  rep(i,0,(int)arr.size()){
    rep(k,0,i+1){
      // 注意前面一半只是 k+1个构成环的方案数, 对于环以外的 freecnt-k-1的自由度任意搭配 才是这些环对总答案的贡献值
      (ans += fac[k] * mulsum[k] % MOD * arr[i] % MOD * mypow(n,freecnt-k-1) % MOD)%=MOD;
    }
    per(k,0,i+1){
      (mulsum[k+1] += mulsum[k]*arr[i])%=MOD;
    }
  }
  printf("%lld\n",ans);
  return 0;
}

总结

我想了很久,都没有注意到题目条件特殊性带给联通分量的特殊性, 这还是不应该,应该加强这方面的反应

其实也算是树的知识没有警醒我, 边=点-1,那么就会反应到这里连通分量的边 <= 点 且 >= 点-1

参考

官方

發表於 更新於 分類於 ， Disqus： 文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘
F(无向图,图,奇数环,偶数环,树上差分)

题目

https://codeforces.com/contest/1680/problem/F

给一个连通无向图,n点,m 边

点覆盖: (所有边至少一个点属于点集

lenient点覆盖: 是点覆盖,且至多一条边两个点都在点集中

找出一个 lenient点覆盖

范围

t 1e4

n 1e6

5s

512MB

我的思路

首先 如果能黑白染色,成功,那么也就是每个边一端黑一端白, 全选黑或全选白都是一个答案

如果 黑白染色出现冲突,那么这两个点一定在一个奇环上

也就是这个奇环上存在两个点都是黑色, 最可以先把这个环上的边全部当作不存在,重新做染色,如果能成功, 计算这个环上同一个并查集点的颜色关系,

如果两两都不在同一个集合中那么说明拆了环都是独立的部分,那么任意染黑白即可

如果存在 a—–b 同集合中

a,b 同色 , [a..b]个数奇数的一半一定是黑白间隔

a,b 异色 , [a..b]个数偶数的一半一定是黑白间隔

换句话说, 其实原图去掉那个两个点都在集合中的边, 剩下的满足黑白染色,现在则是看哪些确定可以连起来

过程中检查冲突

如果剩余还有没连的 任选一个作为分割即可

但是 实现上能找环但如何找奇环

独立染色可以写,但合并时如何实现?

题解

前面几段和我想的一样, 奇偶黑白染色, 也就是需要在奇数环上剪断一条边,让整个染色合法

这里主要是 对无向图做dfs建立树

那么出现环的时候就是子节点指向父节点的时候

我们在dfs过程中黑白染色,那么出现回边时根据染色就可以知道它是奇环还是偶环,

如果我们统计了每条边出现在我们找到的奇环上的次数,和偶环上的次数,那么 如果一条边出现在奇数环上次数等于所有奇环次数,偶数环次数为零,那么删除这条边即可(可能有多个满足,任意删除一条)

// 必要性proof见下面, 充分显然

所以接下来就是当发生回环时,如何统计边在奇环偶环上出现次数了,如果直接对边计数,那么复杂度就过不了

树上差分, cnt[id]表示边id到根的所有边都 进行了+cnt[id],这样 当有点u到点v的回边时,就 cnt[faedge[u]]++,cnt[faedge[v]]–, 对于不在树上的回边edge[id] = {u,v}不需要差分直接统计, cnt[id]++

最后统计完后整理具体次数

然后找满足的边拆掉,再染色即可(注意拆掉边两端需要是黑色

性质证明

这里 显然的是 如果是两端同色的点, 那么它一定在所有奇环中,不在所有偶环中

也就是必要性显然

如果我们枚举了所有的环,那么拆掉它,所有奇数环也被拆掉了, 所以充分性也成立

问题是上面的实现 并没有枚举所有的环,枚举的只是树边+一条回边的所有环, 而环可能是由多条回边构成的

引理1: 如果环A和环B的一部分拼成环C,那么ABC中要么全是偶环,要么其中两个是奇环,

(这里拼成的意思是 A 和 B 有共用的一条链, C= (A-共用链)+(B-共用链)

那么要证明的是两部分, 这个两端同色的边也在未统计到的多回边的奇数环中,不在未统计到的多回边偶数环中

如果它(两端同色的边)不在未统计到的多回边奇数环中

那么这个环H(奇,回边=n) 可以拆成一个H1(奇,回边n-1) + H(偶,回边1)

因为H(偶,回边1) 我们一定计算到了, 只能递归下降, 且不会在 它们两的重复边上,因为它不在偶环上

那么这个环H(奇,回边=n) 可以拆成一个H1(偶,回边n-1) + H(奇,回边1)

因为H(奇,回边1) 我们一定计算到了 所以它在奇数环中

综上它一定在 未统计到的多回边奇数环中

如果它在未统计到的多回边偶数环中

那么这个环H(奇,回边=n) 可以拆成一个H1(偶,回边n-1) + H(偶,回边1)

它一定不在 H(偶,回边1) 中, 所以递归下降,且它也不在 两个环共用的边上

那么这个环H(偶,回边=n) 可以拆成一个H1(奇,回边n-1) + H(奇,回边1)

注意到上述结论, 这个边一定在这两个环里都有,因此这个边在它们重复的边上而不在偶环里

因此 得证

代码

https://codeforces.com/contest/1680/submission/158000410

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i = (a);i<(b);i++)
#define all(v) (v).begin(),(v).end()
const int N = 1000000;
int n,m;
int odd; // 奇环个数
int cnt0[N+10]; // cnt0[边]偶环个数，
int cnt1[N+10]; // cnt1[边]奇环个数，
int c[N+10]; //c节点颜色，
bool vis[N+10]; // dfs中访问过, 多次复用
int fe[N+10]; //fe父边
// 读入
pair<int,int> e[N+10]; // [边] = {点id,点id}
vector<pair<int,int>> G[N+10]; // [点] = 数组 {点id,边id}
//二分图染色同时找环
void dfs(int u,int p/*父边*/,int cl /*颜色*/ ) {
  c[u]=cl;
  vis[u]=1; // 管的当前到根的链上是否有, 减少重复计算 简化差分统计
  fe[u]=p;
  for(auto [v,id]:G[u]){
    if (id==p)continue;
    if (c[v]==-1){ // 未访问过
      dfs(v,id,cl^1);
    } else if(!vis[v]){ // 非父节点
      continue;
    } else if (c[v]==(cl^1)) { //偶环
      cnt0[id]++; // 不在树上的回边
      cnt0[p]++; // 树上边 差分统计 表示这个边到根的次数都+1
      if(~fe[v])cnt0[fe[v]]--; // 这个边到根的次数都-1
    } else { // if (c[v]==cl) {//奇环
      odd++; // 奇环个数
      cnt1[id]++;
      cnt1[p]++;
      if(~fe[v])cnt1[fe[v]]--;
    }
  }
  vis[u]=0;//回溯时撤销访问标记
}
// 整理差分数组，得到每条边的计数, 只用处理树边,递归, 不用处理非树的回边
void dfs2(int u) {
  vis[u]=1;
  for(auto [v,_]:G[u]){
    if (vis[v]) continue;
    dfs2(v);
    if (fe[u]!=-1&&fe[v]!=-1){
      cnt0[fe[u]]+=cnt0[fe[v]];
      cnt1[fe[u]]+=cnt1[fe[v]];
    }
  }
}
void dfs3(int u,int cl) { //二分图染色
  c[u]=cl;
  for(auto [v,_]:G[u]){
    if (c[v]!=-1) continue;
    dfs3(v,cl^1);
  }
}
void run(){
  // 一系列初始化
  odd=0;
  scanf("%d %d",&n,&m);
  rep(i,0,n) G[i].clear();
  fill(cnt0,cnt0+m+3,0);
  fill(cnt1,cnt1+m+3,0);
  fill(c,c+n+3,-1);
  fill(vis,vis+n+3,0);
  // 读入
  rep(i,0,m){
    int u,v;
    scanf("%d %d",&u,&v);
    e[i]={--u,--v};
    G[u].pb({v,i});
    G[v].pb({u,i});
  }
  dfs(0,-1,0); // 以0 为根染色0搜索
  // 整理树上差分数组 变成每个边的统计
  fill(vis,vis+n+3,0);
  dfs2(0);
  int id=-1;
  if (odd) {//存在奇环
    rep(i,0,m){
      // 需要完全相等 所有已知奇环都覆盖了它, 且没有偶环覆盖了它, proof? 必要性显然, 充分性呢?
      if (cnt1[i]==odd && cnt0[i]==0) {
        id = i; // 任选一条
        break;
      }
    }
    if (id == -1) {
      printf("NO\n");
      return;
    }
    //删边
    auto [u,v] = e[id];
    sort(all(G[v]));
    sort(all(G[u]));
    G[u].erase(lower_bound(all(G[u]),make_pair(v,-1)));
    G[v].erase(lower_bound(all(G[v]),make_pair(u,-1)));
  }
  // 再次染色
  fill(c,c+n+3,-1);
  dfs3(0,1);
  int f=(id==-1?0:c[e[id].first]^1); //保证被删边的端点颜色为1
  printf("YES\n");
  rep(i,0,n){
    printf("%d",c[i]^f);
  }
  printf("\n");
}
int main() {
  int T;
  scanf("%d",&T);
  while(T--)run();
  return 0;
}

// 1-2-3-4,3-1,4-1
// 奇边切 3-1在回边上
//
// 1-2-3-4-5, 3-1, 5-1
//
// 奇边切 1-2或2-3,在树边上
//

总结

知识点

无向图 = dfs -> 树+回边

而一部分无向图的环 = 多个树边+一条回边? 也可能由回边组成的环

树上差分 = 记录当前点到根的所有边的统一操作,如+1/-1

学了一手fill()函数,看起来很好用啊

然后 无向图 树上dfs, 的父边而不是父点 dfs(int u,int fe /*father edge*/)

参考

官方

csdn 修复了一些越界和等式操作, 修改了部分变量和包裹逻辑,整体

發表於 更新於 分類於 Disqus： 文章字數： 285 所需閱讀時間 ≈ 1 分鐘

set+lower_bound

http://www.cplusplus.com/reference/algorithm/lower_bound/

On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

set不支持随机访问,所以std::lower_bound 用在set上就不再是log级别了, 而是均摊n级别了,所以要用set::lower_bound而不是std::lower_bound

动态开点线段树

一般来说 空间够常见是开4N大小

但是如果空间很大但是点是离散的又需要在线处理(不能离线离散化)的情况

每个点记录左右节点+lazytag+没有节点要访问时,动态开点idx, 查询时对于没有开点的直接返回空,而不是开点

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
int idx = 0;

// N 按照预估点数而不是 l r 的范围了
int lc[N]; // 点的左子点
int rc[N]; // 点的右子点

void update(int &o,int l,int r,...){
  if(!o) o = ++idx; // 动态开点
  if(l == r){
    // ...
    return ;
  }
  update(lc[o],l,mid,...);
  update(rc[o],mid+1,r,...);
  // ...
}

... query(int o,int l,int r,int ql,int qr){
  if(!o){ // 查询不用创建点
    //....
    return 空状态;// 
  }
  if(ql <= l && r <= qr){ // [ql.. [l..r].. qr]
    // ...
    return //;
  }
  auto resl = query(lc[o],l,mid,ql,qr);
  auto resr = query(lr[o],mid+1,r,ql,qr);
  return ...;
}



發表於 更新於 分類於 Disqus： 文章字數： 1k 所需閱讀時間 ≈ 3 分鐘

比赛总结

比赛id 11200

B:

数组空间没开够等未定义行为,不会像Codeforces报overflow等,而是默认执行报WA.

D:

TLE+WA 只会报WA

竞赛图不能创造大小为2的scc

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
/**
 * @author      : cromarmot (yexiaorain@gmail.com)
 * @file        : D
 * @created     : 星期五 5月 13, 2022 20:35:36 CST
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)

// 竞赛图 任意不同两点间都有恰好一条单向边
int n,m; // n 1e5, m 2e5
vector<int>p2[100010];

// scc -> 成链?

class Tarjan{
  vector<int> low;
  vector<int> dfn;
  stack<int> stk;
  vector<int> res;
  int n;
  int id = 0;
  void scc(int v) {
    low[v] = dfn[v] = ++id;
    stk.push(v);
    for(auto w:p2[v]){
      if(!dfn[w]){ // 未访问过
        scc(w);
        low[v] = min(low[v],low[w]);
      } else if(!res[w]){ // 访问过但没有结果(在栈中)
        low[v] = min(low[v],dfn[w]);
      }
    }
    int u;
    if(low[v] == dfn[v])  {
      do{
        res[u = stk.top()] = v;
        stk.pop();
      }while(u != v);
    }
  }
public:
  Tarjan(int SZ):n(SZ){
    low = vector<int>(n+1,0);
    dfn = vector<int>(n+1,0);
    stk = {};
    res = vector<int> (n+1,0);
  }
  vector<int> calc(){
    rep(i,1,n+1){
      if(!res[i]){
        scc(i);
      }
    }
    return res;
  }
};

vector<int> p3[100010];
int du[100010];

void work(){
  scanf("%d %d",&n,&m);
  Tarjan tarjan(n);
  rep(i,1,n+1){
    p2[i] = {};
    p3[i] = {};
    du[i] = 0;
  }
  rep(i,0,m){
    int u,v;
    scanf("%d %d",&u,&v);
    p2[u].push_back(v);
  }
  // a->b / b->a 至少满足一条
  // scc 成链? 唯一拓扑顺序
  vector<int> num = tarjan.calc(); // scc 联通分量 标识
  vector<int> sccsz(n+1,0);
  rep(i,1,n+1){
    sccsz[num[i]]   ++;
  }
  rep(i,1,n+1){
    if(sccsz[i] == 2){
      // 竞赛图不能创造大小为2的scc!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
      printf("NO\n");
      return ;
    }
  }

  // rep(i,1,n+1){
  //   printf("scc: %lld: %d\n",i,num[i]);
  // }
  // 转化为联通分量关系
  rep(i,1,n+1){
    for(auto item:p2[i]){
      if(num[i] == num[item])continue;
      p3[num[i]].push_back(num[item]);
    }
  }
  rep(i,1,n+1){
    if(num[i] != i)continue;
    sort(p3[i].begin(),p3[i].end());
    int itr = 0;
    rep(j,0,(int)p3[i].size()){
      if(j==0 || p3[i][j] != p3[i][j-1]){ // 去重
        p3[i][itr++] = p3[i][j];
        // i -> p3[i][j]
        du[p3[i][j]]++; // 入度
      }
    }
    p3[i].resize(itr);
  }
  // 拓扑 联通分量中 唯一顺序
  // 入度为0
  vector<int> d0;
  rep(i,1,n+1){
    if(num[i] != i)continue;
    if(du[i] == 0)d0.push_back(i);
  }
  while(d0.size()) { // == 1
    if(d0.size() > 1){
      printf("NO\n");
      return ;
    }
    int i = d0[0];
    // printf("D0:%d\n",i);
    d0.pop_back();
    rep(j,0,(int)p3[i].size()){
      // i -> p3[i][j]
      du[p3[i][j]]--;
      if(du[p3[i][j]] == 0){
        d0.push_back(p3[i][j]);
        if(d0.size() > 1){
            printf("NO\n");
            return ;
        }
      }
    }
  }
  printf("YES\n");
}


int main(){
  int t;
  scanf("%d",&t);
  while(t--){
    work();
  }
  return 0;
}

C题目

https://ac.nowcoder.com/acm/contest/11200/C

大意

从1开始

  1. 每次可以移动 x = x+1
  2. 如果当前格子未被染色, 则染色当前格子并且设置 x = a[x]

a[x]保证非严格单调递增

n<=1e6

输出把所有格子都染色的方案数

题解

设 f(x)把前x个格子全部染色的方案数, 注意到虽然顺序上可能 在染前x个格子过程中,已经把后面的格子染色了,但是后面这个被染色的不计入方案统计

  • x 如果是最后一个被染色的,那么方案数为f(x-1)
  • x 如果不是最后一个被染色的, 那么对于f(x-1)中, 相当于 ? -> x -> y, $y \in [a_x,x-1]$, 所以它可以放在$x-a_x$个位置的前面

所以方案数 = $\prod_{i=1}^n(i-a_i+1)$

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
const double pi = acos(-1.0);

int n;
int a[1000010];

int main(){
  ll ans = 1;
  cin>>n;
  rep(i,1,n+1){
    scanf("%d",a+i);
    if(i-a[i]+1 <= 0){
      ans = 0;
    }else{
      (ans*=i-a[i]+1)%=MOD;
    }
  }
  printf("%lld\n",ans);
  return 0;
}

总结

状态转移的过程中, 对于上面这种,实际上也可以和方案描述不一致, 统计的时候不会包含超过当前位置的移动方案,而后面的移动方案是可以等价的插入到前面的方案中的(才可以乘法)

不过现在好的是,我能判断这个类型算是数学和转移的题了,也想到这样设计状态,但是没有细想

参考

https://ac.nowcoder.com/discuss/952589

發表於 更新於 分類於 ， Disqus： 文章字數： 1.7k 所需閱讀時間 ≈ 6 分鐘
C (trie树, bit flip)

C

https://atcoder.jp/contests/agc057/tasks/agc057_c

0~ 2^N - 1的排列

问能否通过多次任选操作(每次操作独立,在上一次操作结果基础上), 让数列单调递增, 给出方案

操作1: a[i] = (a[i]+1)%(2^n) , 所有值循环+1

操作2: a[i] = a[i] xor x , 选定一个值,所有值异或它

限制

n<=18

我的思路

显然连续的异或没意义,甚至题目可以改成不是+1,+任意

所以问题变成 穿插的正数个+1和xor能否让数列单调递增, 若能给出方案

考虑所有+1/xor 末尾是1, 都是让所有末尾翻转, 因此结论是 末位前两个互为0/1,后面循环这两个

同理考察第二位,发现(0和2)(1和3)两对,互为0/1,后面的同样按照4个一组循环

同理考察第三位,发现(0和4)(1和5)(2和6)(3和7)四对,互为0/1,后面的同样按照8个一组循环

换句话说, 最低位1个自由元,其它由它决定,第2低位两个自由元,剩余的也是由它决定,第低3位4个自由元,低4位8个自由元…

我想先弄好一部分位再弄剩下的,从高位到低位或从低位到高位,但是 没想到实际怎么操作

题解

设计结构

trie tree

先不看方框, 看树上的边, 从根向叶子的方向, 对应值的从低到高的位

然后关注叶子方框,例如上面的6,二进制下是110,和它的路径是一样的

再看带有n的方框,意思是如果从树上截取某个点作为根来看,如果根表示的是n,那么一条边权是0子节点是2n+0,边权是1的子节点是2n+1, 注意的是这里并不是左右节点,而是由边权决定的

树的结构建好以后, 那么把叶子中再填入初始每个值所在的位置,完成初始化

接下来看+1和xor操作对树进行怎样的修改

+1

+1

因为我们的树是越接近根,对应的位越低,所以+1带来的进位效果也是从根向叶子前进的

如果我们以改变树上边的权值,而不是改变左右指向的视角来看,

那么对于根

0变成1

1变成0且它的子树受到和根一样的处理

这样发现改动的实际上只有log级别个

xor

xor

xor 比 +1 其实好观察,

对于xor二进制对应位为1的层级的0变成1,1变成0

实现

现在我们再回头看目标呢, 也就是位置上和它对应的值是一样的

这里可以思考为啥,是按边上的值来描述而不是左右描述的, 考虑不按照涂上那样初始摆,而是按照叶子直接放初始的值,比如这里0 4 2 6 1 5 3 7位置上对应的值, 在放值时就能明确的知道冲突的情况,排除一些不可能

问题变成了,如何让二叉树边上的0/1 变回 完全二叉树的位置对应的值

考虑把叶子变成 0,1 序列.

如果叶子是反着的1,0, 那么只需要把上面的路径变成 从根到它都是1,这样+1 就能完成修正

修正了所有叶子以后, 问题来了, 还可以通过+1/xor的组合修正非叶子吗

1
2
3
   1       0
 1   0   0   1 ( 其它位还有 不是xor 能解决的情况
0 1 0 1 0 1 0 1 ( 高位全部0,1顺序了

证明不可能, 首先 这种情况, 如果能修正,必定是奇数次操作到该层, 因为 xor不改相对一致性,+每次操作到这两个中的一个就会改,所以这两个操作次数总和必为奇数,考虑它们所覆盖的叶子节点,总操作次数也为奇数

因此要么 xor翻转能得到,要么就是不可能

从逻辑上, 已经完成了,还有个实现问题,如果通过枚举导数第二层,再模拟xor和+1, 虽然+1代价小,但是xor的代价可能达到O(n)的级别, 总的会变成n方

简单的增加一个翻转标识记录行的翻转状态, 因为+1是对单个点翻转,xor是行翻转,翻转两次等于未翻转,都是翻转,所以+1直接让对应位置的节点翻转, 而xor 通过行标识记录,

代码

https://atcoder.jp/contests/agc057/submissions/31596691

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

const int N = 262144;

vector<int> lr(N*4+10,-1); // -1 unset 0:01, 1:10

int a[N+10];

int n;
bool build(int pos,int val,int idx = 1,int pwr = 0){
  if(pwr == n)return true;
  int direction = pos%2;
  int v = direction != val%2;
  if(lr[idx] != -1 && lr[idx] != v){
    return false;
  }
  lr[idx] = v;
  return build(pos/2,val/2,idx*2+direction,pwr+1);
}

int xorcache[20] = {0}; // 不要实际的xor, 修改代价大

vector<int>ans;

void fix(int val){
  // printf("Fix %d\n",val);
  int x = 0;
  {
    int pwr = n-1;
    int v = val;
    while(pwr--){
      if(v%2 == (lr[v/2] ^ xorcache[pwr])){
        x |= (1<<(pwr));
      }
      v/=2;
    }
  }
  // printf("xor %d\n",x);
  if(x){
    ans.push_back(x);
    rep(pwr,0,n){
      if((1<<pwr) & x)xorcache[pwr]^=1; // 标记
    }
  }
  // printf("+1\n");
  {
    int idx = 1;
    rep(pwr,0,n){
      if(lr[idx]^xorcache[pwr]){
        idx=idx*2;
      }else{
        idx=idx*2+1;
      }
      lr[idx/2] ^= 1;
    }
  }
  ans.push_back(-1);
}


int main(){
  cin>>n;
  rep(i,0,(1<<n)){
    scanf("%d",a+i);
  }
  rep(i,0,(1<<n)){
    int r = build(i,a[i]);
    if(!r){
      printf("No\n");
      return 0;
    }
  }
  // rep(i,1,8){
  //   printf("lr[%lld]= %d\n",i,lr[i]);
  // }
  rep(i,(1<<(n-1)),(1<<n)){
    if(lr[i] == 0)continue;
    fix(i);
  }
  int x = 0;
  rep(pwr,0,n){
    if(lr[1<<pwr] ^ xorcache[pwr]){
      x |= 1<<pwr;
      xorcache[pwr] ^= 1;
    }
  }
  if(x){
    ans.push_back(x);
  }
  rep(pwr,0,n){
    rep(i,(1<<pwr),(1<<(pwr+1))){
      if(lr[i]^xorcache[pwr]){
        printf("No\n");
        return 0;
      }
    }
  }
  printf("Yes\n");
  printf("%d\n",(int)ans.size());
  rep(i,0,(int)ans.size()){
    printf("%d ",ans[i]);
  }
  printf("\n");
  return 0;
}

总结

其实我的思路和题解中trie树的结论是一致的,但是我的思路不是trie树形状的,所以再往后推导的阻力更大

一个经验就是对于这种2的幂次的 xor 或 加减操作,可以放在trie树中批量操作, 比如稍微变一变, 就可以变成给你+1/-1/xor操作序列,和询问第idx位置是什么,这样多个操作询问交替的题目

参考

官方题解 https://atcoder.jp/contests/agc057/editorial/3925

0%