NOIP2018备考做题笔记

【P4879】ycz的妹子

权值线段树，（代替平衡树）

【P1993】小K的农场

差分约束，判负环别用广搜就行了……

【P2115】破坏

明显的0/1分数规划，二分答案后判断总量减最大连续字段和是否小于$0$

【P2184】贪婪大陆

树状数组记录区间有多少个起始点、多少个终点，然后稍微推算一下就可以了

【P1533】可怜的狗狗

考虑离线来做，由于区间不包含于是排序后询问的区间左右端点均单调增，用权值线段树维护即可~~（我讨厌离散化）~~

【P2073】送花

用钱数作下标维护线段树，记录区间的花朵数、总美丽值，然后删除啥的就都是基本操作

【P3408】恋爱

树形DP，求完子节点后暴力排个序然后取前几小。效率的话应该是$O(nlogn)$的，我记得我以前好像证过

【P2982】慢下来

考虑到一头牛可以且只可以影响到他子树上的节点，于是用在$DFS$序上用树状数组维护区间修改、单点查询即可

【P3097】最优挤奶

线段树维护某区间（取左端点不取右端点、取右端点不取左端点、取左端点和右端点、全不取）的最优值，然后各种合并即可

【P2986】伟大的奶牛聚集

先找所有节点子树上的最小不方便值$f[x]$和子节点个数$siz[x]$，可以发现，根节点的$f[root]$就是想要的答案，于是从上向下用父节点更新子节点的$f$值即可

【P2996】牛收费路径

对点的权值排序，从小到大枚举中间结点跑$Floyd$，记录“最大点为第$k$时$i$到$j$的最距离”$f[k][i][j]$，查询时枚举$k$取最小即可

【P1875】佳佳的魔法药水

常规DP，我觉得记忆化搜索能好写一点，计数啥的更是常规操作

【P1472】奶牛家谱

用$f[x][k]$表示有$x$个节点、高为$k$的树的个数，$s[x][k]$表示$f[x][k]$关于高度$k$的前缀和，由于题目规定不区分左右子树，则有： $f[x][k]=f[ls][k-1]*s[rs][k-1]+f[rs][k-1]*s[ls][k-1]-f[ls][k-1]*f[rs][k-1]$ 其中，$ls+rs=x-1$

【P4316】绿豆蛙的归宿

常规DAG上概率DP，记忆化搜索

【P1972】HHH的项链

离线处理，把询问的区间左端点递增排序，只考虑每一种贝壳第一次出现在什么位置，将该位置+1，用树状数组维护区间和，然后如果左端点越过了该位置，查找该种贝壳的下一个位置，用链表维护（或用向量模拟）

【P1225】黑白棋游戏

广搜，二进制表示状态，注意状态的编码方式和坐标的编码方式

【P3047】附近的牛

要求到每一节点距离不超过$k$的节点的点权和，首先易求每一节点子树内到该节点距离不超过$k$的点权和。然后由根节点向下进行二次$DFS$，由父节点更新子节点，注意减去自身，即

$f[v][k]=f[v][k]+f[x][k-1]-f[v][k-2]$

【P2921】在农场过万圣节

$Tarjan$缩点+DP，遇环则退

【P2985】吃巧克力

二分答案后贪心地对于每一天若达不到希望的开心值就一直吃，直到达到希望的开心值，然后到下一天，看是否能在吃完所有巧克力前过完$D$天

【P2887】防晒霜

贪心，每个奶牛相当于一段区间，防晒霜相当于点，对每个区间的右端点排序，对每个防晒霜的固定值排序，从小到大枚举防晒霜，让其尽可能地满足右端点较小的的区间，直到没有奶牛可以被该防晒霜满足或该防晒霜已用完，换到下一个防晒霜继续进行此操作

【P3609】蹄子剪刀布

状态$dp[i][j][0/1/2]$表示前$i$次能换$j$次，当前为（剪刀/石头/布）的最大得分，可以做到$O(nk)$的时间、空间复杂度

【P2345】奶牛集会

以位置作为下标，将奶牛按听力排序后从左到右扫描，用树状数组维护听力和、个数，再分坐标大小情况讨论一下，加和即可

【P2375】动物园（~）

玄学$KMP$（$next$数组）

【P4838】P哥破解密码（—）

