• P7339 『MdOI R4』Kotori
• P2167 [SDOI2009] Bill的挑战
• P4206 [NOI2005] 聪聪与可可
• P4377 [USACO18OPEN] Talent Show G
• P4766 [CERC2014] Outer space invaders
• P8564 ρars/ey

P7339 『MdOI R4』Kotori

考虑直接思考对于分成\(\frac{n}{2}\)组构成的所有的树。很显然这是一颗完全二叉树。此时，我们将对决树抽象的构建出来：注意到对于这棵树的叶子节点都是这\(2^k\)个可以对决的初始节点。最直接的思考，我们发现我们需要的信息就是针对每个参赛人员求出他可能的敌人。注意，如果当前对决的人员有1号选手，我们需要特判。这个特判操作一定是这颗树上的最左边的一个链。这个链有一个特殊性质：这条链上的所有节点的编号的二进制只有一个1。所以可以使用__builtin_popcount()函数。注意到由于对决的两方都有可能产生一定的对手，所以此时我们需要首先二分查找两边都合法的vector，然后resize()删除，最后合并两个vector。代码

P2167 [SDOI2009] Bill的挑战

发现 \(N\) 的值很小，加上方案数的计算量很大，考虑状压。在转移过程中我们发现最大的问题在于对于不合法字符串的筛选。这里提出了一种新的筛选不合法方案数的方式：利用相对于某个字母合法的可以选择的字符串的个数与当前枚举的状态数进行取交，之后再进行转移。那么我们直接对可以选择的字符串数进行预处理就可以。可悲的是一开始手模样例4出错了\kk代码

P4206 [NOI2005] 聪聪与可可

注意考虑聪聪每次走的点是固定的，所以是可以预处理出来的。代码

P4377 [USACO18OPEN] Talent Show G

这是一道经典的01分数规划问题。该特点就是求两个要素选或不选的最大值。注意到这种问题的贪心都是有问题的，而答案的规模可能会很小，所以直接考虑进行二分答案（浮点二分）。但是此题比较特殊，由于有 \(W\) 的上下限控制，所以我们无法针对所有的正数情况全部选取。考虑01背包就可以解决这个问题。但是还是与01背包有些许不同，需要将所有大于等于 \(W\) 的部分全部计算在 \(W\) 上。代码

P4766 [CERC2014] Outer space invaders

这道题是一类十分典型的区间DP。而经典的区间DP一共有两种情况：一种是以单个物体为单位进行合并，这种情况下可以考虑直接进行合并；另一种就是以一段区间为一个物体，此时我们可以考虑最后执行的操作，再用这个操作将这个区间合并成两部分。blog但是这道题的简单版可以看这道题，这个blog很好。考虑如何合并能使得两边的区间不会计算重复。可以将中间点暂时性扣去。利用一个g[][]计算合并中间点的贡献。

P8564 ρars/ey

这是经典的树上DP背包问题。实际上，树上DP就是孩子节点想给父节点传达什么样的信息。这道题就是每个孩子节点给父亲提供自己分别删除多少个节点的最小代价，以供让父亲节点填充自己的代价数组，最后递交给爷爷节点。由于这里面每棵子树需要在当前情况下删除的点数不一定全部删除，所以就必须枚举出最小节点的最小代价。记录