刷题计划第二弹

Recursion posted @ 2015年3月19日 20:31 in 题解 with tags bzoj POI uoj POJ usaco codeforces , 1868 阅读

这次不屯题了...想想既然离省选不远了还是做点正常的题比较好。

update:

5.1 总算是在ctsc&&apio之前完结了...不知道第三轮省选之前能不能再填一个坑...

完成数：50

[bzoj2154] 了结了多年来的心结...现在看来莫比乌斯反演也不是什么无法理解的东西...不过关于数论的题公式推起来就是烦...

[bzoj3139] 容易发现状态是与得分序列的顺序无关的，所以使它保持递增的顺序。依次搜索每个队的得分，用map进行记忆化。

[bzoj2143] (校内训练的题，没想出来真是sb...)我们把弹射视为获得[tex]a[i][j][/tex]的能量，每走一格消耗1的能量。当能量为0时可以在当前点消耗[tex]b[i][j][/tex]补充能量。然后就是显然的拆点最短路了。用点数换取边数确实是挺厉害的。不过感觉理论上还有优化空间？

[bzoj3622] [tex]n-k[/tex]为奇数时显然无解。先将[tex]a[/tex]和[tex]b[/tex]排序。设[tex]f[i][j][/tex]表示前[tex]i[/tex]个糖果至少有[tex]j[/tex]组比药片数多，其余不管的方案数。显然[tex]f[i][j]=f[i-1][j]+f[i-1][j-1] \times (next[i]-j+1)[/tex]，其中[tex]next[i][/tex]表示最大的j使[tex]a[i]>b[j][/tex]。然后容斥去掉不合法的方案。[tex]ans[k]=f[n][k] \times (n-k)!- \sum_{i=k+1}^n ans[i] \times C_i^k[/tex]。

[bzoj2144] 对于一个状态，只有一个棋子是可以向中间跳的。因此可以将所有的状态视为森林。所有的根节点即为三个点之间等距。然后用类似辗转相除的方法求出两个状态的深度。二分答案即可。

[bzoj3907] [tex]C_{n+m}^n-C_{n+m}^{n+1}[/tex]，直接python也是爽。

[bzoj1149] 两遍dfs。第一遍判断深度。第二遍根据左右子树判断是否交换。

[uoj84] 有生之年终于能捉一道UR的C题啦...虽说看了一天的题解...主要是dp方程比较难想，然后的优化就比较好搞了...官方题解讲的很详细，就不说了。感觉这是7场UR以来最靠谱的C题？

[poi7 viruses] 黑书上的题。建出AC自动机。存在无限长的安全串也就是存在一个环。dfs即可。为了方便可以把fail指针并到子节点里。

[bzoj1831] 注意到最后加入的数一定是单调不降的。于是就是sbDP了。

[bzoj3900] 挺有趣的状压dp。令[tex]f[i][/tex]表示[tex]i[/tex]集合内的最优值。那么一种转移是枚举子集合起来，另一种是通过一个大环调整。有趣的是后一种情况只要当前集合有解那么答案一定是当前集合元素数量-1。因为如果存在更优的情况，在前一种转移里一定会考虑到。于是问题就转变为了判断一个集合是否有解，排个序就行了。不知道为什么跑到了rank1...

[poi17 divine divisor] 神题。把[tex]10^6[/tex]以内的质因数分解掉，那么剩下来的至多是两个大质数的乘积。先用miller-rabin判断是否是质数，然后暴力判断是否是完全平方数。剩下来的两两球gcd就行了。

[uoj28] 分几种情况dp一下就行了，细节比较麻烦不过代码很短。

[bzoj3916] 每种情况扫一遍就行了。一开始竟然会去想kmp真是sb。

[bzoj2150] 裸二分图最小路径覆盖。

[bzoj1826] 每次需要弹出元素时选择下一次出现最晚的就行了，map+priority_queue搞一下。

[bzoj2337] 以前做过的。裸高斯消元，不说了。

[bzoj2561] 分别考虑大于和小于[tex]L[/tex]的边，最小割就行了。

[bzoj3922] 自从有了pear的论文后这种题也算是sb题了吧...非常诡异的是这题我把阈值设成[tex]\sqrt {\frac {n} {\log n}}[/tex]会tle，设成一个很小的数就过了，跑得挺快。难道是线段树常数太大？

[uoj52] 找到[tex]k/3[/tex]的位置。对最小的那个数组，把前面的元素扔掉。每一次可以将[tex]k[/tex]缩小[tex]1/3[/tex]。

[bzoj1912] 求一遍直径。如果[tex]k=2[/tex]把直径的边改成-1，再求一遍。

[bzoj2152] 树形dp直接上。

[bzoj2162] 显然二分完全子图等价于补图的独立集。最小割就行了。为了使[tex]x[/tex]部点数最多，可以整体将权值增加一个较大的数。求出来以后就是简单dp了。

[poi17 antisymmetry] 不卡hash真是一件愉快的事情(不过main的评测机卡了...)。

[poj1737] 一道有趣的dp计数。dlh初二就会做了不知道比我高明到哪里去了...题解请百度shanquan2。

[bzoj3925] 非常神的题。基本的想法跟clj在wc上讲的那题差不多，不过不需要分别考虑每条边。求出多项式[tex]f(x)[/tex]表示边权全部小于[tex]x[/tex]时图不联通的概率，在[tex][0,1][/tex]上积分就是答案。计算这个多项式可以状压dp，用类似poj1737的方法。唯一想吐槽的是卡精度什么心态...非得用__float128...

[bzoj3559] (我能吐槽贾教出的题为何题面都这么长吗...)首先你要看懂题目，然后你要会大胆猜想...证明啥的请去看题解...排个序从小到大只要符合条件就并起来就行了。

[bzoj3928] 考虑一个时间区间中最大的[tex]d[/tex]，这个外星人显然必须以[tex]d[/tex]的代价打，枚举打的时间。区间dp。

[bzoj1856] 可以转化成3907的模型。

[bzoj3932] 将任务离散化，然后主席树直接上。感觉我已经不会捉数据结构题了，写个裸主席树都能错...

[usaco 2015 open gold googol] 其实就是道sb题...询问出右子树的大小，根据奇偶性判断左子树就行了。

[cf round41 d] (Orz bx2k)把点权转化成边权，然后dp大力出奇迹。

[bzoj2131] 旋转坐标系以后可以树状数组优化dp。

[bzoj2342] manacher以后枚举中点。set优化就行了。

[bzoj1560] 显然每一列我们尽可能从下面的点转移过来。[tex]O(nm)[/tex]的dp。

[poi15 toll] 构造一个基环+内向树就行了。

[poi16 fire extinguishers] 人生第一次猜对了poi题的结论，感动的不行...其实结论很sb，每次找到最深的点的[tex]k[/tex]阶父亲[tex]v[/tex]，选出与[tex]v[/tex]距离不超过[tex]k[/tex]的最深的[tex]s[/tex]个点就行了。