SanSiroWaltz's Blog

开新坑啦！

UPD:

2015.7.1 终于完结了，效率低的不忍直视啊，明天去补dzy loves maths的坑

50

【bzoj 4003】如果用倍增显然会超long long，所以直接模拟。注意到假如两支军队汇入一起后战斗力的相对大小是不会发生改变的，所以维护一个可并堆就行了。

【bzoj 4004】补了一下拟阵。。。

【bzoj 3992】sb题

【bzoj 4027】贪心是比较显然的。。。从下往上依次选小的合并

【bzoj 4029】分情况讨论一下就好了

【bzoj 4033】满nice的一个树形dp，经过某条边时，可以直接通过子树内部黑点个数算出这条边经过多少次

【bzoj 4031】裸的生成树计数

【bzoj 4034】sb题

【bzoj 4006】斯坦纳树裸题。。。

【bzoj 4032】其实是四道题：1.对A的每个后缀在B中做一遍kmp。 2.枚举每个后缀，在B中直接扫。 3.求出A每个位置关于每个字符的后继和B的SAM，然后bfs。 4.和3差不多。

【bzoj 3926】trie树建后缀自动机

【bzoj 4036】vfk的论文题

【uoj 111】一道A(N)P(O)I(I)O(P)题，当时没做出来真可以回去搞普及组了

【uoj 112】感觉自己的做法好麻烦。。。

【uoj 114】比赛时做不出来的sb题

【uoj 62】数论真是太厉害了。。。

【uoj 54】继续补数论，最近没啥刷bzoj的欲望啊

【bzoj 4011】并不难，但考场上也并不容易想到？。。。

【bzoj 4128】bsgs，被zxy完虐了。。。

【bzoj 4080】做法非常nice，顺便练一下二分图最大独立集的构造

【bzoj 3626】树链剖分

【bzoj 3601】比较简单的数论。。。

【bzoj 2137】还是比较简单的数论。。。

【bzoj 2151】做法还是满神的。。。或者说可以当做常用算法？。。。

【bzoj 2169】范爷的数学题，超级厉害呀。。。

【bzoj 3559】神结论题，证明似乎并不难，但想到并不容易？。。。

【bzoj 4082】先写倍增然后mle了，然后写了个路径压缩效果还不错。。。

【bzoj 2127】sb题

【bzoj 4062】枚举颜色然后求y最小分成两边继续做

【bzoj 4012】同bzoj3626，在网上搜题解全是动态点分治。。。

【bzoj 4149】枚举最小数，求出范围和最大数后乱搞。。。

【bzoj 4152】分别向两个维度的前驱和后继跑最短路

【bzoj 3560】挺简单的一道数论题

【bzoj 4059】考虑相邻的三个相同的数[tex]a_{i},a_{j},a_{k}[/tex]。

当[tex]r\in [j,k-1][/tex]时，[tex]l\in [i+1,j][/tex]。于是可以构造一个[tex][j,k-1]\times [i+1,j][/tex]的矩形，要求对于每一个[tex]x[/tex]，[tex](x,1)-(x,x)[/tex]被完全覆盖。这个是经典问题，可以简单地用线段树维护。

【bzoj 4064】区域数是可以轻松算出的。对每一个士兵，处理出在每条河的左边还是右边的01串的hash值，然后算出不同的区域数。

【bzoj 4108】阅读理解题。

【bzoj 4153】启发式合并，可以用map搞。。

【bzoj 3561】不多说啥了。。。

【bzoj 4009】整体二分。其实是一道不错的代码题？

【bzoj 1559】sb题

【bzoj 1558】sb题

【bzoj 4007】dp[i][j][k]表示i号点到根的路径上取值为j，该子树中最多有k个去打仗的最优值

【bzoj 1038】第一次写半平面交。。。

【bzoj 2309】将trie树压缩后暴力，各种细节要讨论

【bzoj 1505】[tex]O(N^5)[/tex]dp显然，随便单调性优化一下就行了，似乎有[tex]O(N^3)[/tex]的算法？

【bzoj 2878】码农题，其实也不难写吧。。。

【bzoj 2732】半平面交，注意边界情况的讨论

【bzoj 3739】这里就不多说了，跑到rank1好开心（虽然也没几个人过）