关于 P5650 的解题过程

Eason_AC · 2020-10-15 13:54:05 · 个人记录

从原来的题解中蒯下来的，做了一些修改。

虽然是废话，但又不想删，大佬们轻喷吧。

那天下午两点月赛一开始就点进去看。当时第一眼还理解错了题意，还以为只要算出最多的连续的 0 的个数就行了，于是就写出了代码，满怀信心地交上去，结果 10 分，只过了第一点，剩下 9 个点全 WA 掉。一开始我还有些不明白，但不过 1 分钟便弄出了一个 \texttt{hack} 掉自己的数据：0001100000，如果按照我这个思想应该是 5，但是答案应该是 6，很明显应该选取整段 0/1 串。

过了大约 20 分钟左右吧，听坐对面的巨佬说要特判全是 1 的字符串的时候要输出 -1，于是根据这个特判再结合自己原来的程序弄出了个新程序，然后就拿这个程序交上去多了 10 分。

然后又过去了 5 分钟。

突然想起能打暴力得点分？我真是傻，自己还硬磕在这里磕了半个多小时……不多说，上暴力，终于得到了 60 分的好成绩（当然，剩下四个点 T 得飞起，吸氧都拯救不了）。

可是我依然不甘心于得暴力分，于是，我推了半天，最后突然想到一个这样的想法——把原来连续的几个 0 或者 1 以及他们对这个 0 的个数减去 1 的个数的最大值的贡献看成一个整体。这个方法貌似挺可行，于是我又不断地 \texttt{Code and debug} 了 15 分钟之后，满怀信心地又交了一次。结果只有 80 分，而且更离谱的是，前两个点 \texttt{WA} 了。当时我就懵了，前两个点 n\leqslant 10 的还 \texttt{WA} 就没有道理了吧。

不过好在，我还是弄了一个能够 \text{hack} 掉自己的数据： \begin{matrix}\underbrace{000\cdots0}\\\text{10个零}\end{matrix} ，答案不用多想也知道是 10，但是我这个程序输出 0。于是分析之后发现：这个程序的 for 循环里面有可能段数为 1 的时候就直接略过了。所以将里面的一些小细节改了一下，交上去，就愉快地 A 掉了。