POI18~20部分题(tu)解(cao)
codeforces补全计划

bzoj屯题计划

Recursion posted @ 2015年2月28日 15:13 in 题解 with tags bzoj 屯题 , 2374 阅读

update:

2.28 正式开坑!

跪球bzoj不要把后面的题权限了,我还等着大号屯50题呢...

3.6 3894被权限了,又得多屯一题,不爽...

3.7 完成了一半啦

3.11 bzoj上不去了,坑

3.16 屯了这么多天心力交瘁...感觉自己只会刷水题了...还是赶紧结了这个坑好了...

3.17 完结喽

完成度:50 / 50

 

bzoj3894 经典最小割。再不写写都快忘了。先把所有收益加起来,然后考虑无法获得的收益。选文理直接连边。若一个集合同时选才有收益新建一个节点向集合里的节点连无穷大的边,这个点再向源(汇)连容量为收益的边就行了。

bzoj3620 首先[tex]O(n^3)[/tex]的算法很显然,枚举开头和结尾,kmp搞出next就行了。然后发现我们只需记录上一次next开始合法的位置就[tex]O(n^2)[/tex]了...15000的范围真是坑...

bzoj2823 裸的最小圆覆盖。感觉这个应该算几何里面最好写的算法了吧...不过证明我还不会。

bzoj1064 好题。把每条边拆成权值为1和-1的两条边,然后bfs,分情况讨论。细节比较多WA了好多次...

bzoj3895 神结论题,证明方法简直鬼畜...一句话说不清楚...

bzoj3874 现在发现这道题其实也挺水的。很容易感受到天数是关于送外卖次数的凸函数,于是可以三分。然后按保质期贪心就行了...去年省选时贪心都没想到真是sb。

bzoj2595 裸的最小斯坦纳树,但是要输出方案比较麻烦,要记录每个点转移过来的状态...看了半天别人的题解终于A掉了,但还是没搞懂为什么可以这么实现...大概就是状压dp,[tex]f[i][j][/tex]表示以[tex]i[/tex]为根,[tex]j[/tex]状态下的最小斯坦纳树,一种转移是暴力枚举子集合起来,另一种是新建一个点连过来,这种可以用spfa搞。现在发现spfa真是个强大的东西啊,可以解决各种神奇的dp问题。

bzoj1794 lyd的博客里有这题的数学解法。把P和L看成+1和-1,构造出一条折线,然后分情况列出公式就行了。

bzoj1816 看完题后想这不是sb题么,2分钟后发现我看错题了...又过了2分钟发现我再次看错题了...然后我发现我不会做了...然后看了题解,发现我又看错题了...真是sb到一定境界了...

bzoj2140 pear上次讲的题,现在感觉挺水的。容易发现如果某一条边不是匹配上必须的,那么一定存在一个环调整匹配,于是tarjan求出强连通分量,若某个分量不止1个点,那么显然是不安全的。

bzoj3629 这种题显然是爆搜。然后我们用约数和公式,枚举所有的质因数,直到最后剩下一个质数。判断质数可以先线性筛搞出小范围的质数,大质数[tex]O(\sqrt n)[/tex]枚举。不知道用miller-rabin会不会快一点。一开始没看到多组数据被坑了。

bzoj3208 当时打ch的时候看到这题感觉好神,今天来看了一下数据范围,我就无语了...我当时是有多sb...

bzoj3210 我当时是有多sb...把坐标转化为[tex](x+y,x-y)[/tex],然后分别取中位数就行了。由于有奇偶性的原因要特判一下周围的四个点。

bzoj1407 复(xue)习(xi)了一下拓展欧几里得...

bzoj1211 prufer code推推公式就行了。注意数据比较坑,要判断无解情况。

bzoj2764 这题的重点是高精度我会瞎说?

bzoj3566 目前为止见过的最好的概率dp。(被waltz719神犇D了T_T)一开始感觉各种复杂,于是膜拜题解,感觉做法挺神的。先是把问题分成子树和父节点来考虑,父节点可以看成是总概率去掉子节点对父节点的贡献。用[tex]P(A+B)=P(A)+P(B)-P(AB)[/tex]算就行了,这个公式同样可以用来从总概率算部分概率。

bzoj2560 跟主旋律有点像,但比他简单得多。用补集转化的思想,状压dp求出总数和不联通的数量。

bzoj2339 好神的数学题。依然是用全部减去不合法的思想,然后发现去重时可以缩小问题规模,递推就行了。有一个技巧是算出记顺序的方案数,最后除以[tex]m![/tex]就是不记顺序的方案数,这样方便分析问题。

bzoj1406 (感觉我只会捉水题了)枚举约数显然,然后稍微算算就行了。

bzoj3876 当年在考场上想出算法但写错了费用流真是遗憾T_T按照入度出度大小关系分类,floyd预处理,费用流就行了。布吉岛为什么那么多人写上下界费用流。

bzoj3162 同构计数好有趣啊...就是hash太坑了...见这题专属记录。

bzoj1588 数据坑爹不说啥了...

bzoj2132 以前貌似做过的,不知道为什么没提交...黑白染色,黑白格子连边方式相反,最小割。

bzoj2151 一开始想了半天图论独立集...后来发现每次取最大值,然后把前后两个数删掉,当前位置换成用前后两个数替换的差值,贪心就行了。