分情况讨论，对于$n$位的情况：

1. 第$n$位为”$B$“：前$n-1$位独立，有$f(n-1)$种
2. 第$n$位为“$A$”，第$n-1$位为“$B$”：前$n-2$位独立，有$f(n-2)$种
3. 第$n$位为“$A$”，第$n-1$位为“$A$”：则第$n-2$位必须为“$B$”，前$n-3$位独立，有$f(n-3)$种

综上，有：$f(n)=f(n-1)+f(n-2)+f(n-3)$

另一种推导方式：

第$n$位为”$A$“或”$B$“，则先令$f(n)=2f(n-1)$，然后发现有的不合法，就是后三位同时等于“$A$”的情况，于是还要减去$f(n-4)$，即$f(n)=2f(n-1)-f(n-4)$

满分做法还需要矩阵加速，还没写……

【P1108】低价购买

需要求最长上升子序列长度和最长上升子序列计数，用$O(n^2)$算法即可

【P2389】电脑班的裁员

状态$f[i][j][1/0]$表示前$i$个人中留$k$段，第$i$个同学选/不一定选的最大能力值，则有：$f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j][1])+a[i]$，$f[i][j][0]=max(f[i-1][j][0],f[i][j][1])$

（可以拿滚动数组优化一下）

【P2029】跳舞

正常的DP，$f[i][j]$表示前$i$个箭头，当前累计连续踩中$j$个的最大得分，个人认为用刷表法方便，注意$f[i+1][0]$要单独推一下

【P4568】飞行路线

分层图模板题，常数挺大，好像卡$SPFA$

【P1073】最优贸易

按没买水晶球、买了水晶球没卖、卖了水晶球建分层图。一、二层之间的相邻节点连一条权为水晶球价格的边表示买入；二、三层之间的相邻节点连一条权为水晶球价格的相反数的边表示卖出；各层图内部连边权值为$0$表示走来走去无花费，跑最短路即可。

【P1005】矩阵取数游戏

比较正常的区间DP，问题在高精。__int128这玩意$NOIP$应该是不让用

【P2431】正妹吃月饼

从$A$开始从小到大枚举$A$二进制不包含的数位$k$,若$A+2^k<=B$，则将$A$加上$2^k$，重复此过程直到$A+2^k>B$，输出此时的$A$二进制下有多少个$1$即可

【P1656】炸铁路

~~本来应该是求桥？~~数据范围太小就枚举边拿并查集胡搞就可以了

【P2079】烛光晚餐

状态有一维可以是负的，于是将小明的喜爱程度统一加上一个很大的常数就好了，刷表达法好

【P1353】跑步

正常的二维DP，刷表大法好！！！

【P1536】村村通

并查集找联通块，然后需要连的路等于联通块的个数减一

【P2999】巧克力牛奶

若一个点是“汇聚点”，则$BFS$拓扑排序搜到该点时队列里应该只有这一个元素。特殊的，若已经有点访问到了出点，则队列中和以后入队的点中都不可能再有汇聚点了；而第一次汇聚前会出现类似的问题。具体实现的时候可以正反图跑两遍拓扑序，若有点访问到了出点就停止标记汇聚点，将两次的标记取与即可

另外洛谷上的题解都是分奶流然后通过看是否等于总奶量来判断的，很神奇…

【P1133】教主的花园

一维状态表示第几朵，一维表示这朵放什么花，一维表示是作为高的还是低的，方程也很好写，然后枚举第一朵放什么，逐个DP就行了

【P1273】有线电视网

树形DP经典题，求一下$x$节点的子树上取$k$个人的最大盈利就好了

【P1095】守望者的逃离

二次动归，由于直接跑只与前一秒的距离有关，我们后处理他，于是，先让守望者只用法术闪烁移动，没有法术就原地休息。第二次扫描时对于每一秒判断跑的话是否更优，由于是从前向后更新的，所以每一次都是最优更新最优，且没有后效性

【P1136】迎接仪式

相当于最多把$K$个“$j$”变成“$z$”,把$K$个“$z$”变成“$j$”。令$f[i][j][z]$表示前$i$个中有$j$个“$j$”变成“$z$”，$z$个“$z$”变成“$j$”后最多的“$jz$”子串个数，按原串情况分类DP即可

