计数菌:
50
代码菌：http://kzoacn.is-programmer.com/code
[3.14]完结撒花！
【BZOJ2565】manacher
【BZOJ2729】ans=n!*(A(n+1,2)*A(n+3,m)+2*(n+1)*A(n+2,m-1)*m)我的高精度已经废了
【BZOJ2730】暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力
【BZOJ1415】
bfs预处理\( next[i][j] \)表示聪聪在i可可在j,聪聪的下一个位置
\( f[i][j] \)表示聪聪在i可可在j,聪聪吃到可可的期望次数
\( G[i] \)表示i的边,\( deg[i] \)表示i的度数
\[ f[i][j]=\frac{\sum_{v \in G[j]} f[next[next[i][j]][j]][v]+f[next[next[i][j]][j]][j]}{deg[j]+1}+1 \]
边界:\( f[i][i]=0 \) 若\( next[next[i][j]]=j \)或\( next[i][j]=j \)则\( f[i][j]=1 \)
【BZOJ2435】说好的卡爆栈呢
【BZOJ3239】BSGS裸题
【BZOJ1568】同上
【BZOJ3208】暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力
【BZOJ3043】差分，操作等价于+-1，正的减负的加，没了
【BZOJ1018】分类讨论到吐
【BZOJ3786】(伪)toptree
【BZOJ2223】整体二分
【BZOJ2048】\( \sum_{i=1}^n \frac1{2i}=\frac{ln(n+1)+r}2 \)
【BZOJ3544】前缀和，从左往右扫一遍，在set中边插入边查询
【BZOJ3550】单纯形直接上
【BZOJ2007】裸对偶图最短路
【BZOJ2306】\( f[u][v][d] \)表示从u到v经过\(2^d\)个边的最大值,则\( f[u][v][d]=max(f[u][x][d-1]+p^{2^{d-1}}f[x][v][d-1]) \) ，然后挂精度，然后……就那啥了
【BZOJ1369】对于数据来说三种颜色就可以了……
【BZOJ3036】\(f[i]\)表示从i走到n的期望,[tex]f[u]=\frac{\sum_{(u,v)\in E}f[v]+w}{out[u]}[/tex]
【BZOJ3884】欧拉定理[tex] a^x \% p =a^{x \% \varphi(p) }\% p[/tex] 以及[tex]cx \% cy =c(x \% y)[/tex]然后就可以做此题了
方便起见我们令x等于那一坨2的幂,k为p的2的因子的数量,对于奇数来说直接递归计算,偶数的话\[ans=2^k(2^{x-k}\% \frac{p}{2^k})=2^k(2^{x+k(\varphi(\frac{p}{2^k})-1)}\% \varphi(\frac{p}{2^k}))\]
由于\(x=\varphi(x)\)的递归次数远小于\(log(x)\),就可以过喽,加上记忆化复杂度更好,只不过会MLE……P.S. 算phi的话直接暴力44ms,线性筛1~2s……
【BZOJ2460】按价值降序贪心,线形基判断是否加入就可以了,证明见花神的拟阵 P.S. 终于挤进第二页了……这么弱现在才到第二页,你看看人家xxx和yyy还有人家zzz，比你高到不知道哪里去了
【BZOJ2464】水题
【BZOJ2795】答案一定是长度的约数，直接\(O(\sqrt n)\)枚举约数+hash不行，如果一个循环节可行那么他的倍数也可行，于是预处理出每个数的最小质因子，每次尝试缩小规模，每次询问做到\(O(log(n))\)
【BZOJ3894】好像在哪里见过的最小割裸题……
【BZOJ3083】链剖+dfs序+分类讨论
【BZOJ1978】dp[i]表示以i为因数的答案，枚举因数dp
【BZOJ1409】指数就是fib,矩乘+欧拉定理秒
【BZOJ3173】前缀max+维护序列，fhqTreap秒之
【BZOJ3282】LCT裸题
【BZOJ2141】分块轻松愉♂悦
【BZOJ3306】3083弱化版，本来还以为会有菊花图呢……
【BZOJ1087】水状压
【BZOJ2662】分层图……
【BZOJ3774】题解
【BZOJ3034】质数从小到大选，高(Py)精(th)度(on)(python会T……
【BZOJ1149】若有解答案显然为所有节点的 \( \sum \)[左子树size<右子树size] ,无解情况是maxdep-mindep>1或一棵树的左右子树均不完全,dfs即可
【BZOJ2588】LCA+主席树
【BZOJ3123】上题的启发式合并加强版，没写垃圾回收过了，有空写一写垃圾回收版本
【BZOJ2836】链剖+dfs序+sgt裸题
【BZOJ2843】LCT裸题，也可以离线链剖
【BZOJ2947】multiset
【BZOJ1924】建图缩点最长路
【BZOJ2462&&BZOJ2351】二维hash
【BZOJ3288】phi的前缀积
2015年2月16日 17:41
一下午又刷了两个题太神了OTZ
2015年2月24日 20:26
2223不用整体二分吧= = 出现次数大于len/2的数一定是中位数，因此只要取区间中位数验证一下就行了 用可持久化线段树就能搞
2015年2月25日 11:58
@PoPoQQQ: 能整体二分的我都不写主席树……个人感觉整体二分更好写一点……而且没有内存的问题
2015年2月27日 10:47
@kzoacn: 确实- - 之前就有整体二分的题卡主席树的内存这种事情- - 不过还是觉得主席树更无脑一些- -