bzoj2763 裸拆点spfa。不过跑得比较慢...

bzoj1570 直接暴力枚举答案,建出网络流图,每次枚举值加1的时候直接在图后面加一层就可以了,网络流判定。

bzoj3612 考虑中间点放或不放两种情况。容易发现这就是一个将[tex]n[/tex]分解成[tex]k[/tex]个不等正整数的问题。若最小的数是1,那么转移到[tex]f[i-j][j-1][/tex],否则转移到[tex]f[i-j][j][/tex],由于最大数不超过[tex]n[/tex],所以要减掉出现[tex]n+1[/tex]的情况,即[tex]f[i][j]=f[i-j][j]+f[i-j][j-1]-f[i-n-1][j-1][/tex]。

bzoj3106 容易发现A胜当且仅当开始时两个棋子相邻,否则B必胜。记忆化搜索即可。

bzoj3564 先把坐标轴旋转[tex]a[/tex]度,然后[tex]x[/tex]坐标缩小[tex]p[/tex]倍,就变成正常的最小圆覆盖了。

bzoj1806 暴力五维dp大力出奇迹。64M空间要用滚动数组。

bzoj1804 每次选择左上角的一个点,显然它是在最外面一层的。从这个点开始dfs,直到搜出一个环回到这个点为止,dfs过程中所有仅遍历一次的即可得到要删去的墙。

bzoj1269 不会写spaly?rope大法好...什么,你问我区间翻转怎么办?维护一正一反两个rope就行啦。

bzoj1507 同上,连翻转都不要。

bzoj3224 吓尿我了,vector+lower_bound直接水过去了...跑得还飞快,什么鬼...目测数据是随机的?

bzoj3810 暴力[tex]O(2^4nm)[/tex]dp。[tex]nm<100000[/tex]居然T了...加了个[tex]n>m[/tex]时翻转网格就15s+卡过了,不明真相...我算错复杂度了真是sb...应该是[tex]O(2^4nm(n+m))[/tex]...

bzoj3107 [tex]f[i][j][k][l][flag][/tex]表示前[tex]i[/tex]位中[tex]a,b,c[/tex]分别用了[tex]j,k,l[/tex]个1,[tex]flag[/tex]表示是否进位时的最小值,然后暴力转移就行了。

bzoj2428 随机化+贪心。反正数据小怎么做都行。

bzoj3157&&3516 挺厉害的数学题。令[tex]f[i]=\sum_{k=1}^n {k^im^k}[/tex]。推倒可得[tex](m-1)f[i]=n^im^{n+1}-\sum_{j=0}^{i-1} C_i^j(-1)^{i-j}f[j][/tex]。然后[tex]O(m^2)[/tex]递推就行了。注意特判[tex]m=1[/tex]的情况。

bzoj3610 同时维护路径平方和,路径和,路径数量的矩阵,预处理二的幂次,转化成二进制做。

bzoj2815 (shanquan2说他随便想想就想出来了太神了Orz)fhq出的题...考虑构造一个叫做灭绝树的东西。给所有生产者加一个太阳作为根。然后按照拓扑序依次加入节点。容易发现每个节点的父亲就是他的食物节点的lca,倍增维护一下。最后答案就是每个节点在灭绝树中子树的大小-1。

bzoj3288 由(打表找规律)高斯消元发现最后就是球[tex]\prod_{i=1}^n {\varphi (i)}[/tex]。线性筛搞一下。

bzoj1502 以前一直以为很神,今天才知道原来simpson积分就是个乱搞的方法(果然人类对计算几何的恐惧是永无止境的)...容易发现求的面积就是一堆圆+梯形。simpson直接上就行了。注意调精度。

bzoj1830 同1879...

bzoj1501 (我深信noi2005的出题人急需治疗)打表搞出每种零件的形状,然后大力出奇迹。据说要用dancing links不过不用也能过。

bzoj3211 经典题不说了。唯一的坑点是会有0,要特判...

bzoj1564 [tex]f[l][r][m][/tex]表示将[tex][l,r][/tex]构成treap,根权值[tex]>=m[/tex]时最小的代价。暴力转移即可。

bzoj2330 (只会做裸题真是没救了)裸差分约束系统。

bzoj3673 rope随便水...

bzoj2706 (把三道题合在一起我也是醉了...)A类数据可以直接二分图匹配。B类是一个经典问题可以证明答案是[tex](n^2-1)/3[/tex]。C类直接搜。可以用dancing links优化。现在想想这种东西还是比各种树形数据结构好写多了。学习youyl的好习惯三个程序分成三个namespace...

bzoj1078 我太弱了不会捉...懒得详说了,看题解好了。

 

 

Avatar_small
SanSiroWaltz 说:
2015年3月07日 09:44

还好我3894写完就交了

SanSiroWaltz 说:
2015年3月09日 22:05

我觉得3566挺sb的啊。。。

Avatar_small
Recursion 说:
2015年3月09日 22:47

@SanSiroWaltz: 那是您太神了...

Avatar_small
Recursion 说:
2015年3月09日 22:47

@SanSiroWaltz: 或者说我做过的概率题都是sb题...

Avatar_small
bx2k 说:
2015年3月19日 21:26

太神啦!recursion随手虐掉50题!

Avatar_small
Recursion 说:
2015年3月19日 21:29

@bx2k: 随手被水题虐T_T


登录 *


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