【P1412】经营与开发

从后往前DP，以消除后效性，发现每次对钻头的操作对后面的费用有累加作用，于是每次只考虑后一次的获利即可，可以用滚动数组变量把空间优化到$O(1)$

【P3694】邦邦的大合唱站队

挺不错的状压DP，前缀和记录一下前$i$位每个乐队都有多少人就行了

【P3197】越狱

组合计数，先求越狱的方案数：第一个房间的囚犯可以信仰全部$m$种宗教，剩下的必须和前面的不同，故只能信仰$m-1$种，故答案为$M^n-M(M-1)^{n-1}$

【P2516】最长公共子序列

关键在于最长公共子序列计数。若$dp[i][j]=dp[i-1][j]$、$dp[i][j]=dp[i][j-1]$、$dp[i][j]=dp[i-1][j-1]+1$则加上对应的方案数，另外应该减去$dp[i][j]=dp[i-1][j]=dp[i][j-1]=dp[i-1][j-1]$的情况，因为此时的$num[i-1][j]$与$num[i][j-1]$都包含了$num[i-1][j-1]$，应该减去。另外这题卡内存，要用滚动数组

【P2016】战略游戏

树形DP经典题，$f[x][0/1]$表示子树$x$上，$x$点放/不放所需要的最少士兵数

【P1455】搭配购买

并查集+背包

【P1892】团伙

并查集，遇到朋友的信息就合并，遇到敌人的信息就应该合并他所有的敌人（只记录最后一个敌人，其他的已经合并了就不需要记录了）

【P2394】yyy loves Chemistry I

可能是想考高精度小数，但用long double水过了，毒瘤题……应该不能考

【P1064】金明的预算方案

据说这题引出了树形背包的一堆题，不过原题还是比较简单的，一共最多两个附件，枚举所有情况进行DP即可

【P4969】神秘的703

常规维护，注意数字范围，爆long long的可以就不记录了，因为反正也减不回来

【P1082】同余方程

基本裸的拓展欧几里得，一直弄不明白的是为啥$ax-by=1$可以变成$ax+by=1$来搞，因为反正这是关于$x$的方程，改变$y$的正负也不会影响到$x$的取值，于是直接拓展欧几里得就行了

后来还想拿负数搞，结果算出来的$gcd$有正有负，因为计算机中的$mod$运算结果的正负等于被除数的正负（如：$7$）

【P1083】借教室

二分冲突的时间，然后差分判断是否冲突

【P2191】小Z的情书

模拟，这是一种名叫海军密码的换位密码……

【P4275】萃香的请柬

玄学收敛，经过无限次拓展以后可以认为第一个拓展出的把后面的全都挤出去了，找找规律发现和斐波那契数列有关，就差不多了

【P2683】小岛

还记得【P1119】 灾后重建中，每次增加中间点，然后询问全源最短路。那道题应该用$Floyd$算法的来搞。

$Floyd$算法中，$dist[k][i][j]$的含义是以$i,j$为起点和终点，路径上的中间点编号不超过$k$的最短距离。

这道题的思想类似$Floyd$算法，只不过$Floyd$每次枚举中间点松弛路径，我们枚举中间边来松弛路径

对于每一次增加的边$(a->b,c)$，枚举任意两个点$i,j$，考虑到新增边后，路径方案必须满足：

$dist[i][j]<=min(dist[i][a]+dist[b][j]+c,dist[i][b]+dist[a][j]+c)$

就可以用这个松弛来搞啦~

注意这里新增的边是双向边，所以必须按两个方向进行松弛

效率$O(n^2m)$看起来好像没有$Dijkstra$暴力算法的$O(mnlogn+m^2)$好，但是这种算法的常数比较小，写起来也好写，而且对于这道题的数据$(n<=100,m<=5000)$，这种方法跑起来还是比较快的。

【P4828】Nagisa loves Tomoya

推一下发现每一项的系数都是二项式系数……暴力加起来就行了

【SP5150】JMFILTER - Junk-Mail Filter

并查集的删除操作：开新点，$fa$指针向自己，以后这个点的操作都在新点上进行

【P3029】牛的阵容

尺取法，若区间内有全部品种的牛则记录答案同时左指针右移，否则右指针右移，记录每种奶牛个数用离散化~~（我讨厌离散化）或$map$（贼慢贼慢）~~

