少年挖坑中...

今天是8.31。开学了。

想想颓了一个暑假是时候好好搞OI了...（再不好好搞OI就没大学上了）

当然，这是个可以资瓷动态插入的大坑，并且随时可能拍扁重建...

不过想想我挖的坑基本上还是都填了的嘛...比起とあるak爷...是吧...

 

11.19 update: 似乎这个坑的性质果然和我想的一样变了。

12.31 update: 明年重新开个坑吧...这坑已经乱得不行了...

 

把最近要干的事记一下：

WC2014 紫荆花之恋 好早就想写的题...可惜当时不会树分治...有必要写一写大数据结构呢...顺便学一下旋转式treap...(我好像遇到平衡树的题总会想尽办法不写旋转...)

8.31 AC!

---

bzoj4012

感谢waltz...

写数据结构题果然是体力活啊...

树链剖分，每一条链维护一个可持久化线段树就行了，度数小于等于3并没有什么卵用...估计是为了可以动态树分治的...

---

bzoj3148

终于把这道坑爹题A了...

手算期望的式子，暴力拆开来以后只需要线段树维护0,1,00,11,01,10,011,110八种子序列的数量就可以了。

方差的话，大胆猜想严(bu)格(yong)证明一下答案就是关于[tex]n[/tex]的次数不高的一个多项式。暴力算几个插值一下就好了...然而我很懒所以直接抄了公式...

线段树部分8个域标记下传写得我真是欲仙欲死...@线段树球bx2k

wa了半天还以为线段树写错了...最后发现公式特判错了...

其实感觉这题并不算很难？现场最高分只有46应该是被方差吓到了于是不敢写第二问了？不过直接插值实在是很坑啊...

---

bzoj3821

有趣的思路，我们对线段树的每个节点，用一个平衡树记录所有历史懒标记。下传可以利用可持久化平衡树的合并。于是就没了...

一开始写的可持久化treap怎么调都不对...一怒之下到uoj上抄了个AVL的板子就过了...

---

APIO2013 tasksauthor

玛德以后再也不做提交答案题了

在uoj上面刷了两页半的提交记录终于A掉了...

这种题其实就是考细节胜过考算法...

subtask1:空图。

subtask2:想要卡掉bellmanford只需要一条编号倒过来的链，这样就需要更新[tex]n[/tex]次。

subtask3:空图。

subtask4:看题解的T_T把若干个三角形连起来，每个三角形两条路径，多出来的两条边包含了一条负权边，这样每多一个三角形就需要2倍更新次数。

subtask5:看题解的T_T，和subtask2差不多，不过要算一下点数。

subtask6:同subtask4。

subtask7:团。

subtask8:二分图。

---

UOJ94

神神神神神神神神神神神题！

把集合幂级数当成生成函数，子集和变换一下，然后每个位置的多项式用一个递推求解，最后变回去就行了。具体看题解咯...

不得不说集合幂级数的子集卷积真是神啊...不过预计要在天朝普及开来还是有生之年的事情？不过至少又多了一种神教就是咯...不过说实话集合多项式比起普通多项式的各种神奇算法不知道好写到哪里去了...我到现在还只会背ntt的板子...

卡常数卡到死...之后还是用了vfk的"ugly optimization"才过...

---

妈妈我也会写带花树啦！

uoj.ac/submission/27612

其实就是照着模板抄了一遍...论文里的证明过程看起来好麻烦...

---

tc几道看过题解没写的题...

srm578div1 hard 真·大力出奇迹...暴力[tex]O(n^3)[/tex]dp。转移再加上一个二分图匹配。然而[tex]n=50[/tex]跑得飞快(因为数组开不下我还写了个map套map套map套map)。

srm573div1 hard 把坐标转一下就是sb题了...

srm577div1 hard 挺神的最小割。注意到一次染色相当于把行与列割开来。于是考虑最小化边界的数量。源点向每个需染色的点连容量等于他上下不需染色点数的边，每个需染色的点向汇点连容量等于他左右不需染色点数的边。相邻的需染色的点连容量为1的边。跑最大流即可。dinic不加优化会超时→_→加了以后最大的点15ms...

tco2015round1A hard hall定理。然后就是大暴力了。

srm664div1 medium dlh说的sb题...用期望线性性把答案拆成每一个点所在联通块大小之和，然后随便dp一下就行了。

