codechef OCT19

r_64 posted @ 2019年10月14日 13:57 in 未分类 with tags codechef , 705 阅读

我他妈日了鬼了，当了两次tester，每一次都他妈碰上搬原题的

S10E

大模拟

进制转换题，用python的int函数爆搞就是了

假设有$r$行被翻了奇数次，$c$列被翻了奇数次，那么答案是$rM+cN-2rc$

（说起来这个题数据好像太水了导致一堆人AC

显然只需要考虑每个数最后一次出现的时候。先从右往左扫描出所有最后一次出现的数。

接下来从左往右扫描，对每个数$A$我们花$10^6/A$的时间求这个答案就行了。

显然有循环节。执行

\[K=\begin{cases}K&K\le 3N\\(K\bmod 3N)+3N&K>3N\end{cases},\]

然后暴力模拟。

如果$|E|$是偶数那么显然答案是$K=1$

如果$|E|$是奇数，且存在度数为奇数的点，那么把这个点孤立开就是了，答案为$K=2$

否则可以证明答案$\ge 3$。随便找一条边然后把这条边的两个端点孤立开显然是可行的，于是$K=3$

不会（

对于第$i$秒的询问$+$ $v_i$ $k_i$或$?$ $v_i$，定义$E[i]=i-dep(v_i)$，也就是询问时间减去相关节点的深度

假设有一个询问$?$ $v_i$且$v_i$不是叶子，那么显然只有$E[j]=E[i]$的修改$j$才会影响$v_i$

把那些$j$当中$v_j$是$v_i$祖先的$k_j$加起来就是答案了

我们按照$E[i]$分类把所有询问扫一遍就行

如果询问$?$ $v_i$中$v_i$是叶子，那么$E[j]\le E[i]$且$v_j$是$v_i$祖先的$j$都会影响$i$，需要把这些$k_j$加起来

所以按照$E[i]$从小到大处理这些询问，做子树加法、单点查询就是了，注意把叶子和非叶子分开

为什么大家都是$O(N^2)$或$O(N\log N)$的解法啊。。。出题人、我、admin在验题的时候都没想到这个做法。。。

下面说说（菜的一批的）标解

令$DP(N,Q,r)$表示有$N$行（或$N$列），执行$Q$个操作，每个操作翻转某一行，最终有$r$行被执行了奇数次的方案数

$DP(N,Q,r)$可以推式子，具体去看Editorial吧（敷衍

总之$DP(N,Q,r)$可以在$O(N\log N)$时间内用FFT求出

然后枚举$r,c$，如果$rM+cN-2rc=Z$，那么算出$DP(N,Q,r)\times DP(M,Q,c)$并加入答案

当然这样会TLE。。。原因是如果$Z$恰好等于$NM/2$，那么这种$(r,c)$的个数非常多（只要$r=N/2$或$c=M/2$就满足条件），此时有其他公式爆算一下就好

$Z\ne NM/2$时满足条件的$(r,c)$的数量并不是很多，这么做再卡卡常数就能通过本题辣

拟阵交的题，我不会

总之就是$2n-2$再减掉两个graphic matroid（就是森林组成的拟阵）的最大公共独立集的大小就是了

因为人类的本质是复读机，所以这篇博客的内容基本上就是复读Editorial