Atcoder AGC052

A题
\(\quad\)考虑如果构造的串长度为2N的话,那么只需要输出2N个0或者2N个1,但是要求我们构造的长度为2N+1,所以我们就需要考虑在这2N个0或者2N个1中加一个字符。
\(\quad\)但是这个做法显然是假的,因为我们有可能找不到这个位置。
\(\quad\)所以现在我们考虑利用一下这个东西的复制的性质,我们会发现一个字符串的前半段和后半段是一样的。
\(\quad\)那么我们可以得到什么性质呢?显然就是后面的1和0前面一定会有N个1和N个0。
\(\quad\)如果我们考虑从前半段选择N个0,后半段选择N个1的话,就会出现以下的情况:

  • 后半段最后一个数为0
  • 后半段最后一个数为1

\(\quad\)对于第一种情况显然我们只要最后加一个0就可以了,但是对于第二种情况我们如何验证他的正确性呢?
\(\quad\)我们又需要换一个方式思考,我们会发现我们后半段选择的一可以分为两个部分

  • 后面至少一个0的1
  • 后面一个0都没有的1

\(\quad\)我们发现其中第二部分可以在前半段的区间里面求得,所以可以保证后面一定有一个0。
\(\quad\)因此我们只需要输出N个0+N个1再加一个0就可以了。
\(\quad\)虽然这道题就这么做出来了,但是发现没有什么好的推导过程。

B题

原文地址:https://www.cnblogs.com/wanwanjiuhao7744/p/14592330.html