2016/4/1

Prob Hint
2599-IOI2011-Race 点分治
spoj-FTOUR2 点分
3697-采药人的路径 点分
聪明可可 树形dp
4016-FJOI2014最短路径树问题 点分
3365-Usaco2004-DistanceStatistics路程统计 点分
3626-LNOI2014-LCA 离线+树剖+线段树
1095-ZJOI2007-Hide捉迷藏 动态点分 堆
2286-Sdoi2011消耗战 虚树dp
3611-Heoi2014大工程 虚树dp
3991-SDOI2015寻宝游戏 维护树结构

2017/3/27

Prob Hint
1079 中国剩余定理 51nod 互质
2891 StrangeWayToExressIntegers poj crt 不互质
1061 青蛙的约会 poj exgcd
1407 Savage exgcd 枚举
2115 C-Loop poj exgcd
2480 Mod 一般离散对数
3239 DiscreteLogging p质数的离散对数
1135 原根
1038-高次剩余
2818-Gcd phi基本
2242-SDOI2011计算器 数论三合一
2190-SDOI2008仪仗队 phi
2705-SDOI2012Longge的问题
1927-Sdoi2010星际竞速 上下界。最小费用可行流
hdu5628-ClarkAndMath 狄利克雷卷积
1607-Usaco2008-PattingHeads轻拍牛头 筛法
2186-Sdoi2008沙拉公主的困惑 逆元
3813-奇数国 分解+数据结构
2721-Violet5樱花 ……（推导）

19 in tot
。

2017/3/20

Prob Hint
3998 弦论 字典序第k大
3277 串 神
3673 回文串 sam 不懂
3068 回文 hdu mancher模板
3790 神奇项链 manacher 线段覆盖 有点意思
2565 最长双回文串 nlgn求以i为端点的最长回文串，平衡树
2342 双倍回文 manacher 枚举+分析 平衡树
REPATS sam启发式合并
2084 Antisymmetry manacher反对称。满足rev(rev(x))=x即可manacher
2160 啦啦队教练 manacher
ChessQueue uva 数学
cheerleader uva 容斥
2393 Cirno的完美算数教室 容斥
1853 幸运数字 容斥 剪枝（倍数，从大到小）
1042 硬币购物 全集容斥掉非法方案
4710 分特产 on容斥
3589 动态树 树剖 容斥
1695 gcd hdu 容斥
1770 lights燈 xor方程组
1923 外星千足虫 xor方程组
1013 球形空间产生器sphere 高斯消元
1778 Dotp驱逐猪猡 概率高斯消元
3143 游走 边概率转点概率
1720 二分图游戏 匈牙利，最大匹配必须覆盖点
3270 博物馆 双点状态概率
4031 小Z的房间 矩阵树
1016 最小生成树计数 搜索+性质
1002 轮状病毒 找规律
3168 钙铁锌硒维生素 线性相关 推性质 高斯消元 匈牙利
2460 元素 线性基
4568 幸运数字 树剖 线性基
3949 xor 第k大xor
4184 shallot 按时间分治 线性基
4269 再见Xor xor最大次大
2844 albus就是要第一个出场 线性基找位置
34 多项式乘法 uoj fft
3527 力 fft算卷积
2179 FFT快速傅立叶 fft
2194 快速傅立叶之二 卷积
3160 万径人踪灭 fft算非连续回文子序列。答案=总回文子序列-连续回文子序列

40 in tot

2017/3/13

