刷题计划 第三弹

希望round3之前能填满这个坑

update:

5.11 上面那句话当我没说

5.23 明天就要去常州啦

5.27 目测这个坑要变成无底洞了...

6.2 弃坑弃坑

完成数：36

[bzoj4034] 你们感受一下查错了20min最后发现没开longlong的感觉...两发线段树解决。

[bzoj4048] ...不说了...

[poi15 blockade] 然而我依然不会写tarjan...

[poi17 guilds] sb题...

[bzoj3669] 写了一发spfa...

[poi17 teleportation] 从两个点分别bfs两层，剩余的点必须全部放在某一层，分别统计一下。然而我并不会证...

[bzoj4052] 根据gcd不会太多的性质暴力...

[bzoj1913] 统计凸四边形和凹四边形的贡献就行了，要用long double。

[bzoj1832] 倍增搞一搞...

[bzoj4063] 刷水感觉良好...

[bzoj3867] 还是gcd的性质，直接线段树就好了。

[bzoj4059] 大乱搞...(后来pear发现这个乱搞方法的复杂度是靠谱的...)

[poi20 multidrink] 其实这题也不难，分情况讨论一下就行了...

[poi19 rendezvous] 倍增搞一下。

[bzoj3993] 二分答案+网络流。

[bzoj4036] vfk论文的黑科技。集合并卷积可以用子集和变换来做。于是最后的式子可以化成[tex]\frac {1} {p-1}[/tex]。其中[tex]p[/tex]是子集和变换后的集合多项式。注意无解情况。集合多项式真是个优美的东西啊...

[uoj112] 就一道傻逼题。比赛的时候我居然会傻逼到去想三分而且还没写。刚刚写这题调了半天最后没开longlong。我感觉我已经傻逼到没脸见人了。[tex]k=1[/tex]直接排序取中位数。[tex]k=2[/tex]枚举断点线段树维护两边的中位数。三分应该也是可以过的。

[uoj113] 题目读了半天...显然每一块"&&"是可以分别统计的。

[bzoj1811] 水题。

[bzoj4009] (再不写道数据结构感觉自己代码能力要弱成渣了T_T)整体二分，问题转变为询问水果覆盖了多少个盘子。dfs序以后发现合法区间是一个矩形。扫描线+树状数组就行了。

[bzoj4028] 显然分块。每块维护前缀异或值的hash表。注意到gcd最多变化[tex]\log[/tex]次。所以枚举每块的时候，如果这一块整体取gcd后不变直接从hash表里查找答案，否则暴力。偷懒用了unordered_map...

[bzoj3953] 以52种离子为点，不同分子之间相反的离子连边，判断环就好了。把[tex]O(n^2)[/tex]优化成了[tex]O(52^2)[/tex]。

[bzoj2964] 注意到法术和特技攻击是独立的，可以分别用一个dp计算[tex]i[/tex]回合造成的最大伤害。再使用一个dp表示前[tex]i[/tex]个回合保证不死的情况下，可用来攻击的回合数。然后大力枚举就行了。

[bzoj4025] (妈妈我也会动态图了)hza的论文里的正解貌似是lct维护奇环...然而我显然不会...于是就离线并查集大法好...对于当前区间，先把所有覆盖这个区间的边加进去并查集判断，如果有奇环一定全是No，否则分治左右区间。要注意并查集只按秩合并不路径压缩，一方面方便统计奇环和还原，另一方面路径压缩是均摊的。(虽然这样华丽地多了个[tex]\log[/tex])由于并查集只需要资瓷恢复所以不需要可持久化，记录一下修改原样复原就行了。

[poi12 special forces manoeuvres] 有趣的题。一开始想了半天[tex]O(n^2 \log n)[/tex]的做法...正解考虑所有圆交的最右点。显然这是唯一的。所以我们每次插入一个圆更新两两圆交最右点的最左点(原谅我语文不好T_T)，如果存在，这个点一定是所有圆交的最右点，判断是否在每个圆内就行了，标准的[tex]O(n^2)[/tex]，跑得飞快...

[poi12 piggy banks] 经典并查集。

[poi12 toy cars] 挺sb的贪心...感觉已经考烂了？

[poi11 passage] 状压dp。

[bzoj1820] 赛前刷水。

[bzoj2425] 水数位dp。

[bzoj3967] 爆搜前16个质数。

[bzoj4080] 随机100次+bitset。或许以后球最大团/独立集可以试试这个方法？

[bzoj4057] 大状压dp。又一次多测忘清零真是sb。

[bzoj2127] 最小割。

[poi16 the walk of bytie-boy] pear出过类似的题。要注意dp回文最短路的时候直接同时枚举两边是会t的，可以用两个dp互相转移就行了。

[bzoj1297] sb题。