【P3933】Chtholly Nota Seniorious

考虑到不能拐弯，所以分界线肯定是斜线（或者说每一行/列取出的个数是不严格单调的），假设我们只考虑左下和右上，假设最大的那个元素在左下的部分，二分左下的那部分的最大差值，把所有满足条件的格尽可能选上（按照规则选），然后判断右上的差值是否小于枚举的插值。做完后把整个矩阵旋转三次再做，取最优答案

【P3932】 浮游大陆的68号岛

注意到他们只是在问问题（并不是真的搬东西）所以并没有修改操作，于是用前缀和维护几个量再推公式分类求和计算就行了

【P1868】饥饿的奶牛

对区间右端点排序然后从左到右枚举点，若存在有以该点结尾的区间则判断是否要取，一维DP，虽然我用的是刷表法但是觉得填表法能好一点

【P2326】AKN’s PPAP

贪心地从大到小枚举$2^k$数，若存在两个以上的元素大于$2^k$则排除其余元素，然后接着往下枚举$k$即可

【P2342】叠积木

带权并查集，记录某块积木到其父节点积木之间有多少块积木，把一堆积木最下面那块作为根节点，$getfa$时更新即可

【P2294】狡猾的商人

带权并查集，记录该月到其父节点月份的盈利额，注意路径压缩更新$val$时，父节点应已处理完

【P4092】树

离线倒序操作，用并查集维护每个点的最近打标记的祖先，删点的操作相当于合并。另外不要听信题干里有向边的谎言……该怎么连就怎么连……

【P2170】选学霸

并查集维护联通块，然后一个类似背包的DP判断是否可达（背包的容量设为$2m$因为超过的肯定不如选$0$个学霸的方案优）

【P2785】物理1（phsic1）- 磁通量

多边形面积公式：

$S=\frac{1}{2}(|\sum_{i=1}^{n-1}(x_iy_{i+1}-x_{i+1}y_i)+x_ny_1-x_1y_n|)$

就像穿鞋带

【P1704】寻找最优美做题曲线

首先，如果必须刷题那几天不是单调增，直接impossible。否则对于每一段求一个有上下界的最长不降子序列就行了

【P1122】最大子树和

比较正常的树形DP，若子树的$dp$值小于$0$则剪去即可

【P2220】容易题

首先，令$sum=1+2+3+…+n=\frac{n(n+1)}{2}$，则对于没有限制条件的位，答案为$sum^m$（可以展开一下），而有限制的位只需要将对应的$sum$减去限制的数即可

【P1613】跑路

倍增经典题，令$can[k][i][j]$表示$i$能否走$2^k$条路到达$j$，这个数组可以倍增来求，若可以互达，则连边$map[i][j]=1$，然后对$map$跑$Floyd$即可

【2495】消耗战（~）

虚树……不咋会

【P1091】合唱队形

上下界最长单调子序列……用单调栈写得快~

【2420】让我们异或吧

反正怎么都得求$LCA$啊，可以直接倍增把异或值求出来，也可以利用异或的自反性先预处理出每个节点到根结点的异或值$nim$，再用两端点的$nim$值取异或再异或$LCA$的值

【P2678】跳石头

标准的二分+贪心

【P1314】聪明的质检员

考虑到$Y$是关于$W$的单调减函数，二分枚举$W$，找到$S-Y=0$的临界状态（一般有两个）比较一下即可。或者可以三分$W$，直接求$|S-W|$的最值，就是常数大点

【2679】子串

$dp[i][j][k][0/1]$表示$a$串前$i$位，$b$串前$j$位，分$k$段，此时取/不取的匹配方案数。则有：

$if(a[i]=b[j]):dp[i-1][j][k][0]=dp[i-1][j][k][0]+dp[i-1][j][k][1]$

$if(a[i]=b[j]):dp[i][j][k][1]=dp[i-1][j-1][k-1][0]+dp[i-1][j-1][k-1][1]+dp[i-1][j-1][k][1]$

$if(a[i]!=b[j]): dp[i][j][k][0]=dp[i-1][j][k][0]+dp[i-1][j][k][1]$

$if(a[i]!=b[j]): dp[i-1][j][k][1]=0$

【P3916】图的遍历

