有人说我不写博客=、= 于是我就把我整理的东西扔上来了

9-22
poj 2891 中国剩余定理 模板题 不是指数的话合并两个成x%lcm(c1,c2)=x0的样子，x0用exgcd解一下

poj 1405 找规律 贪心+高精度
poj 2606 简单题
poj 2227 优先队列bfs 把周围一圈入队 每次取最低的 判断四周能否装水就行了
poj 2459 简单题
poj 1837 背包DP 注意一个钩子上可以装多个勾码 所以要以勾码为状态的一维来做
poj 2142 比较麻烦的exgcd 因为砝码还能反着放 所以要求x,y两次 有负的就1430取反
bzoj 3942 && bzoj 3940
主要意思都是一个主串 一个 or 多个模式串 如果匹配上了 那么就在主串删除这个模式串
求最后剩下啥
我们搞一个栈 当匹配上了就入栈 如果把某个模式串匹配完了就弹栈这个模式串的长度
为了保证弹完之后还能继续做 需要记录p[i] 代表栈内i位置在主串的位置
每次获取弹完了匹配到哪就用j=p[top]即可
bzoj 1756 带修改子串最大值 线段树维护lmx rmx mx sum 然后各种乱搞

9-23
poj 2594 最小路径覆盖 可以重复走 floyd一遍就行了
poj 2115 求解Cx+A=B mod p的最小x exgcd或逆元
poj 1485 预处理比DP长 f[i][j]=min(f[k][j-1]+w[k+1][i])
poj 1430 求斯特林数第[N,M]项的奇偶性：
首先s(n,m)%2=m*s(n-1,m)+s(n-1,m-1) 若m为偶数 则答案为s(n-1,m-1)%2
然后通过一些图形变换，可得m为奇数时s(n,m)%2等价于c(n-(m+1)/2,(m-1)/2)的奇偶性
这个可以用阶乘分解质因数求 或者神公式：若n&m=m 则为奇数 否则偶数！！！！

poj 2492 扩展域并查集？为什么写扩展域不对 必须要写带权的那种？
带权的就是记录和fa的关系 0是同性 1是异性 find时r[x]=(r[x]+r[t]+1)%2 t为合并前的fa
merge时r[x]=(r[b]-r[a])%2 x为合并后的祖先 b,a是合并前的
poj 2075 简单题
poj 2137 枚举第一个+dp 发现最后答案和第一个的位置会有关系(一个环) 所以枚举第一个
然后f[i][j]=min(f[i-1][k]+dist[k][j])
bzoj 3245 可以称为分层图SPFA dist[i][j]表示到i点速度为j的最快时间 然后看着转移就行了

9-24

被我弄没了。。

9-25
poj 1737 f[i]为答案 f[i]=全集-不合法 不合法=c[i-1][j-1]*power(2,c[i-j][2])*f[j]
poj 3051 简单题
poj 3040 简单题
poj 1046 简单题
poj 1220 高精进制转换
7进制下的35，转换成2进制，就用3除以2，商是1，余数是1
将1*7再加上第二位的5当成第二个数
poj 1503 简单题
poj 1985 树的直径 虽然带权 但是那样做还是对的
poj 2505 神奇的博弈论
考虑[2,9]肯定stan赢 [10,18]肯定ollie赢 [18+1,18*18]stan赢
我们发现这样一个规律：都是[2*9+1,2*9*2*9]这样的区间
于是我们把n一直除 直到在[2,18]的区间内 再判断
poj 1509 后缀自动机 在后缀自动机上匹配 如果没法匹配上就记下位置break 最后答案就是那个位置
bzoj 3046 对于每一个块拆成3个点 做一下联通块 最后统计答案时%2+1什么的搞一下坐标

9-26
poj 2774 最长公共子串 构建一个串的sam 然后用另一个串去匹配 匹配不上就返回f位置 最后取max
poj 3270 经典问题 考虑两种情况 一种自己换 一种用最小的数作为中介去和其他的换
poj 3268 简单题
poj 3256 简单题
poj 1529 用map搞一下然后floyd出答案
poj 2455 二分答案 然后最大流judge
poj 2985 treap维护size的第k大 tzg有神奇的树状数组二分做法
bc 57 T1 三种情况 全是( 全是) 枚举断点 左边) 右边是(
bc 57 T2 做一个前缀和搞一搞就行了