NOI前小题解合集-解题报告

博主成功苟到了NOI... ### CTSC 2018 混合果汁 主席树求第K大板子题... ### [JXOI2017]颜色 枚举右端点，讨论一下线段树维护左端点 ### AT2557 Ball Coloring 有n个袋子，每个袋子里有两个球，球有权值。对于每个袋子，把两个球分别放入两个盒子，最小化两个盒子的极差的乘积。 蒟蒻只会带log的辣鸡做法。首先，全局最大值和最小值一定出现，我们枚举它们出现的情况： 1.在一边出现：最小化另一边的极差，set+双指针即可（发现会有不合法的情况，但是不合法的情况一定不优） 2.分别出现：大小贪心 ### HNOI 2016 树 树上倍增，有一些细节。犯的错误：1.记得映射到原树的编号！（敲着敲着就忘了）；2.线段树合并的数组要开大，2log ### [NOI2011]Noi嘉年华 这道题注意，对于同一场嘉年华选择的区间可以重叠。 我们DP，设$f[i][j]$表示$[1,i]$，其中一个选了j个，另一个的最多选择。$g[i][j]$表示$[i,n]$... 然后在强制必选的时候，我们可以预处理$ans[l][r]=\max\{\min(x+y+cnt[l][r],f[l][x]+g[r][y])\}$，容易发现当x增大时y会减小。由于是单峰函数，可以单指针。注意判断要用等于。 ### CF1083C Max Mex 注意到信息可以快速合并，于是线段树！ ## CF878D Magic Breeding 有$k\le 12$个初始的$n\le 10^5$维向量，支持：添加一个新向量，每一维是另外两个编号的向量对应取min/max；求一个向量一个维的值。 Bitset好题。遇到这种，对于01权值很好做（例如取min/max）的题目，可以往bitset方面想。 我们设$f[i][S]$表示第i个生物，是否每一维对应大于$S$里每个初始向量的每一维，这样，取max是|，取min是&，bitset加速即可。 考虑统计答案，我们枚举答案的12个来源，则$ans\ge x_i$当且仅当$f[x][S]=1$，S是所有$\ge x$组成的集合。 ### [BJOI2018]治疗之雨 套路题，设$dp[i]$表示血量为i，结束的期望步数。高斯消元，发现每行1的数量不多，$O(n^2)$消元即可。 ~~发现现在经常口胡题而不写怎么办~~ ### [HEOI2012]赵州桥 题目是什么鬼...其实每一行也是相邻的...？ 列出式子，发现可以矩乘。对于p较小的情况，发现前一半的循环节为p，后一半就变成了等比数列求和，由于没有逆元，需要用倍增的思想。 ### [HEOI2013]Eden 的博弈树 其实这道题我也不是特别的理解，感觉和博弈论有一些区别？总之就是dp出最优解，然后构造出最优解的每个方案，取交集。 ### HEOI2015 小L的白日梦 感觉HEOI前几年的题目质量不高啊。~~这道题不建议做，因为极其卡精度~~ [Blog](http://www.cnblogs.com/yousiki/p/6490769.html) 引用几个关键的性质(by jiry_2)： 1.一定存在最优解每一天不高兴的概率是单调不增的。 2.一定存在最优解它选取的项目是所有项目按照不高兴的概率排序后的前缀一段加上后缀一段。 3.每一次选取的项目种类只有三种可能的情况：选了1个，全部选完，其他。且处于第三种状态的至多一个。 我们枚举多余的一个位置，在前缀还是后缀取到，然后枚举前缀，单调移动后缀。 ### [USACO19FEB]Cow Dating 很容易列出斜率优化的式子。打表之后发现决策点单调，可以维护单调指针。 ### [USACO19FEB]Moorio Kart 暴力背包合并，要严格循环范围，只转移不为0的数，这样复杂度是$O(\sum n^2+\min(Y,n^2)Y)=O(nY\sqrt{Y})$ ### CF493E 非常Trick的一道细节讨论题。注意系数都是**非负数**。看注释吧。 ```cpp if(t==a) { if(a==b) puts(t==1?"inf":"2"); else puts("0"); } else if(a==b) puts("1"); // 只有常数项，且为a else if(a<t||b<a) puts("0"); else { LL c=0,p=1; while(b) c+=(b%a)*p,b/=a,p*=t; // 我们可以还原出多项式的系数：就是把b表示为a进制 if(t==1) puts((c==a||c==1)?"1":"0"); // 特判形如1 2 4 else puts((c==a)?"1":"0"); } ``` ### BZOJ 4134 ~~啊啊啊以后不能稍有不会就去看题解，往往和正解就差一点点，这个关键的步骤去看题解很亏~~ 运用SG函数的定义可以得到$O(n^2)$的算法，考虑优化：我们不能枚举子树里每个点了。这就要用上**树的优化策略**之一：子树子结构。我们对每个儿子建一个Trie树，支持合并，全局Xor，求mex。 ### CF551D 多种做法，首先可以无脑二分。我们考虑$O(n)$DP：设$f[i]$表示点i在子树叶子权值中最大排第几，分类讨论minmax即可。 ### CF1107E 套路挖串区间DP。对于挖串DP，我们肯定设两个数组$f[l][r]$表示答案；$g[l][r][k]$表示：删除$[l,r]$后，剩下k个和$s[r]$相同的字符的方案数，转移的话枚举下一个和$s[r]$相同的位置即可。 ### CF1110D 差点被一道提高组难度的DP题爆踩。就在想不出来点开题解的前一刻想到了：最多剩下5个留给后边消除，直接状压DP！$dp[i][6][6]$即可。 ### CF1110E 对于序列上相邻元素加加减减的操作，可以尝试差分（甚至多次差分）后寻找性质。 ### CF1110G [讲的很好的Blog](https://www.cnblogs.com/Itst/p/10356243.html) 一道非常有趣的细节讨论博弈题。 注意，如何处理已经涂白的点？题目通过在已经白色的点下挂一个结构，达到：白色选这个点，黑色必须浪费一步，于是又轮到了白色。 ### [SDOI2017]苹果树 卡常好题~~然后我就咕了~~ 这道题是特殊的树形依赖背包，也就是...树形依赖多重背包。但是我们怎么解决“至少选一个”就可以选子树的限制？我们可以将每个点拆点，拆成大小为1的点和大小为$a_i-1$的点，然后我们选择链肯定直接选择到叶子。然后我们如何处理这条链外挂着的子树？我们求出这棵树的先序遍历和后序遍历，那么除去这条链后，剩下的是先序遍历的前缀和后序遍历的后缀。我们像树形依赖背包那样，按dfs序做背包即可。 ### 重返现世 扩展min-max容斥。我尝试用FFT拼了半天系数，无果。利用的公式：${n\choose m}={n-1\choose m}+{n-1\choose m-1}$ ### [BJOI2019]奥术神杖 AC自动机套路题。首先考虑暴力$dp[i][j][k]$填了i，走到j，选了k。值域复杂度双爆炸。解决值域爆炸：取ln变为求和，然后01分数规划解决复杂度。 ### P5306 COCI2019 Transport ~~注意，对LL从大到小排序时要用`greater<LL>`，不是int！！！~~ 看起来非常经典的题目模型。 emmm我可能过于热爱点分治+dfs时维护在线算法的方式...这道题可以fhq+栈序撤销做，但是...非常恶心。不过，点分治时为什么要维护栈序数据结构！？因为防止不合法的路径。但是我们可以最后容斥掉同一个子树即可。这样我们只需要把到根的路和从根出发的路双指针合并起来即可。 ### [COCI2019] Mobitel 上取整除分块+DP。 ### [APIO2017]商旅 ~~看讨论说二分上界太小会WA，实际答案会爆int，然后把二分上界开太大，一乘直接爆LL了~~ 我们的环可以拆成一段一段的形如“买-最短路-卖”的部分。看到比例肯定是01分数规划，预处理两点间最短路，和a买b卖的最大收益，然后改一下边权找正环即可。 ### CodeChef - TREECNT2 求路径gcd为1的数量。有100次边权修改。 莫比乌斯反演，把$d|w_e$的边拿出来，统计各个联通块的大小。对于修改，注意到数量只有100个，我们把不动的边形成的联通块缩点，这样每次最多只有$O(q)$个点，暴力重跑一遍即可。 ### CodeChef - COUNTARI 分块+FFT。 ### [HNOI2019]白兔之舞 首先，这道题的式子就是单位根套了一层矩阵。关键是如何凑出$w^{-it}$次方。尝试用之前的套路，$i^2+t^2-(i-t)^2$，但是这样没办法开根。看题解后发现，还有另一个式子：$ab={a+b\choose 2}-{a \choose 2}-{b\choose 2}$，适用范围更广（这怕是这道题最核心的部分）。于是用这个来拆，然后注意一下差为定值的卷积即可（调了半天，最后看了一下ztb的代码） ~~GX/GZOI D1T2T3好自闭啊~~ ### [GXOI/GZOI2019]旧词 差分+树剖维护LCA贡献。参考Lnoi LCA ### [GXOI/GZOI2019]逼死强迫症 为啥现在都喜欢Fib了？ 首先发现答案就是$2S(n-3)$，其中 $$S(n)=\sum_{i+j\le n}F_iF_j$$ 我们同时维护以下，即可转移： $$F_i$$ $$G(n)=\sum _{i}F_iF_{n-i},G(n)=G(n-1)+G(n-2)+F_i$$ 矩阵：`Set(0,1,0,3,1,0,1,1,1,3,2,3,3,2,3,3,3,4,4,4);` ### CTSC2014 图的分割 做Kruskal时维护相关信息。注意，如果一条边没有加入，是不能合并并查集的。 DBZOJ没有spj，BZOJ不支持C++11.emmm ### 【UER #6】寻找罪犯 ~~打错两个字母让我调了好久，ri~~ 2-SAT+前缀和优化建图。 ### [TJOI2019]唱、跳、rap和篮球 看了半天，以为数据范围是$10^5$呢，结果只有1000，那不是小水题嘛。至于$O(n^2)$的做法...还是值得学习的。 我们把四个数组的卷积换成前两个和后两个，然后枚举大小把它们合并起来。考虑如何维护两种物品的dp数组，如果我们逐渐减小上界，那么就相当于每次从背包里“扣除”一个物品，$O(n)$扫一遍即可。 ### [SNOI2019]数论 记录一下我的暴力做法。 我们要数$cP+a_i=dQ+b_j$的解数。 显然这个解是$lcm(P,Q)$一循环的。所以，假如这个等式的最小正整数解是x，那么对ans的贡献是$(T-x)/lcm$ 直接算不好算。我们把T分成整块的lcm和边角料。 对于整块的，相当于我们求有多少对$(a_i,b_j)$使得有解，判断gcd即可。 对于边角$t=T\bmod lcm$的（其实可以直接把整个T看成边角，不过常数大一点），枚举$a_i$则$c\le (t-a[i])/P$，我们要看$a_i+c'P\bmod Q$有多少属于B，这个直接倍增凑出来即可。直接开数组会爆空间，所以要滚动数组。 **注意：** 1. 有可能在第二步solve的时候，数字直接就爆掉t！！！要特判！！！ 2. T要-1，有些地方别忘了模Q。 ### [SNOI2019]通信 费用流+主席树优化建图。 ### [SNOI2017]英雄联盟 ri，感觉自己降智了。 **交换下标！！！！！！** ### [SNOI2017]遗失的答案 ri，感觉自己降智了。 LCM的因数只有800个，我们直接状压DP看上界下界有没有满足... 懒得写了。 ### [ZJOI2019]浙江省选 其实这道题挺值得写的，只是我现在咕了，所以放在这里。 考虑第一名怎么求，显然就是半平面交。那么第二名肯定就是去掉第一名之后最靠上的线段，二分出第一名的线段占据的区间，相当于这个区间下的线段排名都+1.其他名次类似。 *明天就是APIO了赶快补一点APIO的题要不然就凉了* ### APIO2018 新家 关键在于我们并不需要知道范围内有几个商店，我们只想知道是不是所有商店都在范围内，我们可以对每个位置维护一个最靠前的pre，然后线段树查一个后缀的min。 ### APIO2018 选圆圈 K-d Tree 玄学题，需要把坐标系旋转随机角度才能保证不被卡。 ### APIO2016 烟火晚会 lx讲的左偏树+分段函数好题。一定写一定写。 ### APIO2015 [APIO2015]八邻旁之桥 关键在于k=2时，我们会选择和“家和办公室的中点”最近的桥，这样我们可以枚举分割点，然后求中位数。 ### [APIO2012]守卫 emmm做出来这道题需要思考。首先我们把没有忍者的位置去掉，然后把区间排序，去掉包含的区间。然后DP覆盖前缀区间和后缀区间的最少数量。**如果一个点必须放，那么它一定是某个区间的右端点**。那么我们强制那个点不放，放前一个点，看看最小的数量是否大于k。 ### [APIO2012]苦无 这道题的关键在于找出这n次的碰撞事件。关键在于删除一个苦无之后的影响。事实上我们根本不用考虑这个影响，就像Dij的堆一样，对每个点求出相遇的时间，每次从堆里取出最小的。如果发现不合法，就再求另外的。 *哇ywy做了好多CF题，让我康康！* ### CF1146D Frog Jumping 当$x\ge a+b$时，$f(x+a)=f(x)+a/\gcd(a,b)$ 所以对于小段暴力做，大段等差数列求和。 ### CF1117G Recursive Queries 题目的描述相当于就一段区间，拿出来建笛卡尔树，每个点的深度之和。一个点的笛卡尔树上的深度相当于从这个点开始，前缀后缀最大值的个数以后缀最大值为例，我们从前往后扫，得到每个点作为后缀最大值的一个区间，把这个区间+1，一个询问就相当于区间求和。 ### CF1101F Trucks and Cities 感觉这道题的复杂度可以做到$O((n+m)\log n\log V)$ 对n建立倍增数组表示加$2^i$次油，最多到哪里。 题解做法是$O(n^3)$的区间DP。$dp[l][r][k]$表示把$[l,r]$分成k段，最小化最大段的长度。 ### CF300E Empire Strikes Back 挺简单的题，显然可以二分，关键在于如何计算阶乘乘积的每个质数的指数，事实上。直接做的复杂度就是对的（但是很卡常，复杂度玄学）。 ### CF294E Shaass the Great 枚举删掉某条边，然后新联的边一定是剩下两棵树的重心。所以这道题毒瘤一点是可以$O(n\log n)$做的。 还有一种方法，就是删掉一条边后，我们在两棵树中分别选一个点，连起来，此时两棵树的选择是独立的，贡献也是独立的，分别选最优解即可。 ### CF351E Jeff and Permutation 瞎想了一个贪心策略，结果过了，证明不会。 对于这类问题，要么从前往后考虑，要么从大到小考虑。我们按绝对值从大到小考虑，我们发现，这个数填正负的代价是可以计算的，分类讨论取最小值即可。 ### CF1166E 瞎猜了一个结论结果过了...  构造方法 by ywy ### CF1032F Vasya and Maximum Matching 一棵树的最大匹配唯一当且仅当除了**孤点**，这棵树的其它连通块内部都构成一个**完美匹配** $dp[i][0...2]$表示点i是孤立的/未匹配的/匹配的。 ### CF1076G Array Game 想的差不多。注意到这个人可以原地跳（其实能不能原地跳都可以做），所以如果$[i+1,i+m]$中没有先手必败，那么答案就和i位置的奇偶性有关。 我们发现可以把一个区间$[l,r]$的信息记录为：若$[r+1,r+m]$的状态为S，那么$[l,l+m-1]$的状态为val[S]，这样信息就可合并了。 那么区间加就相当于区间反转奇偶性，在线段树上每个节点维护两种信息即可。 ### CF1059E Split the Tree emmm想得太复杂了，没想到正解是贪心... 对每个点倍增的求出向上最长能覆盖多少，然后在树上贪心一遍。 ### [SNOI2017]礼物 加强版 这个思路很强。 观察矩阵，发现是上对角矩阵，且对角线有1个2，剩下是1.根据递推数列的相关知识可得，答案可以表示为 $$c_k2^k+\sum_i^k a_in^i$$ 如何算$c_k$？对多项式进行k阶差分即可。 为了插值，需要计算$i^k$，可以线性筛。 复杂度$O(k+\log n)$ ### CF1010F Tree 树剖+分治NTT ### CF915G Coprime Arrays 对$i=1...k$求出$\sum _d \mu(d)\lfloor i/d\rfloor^w$，$O(n\log n)$ 枚举d，然后$i/d$每隔d变化一次。 ### [JSOI2019]精准预测 显然是要2-SAT，建完图之后是DAG。然后拓扑排序看一个点能到达哪些点，bitset来做。但是空间开不下？分批做，每次拓扑10^4个。 ### P4704 太极剑 懒得做了...先口胡一个倍增做法：注意到区间的要求相当于区间内至少有一个，区间外至少有一个，那么我们$(i,i+cnt/2)$连边就可以满足所有需求。那么我们枚举选择的第一个位置，然后维护倍增的贪心数组即可。 题解是这样的：我们将序列贪心地分段，要求同一条线段不能包含在一段里。我们找出长度最小的一段，然后枚举这一段里的分割点，每次直接跳过长度为d的一段，复杂度$O(n)$ ### [CTSC2017]游戏 第一次用贝叶斯公式...不会用... $$P(A|B)=P(B|A)P(A)/P(B)$$ 对于这道题，对于每个位置的期望是独立的， $$\begin{aligned}P(x_m = 1 | x_l,x_r) &= \frac{P(x_l,x_r|x_m=1) P(x_m =1)}{P(x_l,x_r)} \\&= \frac{P(x_l,x_m,x_r)}{P(x_l)P(x_r|x_l)} \\&=\frac{P(x_m,x_r | x_l)}{P(x_r|x_l)} \end{aligned}$$ 概率可以方便地“拆开”！ 这里就很好算了，$P(x_r|x_l)$相当于区间内的概率矩阵相乘，$P(x_m,x_r|x_l)$只需要在乘矩阵乘到m的时候只转移到1的地方即可。 ### Atcoder 某题 算是想到了，但是后来又弃了，因为这是$O(n^2)$的...结果式子写出来是可以前缀和的... 题意：有n个初始为0的变量，每次任选一个最小值，把它变成$[mx,mx+d]$中的一个数，问最后都变成m的方案数。 变成在数轴上每个位置选择若干次，因为是任选，所以系数是阶乘，然后注意满足d的限制。 ### [BJOI2017]喷式水战改 看起来我对平衡树的理解还是太Naive了...一直在想怎么依次求出分割点，没想到正解的做法十分暴力：对每个点维护子树的dp数组$dp[i][j]$表示从i型到j型。 ### [HNOI/AHOI2018]排列 唉，感觉虽然做了一些这种贪心合并的题，但是见到题还是不太会做。对于这道题，我们可以把限制关系建出树来，连边$(i,a[i])$，选儿子之前要先选父亲。然后根据比较相邻两项的优劣，发现按照平均值排序最优。 具体一点，我们的贪心策略是让较小的数更靠前。那么我们每次考虑当前的最小值，如果fa是0，我们就直接选，否则，一定是选完fa之后立即选择它，那么我们可以把它和fa合并！ ### [ZJOI2017]字符串 这题也...太码了吧... 首先我们考虑静态做法，放到线段树上考虑。由border的性质可知，最小后缀一定是$[l,mid]$中**全局后缀最小值**，和递归$[mid+1,r]$的结果取min。 为了修改，我们尝试自底向上的建树，对于每个点，我们暴力地维护一个vector表示可能成为最小后缀的位置。考虑pushup： 首先右儿子的vector可以直接拿过来。 对于左儿子，因为右边接上了新串，所以可能就不是最小可能后缀了。具体来说考虑两个位置$u<v$，如果加上右边之后v不是u的前缀，那么大小关系已经得出了，否则，我们应该保留什么？ **我们应该保留u！** 这很奇怪，因为当前v的字典序小于u。注意到v是u的超过一半的border，说明u有循环节w，是更小的。将来再在右边加上新串，讨论可得要么u更小，要么w更小。 所以左儿子最后只会剩下1个元素。于是vector.size()就是log级别了。现在我们就有了$O(n\log^3n)$的做法。还要用分块支持区间加，求哈希值...（据说这题暴力能过） ### 51nod1446 限制价值树 做出这道题的关键是看出来它由两道题拼起来：先求出大小为k的合法子集个数（折半，双指针，**注意取模！**），然后再求出有恰好k个great点的方案数。 ~~这里我zz了，k个great点方案数只和good点和bad点的数量有关...我以为这个也要把折半的两边拼起来~~ 我们可以用矩阵树定理求出至多i个great点的方案数，这些点是有标号的（标号在第一步处理的cnt数组中）！所以我们要**二项式容斥**！ ### 某位歌姬的故事 把区间的最小限制求出，对最小限制相同的区间一起考虑，这里似乎不能$f[i]$表示$[1,i]$合法的方案，必须$dp[i][j]$表示考虑了前i块，最后一块达到最大值的是j。 ### [SHOI2010]最小生成树 ~~这道题乱贪心有90分...~~ 观察到这条边一定在最小生成树上当且仅当只考虑$\le w$的边，$u,v$两点不联通。注意这个**不联通**，我们可以用最小割解决！每条边的边权是修改到比w大需要的次数，从u到v跑最小割即可！ ### CF643E Bear and Destroying Subtrees 又是利用了double的精度。我们可以很轻松的列出$f[x][i]$表示点x的子树，深度$\le i$的概率。我们可以近似忽略深度$>lim$（试出来的是35）的概率，那么每次添加一个点只需要改它的lim级祖先的dp值。$O(nlim^2)$ ### 「LibreOJ β Round」ZQC 的手办 segment tree beats ### 51nod1160 压缩算法的矩阵 首先显然的一点，我们可以把最后一列排序，得到第一列。那么进而我们就可以得知这个串有多少01段了。然后我就没啥思路了... **最后一列和第一列的01的相对顺序是不变的**，因为我们考虑第一列为0的行，它们字典序和第一位没有关系（都是0），所以把它们都循环左移后的字典序不变！ ### AT2062 ~K Perm Counting ~~爽了，自己做了一道容斥题~~ 首先看到限制很奇怪，我们就要容斥，强制不合法。 不合法，也就是位置i填i-k或者i+k，我们可以视为i想向i+k连了一条边，我们要容斥边的个数，要求每个点出度入度至多为1，我们直接状压i和i-k有没有入边即可。 这里我们要把长为n的序列按下标mod k分成k段分别做，段之间不能连边。 ### 「LibreOJ β Round #2」计算几何瞎暴力 lx讲课内容，01Trie+标记。 ### CF1189E 给定互不相同的序列$a_i$，求满足要求的$i<j,(a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p$的对数。 两边同时乘上$a_i-a_j$，然后分离开随便做做。 ### BZOJ 3145 这道题挺好的。求两个串的最长公共子串，两个串相同当且仅当只有一个位置对应不同。 我们关键是求出形如$A*B$的出现情况。我们可以建出S和T的广义SAM，然后在SAM上枚举出现位置的LCP，然后相当于我们要求出Parent树上这个点子树中的S和T的$right+2$位置两两的LCP的最大值。我们可以维护一颗平衡树，然后每个点把子树的平衡树启发式合并起来，显然最大值应该是在一起后缀排序后相邻的S和T产生，我们可以在插入的时候看一下前驱后继更新答案。 ### CF1188C ri，降智了... 首先有一个显然的DP：枚举最小差至少是v，$dp[i][j]$表示前i个选j个，然后单指针＋前缀和 看似我们只能做到$O(nkA)$，实际上当$v>A/(k-1)$后一定无解，于是复杂度就是$O(nkA/(k-1))=O(nA)$ ### CF1189C 这道题ST表的做法非常显然，但是真正的解法非常美妙： $$ans=\lfloor sum/10\rfloor$$ Imagine, that candy is equal to number 10. Then sum of all numbers doesn't change: when we replace (a,b)→((a+b)mod10) we take 10 iff a+b exceeds (a+b)mod10. Also note, that sum of numbers-candies is divisible by 10 (because we take only tens). Then, in the end, the remaining digit is equal to the remainder of the division of the initial sum by 10, so the number of candies is equal to the quotient. ### CF1186E 细节题 ### CF1187F Expected Square Beauty 好题。但其实也不难。我们要算的答案是 $$E(B(x)^2)=E((1+\sum_{i=1}^{n-1}[x_i\neq x_{i+1}])^2)$$ $$=E(1+\sum_{1\leq i,j\leq n-1,i\neq j}[x_i\neq x_{i+1}][x_j\neq x_{j+1}]+3\sum_{i=1}^{n-1}[x_i\neq x_{i+1}])$$ 用期望线性性做即可。 注意$\sum_{1\leq i,j\leq n-1,i\neq j}[x_i\neq x_{i+1}][x_j\neq x_{j+1}]$，相邻的两个单独算，否则相互独立，直接乘 ### [NOI2008]奥运物流 显然的DP是$dp[i][j]$表示i子树修改j次的最大贡献。但是我们发现把点接到1上的贡献与当前到1的距离（祖先中最后一个修改的）有关，我们多加一维即可。 ### CF587F 降智了降智了。我们需要统计形如“一个点到根的链”编号在[l,r]的点的权值和。一个简单的方法是离线在树上DFS，这样我们只有n次插入和很多查询，分块即可做到每次$O(1)$查询。 ### 猪猪侠再战括号序列 降智了？似乎从前往后扫，每当扫到一个)过多的地方，就从这里开始翻转，知道某处(和)相等，手玩发现是对的。 ### CF802C Heidi and Library (hard) 可以直接无脑上下界。但是直接做会TLE，方法是每天肯定只会买当天需要的书，这样边数就大大减小了。 ### [SDOI2011]保密 01分数规划+最小割。注意这道题对无解的判定。最好先额外跑一边，标记出不可达的点。 ### CF856G 生成函数，线性递推，快速幂+多项式取模 ### CF933E 首先把问题简化为可以把相邻两数同时-1（甚至变为负数，但是这显然不会在最优解中出现），然后可以证明连续0的个数$\le 2$，于是$O(n)$DP即可。 ### 「CEOI2011」Matching 用KMP实现模糊匹配，具体的模糊匹配是指这个串的字典序相对排名相同。利用树状数组，我们可以方便的求出模板串的nxt数组（就扣定义求就行），然后去匹配。 ### LNR#2 D2T1 感觉有一个`map< int,vector< set<int> > >`的做法。