Prob Hint
35 后缀排序 后缀数组板子
1743 musical theme poj 不重叠重复出现最长子串
3261 Milk Patterns poj k重复出现最长子串
Distinct String SUBST1 不同子串数
1297 Palindrome ural 最长回文串
2774 LongLongMessage poj 2串的最长公共子串
3415 Common Strings poj 不短于k的公共子串个数。难点不是sa而是用单调栈求和
3294 LifeForms poj 出现在k个字符串的最长公共子串
PHRASES Relevant Phrases spoj每个字符串中出现至少两次且不重叠。二分，sa，维护h块内最大最小
1031-JSOI2007-字符加密Cipher 复制粘贴一次再遍历sa，忽略不合法的后缀即可
1692 队列变换 贪心策略。sa用来比较前缀后缀字典序
3238 差异 数学+sa+单调栈
2251 2010BeijingWc 外星联络 出现至少两次的子串个数。sub[i] = sub[i - 1] + n - sa[i] + 1 - h[i]可得长度从h[i]+1开始
3230 相似子串 sa，用上式算出子串数，二分定位子串位置，计算长度。然后再算最长公共前缀和后缀
1396 识别子串 sa+线段树
SUBLEX 字典序第k大子串 sam（也可以sa
LCS 用一个串建sam，用第二个串跑
LCS2 上题的直接扩展
2882 工艺 最小循环表示。sam/sa都很简单
4516 生成魔咒 输出每个前缀的不同子串。sam本来就支持在线算
4199 品酒大会 还是按lcp统计
3172 单词 先拼出论文建sam，再把每个单词放进去，输出right集合大小即为出现次数
2555 SubString 意思是强制在线维护right。每次np实际上是从np到根right+1的修改操作，可以lct（避免了ett）
3926 诸神眷恋的幻想乡 广义sam
4566 找相同子串 广义sam
2946 公共串 嗯，还是个多串lcs问题。不过这次用广义sam写了。
2806 Cheat dp题。用sam维护匹配位置

27 in tot
我也很绝望啊
加油吧

2017/3/6

Prob Hint
739 运输问题 费用流
746 骑士共存 二分图最大独立集
734 最长k可重区间集 “分叉”的路径
1517 放国王 状压 影响范围不能作为状态
28 最大获利 最小割
3894 文理分科 最小割，不能拆点
3158 千钧一发 一看是个最大独立点集。一般图是没法做的。想办法转成二分图。也没什么奇怪的性质，只好分奇偶。试试两个条件发现可以。
3144 切糕 强烈建议独立思考后再看题解。灵魂画师题解十分形象
1412 狼羊故事 最小割
1934 善意投票vote 最小割
2132 圈地计划 同一集合有代价。黑白染色之后反过来连st。其他和不同集合有代价一样
1532 Kos-Dicing 二分用最大流验证
1391 order 可租用的太空飞行计划
2561 最小生成树 奥妙重重……乍看毫无头绪，然而只需考虑两个树的生成过程即可轻松出解
1589 路障 我重新想了下，这个题的复杂度真的没有保证。O(两点间最短路边数)
1590 奶牛的十项全能 还是那个状压剪枝套路。可以快20倍，虽然我没写。
12 运输问题2 有源汇上下界最大流
2502 清理雪道 有源汇上下界最小流。注意问题本身的附加汇和附加源，与为了求上下界的附加汇和附加源是不一样的。
3698 XWW的难题 有源汇最大流。没做过这种源汇限制行列和的题，会很难和网络流联系起来吧……
1305 CQOI2009 dance跳舞 二分答案然后最大流做一个近似匹配的东西。
3876 支线剧情 有源汇上下界最小费用可行流
2055 80人环游世界 同上
3670 动物园 KMP
1452 Count 二维平面内某颜色点数
1009 GT考试 kmp+矩阵乘法优化dp
3939 牛跳房子 cdq分治优化dp
1355 Radio Transmission 直接上kmp border
3620 像是梦中见过的样子 还是统计某个范围的border是否存在。n2过15000……
4698 sandy的卡片 最大公共子串：枚举第一个串子串开头，KMP，第一个必定匹配
3942 Censoring 把匹配位置和字符一起入栈
1913 AC自动机 复习一下裸题
1030 文本生成器 dp
2938 病毒 拓扑排序
2434 阿狸的打字机 fail树
2754 喵星球上的点名 出题人——消音——
2580 VideoGame dp
3172 Tjoi2013 单词 我对这题的感觉就是黑人问号
637 排序测试 双关键字桶排

38 in tot
还像话。前几星期干嘛去了？

2017/2/27

