自动搬运

查看原文

来自洛谷，原作者为

	lndjy 退役oier，偶尔参与比赛出题，tag是我另一个身份，有人认识吗（）

搬运于2025-08-24 22:45:15，当前版本为作者最后更新于2023-02-18 20:32:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

官方题解

第一个部分分是爆搜，第二个是记忆化。

A 性质是随便写的贪心就能过。C 性质是给的推出来贪心策略而不是直接求答案的人。

众所周知我是良心出题人，所以这题必然不可能让你巨大分类讨论，你首先要坚信这题有简单做法。

直接考虑构造策略是困难的，可以换个角度，考虑答案的上界，有一个比较明显的是 $\min(1-?,?-2)+\min(2-?,?-1)$。如果上界能取到的话，也就是说每个 $\min$ 里面较小的值对应的每一个木棒都能和对应的拼上。可以发现 B 性质满足条件。想到这里的话造小数据对拍不断修正应该就可以得到正解了。

考虑为什么有时会不够每一个都能和对应的拼上。如果所有的都是 $1-2$，你需要拼成一条链，就有一个拼不上。$2-1$ 同理。

但这样还不够。按照上面方式计算出的是所有木棒围成一个环的答案，而要求的是一条链，所以计算出的答案等于所有非 $0-0$ 木棒数量的和，那么答案要减一。

如果对这个做法的可行性有疑问，可以这样理解，这也是构造方案：对于一个 $i-1$ 和 $2-j$，把这两个“粘贴”在一起，答案+1，同时把这两个删除，变成一个 $i-j$。$2+1$ 同理。这样就能构造出上面求的答案，而最优性上面已经说了。

赛时发现了很多其他做法，欢迎来写题解！