srm669div1 medium 一开始想了个非常复杂的做法T_T还好业界良(du)心(liu)dlh及时告诉了我一个简单dp...我真是sb...

tco2015round1B hard dfs一遍记录每棵子树里面选两个点的方案数，搞一搞就行了...

tco2014semifinal2 hard (这题只有850分什么心态→_→)挺有趣的生成函数，顺便补习了一下高中数学...

tco2014wildcard medium 非常优美的计数题。杜教集训队论文里提到可以直接枚举等价类的数量，乘上第二类斯特林数就可以直接算了，感觉好神。

tco2014wildcard hard 每个位置拆成4个点表示来的方向，每个点记录从终点走过来的最低能量。能量+1相当于在走过来的方向上继续走一步，bfs即可。不过比较卡时...最后还是用吉丽的花式优化才过的...

tco2014final medium 感觉这题虽然只有550但是比前面那道750的计数题难啊T_T最后一定是按照加速度不增排序，令所有的油桶[tex]x[i]\geq y[i][/tex]，然后按[tex]\frac{x[i]}{y[i]}[/tex]从小到大排序，每次加入的油桶要么放到开头要么放到末尾，分别统计对其他油桶加速度的贡献即可。因为值域很小，所以可以dp。好神的题。

tco2014final hard 看了题解并没有看懂，似乎是很神的容斥？然而吉丽等人的程序好像很简单一副靠谱的样子...球老司机教我为何这是对的啊T_T

srm575div1 hard 每个L形可以看成源点到奇数行的白点到黑点到偶数行的白点到汇点的路径，拆点最大流就好了。

tco2015round2D medium 我们只需要找出最左边的球的位置，所以只需要查找[tex]p=n-k+1[/tex]个位置。如果[tex]p\geq 2k[/tex]那么我们总可以每隔[tex]k[/tex]个问一次直到[tex]p<2k[/tex]。然后最优方案一定是二分直到[tex]p=k[/tex]。

tco2015round2D hard 思路非常正统但还是很有趣的期望题。一开始去想期望线性性然并卯。事实上由于每一步只跟上一次停在了哪里有关，所以可以直接列方程递推。题解很详细我就不多说了。

srm518div1 hard 经典fwt板子题。

tco2015round2C hard 有趣的结论题。如果经过[tex]t[/tex]步到达了[tex](x,y)[/tex]，那么[tex]2t[/tex]步后一定到达[tex](x-y,x+y)[/tex]。注意到乘2等价于将每个数后面分别加一位0或者1，根据四种余数关系可以推知。于是暴力就行了，当[tex]x+y[/tex]为偶数时我们用前面的结论将步数减半，否则步数结尾一定是1，直接移动一位。

tco2015round2A easy sb题想了半天。令[tex]a_i[/tex]表示[tex]i[/tex]的数量，显然每次更新只会当前mod值到上次mod值之间的数量，所以总复杂度是[tex]O(R)[/tex]的。

tco2015round2A medium 一道sb题搞了一上午...枚举一个根，二分答案，所有的fox肯定尽可能往根走，标出所有可能目标点，跑一遍匹配就行了。

tco2015round2A hard 不会做的去补bzoj2564。

tco2015round1C medium 这sb题顶多给个200分...

tco2015round1C hard 这sb题顶多给个300分...

srm595div1 hard 经典题。枚举一条边，它出现在凸包上的概率就是两个点的概率乘某一边所有点未出现的概率。统计一下贡献就行了。

srm591div1 hard 暴力轮廓线dp。

srm673div1 easy 枚举1号的匹配点，剩下的乘起来就行了...感觉这个300分很简单啊...

srm673div1 medium 我现在这智商真是...列出dp方程之后竟然不会优化，看了题解才发现直接存一个部分和就行了...感觉我是药丸啊...

srm673div1 hard 好神啊...看了题解并没有看懂...有没有老司机教教我...codeforces.com/blog/entry/21651

srm641div1 hard 陈老师在WC讲的神题。做法就是把答案的期望拆开，这样状态就是多项式级别的了，列方程消元即可。很神的思路。

---

补一补cf的题...

round319div1:

