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

發表於 更新於 分類於 ， Disqus： 文章字數： 3k 所需閱讀時間 ≈ 10 分鐘
E(sosDP,子集和DP,动态规划,贡献统计),F(dp,bitmask,特殊表示,动归状态设计)

E

https://codeforces.com/contest/1679/problem/E

长度n,前17个小写字母组成的字符串s,其中有?表示t中任意字符

q次询问,每次给17个字母中的一个子集,问把?所有填子集的填法中,原串的回文子串个数和, 答案mod 998244353

范围

n 1e3

t 17

q 2e5

2s

256MB

我的思路

首先看到q 2e5, 和 t 17, 因为2^17 == 131072,其实可以变成求所有方案的答案

统计所有回文子串 的效率最好就是选取中心,再枚举长度

那么这个题也是这样做, 枚举中心向两边搜索

其中注意到的是,当选定中心后,如果对称位置上有一个问号一个确定字符,那么这个问号必定填这个字符

如果两个都是问号,那么自由度+1, 它

如果对称都填了但是不一样,那么到此结束

也就是n方可以统计 cnt[必要字符bitmask][自由度] = 次数

那么 每次询问bitmask 是 M 的话

ans[M] = sum { cnt[m 是M的子集][i = 0..] * size(M)^i }

那么问题来了, 朴素计算我必定超时, 但是我不知道如何dp, 看Codeforces的群里有人说sosdp

SOSDP 子集和DP

$F[mask] =\sum_{i \in mask}A[i]$

暴力枚举 $O(4^n)$

1
2
3
4
5
rep(mask,0,1 << N){
  rep(i,0,1 << N){ // 枚举 mask, 检测是否是它的子集
    if((i&mask) == i) F[mask] += A[i];
  }
}

枚举子集和$O(3^n)$

子集遍历

也可以dfs,当然dfs会多函数调用和堆栈 比如mask = 111, i依次为 111,110,101,100,011,010,001,000, 注意到的是mask中间穿插0对应的就是i对应位置穿插0,看起来就像每次-1

1
2
3
4
5
6
rep(mask,0,1 << N){
  F[mask] = A[0]; // 所有集合包含空集 空集合也作为停止条件
  for(int i = mask;i;i = (i-1)&mask){ // 这就是传说中的二进制枚举子集 ,
    F[mask] += A[i];
  }
}

SOSdp $O(n2^n)$

dp[mask][i] 表示 高位和mask一致, 低[0..i]位所有方案的和

dp[10110][2] = A[10000]+A[10010]+A[10100]+A[10110]

状态转移

第i位为0时,dp[mask][i] = dp[mask][i-1]

第i位为1时,dp[mask][i] = dp[mask][i-1] + dp[mask xor (1 << i)][i-1]

这样变成递推 或者记忆化搜索,可以 $O(n2^n)$ 完成

上面合并一下变成,dp[mask][i] = dp[mask][i-1] + (mask & (1 << i)?dp[mask xor (1 << i)][i-1]:0)

注意到i依赖于i-1还可以滚动数组降低空间

1
2
3
4
5
6
7
rep(mask,0,1<<N) f[mask] = A[mask];
rep(i,0,N){
  // 这里不需要从大到小, 因为dp[mask]已经初始化了,只会更新1 << i上为1的,而更新的来源是1 << i上不是1的
  rep(mask,0,1 << N){
    if(mask & (1 << i)) f[mask]+=f[mask ^ (1 << i)];
  }
}

题解

我的暴力的代码

1
2
3
4
5
6
7
8
ans[mask] = 0;
sz = bitcount(mask)
rep(qmark,0,501){ // 自由的问号个数
  ti = pow(sz,qmark)
  for(int i = mask;i;i = (i-1)&mask){
    ans[mask] += cnt[i][qmark] * ti
  }
}

这是$O(n 3^{|t|})$ 的复杂度 肯定过不了

通过sosdp降低到$O(n t 2^{|t|})$ 虽然降低了不少,但是依然过不了

这里dp 改一个方式设计, 变成贡献统计

先交换一下循环层级

1
2
3
4
5
6
7
ans[mask] = 0;
sz = bitcount(mask)
for(int i = mask;i;i = (i-1)&mask){
  rep(qmark,0,501){
    ans[mask] += cnt[i][qmark] * pow(sz,qmark)
  }
}

因为{i,qmark}中i是mask的子集,而{i,qmark}对mask 的贡献来讲 只与bitcount(mask) 有关,与mask 具体无关

1
2
3
4
5
6
7
8
9
10
11
12
13
rep(i,0,(1 << N)){
  rep(sz,1,17+1){
    rep(qmark,0,501){
      cost[i][sz] += cnt[i][qmark] * pow(sz,qmark);
    }
  }
}
ans[mask] = 0;
sz = bitcount(mask)
// sosdp 优化掉
for(int i = mask;i;i = (i-1)&mask){
  ans[mask] += cost[i][sz];
}

下面得到优化了, 但上面看起来复杂度并没有变好

但既然都说道贡献统计了,就去看贡献来源

