2016/4/1

ProbHint
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

ProbHint
1079 中国剩余定理51nod 互质
2891 StrangeWayToExressIntegerspoj crt 不互质
1061 青蛙的约会poj exgcd
1407 Savageexgcd 枚举
2115 C-Looppoj exgcd
2480 Mod一般离散对数
3239 DiscreteLoggingp质数的离散对数
1135 原根
1038-高次剩余
2818-Gcdphi基本
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

ProbHint
3998 弦论字典序第k大
3277 串
3673 回文串sam 不懂
3068 回文hdu mancher模板
3790 神奇项链manacher 线段覆盖 有点意思
2565 最长双回文串nlgn求以i为端点的最长回文串,平衡树
2342 双倍回文manacher 枚举+分析 平衡树
REPATSsam启发式合并
2084 Antisymmetrymanacher反对称。满足rev(rev(x))=x即可manacher
2160 啦啦队教练manacher
ChessQueueuva 数学
cheerleaderuva 容斥
2393 Cirno的完美算数教室容斥
1853 幸运数字容斥 剪枝(倍数,从大到小)
1042 硬币购物全集容斥掉非法方案
4710 分特产on容斥
3589 动态树树剖 容斥
1695 gcdhdu 容斥
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 再见Xorxor最大次大
2844 albus就是要第一个出场线性基找位置
34 多项式乘法uoj fft
3527 力fft算卷积
2179 FFT快速傅立叶fft
2194 快速傅立叶之二卷积
3160 万径人踪灭fft算非连续回文子序列。答案=总回文子序列-连续回文子序列

40 in tot


2017/3/13

ProbHint
35 后缀排序后缀数组板子
1743 musical themepoj 不重叠重复出现最长子串
3261 Milk Patternspoj k重复出现最长子串
Distinct StringSUBST1 不同子串数
1297 Palindromeural 最长回文串
2774 LongLongMessagepoj 2串的最长公共子串
3415 Common Stringspoj 不短于k的公共子串个数。难点不是sa而是用单调栈求和
3294 LifeFormspoj 出现在k个字符串的最长公共子串
PHRASES Relevant Phrasesspoj每个字符串中出现至少两次且不重叠。二分,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 Cheatdp题。用sam维护匹配位置

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


2017/3/6

ProbHint
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 VideoGamedp
3172 Tjoi2013 单词我对这题的感觉就是黑人问号
637 排序测试双关键字桶排

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


2017/2/27

ProbHint
某比赛c题lct维护一元一次方程组
736 星际转移分层图 最大流判定是否有可行方案
461 餐巾最大流 建图。。。
723 试题库最大流
731 alisdp转移上求割
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

ProbHint
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 货币兑换cashcdq分治做斜率优化
USACO 修剪草坪单调队列
SCOI 股票交易单调队列

15 in tot
其实很颓废!!


2017/2/13

ProbHint
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

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