因为刷题实在太少了，所以六月要多刷点题目。
Upd:
因为种种奇怪的原因加上一直在考试，六月刷的题远不如计划。
新高一来了呢。
由于题目变多后查询愈加不方便，加之杂题式的整理针对性不强。
这篇博客咕了。
以后题解会往专题的博客里扔。
已完成
[HNOI2012]射箭
半平面交，斜率单调递增不去重。
[ZJOI2008]瞭望塔
半平面交，结论：直线必过端点。
[NOI2010]航空管制
两个限制，第一是相对关系的限制，第二是时间，那么我们可以边时光倒流边更新拓扑序，每次把满足时间和拓扑关系的点随便弹出一个即可得到可行解。而对于第二问只要每次确定一个点，一直不弹它直到不得不弹，那么当前时间就是这个点的最优解。这样就是一个的做法。来自。
[NOI2010]海拔
考虑到一定是左上角一块,右下角一块，只有分界线上的有费用，那么转化成最小割，因为这个分界线就是割掉后原图恰好不连通的一条线。跑当前弧优化的即可。
因为是一张网格图，那么显然是个平面图，转化成对偶图之后跑即可，复杂度。
[ICPC-Beijing 2006]狼抓兔子
同上。
[NOI2010]能量采集
莫比乌斯反演之后发现可以两个数论分块做。时间复杂度
似乎可以把的式子换成，这样就是求：
这样这个式子是的了，杜教筛处理的前缀和好像可以做到的级别，所以数据可以加到。
[JLOI2013]赛车
运用半平面交的另一种思考方式：
可以发现一条直线被纳入答案当且仅当它属于这个半平面交的一部分。
但是这道题还有很多恶心的小细节：
对于重合的直线应该一起纳入答案，不能去重，所以要更改一下函数的判断条件。
根据题意，因为速度和初始位置都是正的，那么解必须在第一象限，所以要加几个框框。
即便直线不在半平面交但是在的时候依旧可能取最大值，所以还要特判一下。
G.Two Merged Sequences
求一个划分，使一个序列分成一个单调递增子序列和一个单调递减子序列。
考虑贪心，若一个点只能接在某个序列上，那么直接接，若两个都可以接，那么比较下一个点与这个点的关系，若那么把接在上升序列上，否则接在下降序列上。以为例，假设接在了下降序列上，那么不仅不能接在下降上，而且接在上升上所用的代价还是没有变，显然会更劣，所以贪心正确性显然。既然之前每一步采取的都是最优决策，那么如果有一个点没有序列可以接，显然无解。
我最开始的贪心思路依赖于这么一句话“若能接在上升序列上就接”，显然它了，#15WA掉了，但如果是赛制应该能混很多分，所以错误的贪心在没有思路的时候还是要上。
[NOI2012]美食节
费用流。对于这种费用与被增广时间有关的网络流问题，可以考虑分层图，菜,流量为，菜厨师，最开始费用为，表示这道菜作为这个厨师最后做的菜所耗的费用，之后等这个“该厨师最后一个做这个菜”被用过了，我们就再次增加“该厨师倒数第二个做某个菜”的节点，依旧是菜厨师，费用变成，以此类推。因为是边加边做，那么点数是,边数是，增广次，那么复杂度就是,人话来说就是能过。
[SCOI2007]修车
上题的弱化版，唯一要注意的是输入的是反的，样例还是。
[HNOI2016]最小公倍数
前言：这道题是我觉得自己刷题量严重不够的原因之一，如果之前我做过这道题目或者动态图应该就可以切了,当时我发现了就是求一个版本的并查集，满足与的双重要求，但是不知道怎么搞，一直想着归程。感觉这道题蛮经典的，写详细一点吧。
首先转化一下题意，当且仅当路径中,,且路径中所有,时，是的。
连通性可以用并查集来维护，问题是怎么找到一个合法的版本。对于两个限制，可以想到分块，整体第一维排序，块内第二维排序。那么我们把边按照排序后，让数组在块内按照有序。对于询问，就按把它扔进它所在的那个边集块里然后一个块内的询问按照有序。之后对于每个块(设为第块)的询问，对之前块维护一个，当前块内暴力，然后回溯。那么程序写起来就是：
：{
}
一些小细节：
并查集启发式合并保证跳和回溯的复杂度。
因为询问中有且的恶心数据，所以要特判，或者是一开始把都赋值成。
关于复杂度分析和块的大小：不是很懂为什么很多人说最优秀，第一个处理的块的时候，共需要次操作，块内暴力要做次操作，两种操作都要一次，复杂度,所以总复杂度,当的时候取理论最优秀。(虽然实际上数据原因取反而会更快一点，但是取理论最优也只要,时限反正绰绰有余。)
[BJWC2010]严格次小生成树
从刘汝佳的书上看见的题目，正好在看见了就做了。根据生成树的性质，第小生成树一定由第小生成树“交换”一条边得来。所谓交换，就是找一条不在生成树上但两点都在树上且这两点间的路径上边权最大值<=该边的边，用这条边替换掉那条路径中最大的边，即可的到一颗非严格小生成树。怎么做到严格呢？只要倍增/树剖维护最大值的时候顺便着维护下次大值即可。总时间复杂度。
[八省联考2018]林克卡特树lct
首先转化一下题意：求树上条不相交链的。但是这里要特别注意，在此题当中，一个点也算是链(这就是那个边权为的边存在的意义，可以把单个点当做链接上去。)
然后就是一个树形了，设表示点，入度为，共有条链的最优解，转移一下就可以了，特别要注意一下转移的顺序。这样可以。
以上大概就是我现在能在考场上拿的分数了，因为如果不知道题解我估计想不到它是个凸的(当然，说不定我闲的蛋疼输出一下呢。)，既然是凸的那么就可以二分了。但是这里还是有细节：数组的初值问题。首先呢，观察,发现初值就是，因为这个状态对转移没什么影响。的话初值要是,因为如果一个叶子节点显然不能进行的转移:如果只有一个点，网上走一格是要多算一条边的，而如果已经能拼成链，网上走就是免费的，甚至在两个拼在一起的时候还能使链数量。再来看,应该初值是,即和之前说的一样，把它当做一条链来处理(入度为的无向自环),这么做的唯一作用这个转移：
一个入度为的节点和一个入度为的子节点拼在一起。
但是单个节点也可以和入度为的子节点拼在一起，付出一次的代价(根据的规则，要把这个点接在子树已经拼好的链上。)
然后记得开,二分的开大点，就可以了这道题了。
[八省联考2018]劈配
最大流问题。
首先对于第一问，就是一个动态加边的过程，伪代码如下:
注意这里判断是否有增广路不要连了边之后,而是假设它有这些边，在中特判，这样复杂度就是级别(因为所以能过)，不然是级别。
第二问的话类似，伪代码如下：
同样的，第二问判断连了以后是否有增广路也不要连上硬搞，这样边总是级别的，那么复杂度也是级别的。
两问的代码可以合并，但特判会变多，个人习惯还是拆开。
[POI2009]WSP-Island
题意：给定一个凸多边形(1->n顺时针)，点之间两两有边可以走，并且可以在边的交点“转弯”换路，现在规定一些边不能走，求到的最短路。(点<1e5,限制<1e6)
很考验思维的一道题啊,果然是的画风。因为是顺时针给出，我们设每条边编号较大的端点为,较小的为。首先如果之间有边那么距离显然，如果没有的话，因为可以转弯的关系，的最短路就是每条合法边(方向)的半平面交(因为三角形两边之和大于第三边，可以画图手玩)。这样就有一个的算法。
这个是边数，我们考虑优化一下。这个其实很简单了，因为半平面交是左半平面，且每条直线只有原凸多边形内的部分是有效的，那么在某条合法边右边的所有边其实都是无效的，也就是说对于每个,我们只保存它最小的合法即可。这样就只有条边了。因为要这些限制，复杂度是的。
吐槽：为什么没有数据范围啊啊啊啊，为什么不同级啊啊啊啊。
[POI2009]LYZ-Ice Skates
很有趣的一道题目啊。每次给定一些要求，使一个区间的“”加减一个数，即要求你通过选取一些放置方法，使这段区间的权值和加上一个数，问能否找出一组放置方法，满足所有这些区间的要求，并且单个位置上的权值不超过。
数据范围 :，保证每次
部分分做法：线段树优化连边之后跑匈牙利/,边数是那么复杂度是
考虑一下这题相对于一般的二分图特殊的地方在哪里，就是这个的长度是固定的，那么这里就是突破口。思考一下什么时候无解，设每次限制形如,表示将的和加上,那么我们使这个点的权值加上,表示一段区间的之和，当且仅当的时候无解。试着证明一波，因为一样长，那么把区间排序之后所有的都单调递增。有一种贪心策略来填补这些“的限制”，对于每个点，他的取值都尽量往大了取，并塞给包含它的区间中最靠左且所要求的的没填满的那个区间，因为每个区间一样长，所以这样做显然最优，那么当不存在的时候一定可以构造出一组解。
这个贪心策略对应到网络流上就是增广路是从“左”到“右”依次增广的，这就是特别之处。当这么增广都满不了流就是无解，和贪心策略也是对应的。
但是这个式子还不好维护，我们移一下,相当于就是一个初值全是的序列，每次单点加/减，询问序列的最大子段和是否小于等于一个常数，只要开个线段树维护一下就好了。
后续：显然这道题还有很多可以模改的地方，比如是可以输出方案的。
[POI2009]KAM-Pebbles
转化一下题意，每堆石子可拿的范围是，当所有能拿的范围都是的时候就是输。注意到一个性质：我们把堆拿了个之后，堆能拿的范围增大了。那么我们把这些“范围”看做一堆堆石子，相当于你可以每次可以把第堆石子移动到第堆，或者丢掉第堆的一部分。这就是一个经典的阶梯博弈了，只不过此题中的阶梯反了过来，只要一下做奇数即可。
防止自己忘了，写一下阶梯博弈的证明:设阶梯从低到高编号，那么除了第级不能扔，第级的球都能扔到第(那么奇数阶梯肯定全部是自由的),那么对于偶数阶梯上的球，如果选手把它上面个球移动到下面的奇数阶梯上，他的对手一定可以原封不动的再交给下面的偶数阶梯，而当移动到了级时就动不了了，所以偶数阶梯不会有任何影响，奇数阶梯是个游戏。
[NOI2017]游戏
问题。
首先乍一看感觉好像是，但其实可以这么思考，“不选”“选”=“”。这里还有问题，就是枚举复杂度不对。但是我们发现“选”“选”“选”,那么只要枚举即可，总复杂度。
小细节：
连变成的的时候如果发现没有这个要的选项，说明当前这个不能选，直接连向。
要清干净，不要因为的和没清调(比如我)。
[国家集训队]middle
丽洁的题啊。题意：给定一个序列，求的区间的最大中位数，中位数的定义是取上整。
因为之前我出过一道类似的题目，关键点也在偶数序列中位数的定义上。于是很快就能想到整体二分赋值的做法，然而丽洁很过分的强制在线。
想了很久想到一个主席树套二分的做法，因为中位数只会在这个数当中取到，我们只要用维护个版本的数组，然后每次二分中位数，在对应版本上查询是否存在使大于等于的数的个数小于的数的个数，然后下判断二分方向即可。把的赋值成,的赋值成,那么就是询问是否存在使。
那么可以把它分成三段:的最大后缀的最大前缀，用主席树维护这三个东西，时间复杂度。
然后我就发现我不会维护区间最大前/后缀。。。。(要是考试推到这里发现打不出来可真的要骂人了)。赶紧学了一波，大概就是并不能像维护最大子段和一样直接取,而是把多余的直接割掉，如果就割成和在分治下去，用一边的和另一边的拼起来，割成&&停止递归。
[SDOI2009]晨跑
费用流水题，拆点限流上板子。
[HEOI2016/TJOI2016]排序
题意：给定一个的排列，每次(递增递减),求最后第位的值。
很有趣的一道题，自己根本想不到正解，于是厚颜无耻的看了题解（好像之前谁讲过这题来着？）
离线询问，二分答案，把的都赋值成,其他是,的排序是可以用线段树区间推平来做到的，那么排完后检查一下第位是否是,即可知道这一位的真实值是否,然后接着二分即可，复杂度。
双亲数
纪念我又% 真的不要手顺啊。。。
CF739E Gosha is hunting
网络流总算做出一点感觉了呢，的题挺妙的。
题意：有个小精灵，你有个精灵球和个大师球，精灵球对精灵有的概率抓捕成功，大师球有的概率抓捕成功，可以往一个精灵身上丢两个球，但一个球最多只能抓到一只精灵，求最大期望抓捕精灵个数。
首先这显然是个二分图，如果扔一个球，收益就是,否则是。这就是这个题的突破口，即费用只和扔一个球还是两个球有关，和顺序无关。看到“增广时间影响费用”我们考虑类似分层图的思想建图：
流量为，费用;
小精灵 流量为,费用是。
最后关键的一步：小精灵，两条流量为的流，第一条费用,第二条费用,这样增广的时候一定会先增广的那条，表示第一次扔球无额外代价，之后有机会再增广那条要付出额外代价的流。
然后直接跑最大费用最大流即可。
：
网络流边集数组是两倍，数组开小了。
实数最短路在更新的时候要开，不然可能把恰好等于的丢进去从而死循环。
因为,时限,所以费用流可过。然而看了题解之后发现，这两个函数都是凸的(感性理解一下，先用概率大的后用概率小的),于是可以二分套二分给它优化到级别。
[NOI2017]蔬菜
很妙的贪心，首先正着贪心显然是错的，因为如果有的大的可能比较耐坏，而小的不耐坏，这就是问题。
想不出来只能看题解，然后感叹巨佬们的智慧。
时光倒流一下，问题变成本来什么都没有，每次丢进来一些蔬菜，每个时间可以在已经丢进来的蔬菜中选一些。这的时候无脑拿大的显然是对的了，因为以后能拿现在剩下的，现在不能拿以后的（正着来的话以后不一定能拿现在的，因为会有过期的问题）。这部分开个堆模拟就可以了。
之后就是处理多组询问的问题了，考虑如何从推过来,这里有个结论：拿的蔬菜是的一个子集。思考为什么，因为能拿的蔬菜一定可以拿，而且可以通过调整较小的决策就可以做到主动选择这个子集，所以每次就把上一次答案集合弹出最小的一部分即可。
但是弹多少呢？假设共拿了个，那么要舍弃的就是。这里想了好久，其实还是那句话：倒着来以后能拿现在剩下的，现在不能拿以后的，那么最多可以把第次所拿的填到前面次里面。
最后就是代码实现的问题了，这里还要注意一下和的情况，真的贼恶心。然后学到了最好少打“补丁”和特判，想办法把情况搞少一点很重要。
记录一下自己的脑抽时刻吧（算每个蔬菜在刚出现的时刻有多少个）：
1 | if(x[u])q.push((vegtable){i,s[u]+a[u],c[u]%x[u],u});//当整除的时候直接变成0。。。 |
1 | if(x[u])q.push((vegtable){i,s[u]+a[u],(c[u]-1)%x[u]+1,u}); |
(vegetable好像拼错了)
[NOI2016]循环之美
数论与莫比乌斯反演神题。
前方高能。
首先根据定义，可以推出当且仅当存在的时候分数是个纯循环的
那么就有存在
于是就有,又因为要最简分数，又有
于是答案就是
考虑把提到后面，就是
对后面这个莫反一发：
那么原式就是
修改枚举是的多少倍。
把拆出来
令
因为,所以每个的值是一样的，也就是说,只要暴力处理以内的求了，而,所以显然可以接受。
那么原式就是
再设
这里只要处理,然后数论分块就可以拿了，这应该是考场上能搞到的分数。
然后考虑怎么快速处理:
:推到这里我了一下，想着直接把和乘起来，忘了只是积性而不是完全积性。
那么更改枚举项为,并枚举是的几倍，从而抹掉和的限制:
这里是最妙的一步，根据莫比乌斯函数的定义，只有的时候,那么可以往后扔一个:
之前说了，之前不能拆或者乘，是因为不是完全积性的，只有互质才能操作，而现在,我们就可以把扔到前面去：
我们把最初的式子提出来：
再看下现在后面这一块：
唯一不同的是变成了，变成了，于是我们定义：
就有：
边界是什么呢，盯着这个最初的式子：
当,无法递归，;
当,可以递归成，也可以看出
当,无法递归，,但是这个可以很大，我们杜教筛这个前缀和。
但是我始终不知道暴力枚举的约数递归算复杂度为什么是对的，即便它记忆化了(然而它就是对的)。
算的时候如果就不要递归了，不然会掉。
记忆化二元组的时候记得开，似乎对不上红黑树的接口。
[NOI2017]整数
我有生之年居然能秒掉一道NOI。
首先，为什么暴力模拟是不对的，就是首先第位,然后第位，这样复杂度就上天了。
思考怎么优化，假设把拆成二进制，当我们每次把一个加上去：
不进位直接加
往左找到第一个,然后把这个变,并把一路上的都变成。
同样的减就是:
不退位直接减
往左找到第一个,然后把这个变,并把一路上的都变成。
于是开个线段树，维护区间最靠近低位的(用区间最值，和差不多)，然后维护区间修改即可，复杂度是，可以拿。
然后发现根本不用维护每个，只要知道一段表示的数，就 可以知道这一段了，那么可以直接压位，压位最优，因为，并且不用开(比较怂还是开了),之后把它当进制做就可以了。
进制的进/退位和进制类似，就是维护往高位数第一个“不满”的位置（进位），和第一个非的位置（退位）即可，方法和二进制类似。
当然这道题还是很恶心，因为数字是从右往左权重一次递增，线段树又是从左往右，打反了好几次。
[POI2009]SLO-Elephants
之前考试遇到过了，首先变换就是让一个环转一圈，其中主动的那个点算了次，其它的各算了次，那么就有两种策略，第一种就是直接转环里最小的，第二种就是花费转进来一个点，之后用这个点转一圈，处理出环之后线性扫即可。
[POI2011]LIZ-Lollipop
题意：给一个只有和的序列，每次询问有没有一个子串的和为并输出子串位置。
很精妙的一道题。首先发现一个性质，一个子串可以拼出所有且与它奇偶性相同的,如果两端有直接去掉一个即可，否则就抹掉两个。
所以我们只要处理处最长的奇数串和偶数串即可，如果最长的奇数串都拼不出一个奇数那么就无解，偶数同理。然后离线询问并从大到小排序，这样每次两个串都是单调缩短的，总复杂度是排序的。
[POI2011]ROZ-Difference
题意：给一个字符串，求其中的一段，使得出现次数最多的字符与出现次数最少的字符的出现次数之差最大
为数不多的完全不看算法标签和题解切掉的。
一道优雅的暴力题。因为看到字符集很小，可以直接暴力枚举谁是最大谁是最小，因为显然这一段两个端点都是“最大”的那个字符，所以只要枚举最大的字符的位置即可，这样复杂度就是,是每次枚举最小的字符所要的复杂度，而枚举最大字符加起来是一个。
但是写完发现连样例都过不了。因为这不是简单的最大连续子段和，还要至少选一个“最小的”，那么贪心的时候还要判断有没有拿最小的，拿了才能更新答案，而且还有一些其他的转移，比如本来这段没有“最小”，强行往两边扩找到一个最小的也是可行的。
还有就是如果一段为负就扔掉为什么是对的，为什么不会影响“拿最小变可行”的操作。因为如果一段是负的显然是因为这一段至少有俩的（不然至少是）,此时即便因为扔了它而找不到也会在之后因没有而往两边找的时候找到一个,和选两个加一个本质是一样的。
[POI2011]ROT-Tree Rotations
线段树合并板子题。显然只要局部最优全局就最优，那么递归处理即可，两个子树逆序对就是每次它们的权值线段树上左右儿子交叉相乘。
线段树合并复杂度证明：势能分析，只有重合的节点会对复杂度贡献,但每重合次节点总数就减少了,一开始共有个节点，那么复杂度就是。
合并的时候顺手垃圾回收一下。
[WC2005]友好的生物
之前做过一道差不多的[POI2011]ROZ-Difference，发现很小，想一个问题,我们给每个动物每个属性定一个符号，如果符号搞错了肯定没有搞对了优秀，比如,肯定大于,那么我们如果符号弄错了也没关系，会在之后符号正确的时候被更新,但是会发现后面那一项很恶心，符号错误的时候值会变优秀，所以我们考虑让这个符号永远是对的，再枚举其他符号，只要以这一项为关键字排序后维护前缀最小值即可，那么复杂度就是预处理的时候的,另外(-a-(-b))=(b-a),也就是说常数可以再卡掉一个,但是懒得写就算了吧，脑抽了，因为是有序数对，所以种都要枚举，枚举每一位的正负可以得到和，这样才能去掉绝对值。
[POI2011]DYN-Dynamite
二分答案之后就是半径为的树上覆盖问题了，可以用经典的贪心思路求解，只在不得不放的时候才放，维护要覆盖的点中里当前点最远的点和离当前点记录最近的半径点,当两者距离加起来就直接覆盖那个点，否则当最远的点距离的时候才在当前点上放点。
之前做半径覆盖的时候竟然忘了特判根还过了。。。之前不到极限不放是因为可以让父亲去覆盖，而对于根节点只要有一个没有覆盖的关键点就要在上面扔一个额外的点去覆盖。
[POI2012]STU-Well
很妙的一道题目，很容易想到二分答案，然后思考怎么判断：假设我们不考虑绝对值和。那么从左往右扫肯定是“能不减就不减”，只有在的时候我们才会通过减少使它“恰好合法”，不然不仅自己会更劣还可能影响后边的。那么从左往右作为绝对值的一半已经解决了，从右往左显然是一样的(可以假设从来没从左往右扫过，序列本来就长这样），再扫一遍即可
接下来考虑这个限制，我们从左往右枚举，可以发现就是一个字形，是顶点，在下面的不用管(因为我们之前以保证了它们之间距离合法)，只有在它上面的才有代价，就是这些点到的垂直距离，且很容易发现在顶点右边部分，如果在下面,就不可能在上面，左边部分同理，而且这个随着顶点移动还是单调往右的，维护一下即可。
脑抽：二分中直接修改了点的高度而没有备份。
脑抽：快读没开。
[POI2007]MEG-Megalopolis
当年娄底考过的的问题，现在发现就是个子树减，单点求值。。。
[Violet]蒲公英
题意：维护区间最小众数，强制在线。
维护区间最小众数和维护区间众数没有本质区别，但是众数是不可加信息，所以考虑分块维护，维护两个东西：
前块中数字出现的次数。
第到块的众数。
根据定义我们发现这两个数组都可以预处理出来。然后每次询问，只有两种可能，第一种是,第二种就是两边散块中出现的数字加上中间整块的出现次数成为了众数，用数组做个前缀和相减。
这种数组下标一堆中括号的程序一定要多用中间变量转一下，不然就会调到死还很难改。
[WC2011]最大XOR和路径
([题目链接]https://www.luogu.org/problemnew/show/P4151)
因为路径是一条简单路径加一堆环，然后可以发现这条简单路径是可以随意选取的，因为异或的性质可以直接被那些环“修正”回来，那么只要随便找一条简单路径然后把环都扔进线性基，询问这个路径的值在线性基中的最大异或和即可。
[POI2012]SZA-Cloakroom
题意：有件物品，每件物品有三个属性, , 。再给出个询问，每个询问由非负整数,,组成，问是否能够选出某些物品使得：对于每个选的物品，满足且。所有选出物品的的和正好是。
我们首先可以对物品和询问都按排序，这样可以单调指针抹掉的限制，这里是个典型的“收益比状态小很多”的背包,所以设表示当物品的为的时候的最小值，我们尽可能让变大，每次判断是否满足的限制。
[SCOI2016]幸运数字
因为线形基是可以支持的，因为中间重复的部分在第二次插入的时候就不会被插进去，所以我们只要使用倍增，每次询问不用倍增合并次线形基，而用的思想合并即可抹去一个。
总复杂度。
[BJWC2011]元素
把物品按价值排序之后从大往小插入线性基即可。但是为什么这么是对的呢？假设我们没有插入当前最大的，那么插入这个最大的只会从线性基中剔除一个即可，显然是更优的。(的数据范围纯属拿来恶心人的)
城市规划
求逆板子题。
令表示个点的无向连通图数目，表示个点的无向图，那么
组合数拆开移项：
定义三个多项式:
那么
我们要求的就是第项乘上。
[HNOI/AHOI2018]游戏
很精妙的一道题目。首先我们发现在两个门之间的部分是强联通的，直接暴力拓展可能是的，但是有一条性质：如果能到,一定不能到达,且能到达所有能到达的地方。所以即便是暴力，开门的次数也有可能是很少的，导致大部分人好像都是水过去的。
我们根据性质可以发现，如果先更新，那么到的时候就不必暴力开门，而是直接把暴力开过的门并起来即可，也就是说每个门只会被开一遍。那么对于每一道门，如果钥匙在左边，连边,否则连边，表示一个点不能到另一个点，然后按拓扑序更新即可做到。因为一门一边，且连接的是相邻两个点，所以显然是。
[CQOI2013]新Nim游戏
线性基。题意就是我们构造一个最大的集合，使该集合中任意一个子集异或起来不为。根据线性基的原理，这个集合的大小是固定的，那么只要贪心的从大往小往里插入即可，如果能够插入就不用花费用拿走，同样是恶心人的。
[HNOI2016]序列
只想到了的做法。考虑往右移动一格的新加贡献，就是注意到这个一段一段东西是可以前缀和的，需要注意的是最左边一段是不满的，也就是说我们找到最小值,的贡献要单独算，剩下的部分可以前缀和，即，这个是可以直接建完表后二分的，或者单调栈，但是不影响复杂度。
总复杂度是莫队的
原来我一直写了假的莫队，应该先加后减，右端点要比左端点更早右移，左端点要比右端点更早左移。竟然一直没出事。
构造表要,数组一天越界两次竟然都没出事。
[POI2007]BIU-Offices
题意：询问一个无向图的补图的连通块个数。
本质就是每次把序列与起来,直到全为止。一开始感觉可以垃圾回收配线段树合并做，后来发现没什么必要，只要开个，每次弹出队列，再把队首的与进去，把新变成且没被遍历的点再扔队列即可。复杂度,开了最优解第。
[TJOI2019]大中锋的游乐场
对于这种乘起来很小的题目，很容易想到分层图，把每个点拆成个点暴力最短路即可。
因为一直没看见是无向图还了几发。
[ZJOI2019]语言
首先发现我们可以统计与每个点联通的联通块的大小来计算答案，而一个以为中心的联通块的大小就是"经过它的链的并"，对于加链操作可以用树上差分来维护。然而我发现只会差分维护子树内信息而不会连通块信息。经过的点拨，其实只要对于链，在，上都扔两个，在上减去四个即可。接下来考虑统计贡献，我们发现如果按照序来一个个加点，设上一个加入的是每个新加的点的贡献就是，我们不用真的一个个加入，只要维护一个以序为下标的线段树，每次线段树合并即可。特别注意的是，还要加上第一个加入的点与最后一个加入的点之间的贡献，因为当他们不在一个子树的时候第一个加入的点到它们的贡献没有被算上。
所以我们要干的就是，维护以序为下标的线段树，然后每次合并，并用欧拉序求保证复杂度是一个即可。
因为闲的蛋疼了还想垃圾回收，结果一直挂挂挂。因为我很蠢的先一个线段树，在把子树往上并，这样垃圾回收用没有。只要先继承子树，在进行，空间就有了保证。另外最好在空间足够的情况下以保证正确率为第一目的。
[湖南集训]谈笑风生
拆成两个子问题分别搞一下即可，第一问很蠢，第二问就是每个点权值等于子树大小，询问一个点的子树内深度的权值和。很容易可以想到长链剖分，然后我发现不会维护前缀和，就打了个线段树合并，结果合并的时候下标忘了右移挂成.
每次插入维护前缀和的办法:维护前缀复杂度是的，转成后缀，复杂度就是的了。每次插入就在最后一个即可。
CF613D Kingdom and its Cities
裸的虚树,之前只会原理一直不会实现，其实构建虚树本质就一句话：里一直都是一条链。
CF727F Polycarp's problems
题意：给定一个数列，有正有负，多组询问，每次给定一个，求至少删去几个数使得任意位置的前缀和不为负。
很有价值的题。首先可以想到一个的,表示处理前个点，删了个点后的最大前缀和。然而无法处理多组询问，复杂度直接乘起来。
然后可以想到一个贪心，每次前缀和为负数就删去前缀最小值。复杂度。
之后我了很久，我的错误结论是：较大的删点几何必定是较小时候的子集。显然是的，因为大的比较能抗，幸亏数据多。
来看正解，我们思考每个正的数能帮我们往后抵消多少。这里有个贪心：能抵消小的先抵消小的，抵消不了也要用余力使它更小。因为删数不管大小代价都是一样的。那么我们用完了所有正数后剩下的数字就是我们要用抵消的。排序后从小到大做个前缀和然后对于每次询问_一下即可。复杂度是。
Upd:没什么时间，本来打算咕了，后来感觉还是得写，但只写意义较大或者很有意思的。
[AH2017/HNOI2017]影魔
题意：给定序列,对于每个点对,设的,若且，贡献,若或者贡献,每次给定区间，求区间内所有点对的贡献。
首先可以想到一个类似的的莫队做法，可以获得和暴力一个分数的好成绩。
然后我们发现，我们枚举不好搞，考虑枚举，然后求每个会给哪些算贡献，设前后第一个大于的为,那么就是的最大值，产生贡献,对于,我们考虑以作为中间元素的情况，对于,与匹配即可，同理对于，与匹配即可。我们把一个点对当成一个点的横纵坐标，那么每个点贡献权值为的单点、竖着的一条权值的点和横着的一条权值的点，每次查询想到于查询的一个正方形的权值和，因为是正方形，所以可以把竖线扳成横线，然后就是个简单的扫描线了。
推广：
这里其实线段加、正方形求和形成的特殊形式，考虑更一般的形式，二维加减与二维求和如何在离线下做到一个。
通过的讲解，我们可以对每个点维护一个的一次函数，其中是扫描线已经扫过的长度。当扫到一个权值为的矩形的下端的下一格，使这条边上所有点的,这个意义相当于给当前 扫描线上这条边施加一个“持续增加”的状态，到了上端再按照类似的方法取消掉这个状态即可，查询真实的权值就是查询区间的和乘上扫过的距离再加上区间。y
于是的序列那题就可以做到了，但是由于线段树和莫队的常数差异估计八成还跑不过。
CF799E Aquarium decoration
因为要求都是,最后的答案肯定是个加个还有个,最后再在剩下的集合中找几个最小的补满个的限制。
我们可以枚举必须拿的物品的个数，每次多拿一个该物品，必须拿的就都减少了,我们可以用线段树来维护剩下的“凑数集合”，相当于就是单点加减，求全局前小的和。
然而枚举有上界还要下界，还有一吨的细节和数据，所以尽管想出题解很容易，写出来可能还要点时间。
二分图
首先根据二分图的性质，我们知道如果有奇环，就不是二分图，反之就是二分图。考虑如何判断奇环，我们用带权并查集来维护连通性，但是每次连边被抽象成了并查集祖先之间的边，我们要保证的路径长度是奇数（和相同），所以求出和的路径长度来决定这条边是还是。
然后用线段树分治来解决，每次启发式合并并查集来支持撤销即可。复杂度是。
[BZOJ3489]A simple rmq problem
如果可以离线那么就是个莫队了，但是强制在线。于是我们考虑每个点只出现一次相当于上一次出现在左边，下一次在右边，那么每个点可以抽象成一个三维点,权值为,查询就是个三维空间最值问题，即可。
但是要特别注意最优化剪枝，不然会被卡。
[HNOI2011]卡农
题意:求中选择个不重的数异或起来为的方案数。
:设表示选择个的合法方案排列数，我们随便乱选前组成一个不重的排列，都有唯一确定的第个数，但是问题可以有不合法的两种解:前个数异或起来已经是,第个数没得选。必须选择已经在之前出现过的数。
显然第一种就是。而第二种就是。
其实是可以直接设表示组合数的，只不过题解里没人这么写：
两种写法都是的。
非完美算法
[CTS2019]田野
首先可以想到贪心，若两个凸包合并起来更优一定合并。但是我们会发现连样例都过不去。因为很多时候合并两个不会更优，但合并三个可能会更优，那么我们看到的时间限制想到随机化(...),当没有合并更优秀的两个凸包，那么随机两个凸包合并起来，再检查有没有优秀的两个凸包，反复下去。我的可以稳定的拿。
凸包,代码，导致这道题通过率0.9%。
外太空旅行
最大团问题，可以想到的状压,但是这道题出的是,明摆着让你乱搞。于是通过从学到的每次随机一个合法的人，并把他的敌人都扔进不合法集合，卡个时间即可。
非传统题
[NOI2010]成长快乐
题目链接(99pt)
提交答案代码过长可还行(辣鸡luogu)。
就是拿时间换分的题目啊，显然是的。
首先用余弦定理加求根公式写一个算交点的函数，然后：
手玩即可。
爆搜或贪心直接按体积从大到小拿。
随机化排列，每次一遍排列，依次把能吃的吃了，直到不能吃为止。
速度很小，虾速度很大而且垂直向下掉可以当做“接水滴”来做，反正题答，的数据即可。
这两个点很神奇，首先虾子不会动，而且他们构成一个数字三角形，设表示层的数组满足,而且设有层，满足,也就是说最优策略是跑到第层后每次的向上走一步,而且刚好走到最上面一层为止。那么可以直接的当成数字三角形一下即可。
垃圾点，过的时候贪心顺手切了。
无性质的点，目前已知的两个解法：
按照性价比拿，但是退火一个“出错”概率，出错的时候按照时间选一个最优的，或者拿性价比第二的，在一个晚上的努力后可以拿到。
修改性价比的定义，改成会优秀一些，可以拿到，然后把的次幂随便调一调就可以拿到。
，之前总差一点点，输出发现时间没有完全用完但是没有鱼可以吃了，感性理解一波，我们希望某些不高但是很近的鱼经过的时候直接被吃掉，以求填补那一点点差距。于是
1 | if(rand()%1000==0)u=u2; |
本来以为要很久，结果只用了次左右就找出了一种比更优的解。。。
考试记录
6.19 NOI模拟赛Day1
题目来源：湖南省队集训Day8
是个网络流，然而我一上来就把线段当成直线搞了，其实只要一个“口”就可以掉我，然而莫名其妙还是水了。
不会搞只会的，弄完之后感觉不大甘心，于是心理学了剩下的部分，骗了。
是比较擅长的莫反，结果只剩下了，还剩下的时候才明白题目到底要干啥，然后打了个暴力就滚蛋了。最后推了一下午才搞明白为什么我的式子少了个。
最后,。
感觉自己的码力是真的不行，调那个错误的+卡常数搞了两个多小时，之后中间的部分分又调了好久，还是要多练啊。
6.20 NOI模拟赛Day2
题目来源：湖南省队集训Day7
简直是毒中毒，看了就弃掉了。王天懿<<论偏题怪题的危害>>
看了,发现好像是个题，的究极弱化版?又看了好几遍才确认真的就是个水题，写完调完。
还有玩题答的我感觉好像有点稳。手玩了前面个点，搜了第个点，打了个随机化让它后面个点同时开跑。
上个厕所回来发现虚拟机卡住了。。。发现三个点都不动了就关了，专心搞,过了一会也不动了，那么只剩了。
随机化换成退火，发现好像还不如原来。。。把“接收更劣解”概率降低了之后好像更好了？？？那么直接爬山吧。。。瞬间变成多，感觉很,那就让它自己爬完剩下吧。
最后收菜，好像还蛮优秀的？
。
6.22 BJpers2的模拟赛
感觉对没玩过国际象棋的极不友好，弃了。肝了一年后发现只会的，想着先做再回来搞这个暴力，结果一肝就是一年，最后搞出了的算法，理论能过但是自己打的丑了常数上天，于是就只剩了，因为一个的数组次而一直,发现的时候已经要交了，就没有注意卡常。。。
最后全场暴力，就我愚蠢的打了而爆零了。。(好像是原题？蒋巨跟夏令营的人讲过？自闭了。)
6.23 NOI模拟赛
题目来源：湖南省队集训Day9
状态完全爆炸，困得一比。做了的竟然下发了,估计一大票人又是直接交标程，瞬间心态爆炸,不想做了。睡了后随便打了个暴力就接着睡了。然后数组开大了还炸了。
最后愉快爆,。
6.24 zbtrs模拟赛Day1
一上来感觉有点自闭，就睡了。过了发现好像就是看是不是，然后枚举最小值套个重排的式子就好了？一发就过了小样例和大样例？计数题应该大样例蛮稳了，不管了吧。
发现不会做，拿了白给后发现好像暴力合并是包含前面个的？感觉很亏，还是先看看趴。
感觉我的码力是来不及打状压了，打个还调了。发现好像可以跑过状压的部分？那不管了吧。
尝试的失败了，不知道其他人怎么样。
发包了，我被了?但怎么就我一个有分？原来我的还算蛮健壮的。。。组合数忘了判却因为数组开的大没有越出去？竟然了？为什么数据这么水暴力有啊？
。
6.25 zbtrs模拟赛Day2
一看的题面，感觉简单明了，比较符合我胃口，就它了吧。就想到了一个二分配线段树维护括号的的算法，%了我一波，感觉应该没假。后来觉得有单调性,是不是可以单调栈？
然后就了两个小时，还是转线段树。
结果还是没调出来，因为在单调栈转线段树的时候的定义改了，导致我有时候会莫名其妙少拿一个括号，最后只有(直接把所有权值加起来有)。
于是
居然炸成这样总只掉了?还有胡总的薯片吃可还行。
6.26 Col_lin的图论赛
开场发现就是个判欧拉图的题，秒了。
构造了，画了图感觉是对的，不会计数，滚了。
不会计数，滚了。
于是大概就是(被Col_lin十倍常数老年机卡了个点)，滚了。
6.27 NOI模拟赛
题目来源：湖南省队集训Day1
不加解释导致不论是当年的湖南省队还是现在都出现了理解错误，是个裸题却被搞得数据锅了，是我认为的“恶心题”之一，不是很想做。总体这场考试质量堪忧。
6.29 NOI模拟赛
题目来源：湖南省队集训
贼不舒服就睡了,发现应该是个数位，本来分成满/不满，满/不满种情况讨论的，后来发现只管不满且满即可，直接上个的递推即可。
长链剖分裸题，不会维护就套了个线段树合并（了）。
不会就上了个的二分。
不太舒服，又睡了一会到考试结束。
最后一个地方没开爆成。下标忘了是靠右对齐直接爆成，骗了。，两题正解还不如暴力选手分高。
6.30 NOI模拟赛
题目来源：湖南省队集训
回家颓睡了一下午感觉状态还行。
看好像就是讨论一下用几个十字吧，诶好像最多用一个，稍微证了一下感觉没伪，那么取个不就好了。
然后发现，要打高精度？？？？而且这个优美的式子就值,压位高精度除法值？？？这出题人脑子抽了？？？
：因为答案可能很大，请输出最后位？？？今天高精度练习赛？？？感觉还要容斥，高精度容斥我估计打不出来，输出样例滚了。
是个题答，求最长哈密顿回路。感觉点这么稀疏估计都混不到，老老实实打部分分吧。
然后出奇的顺利，几乎每个都是编译完稍微调一下就过了。
周围的人都在打高精度诶，看下发现我负数取上整会变成，改不改呢？算了，改完还要分类讨论，周围的人都切题了我这种咸鱼多几十分少几十分都没区别，就趴了。
结果包一发告诉我是？？？这么多人怎么策略都推错了还怼着行高精度除法打啊。
罗队肝高精却是无脑拿十字的策略，胡队肝高精容斥，进位炸到爆零，蒋队输出格式挂了。。。其他众神都没怎么动题答，然后随便玩了玩题答的摸鱼选手就上位了？？？
感觉最近几次的题答题我都拿到了全场最高的分数，写一点心得给以后的自己吧：
如果没有一定要自己写,而且健壮性一定要较强
时间要至少留以上。
对于非的点一定不要懒。即便看不出全貌也要打程序去猜，比如我这次发现菊花图之后就猜想它是菊花环，看了几组边就猜测是二分图之类。
对于的点一定要换着法的乱搞，乱搞没有正确性可言，有时爬山吊打退火，有时候纯随机化又吊打爬山，如果发现一个算法收敛了效果还不是很好，就一定要及时换算法，比如上次题答的就是因为我发现退火表现不好果断爬山，才能收获一个这么好的分数。
7.1 NOI模拟赛
题目来源：湖南省队集训
感觉这个贼毒瘤，是个恶心人的大模拟，是个恶心人的树上带修改莫队板子题。蛮有意思的然而我当时不会序列，于是就挂掉了，因为没考虑一个时刻可以有多个点出现导致自己的写法会挂掉，数据很水暴力可过系列，大概就是这样吧。
7.2 NOI模拟赛
题目来源：湖南省队集训
一上来感觉就是缩了边之后转生成树计数，没想到我还真猜对了，然而我不会矩阵树定理，于是还是写不出来。于是肝，因为自己决策单调性写的不熟，写了好久才搞出来，然后盯着了后发现：TM决策单调FAKE了，于是在单调性基础上心理学了一波。是个数论板子集合，最后，竟然没挂，很感动。
，被吊打了。
7.3 NOI模拟赛
题目来源：湖南省队集训
第一次因为出问题，昨天有巨佬因为炸掉一题，于是向总今天就开了，然后我就因为的上天了。而且今天考试的状态也很不好，对于的题没有推出来，因为很困又睡了一会，几何的结论也没有推出来。虽然秒了傻逼题还因为了。
于是就垫底了。
7.6 NOI模拟赛
题目来源：湖南省队集训
感觉要二分，后来发现确定一维另一维显然单调的，毛爷爷一开始是准备多组数据的，算了算怎么搞都是过不了的，后来说取消掉了多组数据，还是感觉没什么没什么希望。就弃了，然后最后正解居然真的就是加卡常。
并没想到边权转点权，还忘了有这回事，打了一年的压位线性基，后来还是开卡过去的。
是我的决策失误，我感觉应该的算法没多少分，只打了范围的就弃了，后来胖告诉我高精度有。
最后就是,主要题答玩的不好。
7.7 NOI模拟赛
题目来源：湖南省队集训
这套题被我归为“恶心”一类。强行图计数，一眼插头一吨转移，感觉是个很码农的题。于是就自闭梦游还被向总抓了。
最后花随手上了俩暴力，居然还不是很惨。。。
7.8 NOI模拟赛
题目来源：北师大附中友情赞助
照例还是困得一梦游,看了下，感觉就是个枚举因数然后像克鲁斯卡尔一样合并，码量很小，秒了。感觉有点神仙，我把看成了，然后放弃了乱搞打完暴力就溜了，不然我可能会在的那边搞个队列/线段树暴力合并。感觉是个整体二分套个什么，没想到点分树，弃了。
，应该是没有挂分，数据可能锅了。
7.9 NOI模拟赛
题目来源：安徽师大附中友情赞助
只会的暴力高斯消元，想到了和的做法，觉得要练练就打了，虽然还是不太懂为什么暴力跳复杂度是对的。感觉淀粉质应该和暴力一个分就去打了暴力，结果被卡了的常数。
结果全场都暴力，垫底了。
当然，中间发生的一些奇妙♂的事情也耽误了我的时间，但是菜终究是原罪。
此题暴力跳本质上是树上染色，当一个点跳到被染过色的点，那么这个被染色的点就是答案，所以复杂度就是。
7.10 NOI模拟赛
题目来源：安徽师大附中友情赞助
睡了,看了下是个未来程序之类的题答，性价比应该很低，于是肝,结果发现不会低于级别的算法，打了滚了。
感觉很可做啊，发现两边根本不影响，出一端之后乘起来即可。一开始没考虑到可以不连续的涂色，后面又因为取模的问题调了好久。最后得到了一个的做法。
后来，交卷前猛然发现了人生的奥秘：TM这个式子是的啊！！！，含恨而终。
。
为什么这么多人不会线性筛约数个数啊，感觉我们这样真的会被踩。
当然,蒋队还是打出了统治级别的实力。
7.11 NOI模拟赛
题目来源：PICKS
睡觉选手不配赢。暴力滚粗了。