在我们初始找回文时[i...j] 如果是一个回文,它的必须字符集为mask,自由度为qmark

那么

1
2
3
rep(sz,1,17+1){
  cost[mask][sz] += pow(sz,qmark);
}

这样 初始化就变成$O(|t| n^2)$

综上 $O(初始化幂次 |t|n + 初始化贡献 |t| n^2 + 初始化答案 |t|^2 2^{|t|} + 查询 |t|q )$

注意到 题目要统计 所有字符串个数,也就是说 同一个位置的回文串 在不同字符串中出现,要多次统计

所以

1
2
3
rep(sz,1,17+1){
  cost[mask][sz] += pow(sz,qmark) * pow(sz,total qmark - used qmark);
}

代码

https://codeforces.com/contest/1679/submission/158244316

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
#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

const int t = 17;
char s[1010]; // 读入
char s2[2010]; // 插入井号简化搜索
int n;

ll p[t+10][1010]; // 幂次预处理
ll cost[(1<<t)+10][t+10]; // 具体的值
ll ans[(1<<t)+10][t+10]; // 由具体值的子集和的答案
char query[t+10];

int main(){
  rep(i,1,t+1){
    p[i][0] = 1;
    rep(pwr,1,1000+1){
      p[i][pwr] = p[i][pwr-1]*i%MOD;
    }
  }
  scanf("%d",&n);
  scanf("%s",s);
  int qtotal = 0;
  rep(i,0,n) qtotal += s[i] == '?';
  // 字符两两间插入井号方便处理奇偶
  s2[0] = s[0];
  rep(i,1,n){
    s2[i*2-1] = '#';
    s2[i*2] = s[i];
  }
  // 中心
  rep(c,0,n*2-1){
    int mask = 0;
    int qmark = 0;
    int qcnt = 0;
    rep(l,0,n*2-1){ // 长度
      int il = c-l;
      int ir = c+l;
      if(il < 0 || ir >= n*2-1)break;
      qcnt += s2[il] == '?';
      qcnt += il != ir && s2[ir] == '?';
      if(s2[il] == '#')continue; // 不贡献的
      if(s2[il] == s2[ir]){
        if(s2[il] == '?'){
          qmark++;
        }
      }else{ // 不等
        if(s2[il] == '?'){
          mask |= (1 << (s2[ir] - 'a'));
        }else if(s2[ir] == '?'){
          mask |= (1 << (s2[il] - 'a'));
        }else{ // 不同的字符
          break;
        }
      }
      // 贡献统计
      rep(sz,1,17+1){
        // 不同字符串 同一个位置回文串的贡献要多次统计 所以要乘上 其余位置是问号的所有放入方案 让此处的贡献倍数 sz**(qtotal - qcnt)
        (cost[mask][sz] += p[sz][qmark] * p[sz][qtotal - qcnt] % MOD )%=MOD;
      }
    }
  }
  // sosdp
  rep(sz,1,t+1){
    rep(mask,0,1 << t){
      ans[mask][sz] = cost[mask][sz];
    }
    rep(i,0,t){
      rep(mask,0,1 << t){
        if(mask & (1 << i)) (ans[mask][sz] += ans[mask ^ (1 << i)][sz])%=MOD;
      }
    }
  }
  // query
  int q; // 2e5
  scanf("%d",&q);
  while(q--){
    // string to mask
    scanf("%s",query);
    int sz = strlen(query);
    int mask = 0;
    rep(i,0,sz){
      mask |= (1<<(query[i]-'a'));
    }
    printf("%lld\n", ans[mask][sz]);
  }
  return 0;
}

总结

回文的奇偶处理,可以用两两间插入不会出现的字符,如井号,方便枚举中心

学了一手sosdp

看ssr的twitter说有快速zeta变换, 搜下来看转移方程似乎就是sosdp, https://zhuanlan.zhihu.com/p/33328788?ivk_sa=1024320u

顺便这里的dp转化过程中 通过贡献和来优化效率

参考

官方

F

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

$[0..10^n)$的所有n位整数,不足的补前导零

给m个 (ui,vi) 数对, (ui不等于vi)

x 表示成十进制的数字数组 [d1,d2,…,dn]

一次操作可以交换相邻的d, 但需要满足 这两个数的 (di,di+1)或(di+1,di) 出现在 (ui,vi)中

如果一个数x能够通过上述转换变成y,那么认为它们是相等的, x和x自身相等

问题$[0..10^n)$ 有多少个不同的数, 答案mod 998244353

范围

n 5e4

m 45

u,v [0,9]

3s

256MB

题解

我的思路

先提取一下有用没用的信息,首先m没啥用因为实际就是所有数对的上限

如果x 中有两个数字 c0,c1 但是这两个数字没有在d中出现过, 那么这两个数字的相对前后关系不会改变

换句话说,如果两个相等的 它们互相可以转化,那么它们一定属于某个集合,集合里两两可以转化, 而有限集合一定有最小的, 我们用每个集合中数值最小的来表示一整个集合

于是 这个最小值值可以表示成 [单调递增] [单调递增] [单调递增] , 每两个单调递增之间 的值是不在数对里的

