codechef OCT19

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

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

S10E

大模拟

MSNG

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

SAKTAN

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

MSV

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

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

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

MARM

显然有循环节。执行

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

然后暴力模拟。

EVEDG

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

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

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

MAXLIS

不会(

BACREP

对于第$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]$从小到大处理这些询问,做子树加法、单点查询就是了,注意把叶子和非叶子分开

JIIT

为什么大家都是$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)$的数量并不是很多,这么做再卡卡常数就能通过本题辣

CNNCT2

拟阵交的题,我不会

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

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


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter