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上空间卡的太紧…… |