所以如果我们可以得到[起始,结束,长度]的方案数就可以考虑转移方程了

f[i][j][len1] = sum{ f[i][k][len0] * inc[ < k][j][len1-len0] } + inc[i][j][len]

看似复杂度没法搞,而实际上连逻辑也不一定对 201, 它允许 (0,1),(2,1) 那么显然120和它相等且更小

题解

思路是类似的, 也是集合的代表元, 但是并不是靠单调递增划分

而是说[序列长度l] 在后面加上mask中的数,它不会被移动到前面

那么,d会移动到前面的条件就是,序列的尾部的一串数都大于d,且都可以和d交换

[x,d1,d2,d3,...,ds,y]

其中 x > y, 且 y 可以和x,d1,...,ds交换

dp[suff][mask] 表示, suff个digits, 且只有mask中的digit可以被移到最左

考虑长度为s 的一个具体的串 等价最小串 X=[d0,d1,d2,.....,ds]

它最长的前缀[d0,d1,d2,....dt] 包含的digits 两两可换, 我们把这样的digits变成mask, X 可以表示成贡献到 dp[s][mask] 中

那么现在如果左边放一个d, 变成X1 = [d,d0,d1,d2,...,ds]

一旦d和 mask 中某个值可换, 记为e, 且d > e

显然,因为mask中两两可换,所以X1 可以变成 [d,e,d0,d1,d2,...,ds], 然后交换e,d 得到 [e,d,d0,d1,d2,...,ds]

因为e < d ,所以 这个值比X1 小

即是X前面不能插入d, 如果 mask 中存在比d小,且和d相连的任何一个e

这样可选的d的范围就出来了, 这部分可以预处理

从X而非mask的角度来看,就是说插入了d以后,得到的值依然是 集合表示的最小值(代表元)

mask的变化

如果d可以放,那么X1 = [d,d0,d1,d2,...,ds], 显然,它的 最长两两可换前缀中有d, 且剩余的部分从mask 中取, 因为mask本身就是两两可换,所以只用考虑和d是否有边

所以新mask = d | mask 中和d有边的点

注意到mask 的意义是 mask 中的值两两可换, 又是X的最大前缀

所以这里其实会计算不少无效的mask, 但因为算次数,这些次数一定是0, 不影响答案

代码

https://codeforces.com/contest/1679/submission/158638333

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
#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

namespace X{
  ll r(){ll r;scanf("%lld",&r);return r;} // read
  void add(ll &v0,ll &v1){(v0+=v1%MOD)%=MOD;} // add with MOD
};
using namespace X;

const int S = 10;

// mask 意义, mask中两两可换, 是X的最大前缀
// camp[mask0] = mask1, mask1任意一个bit 和 mask0 中的比它小的bit都没有链接
// 在 mask1中的digit 才能加入到 mask0
vector<int> camp(1<<S,(1<<S)-1);
bool conn[S][S]; // 连接状态
ll dp[2][1 << S];
int trans[1 << S][S]; // [mask][digit] = newmask,

int main() {
  int n = r();
  int m = r();
  rep(i,0,m) {
    int u = r();
    int v = r();
    conn[u][v] = conn[v][u] = 1;
  }
  // 计算 camp
  // O(S^2 * 2^S)
  rep(mask,0,1 << S){
    rep(c,0,S){ // c 在 mask 中
      if (!(mask & (1 << c))) continue;
      rep(j,c+1,S){ // j > c
        if (conn[c][j]) {
          camp[mask] &= ~(1 << j);
        }
      }
    }
  }
  // 计算trans
  // O(S^2 * 2^S)
  rep(mask,0,1 << S) {
    rep(c,0,S){
      trans[mask][c] = 1 << c;
      rep(j,0,S){
        // j 出现在mask 中, (c,j) 可以交换
        if ((mask & (1 << j)) && conn[c][j]) {// 和 mask 中存在相连
          trans[mask][c] |= 1 << j;
        }
      }
    }
  }
  // 滚动数组
  int cur = 0;
  dp[0][0] = 1;
  // O(n * S * 2^S)
  rep(i,0,n){
    // clear
    fill(dp[cur^1],dp[cur^1] + (1<<S),0);
    rep(mask,0,1<<S){
      if (dp[cur][mask] == 0) continue;
      rep(c,0,S){
        // 在camp[mask] 中的才能加
        if (!(camp[mask] & (1 << c))) continue;
        add(dp[cur ^ 1][trans[mask][c]] , dp[cur][mask]);
      }
    }
    cur ^= 1;
  }

  ll ans = 0;
  rep(mask,1,1<<S) add(ans,dp[cur][mask]);
  printf("%lld\n", ans);
}

总结

我的思路里关于 排序,代表元都有了, 这是好事,但是

其实这里一个核心 在于怎么把 最小值元素X,抽象的表示到一个dp的state中

这里给出的state的设计方案是最长两两可换的前缀的bitmask, 和长度来表示

换句话说如果有人告诉我怎么设计state,那么转移方程还是随便写的

参考

官方

發表於 更新於 分類於 ， 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

0%