水题大乱斗(二)
吐血整理水题*466
玩的开心:)
| Codeforces432D | Prefixes and Suffixes | SAM |
| 二分前后缀长度，中间一段在SAM上right集合乱搞下 | ||
| Codeforces449D | Jzzhu and Numbers | dp |
| 非常好的一道容斥题。 考虑求出f[x]为满足a[i]&x=x的a[i]个数，那么在这个集合内任取非空子集，&的和上1的个数不会小于x上的1的个数 那么答案=Σ(-1)^count(x)*(2^f[x]-1) |
||
| Codeforces559D | Randomizer | 几何 |
| 首先皮克定理了解一下 面积S，内部格点数目i，边上格点数目b S=i+b/2-1 那么考虑分两部分求答案 先求S的期望，因为取i个点构成的多边形可以有原来的多边形去掉一些顶点连续的多边形得到。那么考虑去掉的多边形的点数j，它会在2^(n-j)-1个多边形内被去掉。同理考虑一条边，共可生成2^(n-2-j)-1+2^j-1个多边形。 注意这里的j在很小时对答案贡献不大，可以只算到100这样。然后n-2-j可能很大，那么在分数上先同除2^n即可。 |
||
| Codeforces666E | Forensic Examination | SAM |
| 首先得会在parent树上倍增定位字符串。问题转化为：求一个点的子树中出现次数最多的颜色是什么。然后线段树合并即可。 | ||
| Codeforces755G | PolandBall and Many Other Balls | NTT |
| 考虑dp倍增的方式 f[x][k]=f[x-1][k]+f[x-1][k-1]+f[x-2][k-1] f[2x][k] = (f[x] * f[x])[k] + (f[x-1] * f[x-1])[k-1] f[2x-1][k] = 2(f[x] * f[x-1])[k] – (f[x-1] * f[x-1])[k-1] 推导见http://shallwe2000.cc/cf/ 然后就可以ntt优化卷积了 |
||
| Codeforces814D | An overnight dance in discotheque | 贪心 |
| 贪心 先计算出一个圆被多少圆包含 首先没有包含的直接加到答案里，剩下的被包含奇数次的加进答案，偶数次的减去，因为其实放在那里对答案产生的贡献时一样的。 |
||
| Codeforces896E | Welcome home, Chtholly | 模拟 |
| 卡个常暴力n^2过十万是什么操作？把读入的最后一个数换成float就过了是什么操作？ | ||
| Codeforces908G | New Year and Original Order | dp |
| 对于形如3459这种不下降数，一般可以化为a[4]*1111+a[3]*111+a[2]*11+a[1]*1的形式去处理。
其中a[i]的意义为相邻两位的差，又可以表示为所有数位中大等于数字k恰好有i个的k的个数。 |
||
| Codeforces917E | Upside Down | SAM+AC自动机 |
| 毒瘤 | ||
| Codeforces936C | Lock Puzzle | 构造 |
| 构造题，我们考虑用3步把一个字母扔到最后一位 令这个字母在现在的串中的位置x，那么shift(n-k) shift(1) shift(n)三步即可把它丢到最后 且原已经排好的后缀的相对位置不变 官方题解给出了5/2n的做法 |
||
| LOJ2059 | 「TJOI / HEOI2016」字符串 | SAM+线段树 |
| bzoj上被卡常了，就只好放到这里了。 比较暴力的题，先二分答案，那么题目转化判断为S的一个字串S1在S[a..b]中有没有出现过，那么用线段树维护出每个节点的set，把S1用倍增法在parent树上的位置找出来，在线段树中判断一下即可。基本套路hhh |
||
| LOJ2538 | 「PKUWC 2018」Slay the Spire | dp |
| 刚看到的时候是懵逼的，我们先考虑m=k的情况，发现好像可以dp，求出两种牌分别取i张时所有方案的贡献和，卷积起来就可以得到答案。 考虑原题数据范围，可以发现当有强化牌可以用的时候，就全用完，只留一张攻击牌即可。求两个dp数组f[i][j]表示考虑前i张攻击牌选j张的情况，所有乘积的和，g[i][j]表示考虑前i张强化牌选j张的情况，所有方案的和的和。那么分成两种情况讨论，枚举强化牌的张数i： 当i<=k-1时，枚举最小的攻击牌是谁，因为要丢掉m-k张，所以要乘上在更小的牌里选m-k张的方案数。 当i>k-1时，两侧都要枚举最小的牌，乘上弃牌的方案 最后所有方案的攻击和即为答案 |
||
| LOJ2586 | 「APIO2018」选圆圈 | kdtree |
| 嗯，kdtree乱搞。首先预处理将整个坐标系旋转30度，这样出题人就卡不了我们啦。 然后在kdtree上存每个圆心，查询时要判断现在选中的圆与覆盖了子树中的圆的矩形有没有交，很暴力。 |
||
| LOJ6276 | 果树 | 点分治 |
| 大力点分 确定重心G之后，假设我们走到了子树中的i位置，那么i到G这条路径上所有颜色的同色点的子树内的点全标为没有贡献，然后统计有多少点有贡献即可。线段树比较难实现，可以考虑转化为补集。 |
||
| LOJ6353 | 「CodePlus 2018 4 月赛」组合数问题 2 | 堆 |
| 用类似超级钢琴的方法，把所有C(i,n)放进堆里，然后每次取出最大的C(x,y)再把C(x,y-1)丢到堆里就好了。 至于组合数太大的问题，可以都取lg。 |
||
| UOJ348 | 【WC2018】州区划分 | FWT |
| 首先写出状压dp的转移方程，可以发现是个子集卷积的形式，直接做就行了，其实挺裸的。 不会子集卷积请看2015国家集训队《集合幂级数的性质与应用及其快速算法》 至于判断欧拉回路 1.集合内的点与奇数个点有连边 2.从一点出发能走完整个点集 |
||
| UOJ370 | 【UR #17】滑稽树上滑稽果 | dp |
| 首先答案一定是一条链。 先把每个数都一样的那些位拿出来，剩下的位我们等于是希望尽快把他们变成00。 这可以用一个dp来实现，f[S]表示S集合内的位为1的时候，想要变成0还需要多少代价。 dp转移就是枚举一个子集T，强制把这个子集T变成0，f[S]=min(f[S],f[S^T]+(S^T)) |
||
| 1000 | A+B Problem | 模拟 |
| 世纪难题 | ||
| 1001 | [BeiJing2006]狼抓兔子 | 最短路 |
| 平面图最小割，推荐论文https://wenku.baidu.com/view/a10e0529bd64783e09122ba9.html?re=view | ||
| 1002 | [FJOI2007]轮状病毒 | 基尔霍夫矩阵 |
| 果断是抄的，还偷懒写了python，生成树的计数，论文https://wenku.baidu.com/view/782ab9eb19e8b8f67c1cb9a9.html | ||
| 1003 | [ZJOI2006]物流运输 | 最短路，DP |
| 预处理第i天到第j天每天都能走的最短路，dp推一发，注意初始值 | ||
| 1004 | [HNOI2008]Cards | Burnside定理 |
| 根据Burnside定理，要求的是 每种置换的不动点的个数的平均数 。把每种置换分解成循环，用dp求解。 |
||
| 1005 | [HNOI2008]明明的烦恼 | prufer编码 |
| 简略的说就是一个n个节点的树的prufer序列长度为n-2，序列中每个数∈[1,n]，一个点在prufer序列中出现次数+1就是它的度数，组合数学算一下就行了。 | ||
| 1006 | [HNOI2008]神奇的国度 | 弦图 |
| 题目即是求一个弦图的最小染色数。先求弦图的完美消除序列，最大势算法，注意求得的序列是倒序的。然后按照完美消除序列倒序贪心染色即可。为什么？我也不知道。 | ||
| 1007 | [HNOI2008]水平可见直线 | 单调栈 |
| 按斜率排序，单调栈维护凸包模板题。 | ||
| 1008 | [HNOI2008]越狱 | 组合数学 |
| 拿总的减去不合法的，即不会越狱的情况，那么第一个有m种可以选，后面每个都有m-1种可以选 | ||
| 1009 | [HNOI2008]GT考试 | AC自动机 |
| AC自动机上dp，用矩阵优化，也是比较裸。 | ||
| 1010 | [HNOI2008]玩具装箱toy | 斜率优化，DP |
| 斜率优化嘛，不会的话为什么不问问隔壁hk呢 | ||
| 1011 | [HNOI2008]遥远的行星 | 模拟 |
| 误差分析???实在不行模拟调调参。 | ||
| 1012 | [JSOI2008]最大数maxnumber | 单调栈 |
| 如果对于i<j有a[i]<a[j]那么a[i]死都用不上。栈里要存位置，查询的时候二分下 | ||
| 1013 | [JSOI2008]球形空间产生器sphere | 高斯消元 |
| 高斯消元模板题 | ||
| 1014 | [JSOI2008]火星人prefix | 平衡树 |
| 用平衡树维护区间内的Hash值，就可以支持修改，插入操作了。 | ||
| 1015 | [JSOI2008]星球大战starwar | 并查集 |
| 考虑倒序操作，用并查集维护即可。 | ||
| 1016 | [JSOI2008]最小生成树计数 | 最小生成树 |
| 1.最小生成树每种边权的边数量一定。2.当一个图有多个最小生成树时，只可能由一条边替换掉一条等边权的边来得到一颗新的最小生成树。所以求出每种边权出现几次，用dfs判断每种方案即可。 | ||
| 1017 | [JSOI2008]魔兽地图DotR | 树形dp |
| 简单树形dp，要dp的东西有点多。 | ||
| 1019 | [SHOI2008]汉诺塔 | dp |
| 比较神的题，首先步骤的唯一的，dp设 f[j][i] 为 i 中有 j 个盘子，且除 i 以外其余柱子中没有盘子，将 i 中的全部盘子移到 g[j][i] 的最小步数.。具体推理见https://blog.sengxian.com/solutions/bzoj-1019 |
||
| 1024 | [SCOI2009]生日快乐 | dfs |
| 暴力dfs | ||
| 1025 | [SCOI2009]游戏 | dp |
| 即求和为n的几个数的最小公倍数种数，dp即可。 | ||
| 1026 | [SCOI2009]windy数 | 数位dp |
| 数位dp模板题 | ||
| 1029 | [JSOI2007]建筑抢修 | 贪心 |
| 贪心，先以T2排序，建一个大根堆。枚举所有建筑，如果当前建筑能修就修，不能修就在堆里找一个T1最大的，判断去掉它后1能不能修2时间是不是更少即是不是更优 | ||
| 1030 | [JSOI2007]文本生成器 | AC自动机 |
| AC自动机+DP，都不用矩阵乘法优化 | ||
| 1031 | [JSOI2007]字符加密Cipher | SAM |
| 拿SAM跑最小表示，把字符串自复制一遍，建SAM，从root开始跑最小编号的结点，在上面跑|S|个结点，然后输出当前结点的信息就行了。 | ||
| 1036 | [ZJOI2008]树的统计Count | 树链剖分 |
| 裸题 | ||
| 1037 | [ZJOI2008]生日聚会Party | dp |
| 定义 dp[i][j][b][g] 为当前序列中有 i 个男孩 j 个女孩且后缀序列中男生最多比女生多 b 个, 女生最多比男生多 g 个，转移的时候注意对0取max. |
||
| 1040 | [ZJOI2008]骑士 | 基环外向树+树形DP |
| 把恨的人转化为它在树上的父亲，先想到二分图的最大权值独立集，转化为网络流在这么大的数据范围下显然不行。（然后偷瞄了几眼题解）那么对于一棵树，做法就同 没有上司的舞会一样。那么现在n个点，n条边，可能是基环外向树森林。对于一个环，先dfs找到一个环边，断开这条边（记录一下不要通过这条边转移），转化为树。对于这条边连接的点u，v，因为不能同时选u，v，那么有两种情况，不选u，v随意，不选v，u随意，对应dp时的f[u][0]和f[v][0]，这个联通块的最大值就是取个max。因为是森林，所以，把所有联通块的最大值都加起来就好了。 |
||
| 1041 | [HAOI2008]圆上的整点 | 数学 |
| 推式子，见https://blog.csdn.net/linkfqy/article/details/77922193 | ||
| 1044 | [HAOI2008]木棍分割 | 二分+dp |
| 第一问二分，第二问优化一下暴力的dp | ||
| 1045 | [HAOI2008] 糖果传递 | 数学 |
| 数学题 | ||
| 1047 | [HAOI2007]理想的正方形 | 单调队列 |
| 枚举点(i,j)，维护同一行前n个的最值，把这个单调队列的最值添加到列对应的单调队列中，维护一下。 | ||
| 1050 | [HAOI2006]旅行comf | 并查集 |
| （又看了一眼题解）既然是个分数，要求值最小，那么和 秦始皇的国家道路系统 有些雷同，枚举最小边的值，找一个合法的最小的边来做分子。然后就没想出来（划掉）。先按边的权值从小到大排序，枚举第i条边做最小边，那么从再按顺序枚举剩下的边做分子，这里用并查集来维护S和T的连通性，当联通的时候就可以统计答案了。 |
||
| 1051 | [HAOI2006]受欢迎的牛 | 强连通缩点 |
| 对于一个联通块里的牛，获得了这个块内所有牛的欣赏，如果缩点后处在拓扑图尾端（即出度为0）的块有且仅有一个，那么这个块内的所有牛都符合条件 | ||
| 1053 | [HAOI2007]反素数ant | 数学+搜索 |
| 应该算反素数里比较水的吧，主要满足两个性质（1）一个反素数的所有质因子必然是从2开始的连续若干个质数，因为反素数是保证约数个数为的这个数尽量小 （2）同样的道理，如果n=2^t1*3^t2*5^t3*…，那么必有t1>=t2>=t3>=…，然后就可以dfs大暴力啦，推荐http://blog.csdn.net/ACdreamers/article/details/25049767 |
||
| 1056 | [HAOI2008]排名系统 | hash+平衡树 |
| 不穿衣服的平衡树题 | ||
| 1058 | [ZJOI2007]报表统计 | stl |
| 用multiset和priority_queue维护，很良心的题 | ||
| 1059 | [ZJOI2007]矩阵游戏 | 二分图匹配 |
| 事实上是找是否有n个棋子任意两个都不同行且不同列，对行列拆点建图 | ||
| 1061 | [Noi2008]志愿者招募 | 费用流 |
| 线性规划经典问题，参见https://www.byvoid.com/zhs/blog/noi-2008-employee | ||
| 1064 | [Noi2008]假面舞会 | 图论+dfs找环找链 |
| 非常电压的题目，题解http://blog.sina.com.cn/s/blog_86942b1401015r81.html，反正菜鸡是想不出来的。主要思路就是a能看到b，那么就建一条边a->b。然后分两种情况：有环，只有树。对于第一种情况，找出这些环，k的最大值就是这些环的大小的最大公约数。k的最小值就是k的最大值中第一个大于等于3的约数。因为题目中说“由于并不是每个人都能记住自己所看到的全部编号”，那么只要环满足，树一定能满足。第二种情况k的最大值就是所有链的链长之和。最小值显然是3。关于找环：双向建边，对每个点进行标号，遇到正向边标号+1，反向边标号-1，然后当遇到已经被标号了的点，就说明找到了一个环，其点的个数为|已标号-当前标号|，然后标号不变继续查找。 | ||
| 1066 | [SCOI2007]蜥蜴 | 网络流 |
| 模板题 | ||
| 1068 | [SCOI2007]压缩 | dp |
| 区间dp | ||
| 1070 | [SCOI2007]修车 | 费用流 |
| 拆点费用流 | ||
| 1079 | [SCOI2008]着色方案 | dp |
| 普及组水平dp | ||
| 1083 | [SCOI2005]繁忙的都市 | 最小生成树 |
| 裸题，写的prim也过了 | ||
| 1085 | [SCOI2005]骑士精神 | A* |
| A*搜索模板题，估价函数直接取不同点个数。 | ||
| 1086 | [SCOI2005]王室联邦 | 树分块 |
| 这题教你怎么树分块 | ||
| 1087 | [SCOI2005]互不侵犯King | dp |
| 裸状压do | ||
| 1088 | [SCOI2005]扫雷Mine | 模拟 |
| 枚举前两个格子填什么即可确定所有格子，我写了个dp（雾 | ||
| 1089 | [SCOI2003]严格n元树 | DP |
| 抄题解啦啦啦。假设我们已知dp[i-1]，那么深度不大于i的树就相当于多出了一个根节点，其每一个儿子(共n个儿子)都是一颗深度不大于i-1的树。那么dp[i]=dp[i-1]^n+1（还有没有儿子的情况），直接线性递推就可以得到答案了。(长一个根挺巧妙的) | ||
| 1090 | [SCOI2003]字符串折叠 | dp |
| 区间dp | ||
| 1095 | [ZJOI2007]Hide 捉迷藏 | 动态点分治 |
| 动态点分治代码练习题，注意细节，为了卡常分类讨论写了好长（雾 | ||
| 1096 | [ZJOI2007]仓库建设 | dp |
| 斜率优化 | ||
| 1101 | [POI2007]Zap | 莫比乌斯反演 |
| 推推式子 | ||
| 1113 | [Poi2008]海报PLA | 单调栈 |
| 维护一个单调递增的栈 | ||
| 1115 | [POI2009]石子游戏Kam | SG函数 |
| 先做差，转化为阶梯Nim游戏，考虑奇数位的异或和即可，注意阶梯Nim游戏是将后面的移到前面，要反一下 | ||
| 1121 | [POI2008]激光发射器SZK | 模拟 |
| 因为一一对应，直接输出n/2 | ||
| 1143 | [CTSC2008]祭祀river | 最大独立集 |
| 定义：选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。方法：最大独立集=所有顶点数-最小顶点覆盖。证明：若2,4,7构成最小顶点覆盖，那么其他点6个构成最大独立集。且其他点不可能相连。假设其他点相连则这条边必定没有被2,4,7 覆盖，与2,4,7是最小顶点覆盖矛盾。因此其他点之间必定没有边。而2,4,7是最小顶点覆盖，所谓最小就是不能再小了，因此我们的独立集就是最大了。 |
||
| 1150 | [CTSC2007]数据备份Backup | 堆 |
| 带撤销操作的贪心，用堆+链表维护，类似网络流的退流思路 | ||
| 1179 | [Apio2009]Atm | 最短路+缩点 |
| 强连通缩点，记录这个强连通内所有ATM 的钱的总和，构建新图，从S到T跑最短路即可 |
||
| 1188 | [HNOI2007]分裂游戏 | SG函数 |
| 考虑每个石子的SG值，SG[i]表示第i堆的任意一个石子，后继状态为枚举两个j,k且i<j<=k | ||
| 1189 | [HNOI2007]紧急疏散evacuate | 二分图匹配 |
| 先二分答案，连边做二分图匹配，出口要按时间拆点 | ||
| 1191 | [HNOI2006]超级英雄Hero | 二分图匹配 |
| 裸 | ||
| 1192 | [HNOI2006]鬼谷子的钱袋 | 数学题 |
| 裸 | ||
| 1202 | [HNOI2005]狡猾的商人 | 并查集 |
| 裸 | ||
| 1207 | [HNOI2004]打鼹鼠 | dp |
| n^2dp 枚举上一个打死的鼹鼠 | ||
| 1208 | [HNOI2004]宠物收养所 | Splay |
| 最讨厌splay了，还得维护两个splay，hzw那里有用set水过的代码 | ||
| 1212 | [HNOI2004]L语言 | trie+DP |
| 首先令f[i]表示到i的前缀能否被理解，那么答案就是f[i]==1时最大的i 转移也很简单，如果f[i]==1，这个串就可以从i+1开始匹配一个新单词，因为单词长度<=10，暴力在trie上走就是了 |
||
| 1213 | [HNOI2004]高精度开根 | Python+二分 |
| 牛顿迭代了解下 | ||
| 1214 | [HNOI2004]FTP服务器 | 模拟？ |
| 看到题的第一眼慌掉了，这么复杂的模拟题？当看到Python 2B的时候就懂了 |
||
| 1218 | [HNOI2003]激光炸弹 | 扫面线 |
| 暴力枚举 | ||
| 1221 | [HNOI2001] 软件开发 | 费用流 |
| 按题意建图，这题貌似有更高级的做法？参见bzoj5164 | ||
| 1222 | [HNOI2001]产品加工 | dp |
| f[i]表示A机器工作了i小时，B机器最少工作了几个小时，背包DP | ||
| 1237 | [SCOI2008]配对 | DP |
| 可以证明配对的两个数的位置最多差两格远，不然会有更优方案 | ||
| 1242 | Zju1015 Fishing Net弦图判定 | 弦图 |
| 判断完美消除序列中每个元素相邻的所有点中在序列中位置最小的点和其他点是否相邻 | ||
| 1260 | [CQOI2007]涂色paint | dp |
| 还是区间dp | ||
| 1269 | [AHOI2006]文本编辑器editor | stl |
| rope了解下 | ||
| 1303 | [CQOI2009]中位数图 | 模拟 |
| 挺sb的 | ||
| 1305 | [CQOI2009]dance跳舞 | 网络流+二分 |
| 裂点，仔细想想还算简单的，当时智障连错边WA了一天 | ||
| 1307 | 玩具 | |
| 不好意思忘了。。。 | ||
| 1318 | [Spoj744] Longest Permutation | 模拟 |
| 考虑一些限制条件 | ||
| 1355 | [Baltic2009]Radio Transmission | kmp |
| kmp求字符串周期，ans=n-fail[n] | ||
| 1396 | 识别子串 | SAM+李超线段树 |
| sam上一个right集合大小为1的点可以更新这个点代表的子串，因为是一个一次函数，用李超树维护。 | ||
| 1406 | [AHOI2007]密码箱 | 数论 |
| 化简式子，枚举，set去重 | ||
| 1412 | [ZJOI2009]狼和羊的故事 | 最小割 |
| 建图：狼连原点，边权inf，羊连汇点，边权inf。狼到空地，狼到羊，空地到羊，连边，边权为1。最大流最小割定理完事。基本套路？ | ||
| 1433 | [ZJOI2009]假期的宿舍 | 二分图最大匹配 |
| 裸题 | ||
| 1444 | [Jsoi2009]有趣的游戏 | AC自动机+消元 |
| 需要定义 xi 为一局比赛经过 i 点的期望次数，参见https://blog.sengxian.com/solutions/bzoj-1444 |
||
| 1452 | [JSOI2009]Count | 树状数组 |
| 裸 | ||
| 1457 | 棋盘游戏 | SG函数 |
| 因为每个棋子互不影响，所以游戏的SG值等于每个棋子的SG值异或和。对棋盘建图求SG值即可。 | ||
| 1468 | Tree | 点分治 |
| 裸题 | ||
| 1477 | 青蛙的约会 | 扩展欧几里得 |
| 裸题 | ||
| 1483 | [HNOI2009]梦幻布丁 | 启发式合并 |
| 裸 | ||
| 1486 | [HNOI2009]最小圈 | 二分+spfa |
| 二分最小值，每条边都减去mid，如果存在负权圈，说明有一个平均权值<mid的圈 | ||
| 1497 | [NOI2006]最大获利 | 网络流 |
| 最小割=最大流，此模型有个名字叫最大权闭合图 | ||
| 1500 | [NOI2005]维修数列 | splay |
| 贴的代码，不想说话，听说可以rope水过 | ||
| 1511 | [POI2006]OKR-Periods of Words | kmp |
| 水的不行了。 | ||
| 1535 | [POI2005]Sza-Template | kmp |
| … | ||
| 1552 | [Cerc2007]robotic sort | 平衡树 |
| 模拟题意 | ||
| 1565 | [NOI2009]植物大战僵尸 | 网络流 |
| 最大权闭合图 | ||
| 1568 | [JSOI2008]Blue Mary开公司 | 李超线段树 |
| 裸题，自行百度 | ||
| 1588 | [HNOI2002]营业额统计 | splay |
| 娘的又是splay，也有set水过的方法 | ||
| 1597 | [Usaco2008 Mar]土地购买 | 斜率优化，DP |
| 不是很懂，再去看看题解 | ||
| 1607 | [Usaco2008 Dec]Patting Heads 轻拍牛头 | 暴力 |
| for循环专练 | ||
| 1628 | [Usaco2007 Demo]City skyline | 单调栈 |
| 同海报pla | ||
| 1758 | [Wc2010]重建计划 | 点分治 |
| 要注意子树大小需要排序，否则复杂度不正确 | ||
| 1778 | [Usaco2010 Hol]Dotp 驱逐猪猡 | dp |
| 期望dp+高斯消元裸题 | ||
| 1787 | [Ahoi2008]Meet 紧急集合 | LCA |
| 挺明显的 | ||
| 1798 | [Ahoi2009]Seq 维护序列seq | 线段树 |
| 线段树+lazytag模板题 | ||
| 1800 | [Ahoi2009]fly 飞行棋 | 暴力 |
| 就是暴力嘛 | ||
| 1823 | [JSOI2010]满汉全席 | 2-SAT |
| 模板题 | ||
| 1832 | [AHOI2008]聚会 | LCA |
| 双倍经验，同上 | ||
| 1833 | [ZJOI2010]count 数字计数 | dp |
| 数位dp，要考虑前缀0怎么处理，我是后面计算的 | ||
| 1854 | [Scoi2010]游戏 | 二分图最大匹配 |
| 裸 | ||
| 1855 | [Scoi2010]股票交易 | DP |
| 单调队列优化 | ||
| 1856 | [Scoi2010]字符串 | 数学题 |
| 卡特兰数 | ||
| 1857 | [Scoi2010]传送带 | 三分套三分 |
| 貌似是我在bzoj上交的第一题，三分AB上的点再三分CD上的点，没证过 | ||
| 1861 | [Zjoi2006]Book 书架 | 平衡树 |
| 撕烤一下怎么用平衡树来维护 | ||
| 1862 | [Zjoi2006]GameZ游戏排名系统 | 平衡树 |
| 双倍经验题 | ||
| 1864 | [Zjoi2006]三色二叉树 | dp |
| noip难度dp | ||
| 1874 | [BeiJing2009 WinterCamp]取石子游戏 | SG函数 |
| 建图求SG函数，入门题 | ||
| 1876 | [SDOI2009]SuperGCD | 高精度 |
| Python水过 | ||
| 1878 | [SDOI2009]HH的项链 | 莫队 |
| 裸 | ||
| 1895 | Pku3580 supermemo | 平衡树 |
| 考验码力 | ||
| 1898 | [Zjoi2005]Swamp 沼泽鳄鱼 | dp |
| 矩阵乘法优化，考虑一整个周期 | ||
| 1911 | [Apio2010]特别行动队 | dp |
| 高级的斜率优化 | ||
| 1922 | [Sdoi2010]大陆争霸 | Dijkstra |
| 记录 dis[0][i] 表示到 i 点的最短时间， dis[1][i] 表示 i 可以被摧毁的最短时间。 | ||
| 1924 | [Sdoi2010]所驼门王的宝藏 | tarjan |
| 缩点求最长路 | ||
| 1925 | [Sdoi2010]地精部落 | dp |
| 参见https://oi.men.ci/sdoi2010-goblin/ | ||
| 1927 | [Sdoi2010]星际竞速 | 费用流 |
| 按题意建图 | ||
| 1934 | [Shoi2007]Vote 善意的投票 | 网络流 |
| 裸 | ||
| 1968 | [Ahoi2005]COMMON 约数研究 | 暴力 |
| 又刷了一道水题 | ||
| 1970 | [Ahoi2005]Code 矿藏编码 | 模拟 |
| 思博题 | ||
| 1975 | [Sdoi2010]魔法猪学院 | k短路 |
| A*+spfa，一直找接下来的一条路，直到能量不够，用STL的优先队列也过了 | ||
| 1977 | [BeiJing2010组队]次小生成树 Tree | 倍增 |
| 严格次小生成树裸题，枚举加上哪条边，在形成的环上选边删去即可 | ||
| 1997 | [Hnoi2010]Planar | 2-SAT |
| 剩下的不在环上的边则有两种选择: 从环里穿过去或者从环外绕过去. 根据边所连接的两个节点在哈密顿回路中的顺序确定如果边同时在环内是否会相交, 如果会相交的话这两条边必须分居哈密顿环两侧. 处理出所有之后判断可行性就好了 |
||
| 2002 | [Hnoi2010]Bounce 弹飞绵羊 | 分块 |
| 分块，每个元素计算几次弹出所在块和弹出后落到的位置 | ||
| 2005 | [Noi2010]能量采集 | 容斥 |
| 容斥/莫比乌斯反演 | ||
| 2006 | [NOI2010]超级钢琴 | 堆+主席树 |
| 挺神的思路，求出前缀和。对于每个结尾i，设现在取的区间是[j+1,i]，则i-R<=j<=i-L，取出该区间sum[j]的最小值，将sum[i]-sum[j]放入堆中。建立一个大根堆，每次取出堆顶元素，将排名k+1，将sum[i]-区间第k小值放入堆中。重复k次即可。 | ||
| 2038 | [2009国家集训队]小Z的袜子(hose) | 莫队 |
| 莫队模板题 | ||
| 2049 | [Sdoi2008]Cave 洞穴勘测 | LCT |
| 裸 | ||
| 2095 | [Poi2010]Bridges | 网络流 |
| 其实是混合图欧拉回路判定。参见https://blog.csdn.net/aarongzk/article/details/50270389 | ||
| 2111 | [ZJOI2010]Perm 排列计数 | 组合数学 |
| 完全忘光了，设f[i]表示以i为根的子树形成小根堆的方案数，f[i]=C(si[i<<1],si[i]−1)∗f[i<<1]∗f[i<<1|1] | ||
| 2115 | [Wc2011] Xor | dfs找环+线性基 |
| 任意地先找出一条从1到n的路径，把这条路径上的xor和作为ans初值，然后求若干个环与这个ans初值所能组合成的xor最大值。 | ||
| 2118 | 墨墨的等式 | 最短路+数论 |
| 若x能被表示出来，那么x+a[1]*k也能被表示出来，那么就要求最小的x[i]满足x[i]%a[1]==i，最小值转化为最短路就是i向i+a[j]%a[1]建一条长度为a[j]的边(0<=i<a[1],1<j)，最后所有小于等于x的能被构造出来的数总共ans[x]=∑((x – d[i]) / a[1]) + 1(0<=i<a[1])个，答案即为ans[bmax]-ans[bmin-1] |
||
| 2119 | 股市的预测 | SA |
| 后缀数组神题，求形如ABA的子串。大致思路是枚举A部分的长度L，然后每隔L位放一个关键点，再枚举每一个关键点i，计算i和i+B+L往左往右能扩展最大长度l,r之后的串是一样的，若l+r>=L，则这里又l+r-L+1个子串满足条件。 | ||
| 2120 | 数颜色 | 莫队 |
| 带修改的莫队，多一维记录时间，作为第三级关键字，暴力修改就行了，感觉没多大用 | ||
| 2124 | 等差子序列 | hash+线段树 |
| 其实我们只要找一个长度为3的等差序列即可。考虑枚举中间那个数为a，考虑维护一个以权值为下标的数组，对于每一个数，出现在a左侧记为1，右侧为0。那么对称比较每一位，若两位不同就是找到了一个等差序列。这个过程可以用线段树维护hash来支持修改查询。 | ||
| 2134 | 单选错位 | dp |
| 非常简单的期望计算题，单独考虑每一小题就行了。 | ||
| 2140 | 稳定婚姻 | 强连通分量 |
| 结论：在同一个强连通分量里的夫妻是危险的 | ||
| 2141 | 排队 | 树套树 |
| 树套树计算逆序对，裸 | ||
| 2152 | 聪聪可可 | 树形DP |
| 求出每个节点i长度对3取模为j的点数f[i][j]，直接统计 | ||
| 2154 | Crash的数字表格 | 莫比乌斯反演 |
| 推式子 | ||
| 2159 | Crash 的文明世界 | 斯特林数 |
| 左转学习第二类斯特林数，https://shichengxiao01.github.io/2018/02/17/%E7%AC%AC%E4%BA%8C%E7%B1%BB%E6%96%AF%E7%89%B9%E6%9E%97%E6%95%B0%E5%B0%8F%E7%BB%93/ | ||
| 2179 | FFT快速傅立叶 | FFT |
| 裸 | ||
| 2190 | [SDOI2008]仪仗队 | 数学 |
| 考察phi的定义 | ||
| 2194 | 快速傅立叶之二 | FFT |
| 裸 | ||
| 2208 | [Jsoi2010]连通数 | floyd |
| bitset优化求传递闭包 | ||
| 2212 | [Poi2011]Tree Rotations | 线段树合并 |
| 线段树合并比较好的题。建立权值线段树，每次合并的时候计算交换前后的逆序对个数。 | ||
| 2221 | [Jsoi2009]面试的考验 | 树套树 |
| 线段树套set乱搞 | ||
| 2227 | [Zjoi2011]看电影(movie) | DP |
| 抄题解：概率等于合法的方案数除以总方案数。总方案数=K^N，合法方案数的计算：在最后面加一个座位，然后所有的座位连成一个环。现在那么总方案数等于(K+1)N，每种环都算了(K+1)次，所以除以(K+1)，最后抽调一个空白的座位来构造一个合法的方案，所以要乘(N−K+1)。ans=(K+1）^(N-1)*(K-N+1)/K^N | ||
| 2242 | [SDOI2011]计算器 | 数论 |
| 第二个扩欧，后一个BSGS，模板题 | ||
| 2243 | [SDOI2011]染色 | 树链剖分 |
| 树链剖分，打标记，比较难写。 | ||
| 2251 | [2010Beijing Wc]外星联络 | SAM |
| SAM随便做 | ||
| 2257 | [Jsoi2009]瓶子和燃料 | 裴蜀定理 |
| 两个容量为a和b的瓶子，它们倒来倒去最后可以得到的体积一定是ax+by (x和y为可为负的整数)。裴蜀定理：若a和b是整数，且Gcd(a, b)==d，那么ax+by(x和y为整数)一定是d的倍数 | ||
| 2286 | [Sdoi2011]消耗战 | 虚数 |
| 建虚树然后dp，比较裸，当时因为编译器的神奇入栈顺序调了一晚上。 | ||
| 2288 | 【POJ Challenge】生日礼物 | 堆 |
| 同1150 | ||
| 2299 | [HAOI2011]向量 | 裴蜀定理 |
| 先要枚举奇偶性 | ||
| 2301 | [HAOI2011]Problem b | 莫比乌斯反演 |
| 需要用到分块技巧 | ||
| 2323 | [ZJOI2011]细胞 | dp |
| 利用矩阵相加预处理转移矩阵，十进制拆位dp。详见https://blog.sengxian.com/solutions/bzoj-2323 | ||
| 2330 | [SCOI2011]糖果 | 差分约束 |
| 这题神坑，如果按普通方法建边的话会有负边，就会出现负权，那么最后统一加一个值是错的，因为不一定联通。所以要转化，这题要倒着建边的玄学优化？ | ||
| 2331 | [SCOI2011]地板 | dp |
| 三进制状压dp，敬请自行yy | ||
| 2333 | [SCOI2011]棘手的操作 | 左偏树 |
| 左偏树模板题，带标记，这题靠着hzw大神的对拍，总共还写了4个小时，交了4发才过，感觉写了几百个BUG | ||
| 2351 | [BeiJing2011]Matrix | HASH |
| 同2462，可以KMP，模数比较毒，进制大一点 | ||
| 2428 | [HAOI2006]均分数据 | 模拟退火 |
| 模拟退火踩标算 | ||
| 2429 | [HAOI2006]聪明的猴子 | 最小生成树 |
| 比较水 | ||
| 2431 | [HAOI2009]逆序对数列 | dp |
| dp即可，f[i][j]表示填了i个数，有j个逆序对 | ||
| 2434 | [Noi2011]阿狸的打字机 | AC自动机 |
| 建出AC自动机，DFS序+树状数组统计 | ||
| 2435 | [Noi2011]道路修建 | DFS |
| 看起来像水题，就是水题，直接DFS，也算是Noi题?? | ||
| 2436 | [Noi2011]Noi嘉年华 | dp |
| 不错的题，先写一个暴力的dp，考虑优化即从两侧分别dp，在某处合并是考虑单调性即可n^3 | ||
| 2456 | mode | 技巧 |
| On求众数，考虑抵消的思想 | ||
| 2460 | [BeiJing2011]元素 | 线性基 |
| 线性基模板题，能插入到线性基里就把膜力加起来。线性基的性质：1.线性基的异或集合中不存在0。 2.线性基的异或集合中每个元素的异或方案唯一，其实这个跟性质1是等价的。 3.线性基二进制最高位互不相同。 4.如果线性基是满的，它的异或集合为[1,2n−1]。证明左转拟阵。 |
||
| 2462 | [BeiJing2011]矩阵模板 | HASH |
| 一开始以为是KMP，我又不会写，查了下题解是矩阵hash，跟一维差不多，自己想吧 | ||
| 2463 | [中山市选2009]谁能赢呢？ | 博弈论 |
| 直觉告诉我跟面积奇偶有关，证明：首先对于n是偶数，一定能被1*2的骨牌覆盖！所以从起点开始，先手一定走的是骨牌的另一端，后手一定走的是骨牌的前一端，因此无论何时，先手总是可以走。因此先手必胜。 | ||
| 2464 | 中山市选[2009]小明的游戏 | spfa |
| 建图跑最短路，裸 | ||
| 2527 | [Poi2011]Meteors | 整体二分 |
| 做为模板很合适 | ||
| 2534 | Uva10829L-gap字符串 | SA |
| 同2119 | ||
| 2555 | SubString | SAM+LCT |
| 曾经的大毒瘤题，会SAM和LCT的话应该不难，把子树求和转为链修改操作 | ||
| 2561 | 最小生成树 | 网路流 |
| 对于最小生成树而言，就是不能存在一条由比加入的边权值更小的边组成的路径，那么将uv作为源汇，给所有权值更小边加1的流量求最小割，最大生成树同理。 | ||
| 2565 | 最长双回文串 | Manacher |
| Manacher裸题，用 right[i] 表示以第 i 个位置为最右字符的最长回文串长度，利用单调性可On求出，left[i]同理，最后求下答案。 |
||
| 2588 | Spoj 10628. Count on a tree | 主席树 |
| 按dfs序建以父亲为旧版本建主席树，差分求解即可。 | ||
| 2594 | [Wc2006]水管局长数据加强版 | LCT |
| LCT维护最小生成树 | ||
| 2599 | [IOI2011]Race | 启发式合并 |
| 启发式合并或点分治 | ||
| 2626 | JZPFAR | kdtree+堆 |
| 每次维护一个大小为k的小根堆，在估价时对堆顶判断一下 | ||
| 2648 | SJY摆棋子 | kdtree+堆 |
| kdtree重构 | ||
| 2653 | middle | 主席树 |
| 用到 把序列里所有的比它小的数看成-1，所有的比它大的数看成1 这个技巧，转化为求左端点在[a,b]，右端点在[c,d]中的某一段最大和区间，在主席树上维护标记。 |
||
| 2656 | [Zjoi2012]数列(sequence) | 高精度 |
| 展开可得k1*A[2i]+k2*A[2i+1]=(k1+k2)*A[i]+k2*A[i+1]，+Python没了 | ||
| 2683 | 简单题 | kdtree |
| kdtree裸题 | ||
| 2705 | [SDOI2012]Longge的问题 | 欧拉函数 |
| 枚举n的约束k，令f(k)为gcd(i,n)=k的i个数（i<=n），答案为∑(k*f(k))。∵gcd(i,n)=k ∴gcd(i/k,n/k)=1=euler(n/k) |
||
| 2716 | [Violet 3]天使玩偶 | kdtree |
| 同2648 | ||
| 2728 | [HNOI2012]与非 | dp |
| 神奇的数位dp，大概就是如果a[1]~a[n]的所有数第i位和第j位相同，那么nand出来的数第i位和第j位也相同，感性理解题解https://blog.csdn.net/thy_asdf/article/details/50456620 | ||
| 2730 | [HNOI2012]矿场搭建 | tarjan+DFS |
| 求割点，分三种情况：1.联通块内没有割点，建两个出口，方案数*=size*(size-1) 2.联通块内有一个割点，建一个出口，方案数*=size 3.联通块内有三个以上个点，不用建 |
||
| 2733 | [HNOI2012]永无乡 | 启发式合并 |
| 线段树启发式合并 | ||
| 2751 | [HAOI2012]容易题(easy) | 数学 |
| noip难度数学题 | ||
| 2754 | [SCOI2012]喵星球上的点名 | 后缀数组 |
| 后缀数组模板题，最水的一道？感觉我就能理解这道的解法，果然我太渣了，什么 弦论 根本搞不懂。做法就是把所有字符串连起来，中间接个分割字符，然后对每个点名，找到，排名rank，再向左右找，直到公共前缀长度小于点名的长度，再在这个区间里统计有哪些喵即可。（其实是对暴力的优化） |
||
| 2756 | [SCOI2012]奇怪的游戏 | 网络流 |
| 先讨论是否有解，二分+网络流黑白建图判断即可 | ||
| 2761 | [JLOI2011]不重复数字 | STL |
| SET，MAP随便搞 | ||
| 2806 | [Ctsc2012]Cheat | SAM+dp |
| 先用SAM求出求出以每个字符结尾的最长匹配长度a[i]，然后二分+单调队列优化dp判断即可，真·noip难度dp | ||
| 2809 | [Apio2012]dispatching | 左偏树+DFS |
| 左偏树。对每个节点维护一个堆，堆的大小，总的薪水三个值。从根DFS，先递归儿子，再把信息都合并，如果总的薪水>预算，那么就弹出最大值，直到薪水<预算，更新答案 | ||
| 2815 | [ZJOI2012]灾难 | 支配树 |
| 灭绝树：一个东西的父亲是所有入边的另一端的点的LCA。详见http://fanhq666.blog.163.com/blog/static/8194342620124274154996/ | ||
| 2819 | Nim | lca |
| 求链的异或和，基本题 | ||
| 2843 | 极地旅行社 | LCT |
| 裸 | ||
| 2844 | albus就是要第一个出场 | 线性基 |
| 每个可以表示出的数的方案有2^(n-|S|)种，证明见https://oi.men.ci/bzoj-2844/ | ||
| 2865 | 字符串识别 | SAM |
| 同1396 | ||
| 2879 | [Noi2012]美食节 | 费用流 |
| 同1070，但时要动态加点 | ||
| 2946 | [Poi2000]公共串 | SAM |
| 广义SAM裸题 | ||
| 2965 | 保护古迹 | 平面图点定位+最小割 |
| 平面图点定位的做法见【WC2013】平面图，剩下的就是最小割了 | ||
| 3016 | [Usaco2012 Nov]Clumsy Cows | 贪心 |
| 贪心乱搞，我想了一晚上。。。 | ||
| 3028 | 食物 | 生成函数 |
| 生成函数基本题，见金策的国家集训队论文《生成函数的运算与组合计数问题》 | ||
| 3051 | [wc2013]平面图 | 平面图点定位 |
| 百度做法，就当练习平面几何了。 | ||
| 3083 | 遥远的国度 | 树链剖分 |
| 并不真的换根，而是在查询的时候讨论，神题。1.u就是root 2.lca(u,root)不为u 3.lca(u,root)是u |
||
| 3103 | Palindromic Equivalence | Manacher+弦图 |
| 嗯。感性理解题解吧，它说的都对…http://foreseeable97.logdown.com/posts/194507-herbicidalontak2010palindromic-equivalence | ||
| 3110 | [Zjoi2013]K大数查询 | 树套树 |
| 裸 | ||
| 3112 | [Zjoi2013]防守战线 | 线性规划 |
| 学习一下单纯形（完了忘光了），详见http://nanoape.is-programmer.com/posts/202149.html，uoj上这题的标程全挂了 | ||
| 3143 | [Hnoi2013]游走 | 高斯消元+贪心 |
| 基本的高斯消元方法，然后贪心编号即可 | ||
| 3155 | Preprefix sum | 树状数组 |
| 差分一下，同理可以得到树状数组区间修改的方法，不会的自行百度 | ||
| 3166 | [Heoi2013]Alo | 可持久化trie |
| 思路挺明显的，枚举一个数成为次小值，向左向右找到两个极大区间，在区间内找异或值最大的数，用可持久化trie就行了 | ||
| 3170 | [Tjoi2013]松鼠聚会 | 数学 |
| 坐标系转化，百度 | ||
| 3172 | [Tjoi2013]单词 | SAM |
| 裸，即right集合大小 | ||
| 3175 | [Tjoi2013]攻击装置 | 网络流 |
| 黑白染色建图，跑网络流 | ||
| 3196 | Tyvj 1730 二逼平衡树 | 树套树 |
| 裸 | ||
| 3207 | 花神的嘲讽计划Ⅰ | HASH+STL |
| 正解应该是主席树来存HASH的值吧，这里又用vector水过了，存一个hash的值和出现位置，找的时候挨个找再判断就行了 | ||
| 3209 | 花神的数论题 | 数学 |
| 数位dp+欧拉定理 | ||
| 3211 | 花神游历各国 | 线段树 |
| 常见套路 | ||
| 3212 | Pku3468 A Simple Problem with Integers | 线段树 |
| 我怎么还写了这种题？？？ | ||
| 3223 | Tyvj 1729 文艺平衡树 | 平衡树 |
| 裸 | ||
| 3224 | Tyvj 1728 普通平衡树 | Splay |
| 用pb_ds里的splay水过了，洛谷上有vector的写法 | ||
| 3238 | [Ahoi2013]差异 | SAM |
| SAM在fail树上dp一下 | ||
| 3239 | Discrete Logging | BSGS |
| 模板题 | ||
| 3240 | [Noi2013]矩阵游戏 | 暴力 |
| 真·暴力 | ||
| 3270 | 博物馆 | 高斯消元 |
| 将两个人的位置压起来，消元即可 | ||
| 3277 | 串 | SAM |
| 用set启发式合并维护right集合 | ||
| 3289 | Mato的文件管理 | 莫队+树状数组 |
| 每次需要交换的次数就是区间内的逆序对数，先用莫队，修改答案的时候用树状数组就好了 | ||
| 3293 | [Cqoi2011]分金币 | 数学 |
| 同1045 | ||
| 3295 | [Cqoi2011]动态逆序对 | CDQ分治 |
| 三维CDQ分治模板题，一维来记录插入时间（倒着做），一直都在的为0，注意统计对答案的影响的时候有两种情况，如果你是像我一样最后一位是插入时间，还要判断时间相同的情况 | ||
| 3309 | DZY Loves Math | 莫比乌斯反演 |
| 好难啊TAT | ||
| 3350 | 相似回文串 | Manacher |
| 同3103 | ||
| 3351 | [ioi2009]Regions | 分块 |
| 数据分治，可以看2015年国家集训队论文《浅谈分块在一类在线问题中的应用》 | ||
| 3436 | 小K的农场 | 差分约束 |
| 裸 | ||
| 3438 | 小M的作物 | 网络流 |
| 最大权闭合子图 | ||
| 3439 | Kpm的MC密码 | DFS序+主席树+Trie |
| DFS序和主席树简直绝配，先对所有字符串倒着建trie树，那么一个串的kpm串就在它的子节点上。插完后对trie树进行DFS编号，那么每个点都有进入时间in和退出时间out,，如果这个点对应了一个存在的字符串，就把编号插到主席树上in这个位置上。对于每个查询，就是找 字符串对应的trie树节点的in到out区间内的第k小的数。 |
||
| 3473 | 字符串 | SAM |
| 同3277 | ||
| 3489 | A simple rmq problem | kdtree |
| 给每个点三维信息（位置，相同权值的前继置，后继位置），就可以上kdtree了 | ||
| 3504 | [Cqoi2014]危桥 | 网络流 |
| 虽然我觉得题解是错的，但还是这么写了。正常建边之后跑一遍网络流，但是这样可能会使得a1到an的流量跑到b1到bn去了，所以把b换过来，然后再跑一发网络流就好了。 | ||
| 3506 | [Cqoi2014]排序机械臂 | 平衡树 |
| 裸 | ||
| 3513 | [MUTC2013]idiots | FFT |
| B[x]代表两根木棒的长度和为x的方案数，ans=(C(n,3)-∑B[A[i]])/C(n,3)，减掉和自身组成的木棒 | ||
| 3514 | Codechef MARCH14 GERALD07加强版 | LCT+主席树 |
| 感性理解题解：从左到右加边, 假如+的边e形成环, 那么记下这个环上最早加入的边_e, 当且仅当询问区间的左端点> _e加入的时间, e对答案有贡献(脑补一下). 然后一开始是N个连通块, 假如有x条边有贡献, 答案就是N-x. 用LCT维护加边, 可持久化线段树维护询问 |
||
| 3531 | [Sdoi2014]旅行 | 熟练剖分 |
| 裸 | ||
| 3533 | [Sdoi2014]向量集 | 线段树 |
| 注意到一个没有插满的线段是不会被询问的，所以只有当插入位置为线段右端点时，将线段上的点搞一个凸包。注意到一个没有插满的线段是不会被询问的，所以只有当插入位置为线段右端点时，将线段上的点搞一个凸包。非叶子节点直接用下面的凸包合并。 然后因为斜率有正有负，要维护上下凸包， 代码挺好写的（雾 |
||
| 3550 | [ONTAK2010]Vacation | 线性规划 |
| 列出不等式，套线性规划 | ||
| 3555 | [Ctsc2014]企鹅QQ | HASH |
| 枚举去掉哪一位，HASH即可 | ||
| 3561 | DZY Loves Math VI | 莫比乌斯反演 |
| 好难啊TAT | ||
| 3578 | GTY的人类基因组计划2 | stl |
| map，set，hash乱搞 | ||
| 3580 | 冒泡排序 | 树状数组 |
| 我们用upper[i]记录给定数组中i前面比i大的数的个数。然后二分外层循环做了几次。若做了x次。则总次数=sigma(min(upper[i],x))。 然后我们发现，upper[i]<=x的话，那这个数一定排序完毕了。而对于upper[i]>x的部分，他们相对于原数列的位置不变。 |
||
| 3609 | [Heoi2014]人人尽说江南好 | 数学 |
| 等下。这题不是我做的。 | ||
| 3611 | [Heoi2014]大工程 | 虚树 |
| 虚树+dp | ||
| 3622 | 已经没有什么好害怕的了 | dp |
| 利用容斥原理dp，太神了！http://www.cnblogs.com/candy99/p/6617195.html | ||
| 3624 | [Apio2008]免费道路 | 并查集 |
| 用并查集维护连通性，1.先加入所有水泥路，判断是联通块数是否小于等于k + 1，否则输出无解。2.加入鹅卵石路，要求每条路连通两个不连通的集合，并标记为选中，判断联通块是不是只有一个，否则输出无解。3.删除所有边。4.插入第二步所选的边，共addedges条，再插入k-addedges条鹅卵石路，加不到输出无解。5.最后补上能连的水泥路即可 |
||
| 3626 | [LNOI2014]LCA | 树链剖分 |
| x和y的lca的深度，可以把x到根的所有结点加1，求y到根的路径上的权值和即可，那么可以用树链剖分维护，同时用支持区间操作带懒惰标记的线段树。最后用ans（r）-ans（l）即可。 | ||
| 3631 | [JLOI2014]松鼠的新家 | 树上差分 |
| 裸 | ||
| 3632 | 外太空旅行 | 随机化 |
| 随机化求最大团 | ||
| 3668 | [Noi2014]起床困难综合症 | 贪心 |
| noip难度贪心 | ||
| 3669 | [Noi2014]魔法森林 | LCT |
| 大佬都是写LCT的，菜鸡使用spfa艹过去的 | ||
| 3670 | [Noi2014]动物园 | kmp |
| 类似记忆化的做法 | ||
| 3671 | [Noi2014]随机数生成器 | 模拟 |
| 模拟题意 | ||
| 3673 | 可持久化并查集 by zky | 主席树 |
| 用主席树实现可持久化数组，这题要路径压缩 | ||
| 3674 | 可持久化并查集加强版 | 主席树 |
| 双倍经验 | ||
| 3675 | [Apio2014]序列分割 | dp |
| 斜率优化 | ||
| 3676 | [Apio2014]回文串 | manacher+SAM |
| 仅对manacher跑出来的极长的回文串，在fail树上倍增找对应节点即可 | ||
| 3680 | 吊打XXX | 爬山算法 |
| 物理题？反正我不会，左转hzwer.com | ||
| 3702 | 二叉树 | dp |
| 同1864 | ||
| 3709 | [PA2014]Bohater | 贪心 |
| 把怪物分成两种怪物，第一种是回复>伤害的，我们按照伤害从低到高去打就是最优的。 第二种是伤害>回复的。我们打完所有怪物的时候，血量一定是固定的，所以我们先把把回血多的先杀掉，再杀回血少的。 |
||
| 3714 | [PA2014]Kuglarz | 最小生成树 |
| 要知道每一个位子有球，就得知道sum(i)-sum(i-1)。花费a[i][j]即可把i-1,j放到同一个集合里，最后要所有i在同一个集合，那么对每一个a[i][j]，建一条i-1到j权值为a[i][j]的边，跑最小生成树即可。 | ||
| 3715 | [PA2014]Lustra | 乱搞 |
| 小学组题 | ||
| 3720 | Gty的妹子树 | 分块 |
| 树分块模板题 | ||
| 3730 | 震波 | 动态点分治 |
| 动态点分治，还要用两棵线段树算算贡献，比较麻烦 | ||
| 3731 | Gty的超级妹子树 | 分块 |
| 树分块毒瘤题，注意细节，随意yy就行了 | ||
| 3732 | Network | 最小生成树 |
| noip题 | ||
| 3744 | Gty的妹子序列 | 分块 |
| 这个怎么分块没想出来，查题解的。记录f[i][j]代表第i的开头位置到第j个位置的逆序对数，然后如果询问lr在一个块中的话，我们就暴力树状数组查询，否则就找到l后面的最靠前的块i，然后取出f[i][r]，对于前面的数字我们查询区间中这个数字后面的比它小的数的个数。还要棵主席树。 | ||
| 3747 | [POI2015]Kinoman | 线段树 |
| 又一道noip题系列 | ||
| 3751 | [NOIP2014]解方程 | hash |
| 真·noip题 | ||
| 3767 | A+B Problem加强版 | 模拟 |
| python | ||
| 3786 | 星系探索 | 平衡树 |
| 用平衡树维护dfs序，模板题 | ||
| 3811 | 玛里苟斯 | 线性基 |
| 抄题解QAQ。https://blog.csdn.net/SmallSXJ/article/details/73205569 | ||
| 3821 | 玄学 | 线段树 |
| 线段树神题。对操作建线段树，一个线段树节点只在加入操作的编号==区间的右端点后update。将同样a,b值的区间放在一起维护，这样一层上的区间数O(L)。 | ||
| 3876 | [Ahoi2014&Jsoi2014]支线剧情 | 费用流 |
| 好像是和带下界的网络流一样的建图方法？ | ||
| 3894 | 文理分科 | 网络流 |
| 我的建图方法比较渣，反正最小割就对了。复制一个网上的 先把答案赋值为所有读入数字之和。 每个人向源点连文科的边，向汇点连理科的边，割掉哪边表示不选哪科。 然后再对每个人分别建一个“文科点”和“理科点”。 源点连向“文科点”，“文科点”连向本人和周围的人(inf)，只要有一个人选了理科，这条路就联通了，需要割掉。 “理科点”同理。 |
||
| 3926 | [Zjoi2015]诸神眷顾的幻想乡 | SAM |
| trie上建广义SAM，不会的可以见https://toonaive.top/wordpress/archives/354 | ||
| 3932 | [CQOI2015]任务查询系统 | 主席树 |
| 裸 | ||
| 3956 | Count | 主席树 |
| 发现好点对互不跨立，所以只有O(n)个，用单调队列找出这O(n)个然后用主席树维护就可以了。 | ||
| 3996 | [TJOI2015]线性代数 | 网络流 |
| 化简矩阵，发现是个最大权闭合子图 | ||
| 3997 | [TJOI2015]组合数学 | dp |
| 答案是满足每一个点都在前一个点的严格右下方的最长链长度。 | ||
| 3998 | [TJOI2015]弦论 | SAM |
| 不会的嗯https://toonaive.top/wordpress/archives/354 | ||
| 4003 | [JLOI2015]城池攻占 | 左偏树 |
| 带标记的左偏树模板题，参考2809，战胜之后打标记即可。这里维护了三个标记，统一加了多少，称了多少，攻下几个城池。 | ||
| 4012 | [HNOI2015]开店 | 动态点分治 |
| 动态点分治+线段树+vector维护一波，估计写渣了，码量巨大 | ||
| 4025 | 二分图 | LCT |
| 神题，考虑统计有多少条边满足：在这条边被删除之前图一定不是二分图，详见http://c-sunshine.logdown.com/posts/261889/bzoj4025-bipartite-graph | ||
| 4031 | [HEOI2015]小Z的房间 | Matrix-Tree |
| 裸，此题要辗转整除消元，要注意 | ||
| 4033 | [HAOI2015]树上染色 | 树形DP |
| f[i][j]表示i结点及其子树总共染黑j个点所获得的最大收益。对于每一条边，贡献为左边白点数*右边白点数+黑点*黑点。 | ||
| 4034 | [HAOI2015]树上操作 | 树链剖分 |
| 裸 | ||
| 4036 | [HAOI2015]按位或 | 快速莫比乌斯变换 |
| 论文题，2015年国家集训队论文《集合幂级数的性质与应用及其快速算法》， | ||
| 4037 | [HAOI2015]数字串拆分 | dp |
| 同2323 | ||
| 4066 | 简单题 | kdtree |
| 同2683 | ||
| 4078 | [Wf2014]Metal Processing Plant | 2SAT |
| 完全没有印象。https://blog.csdn.net/baidu_36797646/article/details/80100216 | ||
| 4152 | [AMPPZ2014]The Captain | spfa |
| 只有坐标排序后相邻的两个点需要连边，然后跑spfa即可 | ||
| 4161 | Shlw loves matrixI | 矩阵 |
| 特征多项式优化矩阵乘法，见https://blog.csdn.net/qq_33229466/article/details/78933309 | ||
| 4162 | shlw loves matrix II | 矩阵 |
| 同上，需要前置技能：拉格朗日插值法 | ||
| 4184 | shallot | 线段树+线性基 |
| 线段树维护线性基，对时间分治的线段树 | ||
| 4195 | [Noi2015]程序自动分析 | 并查集 |
| 先把所有相等的并起来，在判断不等的满不满足即可 | ||
| 4196 | [Noi2015]软件包管理器 | 树链剖分 |
| 裸 | ||
| 4197 | [Noi2015]寿司晚宴 | dp |
| 状压dp神题，将大于根号n的素因子单独考虑，https://blog.sengxian.com/solutions/bzoj-4197 | ||
| 4198 | [Noi2015]荷马史诗 | 哈夫曼编码 |
| 插入一些长度为0，深度为1的点，把字符串总数凑到k-1的倍数，然后每次以k个最短的字符串做哈夫曼编码。 | ||
| 4199 | [Noi2015]品酒大会 | SAM |
| fail树上dp | ||
| 4236 | JOIOJI | map+hash |
| 维护前缀和，插到map里 | ||
| 4237 | 稻草人 | 分治 |
| 有点难度，抄题解呀，http://www.cnblogs.com/CQzhangyu/p/7123515.html | ||
| 4241 | 历史研究 | 莫队 |
| 回滚莫队hhh，随便搞就行了 | ||
| 4242 | 水壶 | 网格图最小生成树 |
| 从每个建筑物开始BFS，两个建筑物的“势力范围”相遇时就作为一条边先存储着，最后扔到kruskal即可。这题我好像爆栈了? | ||
| 4259 | 残缺的字符串 | FFT |
| 神题，怎么转化？式子在此https://blog.csdn.net/clover_hxy/article/details/62881696 | ||
| 4260 | Codechef REBXOR | trie树 |
| 先求前后缀异或和，上trie树即可 | ||
| 4269 | 再见Xor | 线性基 |
| 次小值去掉最低的位即可 | ||
| 4292 | [PA2015]Równanie | 数学 |
| 发现f最多只有1458，暴力枚举f | ||
| 4299 | Codechef FRBSUM | 主席树 |
| 主要是有一条性质很重要，当前可以凑到的数是mx，那么就一定可以凑到sum(mx+1)，否则不行。
然后就可以主席树乱搞了，因为每次至少扩大一倍 |
||
| 4300 | 绝世好题 | dp |
| noip难度 | ||
| 4305 | 数列的GCD | 数学 |
| 无可奉告 | ||
| 4311 | 向量 | 线段树 |
| 3533的简化版 | ||
| 4316 | isn | dp |
| f[i][j]表示前i个数，选出j个不降的数的方案数（i必须选），先不考虑停止，最后计算答案时容斥一下。 | ||
| 4318 | OSU! | dp |
| 考虑每一步的增量，题解https://oi.men.ci/bzoj-4318/ | ||
| 4320 | ShangHai2006 Homework | 分块 |
| 小于根号的暴力维护答案，否则枚举商，用set找一个余数最小的 | ||
| 4326 | NOIP2015 运输计划 | 二分+LCA+树上差分 |
| 树上差分：找出被所有路径都覆盖的边，在树中将所有路径起、始权值加1，起、始点的lca权值减2，从所有叶节点开始把权值往上累加。二分最短时间x，那么所有大于x的路径都要改造。找到这些路径，判断这些路径是否有共同覆盖的边，即为要改造的边，乱搞判断即可。 | ||
| 4327 | JSOI2012 玄武密码 | AC自动机 |
| 裸 | ||
| 4327 | 烁烁的游戏 | 动态点分治 |
| 需要一个线段树 | ||
| 4403 | 序列统计 | dp |
| 问题等价于，从 [1, R – L + 1]中选择 N 个数（可重复）的方案数。还需要lucas定理。 | ||
| 4408 | [Fjoi 2016]神秘数 | 主席树 |
| 同4299 | ||
| 4415 | [Shoi2013]发牌 | 线段树 |
| 转化为每次查询第k大的问题 | ||
| 4443 | [Scoi2015]小凸玩矩阵 | 二分+二分图匹配 |
| 二分答案x，那么就要找到n-k+1个小于x的数。遍历a[i][j]，若a[i][j]<x则i像j连一条边，跑二分图匹配即可。 | ||
| 4448 | [Scoi2015]情报传递 | 树链剖分 |
| 应该挺裸的 | ||
| 4455 | [Zjoi2016]小星星 | dp |
| 状压dp+容斥，神题。即记dp[i][j]表示考虑了以i为子树的映射情况，且i号点映射到原图中的j号点的方案数。但这个DP是有问题的，因为你可能会把多个树上的点映射到图中的同一个点上去，于是我们考虑容斥。设dp[S][i][j]表示只将树上的点映射到集合S的方案数，那么再在每一次计算时乘上一个容斥系数即可。 | ||
| 4503 | 两个串 | FFT |
| 4259的简化版 | ||
| 4515 | [Sdoi2016]游戏 | 树链剖分+李超线段树 |
| 会这两个前置技能，大力码就可以了 | ||
| 4516 | [Sdoi2016]生成魔咒 | SA |
| 忘记怎么写的了，代码倒是跑的挺快的。讲道理SAM也能做。 | ||
| 4517 | [Sdoi2016]排列计数 | 数学 |
| 简单错排问题 | ||
| 4518 | [Sdoi2016]征途 | dp |
| 斜率优化dp | ||
| 4520 | [Cqoi2016]K远点对 | kdtree |
| 裸 | ||
| 4523 | [Cqoi2016]路由表 | trie树+单调栈 |
| 建一棵trie树，点内存插入时间的编号。每次查找的时候维护一个单调上升的序列，最后统计序列内有多少点在l~r区间内 | ||
| 4537 | [Hnoi2016]最小公倍数 | 分块 |
| 按照a分成M^0.5块，然后每一块按照b排序。这样查询的时候把所有当前块之前的路径按b排序扫一遍，当前块中的路径暴力插入还原。用并查集维护即可。 | ||
| 4538 | [Hnoi2016]网络 | 树链剖分+暴力 |
| 暴力的一批 | ||
| 4542 | [Hnoi2016]大数 | 莫队 |
| 题解http://www.cnblogs.com/Ngshily/p/5409409.html | ||
| 4547 | Hdu5171 小奇的集合 | 矩阵 |
| 显然每次用最大和次大相加，类似斐波那契了，要特判原先有负数 | ||
| 4551 | [Tjoi2016&Heoi2016]树 | dfs+并查集 |
| 先dfs把最后的并查集求出来，让每个代表及的点成为并查集的根，到这处理询问，询问的就是这个点的集合的根，去掉标记就是把x和x的父亲连起来 | ||
| 4552 | [Tjoi2016&Heoi2016]排序 | 线段树 |
| 二分答案，把小于答案的看成0，大于答案的看成1，用线段树区间修改模拟操作 | ||
| 4553 | [Tjoi2016&Heoi2016]序列 | CDQ分治+dp |
| CDQ分治优化dp，好题！ | ||
| 4554 | [Tjoi2016&Heoi2016]游戏 | 二分图匹配 |
| 裸 | ||
| 4562 | [Haoi2016]食物链 | dp |
| noip难度 | ||
| 4563 | [Haoi2016]放棋子 | 数学 |
| 方案数等价于所有障碍都在对角线上，本质是个错排问题 | ||
| 4566 | [Haoi2016]找相同字符 | SAM |
| 裸 | ||
| 4567 | [Scoi2016]背单词 | trie树 |
| 题意杀，读懂了应该一波贪心就没了 | ||
| 4568 | [Scoi2016]幸运数字 | 线性基 |
| 倍增维护线性基，要会线性基合并 | ||
| 4571 | [Scoi2016]美味 | 主席树 |
| 把trie树上的区间放到主席树上查询，就可以处理+一个数了，即区间整体偏移 | ||
| 4590 | [Shoi2015]自动刷题机 | 二分 |
| 普及组题 | ||
| 4591 | [Shoi2015]超能粒子炮·改 | 数学 |
| 推式子，https://blog.sengxian.com/solutions/bzoj-4591 | ||
| 4602 | [Sdoi2016]齿轮 | dfs |
| 爆搜zz题 | ||
| 4604 | kth maximum number | 模拟 |
| 照题意暴力即可，升级版4605 | ||
| 4627 | [BeiJing2016]回转寿司 | 线段树 |
| noip难度 | ||
| 4636 | 蒟蒻的数列 | 排序 |
| 把操作离线，单独考虑每一个区间即可，noip题 | ||
| 4644 | 经典傻逼题 | 线性基 |
| 将边权异或到点上，这样问题就转化成了选择若干点使得他们的异或和最大 至于每次添边时询问，线段树分治即可 |
||
| 4653 | [Noi2016]区间 | 线段树 |
| 将所有区间按照长度排序，按长度从小到大枚举每个区间，在线段树上对其标记，如果线段树上已有一点被 m m 个区间覆盖，则从小到大删除区间，每次更新答案。 |
||
| 4689 | Find the Outlier | 高斯消元 |
| 裸 | ||
| 4690 | Never Wait for Weights | 并查集 |
| noip难度 | ||
| 4719 | [Noip2016]天天爱跑步 | 线段树+DFS序 |
| 推荐题解http://www.cnblogs.com/TheRoadToTheGold/p/6677435.html，把一条路径分成向上的和向下的，可以计算得可以统计答案的深度，用dfs序来限制答案在子树内 | ||
| 4720 | [Noip2016]换教室 | dp |
| 有点意思的noip题，多的不说了 | ||
| 4721 | [Noip2016]蚯蚓 | 堆 |
| 开三个队列，第一个队列储存没有被切得蚯蚓，第二个队列储存被切过得前一半蚯蚓，第三个队列储存被切过的后一半蚯蚓。 | ||
| 4730 | Alice和Bob又在玩游戏 | SG函数 |
| 这道题emmm，要求的是以i为根的子树的sg值，考虑暴力求法，再用trie树合并优化一下。 | ||
| 4736 | 温暖会指引我们前行 | LCT |
| 裸 | ||
| 4755 | [Jsoi2016]扭动的回文串 | Hash |
| 写了一堆二分+hash乱搞 | ||
| 4771 | 七彩树 | 主席树 |
| 先考虑怎么用主席树求距离不超过k的节点个数，然后先假设每个点的贡献是1，那么同色两点对于其lca的贡献就要-1，把dfs序记到set中，修改的时候注意一下就好了。 | ||
| 4802 | 欧拉函数 | 素数测试+质因数分解 |
| MillerRabin+PollardRho模板题 | ||
| 4808 | 马 | 二分图匹配 |
| 黑白染色建图 | ||
| 4813 | [Cqoi2017]小Q的棋盘 | dp |
| 记f[i][j]表示在i的子树里走j步最多能走多少个点。实际上的决策一定是先进一个i的儿子节点的子树，然后出来，再进一个子树，再出来……最后进一颗子树，也许还会出来。枚举在外面走多少步，转移到最后进去的子树即可。 | ||
| 4818 | [Sdoi2017]序列计数 | dp |
| 矩阵乘法先求没有素数的情况，最后加上即可 | ||
| 4832 | [Lydsy1704月赛]抵制克苏恩 | dp |
| 期望dp，写记忆化方便点，比较水的 | ||
| 4836 | [Lydsy1704月赛]二元运算 | FFT |
| 分治FFT | ||
| 4869 | [Shoi2017]相逢是问候 | 数学 |
| 扩展欧拉定理的应用，https://blog.sengxian.com/solutions/bzoj-4869 | ||
| 4887 | [Tjoi2017]可乐 | 矩阵乘法 |
| noip难度 | ||
| 4922 | [Lydsy1706月赛]Karp-de-Chant Number | dp |
| 类似3709，题解https://blog.csdn.net/PoPoQQQ/article/details/73500034 | ||
| 4923 | [Lydsy1706月赛]K小值查询 | 平衡树 |
| 很强的思路，对[1,k]的数不管，对于[k+1,k*2]暴力重新插入，对于[k*2+1,INF]的树打标记。不难发现一个数字最多被插入log次，因此复杂度十分优秀 | ||
| 4945 | [Noi2017]游戏 | 2SAT |
| 先dfs枚举x地图，然后就可以建图跑2SAT了 | ||
| 4950 | [Wf2017]Mission Improbable | 二分图匹配 |
| 求每一行和每一列的最大值，遍历，若i行的最大值=j列的最大值，从i向j建边。最后跑二分图匹配，注意0的情况 | ||
| 4952 | [Wf2017]Need for Speed | 二分 |
| 数学题+二分 | ||
| 4953 | [Wf2017]Posterize | DP |
| 貌似是贴的，自己写的超时了…，题解http://www.lydsy.com/JudgeOnline/upload/7sol.pdf | ||
| 4956 | [Wf2017]Secret Chamber at Mount Rushmore | 传递闭包 |
| 求每两个字符间能否转移，然后暴力判断即可 | ||
| 4972 | 小Q的方格纸 | 前缀和 |
| 构造一个梯形的前缀和和一个矩形的前缀和，乱搞即可 | ||
| 4974 | [Lydsy1708月赛]字符串大师 | KMP+bitset |
| 考虑这一位是不是之前循环节的一部分，是的话已经填好了，不是的话不能填会匹配到fail链上某个点的字母，用bitset压位即可 | ||
| 4975 | 区间翻转 | 正序对 |
| 可证一次操作都会使正序对数和逆序对数互换且顺序对奇偶性发生变化，最后正序对数为0，所以若顺序对数为偶数，先手必败否则必胜 | ||
| 4976 | 宝石镶嵌 | DP |
| 若n – k > (log(最大值) / log(2)，答案即为所有数or的结果，否则dp直接转移。 |
||
| 4989 | [Usaco2017 Feb]Why Did the Cow Cross the Road | 树状数组 |
| 先统计总的逆序对数，每次暴力用树状数组旋转即可 | ||
| 4990 | [Usaco2017 Feb]Why Did the Cow Cross the Road II |
LCM |
| 转化为最长公共前缀 | ||
| 4991 | [Usaco2017 Feb]Why Did the Cow Cross the Road III |
CDQ分治 |
| 三位偏序裸题 | ||
| 4992 | [Usaco2017 Feb]Why Did the Cow Cross the Road | spfa |
| 一个点拆成走了3k,3k+1,3k+2步3个点，建边，最短路 | ||
| 4993 | [Usaco2017 Feb]Why Did the Cow Cross the Road II |
LCM |
| 转化为最长公共前缀 | ||
| 4994 | [Usaco2017 Feb]Why Did the Cow Cross the Road III |
树状数组 |
| 二位偏序稍加改动，a先从小到大排序，统计a[j]<b<b[j]的个数 | ||
| 5016 | [Snoi2017]一个简单的询问 | 莫队 |
| 神题，https://blog.csdn.net/blue_cuso4/article/details/77940744 | ||
| 5018 | [Snoi2017]英雄联盟 | dp |
| noip难度dp | ||
| 5020 | [THUWC 2017]在美妙的数学王国中畅游 | LCT |
| LCT维护泰勒展开了解一下 | ||
| 5037 | [Jsoi2014]电信网络 | 网络流 |
| 最大权闭合子图 | ||
| 5039 | [Jsoi2014]序列维护 | 线段树 |
| 同1798 | ||
| 5052 | 繁忙的财政官 | 繁忙的财政官 |
| 同2221 | ||
| 5055 | 膜法师 | 树状数组 |
| 先离散，然后就是noip模拟题 | ||
| 5056 | OI游戏 | spfa |
| noip2017D1T1就想到了这题，题目要求求0~所有点的最短路径树的数目， 就可以直接算出0~所有点各自的最短路的数目， 然后乘起来就是答案。 |
||
| 5077 | [Ctsc2016]时空旅行 | 线段树 |
| http://www.acyume.com/archives/2511 | ||
| 5083 | 普及 | RMQ |
| 这个乱搞的，10s卡过，就不说了 | ||
| 5084 | hashit | SAM |
| 建trie树，在dfs时打log，回溯把sam还原即可 | ||
| 5091 | [Lydsy1711月赛]摘苹果 | 数学 |
| 妙啊，http://www.dtenomde.com/2018/03/author=jiangyutong/article=1216/ | ||
| 5092 | [Lydsy1711月赛]分割序列 | 高维前缀和 |
| 首先我们设a[i]表示b的异或前缀和，那么我们就是要对于每个i，求max(a[j]+a[i] xor a[j])。 从高位到低位贪心地想，如果a[i]的第k位是1，那么无论a[j]的这一位是什么，对答案的贡献都是2^k。 若a[i]的第k位是0，那么如果a[j]这一位是1，贡献就是2*2^k，否则贡献为0。 那么我们可以先预处理出tim[s]表示最小的i使得a[i]&s=s（即你可以多一些1但不能少），然后对a[i]从高位到低位进行贪心，看每一位0是否能找到一个j使得a[j]的这一位是1即可。 |
||
| 5093 | [Lydsy1711月赛]图的价值 | NTT+第二类斯特林数 |
| https://blog.csdn.net/Charlie_jilei/article/details/80126866 | ||
| 5105 | [CodePlus2017]晨跑 | 数学 |
| 普及组第一题难度 | ||
| 5106 | [CodePlus2017]汀博尔 | 二分 |
| noip题 | ||
| 5107 | [CodePlus2017]找爸爸 | dp |
| 有一点点难度的dp | ||
| 5108 | [CodePlus2017]可做题 | dp |
| 考虑暴力dp，把一长段未知的一次dp出来 | ||
| 5109 | [CodePlus 2017]大吉大利，晚上吃鸡！ | dijkstra |
| 水过的，不说了。 | ||
| 5110 | [CodePlus2017]Yazid 的新生舞会 | 线段树 |
| 线段树维护一些神奇的东西，http://www.cnblogs.com/CQzhangyu/p/7906099.html | ||
| 5117 | [清华集训2015]V | 线段树 |
| 历史最值问题，见国家集训队2016论文集之《区间最值操作与历史最值问题》 | ||
| 5120 | [2017国家集训队测试]无限之环 | 费用流 |
| 利用流量守恒模拟欧拉回路，http://www.cnblogs.com/zhouzhendong/p/8036439.html | ||
| 5127 | [Lydsy1712月赛]数据校验 | 模拟 |
| 合法的区间中所有长度为2的区间必然满足条件,所以相邻两个数字之差的绝对值必然满足条件.显然满足这个条件那么所有子区间都满足条件. | ||
| 5131 | [CodePlus2017年12月]可做题2 | 数学 |
| 第k项（ai+bx,l<=x<=r）的系数a,b，是斐波那契数列中的两项，可以通过矩阵求得。
然后就是解同余方程。 |
||
| 5132 | [CodePlus2017年12月]火锅盛宴 | stl |
| 数据结构搞一团 | ||
| 5133 | [CodePlus2017年12月]白金元首与独舞 | Matrix-Tree |
| 先预处理出：从每个已决策点，一直走下去会走到哪个未决策点（我们将最外面看作一个大的未决策点）。可以用拓扑排序搞定，若有环则无解。 然后我们枚举每个未决策点的四个方向，看一下一直走下去会走到哪个点，在新图中从这个点到终点连一条边。得到新图的出度矩阵和邻接矩阵，求出|出度矩阵-邻接矩阵|即可 |
||
| 5136 | [CodePlus2017年12月]可做题1 | 模拟 |
| 显然一个方阵是巧妙的当且仅当它的所有 2 阶子方阵都是巧妙的。 | ||
| 5140 | [Usaco2017 Dec]A Pie for a Pie | spfa |
| https://blog.csdn.net/icefox_zhx/article/details/79689941 | ||
| 5141 | [Usaco2017 Dec]Barn Painting | dp |
| noip难度 | ||
| 5142 | [Usaco2017 Dec]Haybale Feast | 优先队列 |
| 对每个b，维护一个最禁的a，判断是否符合即可 | ||
| 5152 | [Wc2018]通道 | dfs |
| 10次迭代水过 | ||
| 5158 | [Tjoi2014]Alice and Bob | 贪心 |
| 忘记了。https://blog.csdn.net/qq_35914587/article/details/79775421 | ||
| 5165 | 树上倍增 | lca |
| 这些点的lca为dfs最大和最小点的lca | ||
| 5166 | [HAOI2014]遥感监测 | 贪心 |
| 一边加入圆一边删没用的圆，正确性我也不知道 | ||
| 5170 | Fable | 模拟 |
| 同3580 | ||
| 5182 | [Baltic2016]Bosses | dp |
| noip难度，直接枚举根就win了 | ||
| 5205 | [CodePlus 2018 3 月赛]白金元首与莫斯科 | dp |
| 比较难♂的状压dp，从前面后面各做一次轮廓线dp，考虑的东西比较多 | ||
| 5212 | [Zjoi2018]历史 | LCT |
| 首先猜出贪心结论，用lct维护 | ||
| 5215 | [Lydsy2017省队十连测]商店购物 | dp |
| 容斥原理，详见http://blog.leanote.com/post/okami/%E7%9C%81%E9%80%89%E5%8D%81%E8%BF%9E%E6%B5%8B-Day-1 | ||
| 5285 | [Hnoi2018]寻宝游戏 | dp |
| 考虑把所有运算符写成一个01串，令所有|运算为0，&运算为1，第i位上的0/1代表第i个数前的运算符。 可以发现，能使结果为1的运算符串为所有字典序小于当前位构成的01串的01串。 |
||
| 5321 | [Jxoi2017]加法 | 二分 |
| noip难度，转化为验证是否能用 ≤k 个线段覆盖掉 ti 数组 | ||
今天的题解就到这里，感谢您的收看，祝您心明眼亮，再见。