洛谷秋令营Day6-模拟赛

实况

• 13：55 发题目，写代码模板，创建目录
• 14：25 看完 4 道题，但是只有 T1 50 分的思路，后边都思路不太明确。
• 15：25 写完了 T1 正解，对拍应该是通过了。
• 15：30 上厕所放松一下。
• 16：15 写完了 T2 50 分部分分，通过了两个样例（一小一大）。按理说需要对拍，但是我不会写暴力，所以先看后边的题了。
• 17：10 写完了 T3 的两个部分分，其中写第二个部分分的时候先尝试用 next_permutation，后来发现有重复的时候没法用，就只能手写 3 个串分别的排列了。
• 17：30 尝试写 T4 部分分失败，发现没想象中那么好写，事已至此也不想写了，回去测试其他题目去了。
• 17：45 不再做任何改动，直接提交了。

思路

T1

暴力做法，枚举 S，然后去掉 S 中最小的 k 个数，看是否符合题意，可以拿 50 分。

这个题给的数据范围只有 3000，且是求方案数，这题大概率是个 DP，我目前可能只能做 300 的情况。

考虑前 i 个数里面选一个集合，看总和 >= j 的集合有多少个，只要枚举当前的数选或者不选就好了，可以 n 方算出来。

我们先看看立方做法吧。

m 也比较小，说明和是多少可能是一维状态

能枚举 T 然后算 S 的个数吗？这样的问题在于会重复，我们要考虑怎么去重

发现 a 的顺序似乎无所谓，所以先排个序也挺好。

考虑前 i 个数里选一个集合，去掉 j 个元素之后总和能 >= s 的方案数，

能不能正难则反呢，考虑计数 S 集合，S 应满足其去掉任意 k 个元素后得到的集合 T 一定和 < m，当然是去掉最小的 k 个。

我们不妨先固定住 k，看看怎么算结果，这样我们只关心留下的数字是否 >= m。

我们关心留下的最小的数字是谁，这样从留下的数字往右的可以拿到 >= m，往左的需要挑 k 个删除掉。

这样做法似乎就呼之欲出了

我们枚举 S 集合去掉 k 个元素之后剩下的元素中，最小的那个是谁，假设是第 i 个。

这样，S 集合的个数转化为两部分的方案数，第一部分是左边 i - 1 个中选 k 个的方案数，第二部分是右边 n - i 个数里选到和 >= m - a[i] 的方案数。左边就是一个组合数，右边就是一个 DP

如果倒序排序一下，就更好写一些了，左边是看前 i - 1 个数中随便选数，和 < m - a[i] 的方案数（正难则反），右边是 C(n - i, k)，相乘就好了。

这样就是需要一个 n 方的预处理，然后枚举 k，对于每个 k，左边可以枚举和究竟是多少，右边一下子算出来了，总复杂度就是平方的（前缀和优化的话）。

这样会重复或者漏掉吗？

用样例手玩了一下，应该是对的

对拍了一下，没有测出问题

对拍并没有测大数据，实际上我有一个地方忘了取模了，导致挂了 30 分，麻了。

T2

多测

优先要满足插入操作尽可能少，其次才是字典序。

括号序列的字典序应该指的是尽量左括号在前吧。

最小插入次数是多少？似乎可以根据目前已有的左右括号数算出来。

如果左右括号补到相等了，一定能通过操作 2 变成字典序最小吗？

有一个特殊数据，左右括号数量相等，则只需要前提就好了，可以考虑做一下。

最大的暴力怎么做？不太懂

我觉得，应该先做 2 操作再做 1 操作比较好。

什么时候才需要做 2 操作？

如果末尾是左括号，则拉到最左边后可能不需要再插入新的括号了，当然也可以选择 1 操作塞到末尾右括号。

如果末尾是右括号，则其拉到最左边之后，至少要从后边再拉过来一个左括号，否则还需要用一个操作 1。

我们刚才分析出来了要先做 2 再做 1，所以其实就是对输入的串进行了一波循环移位

即，先循环移位一下，再看看还得补哪些地方的括号。

再进行 1 操作时，为了保证字典序最小，左括号肯定是尽量往前放，右括号往后放，这必然是优的。

这样，我们只需要循环移位，然后从左到右扫一遍，把前缀和 < 0 的给补到 >= 0，最后再往右塞右括号就好了。这样能拿 50 分。

出 bug 了，我们来看一下。

先做 2 再做 1 应该是没有疑问的。

万幸，发现只是一个笔误！修复之后就通过了两个样例

但现在没有能对拍的程序，我们可能要写一个暴力，可惜虽然我会写 50 分的做法，但只让我做这 50 分里的 20 分的暴力部分我还真不会写。这是一个隐患。

不妨考虑一下特殊性质分数。如果左右括号数量相等，是否存在一种排法，使得所有前缀和都 >= 0 呢？

我们可以写一下，生成一些数据 assert 一下看看，发现并非如此。T2 就先这样吧。

T3

似乎是一道很不擅长的题目呢。

后边又看了一下，似乎还是完全不知道咋入手。

发现第一个测试点 n = 1，直接输出 m + 1 就白送分了，奖励读完题的朋友。但是这种点容易想当然输出错，要想清楚。

对于 2-4 测试点，需要枚举 (5!)^3 种情况，不到 2e6 种情况，然后用 trie 模拟一下就好了，也算是白给的。

好像要用 next_permutation 写比较好呢？如果要用的话，考虑到有重复元素，所以需要把每个元素带上一个唯一的 id，然后就可以用 next_permutaion 写了。

T4

有点像 NOIP 2020 的污水处理题。最暴力的分怎么拿？

无自环，但是可能有平行边。

有一个给出的图是一条链的部分分。

我们可以把每个点连接的其他点，按照管道高度从高到底排序，然后模拟注水的分发过程

链的情况可以做，但是没时间写了，并且其实也不是很好写。

最终期望得分 100 + 50 + 16 + 0 = 166，实际得分 70 + 50 + 16 + 0 = 136。

经验教训

• **对拍也不是万能的！**脑子里一定要知道对拍有哪些错查不出来，然后人工去检查这样的错误。我曾经在 5 年前在洛谷上发过这样一个帖子，可以参考：【集思广益】对拍查不出的bug - 洛谷。这次只挂 30 分纯属是因为数据水，事实上完全可能挂得和暴力分一样的。
• 平时主要练绿题是对的。这次 T1 就是一个上位绿题，T2 也差不多，后边两个题比较难，大家几乎都得不了几分，所以谁能 AC 掉前两题中的任何一道，其他的只打最基础的暴力至少就是个省一了。我就算挂了 30 分，排名依然不是很差，在弱省拿个一等奖还是没问题的。
• **难题的部分分也很难打，但也并不是一分都打不了。**本次比赛的 T3 数学含量非常高，题也很长，看起来就非常难做，但是仔细读完题会发现第一个测试点的 4 分是白送的，直接输出 m + 1 就好了，2-4 个测试点只需要暴力枚举全排列然后模拟在字典树中插入，完全不用会其他高超的技巧就可以，这样就在一道难题上拿到了 16 分。T4 的话就确实过于困难了，最小的暴力以及特殊性质的想法和代码都困难，大家普遍得分是 0。