Educational Codeforces Round 119

發表於 更新於 分類於 ， Disqus： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘
F(DP)G(容斥原理,集合)

CF tracker

Edu List

https://codeforces.com/contest/1620

F. Bipartite Array

给你1~n排列数组a

问能否 给每个数乘上 1或-1,

然后对所有逆序点连边, 让所有点能二分图

范围

n 1e6

2s

256mb

我的思路

考虑一个点是负数, 那么它前面所有点和它相连, 所以前面点和它 都在二分图对面, 所以它们之间不能有边, 所以它们需要单调递增,

如果考虑n是正数, 同理 它右侧的点 需要单调递增

如果n是负数,那么它左侧的点要单调递增

问题是这样分割, 会产生n个分支?

dfs 来控制 ?

题解

没有长度为3的降序列!!!!!!!!!!

所以 dp[i][i的正负][长度为1/2的降序列] = 最大值

再记录一个反向状态来源就没了

G. Subsequences Galore

n个字符串 数组a=[s1,s2,…,sn] , f(a) = 不同的字符串个数(空串也算) 至少是其中一个字符串的子序列(可以不连续)

f([]) = 0

每个si 的字符都小写字母,且sorted,就是 a*b*c*...

问 a的 2^n个子数组(可以不连续) 的 ((f(a’) mod 998244353) * |a’| * (a’中s下标和) ) 的xor

范围

n 23

|si| 2e4

10s

1024mb

我的思路

既然 所有字符串都是 a~z 的任意的顺序排列, 那么子串也是

a的方案就是 max{si 中的a的个数}

ab的方案是 对于每个 a的个数c[a], max{si 中 a >= c[a], b的个数}, 相当于 随着c[a] 选择值的增加, 对应s的集合在递减, 导致b的个数也在递减

abc 就更复杂了, for c[a], for c[b], sum max(c[c])

这样 for , 时间上就会不满足了

其实从过程中也可以看到, 这里的子序列其实意义不大

转换成 问有多少26维的向量, 至少小于s[i] 中的 一个

那么 从增删的角度去考虑, 若当前集合 {s1,s2…} 现在多一个si, 有哪些 26维向量满足, <= si ,但是不小于之前集合中的任何一个

感觉是个26维度的矩体的交的问题…, 似乎可以容斥掉???

题解

对于字符串t, 它的characteristic mask 是n个bit的, 第i个bit 表示它是否是si的子串

假设对于 a的子序列 的mask 为 x, 可以 SOSDP 来计算,

$S=\lbrace s_1,s_2,\cdots,s_n \rbrace, T \subseteq S$ 要求$f(T)$

$f(T)$ 代表$T$ 中欧给你每个串的子序列之并的数量

一个具体的$s_i$的子序列数量为$\prod (1+c_i)$

但是求 子序列并,并不直接, 而子序列交很好求 $=\prod (1+\min c_i)$

基本的容斥, 把 有si看成属性, 那么 并的个数 $f(T) = \sum_{Q\subseteq T} (-1)^{|Q|-1} \prod (1+\min_Q c_i)$

就没了f(T)能算 就随便做了

代码

https://codeforces.com/contest/1620/submission/190579441

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef int i32;
const i32 INF=0x3f3f3f3f;
#define MOD 998244353
// mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count()); // usage rnd()
#define rep(i,a,n) for(ll i=(a);i<(ll)(n);i++)

ll read(){ll r;scanf("%lld",&r);return r;}
int cnt[30][30]; // cnt[i][char]= 第i个字符串的char的个数
ll s[1<<24];
array<int,1<<23 > mn; // mn[mask] 最小的min c[char]
char tmp[20010];
int lowbit(int x){ return x & (-x); }
int popc[1<<23]; // popcount even/odd 直接记录奇偶
int sidx[1<<23]; // sum idx,(1-index)
int lg[1<<23]; // lg(0)=0, lg(1)=1, lg(2)=2 lg(4)=3, 对应1-index
int main(){
  ll n=read();
  rep(i,1,n+1){ // 1-index
    scanf("%s",tmp);
    ll m = strlen(tmp);
    rep(j,0,m) cnt[i][tmp[j]-'a']++;
  }
  rep(msk,1,1<<n) {
    lg[msk]=lg[msk/2]+1;
    popc[msk] = popc[msk&(msk-1)]+1;
    sidx[msk] = sidx[msk&(msk-1)]+lg[msk&-msk];
    s[msk] = (popc[msk]&1)?1:-1; // 默认是空串, 预先给符号
  }
  rep(ch,0,26){ // 字母
    mn[0] = INF;
    rep(msk,1,1<<n){ // 字符串选择mask
      mn[msk] = min(mn[msk-lowbit(msk)],cnt[lg[lowbit(msk)]][ch]); // 字母ch 在字符串msk下的交的最大值
      (s[msk] *= (mn[msk] + 1))%=MOD; // = \prod (min c + 1)
    }
  }
  // s[字符串mask] = 子集的交 * (-1) 幂次权重
  rep(i,1,n+1) rep(msk,1,1<<n) if(msk & (1<<(i-1))) (s[msk] += s[msk-(1<<(i-1))])%=MOD; // 子集汇总
  // s[字符串mask 的子集] = sum (子集的交) = f(mask)

  ll ans = 0;
  rep(msk,1,1<<n) ans ^= popc[msk]*sidx[msk]* ((s[msk]+MOD) % MOD); // s[]可能是负值
  printf("%lld\n",ans);
  return 0;
}

总结

F. 我为啥自己观察不出 没有长度为3的降序列啊???????????

G. 反而感觉 很显然的思路方向和过程, 比F简单, 以及对于是要具体算出每一个的猜测 而无法直接统计 mod 乘法以后的 xor 的想法也是对的

参考

官方