CF290E 题解
Peter0701
2019-07-23 10:47:48
此题来自 $CodeForces$ $2013$ 年愚人节比赛的 $E$ 题。
这题难度比较大，主要是思维难度（愚人节题目都这样）。
首先，根据题意，~~问题陈述被一只流浪浣熊毁掉了~~，所以你需要先查找关于编程语言 $HQ9+$ 的资料。[资料1，有时打开较慢](http://progopedia.com/language/hq9-plus/) [资料2,大多数时间打开较快](https://esolangs.org/wiki/HQ9+)
$HQ9+$ 一共由4个命令 $H$ 、 $Q$ 、 $9$ 、 $+$ 组成。~~为了浪费大家的时间~~，简要叙述一下 $HQ9+$ 的四个命令：
$H$ 命令表示打印出“ $hello, world$ ”这个字符串。
$Q$ 命令表示打印出完整的源程序。比如源程序为“ $HH+QH99$ ”时，你就需要打印出“ $HH+QH99$ ”这个字符串。拓展：这种行为也被称为[“奎因”](https://esolangs.org/wiki/Quine)。
$9$ 命令表示打印出~~著名歌曲~~[《99瓶啤酒》](https://esolangs.org/wiki/99_bottles_of_beer)的歌词。 $C++$ 实现如下：
```cpp
for(int i=99;i>0;i--)
{
printf("%d bottles of beer on the wall,\n%d bottles of beer.\n", i);
printf("Take one down, pass it around,\n%d bottles of beer on the wall.", i-1);
}
printf("1 bottle of beer on the wall,\n1 bottle of beer.\nTake one down, pass it around,\nno more bottles of beer on the wall.");
```
而 $+$ 命令则表示向一个累加器当中增加 $1$ 。 $C++$ 实现如下：
```cpp
unsigned long accumulator = 0;
......
if(c[i]=='+') accumulator++;
```
根据题意，“在这个问题中，我们将探索它的子集——一种叫做HQ的语言……”，因此只需要考虑 $H$ 命令和 $Q$ 命令。根据[出题人Nickolas（有时打开较慢）](http://codeforces.com/profile/Nickolas)~~话说小姐姐还挺好看的~~[的博客（有时打开较慢）](http://codeforces.com/blog/entry/7216)所述，本题中 $H$ 命令经过了简化，只会输出一个字符“ $H$ ”。
接下来，就可以猜测做法了。大多数人 $WA$ 的地方就在于按照给定字符串的奇偶性去判定结果了，其实这个做法的思路是完全不正确的。实际上，这题给定的字符串是一段 $HQ$ 语言程序的运行结果，而答案要求的 $Yes$ $or$ $No$ 是在询问是否存在一段 $HQ$ 语言程序满足这个运行结果。
分析一段 $HQ$ 语言程序，假设其中有 $a$ 个 $H$ 命令和 $b$ 个 $Q$ 命令。则运行结果就是由 $a×(b+1)$ 个 $H$ 字符和 $b×b$ 个 $Q$ 字符组成的。
统计运行结果中的 $Q$ 字符数。若其为完全平方数（包括 $0$ ），则有可能满足条件，否则一定不满足条件。
再分析运行结果中第一个 $Q$ 字符之前的部分。由于第一个$Q$ 命令发出时，输出了整个程序，并且在第一个 $Q$ 命令发出前，已经输出了其前面所有的 $H$ 字符。因此第一个 $Q$ 字符之前的部分为偶数时才有可能满足条件，否则一定不满足条件。为了得到源程序，此时你应该将第一个 $Q$ 字符之前的部分的一半放入设想的源程序中。
然后，由于源程序中含有 $b$ 个 $Q$ 命令，运行结果中含有 $b×b$ 个 $Q$ 字符，因此在运行结果中第一个 $Q$ 字符到第 $b$ 个 $Q$ 字符之间的部分均为源程序，此时你应该将它们放入设想的源程序中。
接下来，直接找到最后一个 $Q$ 字符。它的后面还含有的 $H$ 字符也应该为偶数个，否则一定不满足条件。同理，此时你应该将后一个 $Q$ 字符之后的部分的一半放入设想的源程序中。
接下来，请对设想的源程序进行验证。使用源程序得到运行结果并将其与输入的运行结果比较。若不同，则不满足条件，否则就是一个满足条件的源程序。
这道题到这里就结束了，感谢观看，如有疑问评论区见，我会尽快回复。
代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
int q,sq,ctr,lens;
string s,res;
bool check()
{
int lenr=res.size();
string wynik;
for(int i=0;i<lenr;i++)
{
if(res[i]=='H')
wynik+='H';
else
for(int j=0;j<lenr;j++)
wynik+=res[j];
if(wynik.size()>1000*1000)
break;
}
return wynik==s;
}
int main()
{
cin>>s;
lens=s.size();
for(int i=0;i<lens;i++)
if(s[i]=='Q')
q++;
if(q==0)
{
printf("Yes\n");
return 0;
}
sq=sqrt(q);
if(sq*sq!=q)
{
printf("No\n");
return 0;
}
for(int i=0;i<lens;i++)
{
if(s[i]=='Q')
break;
ctr++;
}
if(ctr&1)
{
printf("No\n");
return 0;
}
for(int i=0;i<ctr/2;i++)
res+='H';
for(int i=ctr;i<lens&&sq;i++)
{
if(s[i]=='Q')
sq--;
res+=s[i];
}
ctr=0;
for(int i=lens-1;s[i]!='Q';i--)
ctr++;
if(ctr&1)
{
printf("No\n");
return 0;
}
for(int i=0;i<ctr/2;i++)
res+='H';
if(check())
{
printf("Yes\n");
return 0;
}
printf("No\n");
return 0;
}
```