$Tarjan$缩点+DAG上DP

【P1407】稳定婚姻

难在建图：夫妻关系男向女连边，交往过就女向男连边，若有一对夫妻处于同一个强连通分量中就一定是危险的，否则一定是安全的

【P2515】软件安装

强连通缩点之后就是一个树形背包问题

【P1941】飞扬的小鸟

状态转移挺乱的，$70$分到$100$分的优化在于重复性子问题。注意DP时先后顺序对答案的影响

【P2296】寻找道路

反向跑终点的单源最短路，然后判断哪些点不能走即可

【P1351】联合权值

考虑所有点作为中间点（距离为$2$路径的中点）对答案的贡献：所有子节点的权值和的平方减去子节点权值的平方和

【P1967】货车运输

求最大生成树，然后对于给定的起点和终点，求最大生成树上两点间路径上最小的最小权值，用倍增法

【P3953】逛公园（~）

先在反向图上预处理出到终点的最短路，然后图上DP，注意判负环

【P1966】火柴排队

由某某不等式可知两列火柴高度顺序一一对应时$∑(a_i−b_i)^2$最小。因为同一列没有高度相同的火柴，所以只需要找出第二列移动到对应位置所需要的最少次数即可，即排序、标号后求对应序号的逆序对

【P1965】转圈游戏

$ans=(m$

【P1970】花匠

最长摆动序列，$f[i][0/1]$的状态表示前$i$位，第$i$位作为高/低位的最长摆动序列长度，暴力DP即可

【P1514】引水入城

可以证明，若存在可行方案，则所有的水利设施可以覆盖的区域为连续的。于是问题转变为用最少的区间覆盖整个区域。$f[l][r]$表示覆盖$[l,r]$区域的最少区间数。记忆化搜索即可（效率$O(mn^2)$）

【P1637】三元上升子序列

树状数组维护，对于每个数，预处理出序列中左边比它小的、右边比它大的个数（还要离散化）

【P3959】宝藏

$Prim$的贪心策略可证伪，正解是状压DP（记忆化搜索写法）。用类似$SPFA$的状态更新策略来搜索

【P1352】没有上司的舞会

树形DP经典题，$dp[x][0/1]$状态的第二维表示$x$选/不选即可

【P4084】Barn Painting

树形DP，$dp[x][0/1/2]$表示子树$x$内，$x$为颜色0/1/2的方案数

【P4085】Haybale Feast

有很多做法，我是首先枚举最小值，然后把$S$大于枚举值的$F$值设为$-inf$，再做最大连续字段和看能否大于$M$

或者也可以用尺取法（双指针）找出合法区间，再用单调队列维护最大值，时间复杂度比前面的方法低

【P1879】玉米田

状压DP，$DFS$刷表写法

【P1725】琪露诺

动态规划，单调队列优化。一开始写的都没有出队操作居然还能$AC$……啥数据啊……

【P1714】切蛋糕

前缀和+单调队列优化

【P3957】跳房子

二分金币数，DP求得分+单调队列优化。状态转移挺复杂的

【P1127】词链（—）

字母作点，每个单词都作一条首字母与尾字母之间的边，然后找欧拉路

【P1040】加分二叉树

区间DP经典题，$f[l][r]$作状态，枚举这个区间的根节点进行DP

【P1576】最小花费

用$Dijkstra$的贪心思想解决，先求转账单位钱数能让所有人得到多少钱（类似单源最短路），每次找到收到金额最大的人进行拓展

【P1144】最短路计数

常规问题，有很多种方法，比如$Dijkstra$或$Floyd$求最短路时直接处理出来，或者求完最短路再按照$dist[v]=dist[x]+c[x][v]$判断某条路是否是最短路，然后更新，对于点$x$，有：

$num[v]=∑(num[x]|dist[v]=dist[x]+c[x][v])$

【P1525】关押罪犯

二分最小冲突，用种类并查集维护，遇到冲突值超过最小值的就标记为不同监狱。若发现冲突值超过，且这两人已经在一个监狱里了则返回不合法

【P1268】树的重量（~）

神奇的思路，以$1$为根，可知每次加点（$x$）都在$1-r$的一条链上连出一条新链（$r$为某一个已加入的点），新链的长度$len=map[1][x]+map[r][x]-map[1][r]$，不会证明……