论NOIP2022如何进队

_farawaystar_ · 2022-12-08 15:57:25 · 个人记录

~~可能这是一场令人刻骨铭心的比赛吧（我是废物）~~

其实NOIP真的会告诉我们进队就是简单题的正解+暴力拉满

下面我将尽可能详细地介绍在我能力范围内的骗分方法。

T1：(100pts)

不进行赘述。 ~~对萌新同学很体贴，保证了他们在不容易的NOIP之旅中不会保龄~~ 。我觉得这个题的思维量完全在扎实学习过前缀和的同学们的能力范围内，如果实在想不到，貌似我的同学用的n^3也可以拿到接近满分的成绩。

T2:(50pts)

对于 k=2×n-2 的情况，其实我们完全可以通过消去同样的，留下不同的都堆在前 n-1 个栈里面的方法来处理。我们先假设我们可以保证现有的牌均互不相同，那么我们完全可以将牌平均分配到每个栈中，这样每个栈中牌的个数不超过两个。那么接下来。对于一个不在栈底的牌，后面我们发现了与其种类相同的牌之后，可以通过螺放在它的上面令其消去；对于一个在栈底的牌，我们就将后面一样的牌放入第 n 个栈，然后通过操作 2 消去两张牌。(15pts)
对于 m<=14 的情况，暴搜。(20pts)
对于 n=2 的情况，先能消的消去直到最后在两个栈底和当前要放的牌是三张不同的牌。第三个开始考虑：后一个元素如果不和第一个栈的一样，那么记放在第一个上面，否则放在第二个上面。这样起码保证了后一个元素是可以消去的。消去之后我们得到了一个空栈和一个有两牌的栈。接下来考虑，如过直接能和其中之一消去就消去，否则就再考虑下一张牌，若和两元素栈中上面的元素一样，当前元素就放在空栈栈底，下一个元素消去两元素栈中靠上一个后又成为了开始情况；若与栈底一样，则将当前元素再放到两元素栈上，这样后面的元素放在空栈后消去两栈的栈底之后又回到了一个空栈和一个有两牌的栈的情况。（15pts）

T3：(100pts)

首先这题可以写正解。

不过写不出正解的同学给出如下骗分策略：

大众分：暴搜(35pts)

不会 tarjan 。在暴搜基础上写单纯树形dp的分(60pts)，~~如果有心情再写一个基环树dp，可以获得整整70pts~~
不会树形dp。在此基础上拿到链的分是可以的。链是可以推出式子的。链上军营数>=2时，最左端和最右端的建军营的点，这两个军营之间的边是必然要选的，而点则是可选可不选，这两个点之外的边都是可选可不选的，而点必然不选（否则就不满足最左端和最右端了）。然后简单尝试就可以发现，有一个神奇的现象（原因显然了）：不管最左端最右端两个点在哪里，都有 2^ n/4 种情况，再乘上 n×(n-1)/2 个左右端点的情况。链上军营=1时，显然有 n×2^n/2 种情况。两种情况数求和可合并 n×(n-3)×2^n/4 种。(45pts)

T4：(36pts)