CFR628

Codeforces Global Round 7

D复制了错误的板子,调了30min,心情极差

还好做出了E,虽然说比较慢导致没时间写F1

所以比赛时间长就是好,有重大失误也有机会稍微弥补

CF1326A Bad Ugly Numbers

code

CF1326B Maximums

code

CF1326C Permutation Partitions

一开始没看到全覆盖,浪费了点时间

CF1326D Prefix-Suffix Palindrome

请先思考后再展开

其实如果我选择复制hash而不是错误的manacher,保守估计能减少40min耗时

不妨设前缀长度不超过后缀,那么就是要求最大化后缀多出来的部分,且使得那个部分回文,当然前后缀公共长度区相等是必要的

核心观察:各自增长1,答案不会变坏

因此直接得到最长的前后缀相等长度L,那么就是要找个最长的玩意,然后直接枚举长度跑hash根本不用动脑子,但我看着手边正好有个manacher就贴了上来,剩下的只有悲剧了

code

CF1326E Bombs

请先思考后再展开

这题的确不难,就是把做D时崩坏的状态调整过来花了挺久

肯定先想单组,二分答案T后,贪心check:找到最晚出现的不小于L的数位于R,那么合法条件就是$\max_{l<R}(\sum_{i \in [l,R-1]} [p_i \ge T]-[i有炸弹])+1 \ge R后面的炸弹总数$

答案递减没必要二分,此时已经是n方了,代码的话可以看ac代码中除去线段树和树状数组的部分,以及注释掉的for循环

每次随便复制个树状数组,再快速敲个区间加区间询问最小值的线段树,就能一个log了,code

CF1326F1 Wise Men

请先思考后再展开

easy:

当做n个点走哈密顿回路

我的想法是meet in middle,应该是个$O(2^6*C_{14}^6*7^2+C_{14}^72^{14})$,组合数是去过哪些点,常数很小,也看到好像有人这么过了

比较优美好写的写法是benq,就是我没意识到,将去过哪些点放外面,里面用vc开空间存走过的路径01状态,这样的话里面的状态不会超过外面的点数,即$\sum_S 2^S=3^n$

hard:

我不知道我的做法常数是否能小到日过去,不过看起来就不是很优美

核心观察:考虑求$f_S=\sum_{S \subseteq T} ans_T$,能求出只要再跑个IFMT;相当于要拼接若干条链,且不关心连接处其实有没有边,于是多重集(考虑被1连接起来的点,例如$11100110111$是4、1、3、4这四条链,记作$a_1,a_2..a_m$)相同的状态f是相同的,即状态数=分拆数,而18的分拆数=385

剩下就是套路了,先$O(2^nn^2)$直接dp出$link_{S,lst}$进而求出$link_S$,$f_S=[x^{U}]\prod_{i=1}^m ( \sum_{T,|T|=a_i(S)} link_T [x^T] )$

因为我们只关心这个集合幂级数或卷积后一个位置(即全集)上的值,记当前点值表达法为A,$f_S=\sum_T A_T (-1)^{|U \setminus T|}$

dfs时精细地边搜边乘,复杂度为$O((P(n)+n^2)*2^n)$,好平衡,我的实现方法是用hash判断多重集相同

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
ll hs[bin(N)],BS=131,MD=993244853;
int n;ll B[N][bin(N)],A[N][bin(N)],ans[bin(N)];
void dfs(int left,int lst,ll HS)//满足left>=lst
{
ll sum=0;fo(s,0,bin(n)-1) sum+=A[left][s]*B[left][s]*((n-PC(s))&1?-1:1);
fo(s,0,bin(n-1)-1) if( (HS*BS+left)%MD==hs[s]) ans[s]+=sum;//统计最后一个是left
fo(nxt,lst,left/2){
fo(s,0,bin(n)-1) A[left-nxt][s]=A[left][s]*B[nxt][s];
dfs(left-nxt,nxt,(HS*BS+nxt)%MD); }
}
char to[N][N];ll link[bin(N)][N];
void main()
{
n=qread();fo(i,0,n-1) scanf("%s",to[i]);fo(i,0,n-1) link[bin(i)][i]=1;
fo(s,0,bin(n)-1) fo(x,0,n-1) fo(y,0,n-1) if(to[x][y]=='1' and (s>>y)%2==0) link[s|bin(y)][y]+=link[s][x];
fo(s,0,bin(n)-1) fo(x,0,n-1) B[PC(s)][s]+=link[s][x];
fo(ln,1,n) fo(i,0,n-1) fo(s,0,bin(n)-1) if(s&bin(i)) B[ln][s]+=B[ln][s^bin(i)];//子集fwt
fo(s,0,bin(n-1)-1){
int lst=-1;vc<int> hh;fo(i,0,n-2)if(!(s&bin(i))) hh.PB(i-lst),lst=i;
hh.PB(n-1-lst);sort(all(hh));for(auto i:hh) hs[s]=(hs[s]*BS+i)%MD;
}
fo(s,0,bin(n)-1) A[n][s]=1;dfs(n,1,0);
fo(i,0,n-2) fo(s,0,bin(n-1)-1) if(s&bin(i)) ans[s^bin(i)]-=ans[s];//超集fwt
fo(s,0,bin(n-1)-1) write1(ans[s]);
}

CF1326G Spiderweb Trees

咕咕咕

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/6b2dc66c.html
转载请注明出处,谢谢!