A题直接输出所有只有一个质因数的数。做完A题后发现已经有人过了C，于是看了一下，写了一发莫队的根号构造方法，于是A了...为毛做出来的中国人这么少...B题感觉很麻烦，想了一会儿发现貌似确定重心就可以直接构造菊花树了？于是写了一发，A了...剩下来的时间看了看D题，想了一会奇怪的最短路根本不会做。E题很像是动态二分图...然而并不知道怎么确定边的消失时间...于是弃疗了...

round320div1:

B:猜了个结论。只会乘同一个数...

C:刚打开题目就被tag剧透一脸...

D:tc原题弱化版...挺显然的dp套dp，不过写起来令人意外的麻烦呢...

round325div1:

E:bx2k都会做的数学题，你说是不是水题？

round327div1:

由于我打开这场的时候已经开始15min了加上感觉这场画风不大对就没敢交代码...后来想想要是我开场把D交了应该没啥问题，不过我后来做D也交了好几次才过感觉没什么救啊...

C:傻逼bfs。貌似若干年前的usaco一道题跟这个差不多。

D:我从未见过如此水之D题...一开始以为是贪心，发现范围只有150，直接大力dp。显然左右两部分的代价是不相关的，分别背包就行了。特判没搞好交了好几次。

round334div1:

C:裸sg函数。就算不会分析也可以大力找规律。

round335div1:

E:toosimple 16min就秒了这题...这种最优策略的期望题我向来不会捉。每个点的最优策略一定是选择指出去的若干个最短的点或者停1s，用类似dijkstra的方法更新就行了...感觉只可意会不会言传啊...

round336div1:

C:想不出来的sb题T_T

---

poi21的"可做"题

little bird:以前做的。貌似是单调队列dp？

solar panels:貌似是根号算法？

hotel:dfs一下就可以了。

couriers:裸主席树。用指针会mle。

bricks:放在cf一定是cha人好题...做法的话一通乱搞就行了...

salad bar:单调队列搞一搞...

---

bzoj4236~49 JOI系列(感觉难度还算靠谱？)。好在现在开了权限号可以慢慢刷了...

弃坑...还有几题不想写了T_T

bzoj4236 转化成前缀和以后出现次数相等等于相对数量之差相等，map搞一下。

bzoj4237 按y轴分治，每一层按x轴排序，不想写数据结构的话直接上下分别维护一个单调栈就行了，答案一定是连续的一段可以二分。

bzoj4238 经典题。注意到无向图dfs树的非树边都是返祖边的性质可以随便做到[tex]O(n+m)[/tex]。当然直接上bzoj4025也是可以过的。

bzoj4239 按时间排序，求出每个最晚的时间，二分。

bzoj4240 答案就是每个数左右两边比它大的数量较小值之和。

bzoj4241 做一下bzoj2821就会了。

bzoj4242 noip题。

bzoj4243 把每组连着双向边的点用并查集连一块，每个点连出去的所有点之间也连上，然后对大小大于1的块bfs，显然最后得到的块都是完全图，其余边不变。

bzoj4244 花样dp。

bzoj4247 sb背包。

---

随便做做bzoj新题吧...

bzoj4264 显然如果[tex]n[/tex]比较小就可以压位了，这题[tex]n[/tex]这么大显然只能hash乱搞...

bzoj4269 完全不知道出题人出一道裸题什么意思...

bzoj4259 星号看成0乘进多项式里，然后直接fft就行了。

bzoj4291 傻逼题。

bzoj4292 一开始以为是数位dp，仔细想了一下发现不是傻逼暴力吗...

bzoj3073 波兰人的图论题...线段树存边，并查集记录点，利用bfs的性质可以直接更新即可，感觉均摊一下可以优化到线性？bzoj上跑到了rank2真是好评。

bzoj4297 每个点的取值范围是个区间，dfs一下就好了。

bzoj4220 神题。orz starzxy...www.zhihu.com/question/32116679#answer-18414975

bzoj2708 一看数据范围，卧槽[tex]n\le 50[/tex]？再一看题目来源，卧槽tc？于是就是一个[tex]O(n^3)[/tex]脑洞dp了，网上题解基本上都是“我也不知道为什么这样是对的，不过看起来很靠谱”之类的...其实还是挺显然的吧，不过我也说不清楚...

bzoj2721 化简一下答案就是[tex]n!^2[/tex]的约数个数。

bzoj2709 sb题。

bzoj4282 一个结论是一定存在一个最优解用到了所有的N，于是直接dp就好了。

