做题记录2

2015-4-13至2015-4-18

颓废了一个星期,我也不知道为什么。

BZOJ1978: [BeiJing2010]取数游戏 game 记$f_i$表示第$i$个数字选择的时候最多选多少个。可以枚举$a_i$的大于$L$的约数$d$,然后记上一个含有$d$的约数为$last[d]$那么显然$f_i=max(f_i,f_{last[d]}+1)$。因为如果从一个$j < last[d]$且$d | a_j$转移,那么一定也可以选择$a_{last[d]}$使得答案更大。每个数字最多有$2\sqrt{n}$个约数,复杂度为$O(n\sqrt{n})$

BZOJ3563: DZY Loves Chinese 首先扔度娘的文言文翻译,接着我看了好久也没有意识到哪里逗比了,后来找到了这个……由于每行数量可以读出,就可以利用$k$知道$lastans$,最后一个没法推就并查集暴力。

BZOJ3569: DZY Loves Chinese II 求出dfs树,去掉一些边不连通,那么去掉的边中一定有一条树边且覆盖这条边的非树边全部被去掉。可以记录每条树边有多少条非树边覆盖,然后再枚举其他边要去掉的边看是否覆盖。判断一条边是否覆盖另一条边,可以断判断覆盖边的端点是否是被覆盖边的儿子和祖先,可以利用dfs是记录的$pre$和$suf$两个时间戳判断。还看到另一种判断方法是高斯消元,感觉比较神,记下了可能以后有用。


BZOJ3561: DZY Loves Math VI 推出来一个奇怪的公式:$\sum_{T=1}^{n}\sum_{d\mid T}d^{d^{mod-2}}T^{2d}\mu(\frac{T}{d}) \sum_{i}^{n/T}\sum_{j}^{m/T}i^dj^d$,然后枚举$d$,预处理出$i^d$,然后枚举$d$的倍数$T$。似乎复杂度是$O(nlog^{2}n)$计算$T^{2d}$的log去不掉。卡时过了没有再管。


BZOJ2668: [cqoi2012]交换棋子 建立三层节点…刚才编辑的时候remarkable蹦了,什么都没了…那就YY吧


BZOJ3683: Falsita 可以先dp预处理出答案。接着发现对于单点修改操作,可以用树链剖分修改父亲:对于主链上的点,每次修改答案变动$(size[u]-size[son[u]])d$,主链就可以预处理出变动值,每次询问求d的和。树状数组即可。而主链间交接的点直接暴力修改。对于子树修改,对父节点的影响相当与单点$dsize[u]$。对儿子的修改,相当于平均值加上$2*d$,可以在dfs序上用树状数组维护。