做题记录3

4.20

COGS1941. 超牛冠军赛 想了个显然错误的贪心,显然WA了…最小生成树,然后就$O(n^2)$没了。学了prim,似乎COGS的逆天评测机kruskal也不会跪。

COGS1942. 审查 AC自动机,顺便记录每个字符匹配到自动机上那个点,以便删除后可以直接找到对应点。我忽略了一个致命的问题,因为这个会往回退,所以复杂度好像不是$O(n)$。科学的做法应该是记录last[u][c],作为当节点u到试图匹配字符c错误时到哪里可以匹配上,不科学的做法是cheat掉….

BZOJ3218: a + b Problem 神题…网络流。首先连边$(S,i,w_i)$,$(i,T,b_i)$,假设已经获得选择白色和黑色全部收益,再减去最小割就是实际收益。对于点$i$,连边$(i’,i,p_i)$,所有满足题目条件的$j$连边$(j,i’,inf)$。这时最小割要么使得所有$j$都为黑色,要么使得$i$为黑色且扣除$p_i$或者$i$为白色。但是因为边数量是$O(n^2)$的,会T掉,就有特别神的方法:把边像主席树上的边一样连起来。PoPoQQQ的题解,看了他的图我才看懂,我就不画了。

BZOJ3687: 简单题 bitset好神奇。背包dp,记录每个和的数量,再异或起来。发现是异或所以只关注每个和的奇偶性即可。对于模2意义下的加法,相当与异或,可以用bitset加速转移。

BZOJ3688: 折线统计 dp即可。可以发现转移条件可以用树状数组优化,就没有了。


4.21

BZOJ3689: 异或之 对于每个数字寻找在这个数字前面的数字的第k小值。可以利用可持久化trie来寻找。


4.22

BZOJ3694: 最短路 符合题目条件的最短路一定可以只经过一条非树边,枚举每条边,会影响的点一定是该边在树上的路径除去lca。可以用树链剖分,我用的是枚举每个点相邻的边,暴力更新这个点的父亲,栈优化。还有种神做法我没有看懂QAQ。


4.23

BZOJ3695: 滑行 有个叫最速原理的东西, 我似乎没有上过高二,大概就是这样。接着二分第一个入射角即可。注意二分的时候角度的误差不能太大,否则时间的误差会更大。


4.25 省选日

就这样低速行进了三天,浮躁了两天去省选了。省选我似乎跪傻了,真的一天啥都不会写。写一天暴力。结果机器逗比奇怪的使得某些正解谜之T,但是神犇们依然虐场,跪梦迪和夹心。

接下来因为奇怪的原因没有去学校,继续浮躁QAQ。


谢谢夹心共享的HAOI2015题解包


4.29

COGS1962. [HAOI2015]树上染色 大力出奇迹,直接dp复杂度其实是$O(n^2)$,ydc大爷的题解。(我才不会告诉你考场上我写的是30分暴力)


5.1

1964. [HAOI2015]数组游戏 好神奇,讲不详细,直接看题解吧,题解包在上面。证明跳跃次数一样($N/i$一样)时,sg值一样。接着就乱搞了。最后不知道怎么搞的卡时过了,就没再管那比较玄学的复杂度了。