bzoj2738 为何我的整体二分这么慢！为何我的整体二分这么慢！为何我的整体二分这么慢！(因为很重要所以说三遍)完全不明真相...

bzoj3328 矩阵快速幂显然，然后可以利用原根的性质构造一个式子使得只有[tex]i\%k==0[/tex]时为1。

bzoj3817 mark一下神做法：

就是要求：[tex]n+4\sum_{d=1}^{n}{\lfloor dx/2\rfloor}-2\sum_{d=1}^{n}{\lfloor dx\rfloor}[/tex]。

这个东西可以类拓展欧几里得的做法搞：www.cnblogs.com/Dyzerjet/p/4452916.html

bzoj2557 动态加边费用流。因为图长的很简单，所以可以匈牙利增广。

bzoj4129 带修改树上莫队...我跑得好慢...

bzoj3052 带修改树上莫队...我跑得还是挺快的...

bzoj4199 膜了下bx2k的后缀数组板子，于是超时了...不得不说uoj的评测姬稳定性不靠谱啊...不过一个[tex]O(n\log n)[/tex]的后缀排序居然要跑700+ms简直不靠谱。bzoj上面也果断垫底...尼玛bx2k你noi的时候两个[tex]\log[/tex]怎么卡过去的...

bzoj3033 sb题。

bzoj3248 二分答案。然后对于所有的弱机器人从小到大排序，依次选择体积最大的若干个玩具。小机器人同理。用堆可以做到[tex]O(n\log ^2n)[/tex]。

bzoj4204 循环矩阵快速幂。这种题要是我就出成100000写fft嘛...

bzoj3742 暴力dp，费用流转移。跑得比我想象得快。

bzoj4305 直接上容斥就好了。

bzoj3737 直接爆搜+miller_rabin判素数就好了...我按照黑书上的millerrabin写了下，发现是错的。

bzoj4318 把[tex]p^3[/tex]拆成相邻两项的差。dp。

bzoj4320 小于[tex]\sqrt {300000}[/tex]的询问直接开个数组记录，否则枚举它的倍数，转化为求比一个数大的最小数，分块。

bzoj4311 按时间分治+凸包+三分。

bzoj3509 分块fft。理论上块大小700是最合理的，不过实际会tle。开到3000左右最快，感觉非常不靠谱。

bzoj2000/3493 挺神的贪心。source里的sg不知道什么鬼。

bzoj2395 最小乘积生成树。

bzoj4319 利用sa搞出rank，直接构造就行了。

bzoj1101 莫比乌斯反演始祖题。

bzoj4068 考场上一直在想另一种贪心方法，然后发现根本没法动态维护...正解的话容易发现这是一个拟阵，因此每次插入或删除只会更改至多一个元素，贪心地选一下就行了。具体细节参见陈老师题解。

bzoj3571 最小乘积匹配。

bzoj2635 高中数学题。小范围要预处理不然会T。

bzoj3570 高中物理题。然而我并不明白为什么质量相同的汉中球和襄樊球弹性碰撞之后是交换速度而不是速度不变...

bzoj3534 以前想过这个题不会捉，今天看了题解发现只要把基尔霍夫矩阵改一下就行了...挺有趣的题。

bzoj3241 其实还是挺有趣的一道题吧...关键是想到可以一列一列更新就可以扫描线dp直接上了。都说很码农，我感觉除了N的转移要稍微优化一下其他都很sb吧...这种题关键还是心态要好...

bzoj2564 分别球凸包，边扔一起排极角序就是最后答案。

bzoj3249 好久没写数据结构了，写了个kdtree压压惊...爆了半天oj最后随手给坐标加了个1一交，尼玛竟然A了...最近总有灵异事件啊(刚刚发现貌似是初始化写错了)

bzoj2525 有了vfk的翻译就不用去google波兰文啦！vfleaking.blog.163.com/blog/static/174807634201328115553196/

"这种题目好难想啊......哭烂了......" by vfk

bzoj4055 考场上不会做的noip题。似乎bzoj上dijkstra会t？反正我卡不过去。

bzoj2419 ctsc的物理题窝都不会捉只会捉这种水题。设终点电势为0，对每个点流入流出电流相等，起点流出去1A的电流，解出每个点电势就行了。似乎这个方程矩阵确实跟矩阵树定理行列式很像？