Prob Hint
某比赛c题 lct维护一元一次方程组
736 星际转移 分层图 最大流判定是否有可行方案
461 餐巾 最大流 建图。。。
723 试题库 最大流
731 alis dp转移上求割
729 圆桌聚餐 最大流
727 太空飞行计划 最小化得不到的，最小割
b1711 Dining 最大流
奶牛的交通 最小点割
1573 最优标号 最小割。划分集合。同集合代价
1555 放置机器人 x,y坐标建二分图匹配
1588 贪婪之岛 扔掉一些不够优的决策再最大流
POI1999 洞穴探险 最大流
NOI2001 炮兵阵地 二维状态，先搜再状压
HNOI2012 集合选数 先分析，三角形棋盘状压
1520 1xr 覆盖 r进制状压，复杂的dfs转移
1519 1x2+L形覆盖 dfs转移状压dp
1518 1x2骨牌覆盖 轮廓线/dfs转移状压dp
657 放棋子 先搜合法状态的状压dp
654 特殊方格棋盘 状压dp入门
USACO 奶牛接力 经过k点的最短路，分析dp来推出矩阵
SCOI2009 迷路 带权路径数，拆点即可
2326 HNOI2011 数学作业 数位分段+矩阵乘法dp

23 in tot

2017/2/20

Prob Hint
3091 城市旅行 本来早上起来想写道裸题休闲一下，结果随机抽中了一道数学期望…不会数学期望就去搜题解，题解2吧
3282-Tree 休闲
2631-Tree 卡常！！
1798-AHOI2009-Seq维护数列 水线段树
2157-旅游 明明是树剖题。不过可以用lct做，试下把边转换成点的技巧。我没仔细看题以为有link-cut操作才写的树剖
水管局长 瓶颈居然是找边……排序lowerbound, 注意uv定序
1180-CROATIAN2009-OTOCI 淼淼淼，安慰自己今天不是特别颓废，至少膜 chad 学了不存rt的写法对吧？。。。顺便把自己的lct压到最短
1010 HNOI2008 玩具装箱toy
4518 SDOI2016 征途 最简单的
1911 Apio2010 特别行动队 可见对二次函数型的代价都适用
1096 ZJOI2007 仓库建设 中等
1597 Usaco2008Mar 土地购买 不会的话就查题解吧……难点不在斜率优化的变形上
3156 防御准备 随便写写
HZOI2016 采花在线版 主席树把离线算法在线化
4300 绝世好题 位dp
1492 NOI2007 货币兑换cash cdq分治做斜率优化
USACO 修剪草坪 单调队列
SCOI 股票交易 单调队列

15 in tot
其实很颓废！！

2017/2/13

Prob Hint
2588-Count on a tree 主席树裸题？a + b - lca(a, b) - fa[lca(a, b)]
2741-【FOTILE模拟赛】L 可持久化Trie+分块，各种woc……
3932-CQOI2015-任务查询系统 悄悄问蒟蒻，logN是哪个N
3673-可持久化并查集 用主席树维护下fa
3524-Poi2014-Couriers 严格大于(r - l + 1)/2 妙啊。
Hackerrank-101hack-Maximizing Mission Points 分治dp。先算前面再算前面对后面的贡献。再算后面
2648-SJY摆棋子 kdtree 不需要重建
4066-简单题 kdtree 区域查询
3053-The-Closet-M-Points 真k dtree，不带修改
1541-URAL1569-Iset塔上的网络 COGS，无权图最小直径生成树
4520-Cqoi2016-K远点对 欧氏最远估价
2049 SDOI2008 Cave洞穴勘探 摸鱼

12 in tot

2017/2/11

Prob Hint
lydsy
2724: [Violet 6]蒲公英 cnt显然不能合并，存块块间答案，答案只能来自块块答案或半块
3110: [Zjoi2013]K大数查询 本来是石蒙跟我说的一题，让我练练树套树。然而我发现空间并过不了。于是写了整体二分。顺便学习了一发区间修改区间查询的树状数组
COGS
257. 动态排名系统 Zju的一道题。我写的线段树套平衡树。暴力建平衡树的复杂度是对的比较奥妙。然而bzoj上空间卡的太紧……