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