bzoj1116 poi鬼畜图论智商题系列。

bzoj4327 初一省选时的题，我还以为再也看不到这题了呢...SAM板子题，虽然正解应该是AC自动机...

bzoj3822 半平面并包含所有点等价于半平面交不包含任何点。枚举凸包的一个点，转化成区间dp。超神的一道题。似乎数据有点弱？

bzoj3870 sb状压dp。

bzoj4092 大胆dp，yy一下是对的...

bzoj4032 后缀自动机，序列自动机四合一你服不服？前两问建出自动机枚举a串在自动机上跑就行了。后两问可以在自动机上dp。莫名其妙跑了个rank1...

bzoj3205 斯坦纳树直接跑。有两个注意点：1.转向器可能会陷入死循环。2.边权是1，可以用bfs代替spfa，具体地，用两个队列，新拓展出的点存在另一个队列，每次取队列头较小的。

bzoj4289 把边当成点，对于每个点相邻的边，排序后只需连相邻的边。总边数是[tex]O(m)[/tex]的。

bzoj3621 把点放到复平面上解方程就行了。eps开到1e-4才能过...

bzoj3989 UOJ上过了，bzoj没有spj。思路挺神的题不过题目感觉不是很优美。具体题解看官方的吧，挺详细的。

bzoj2963 dp+爆搜。其实也不想想象中那么难写...而且这题也很良心。

bzoj1158 建图还是比较神的...不过重点还是上下界网络流？

bzoj3860 sb分治fft。数组开小了T_T

bzoj3616 TM的这种题居然是集训队胡策题？你也配姓胡？调了半天发现kdtree建树错了。sb题目毁我青春。

bzoj4368 不错的IOI送分题。

bzoj1123 我想了半天才搞懂样例是什么意思...

bzoj3998 sam板子题。我非常naive地认为当前编号最大的节点就是sam上一次的更新节点，于是调了一下午。

bzoj4373 一开始想了个靠谱做法被shanquan2叉掉了，然而shanquan2表示似乎特判一下就可以了？不过我今天突然想到似乎可以直接hash搞，写了一发居然过了...

---

每一场bestcoder都(不)要打...

round54div1

1001:暴力分解质因数。

1002:fst好题。

1003:显然答案就是与[tex]n+1[/tex]互质的数量。

貌似又喜闻乐见地遇到了数据出错的情况。现在的出题人真是...

round56div1

1001:sb题。

1002:无脑二维树状数组+博弈。

1003无脑码农1004lct不想说啥...

round57div1

1001:行列分别判一下。

1002:期望线性性随便搞...我太sb，40min才A...

感觉现在智商越来越低了，1003,1004明明都是sb题...竟然想了半天没想法...

round58div1

1001:sb题，我竟然一眼看上去不会捉...

1002:sb题。

1003:sb题。

1004也是sb题，可是题意写得我也是醉了...

round60

我tm再也不做bc了

我tm再也不做bc了

我tm再也不做bc了

于是我就永远是紫名狗了...

---

清华集训2015

既然UOJ上在同步更新题目那我也来做做...估计要被虐翻了

12.12 update:卧槽剩下的题能玩？

UOJ155 神题...见我另一篇博客。

UOJ156 据说正解是特征方程相关...然而暴力直到相邻两项之差小于eps可以A...

UOJ161 挺水的期望题，然而不加输入优化过不了是什么意思？！

UOJ164 花式线段树...反正我不会做...似乎存4个tag搞一搞就行了？非常厉害的样子我要好好感受一下...

UOJ165 挺传统的交互题。暴力维护抛物线下轮廓，每次找到最高的一个点询问，如果发现了一个新的抛物线就把轮廓更新一遍，否则就是最后答案。

---

USACO月赛又开始了...虽然感觉也没啥意思，不过感受一下水题和即时评测也挺爽的？

然而今年又冒出来了个platinum组不知道要搞啥...

DEC:

2.5h把gold组ak了(写错一个细节调了1.5h+)，然后发现可以接着打platinum？

晚上花了1.5h把platinum也ak了...感觉USACO这么水下去吃枣药丸啊...

 

[取消回复评论]

昵称 登录 E-mail: *
Web:
Twitter:

当有新评论通过 E-mail 通知我

(输入验证码)

or Ctrl+Enter