阅读原文
此题来自 \(CodeForces\) \(2013\) 年愚人节比赛的 \(E\) 题。
这题难度比较大，主要是思维难度（愚人节题目都这样）。
首先，根据题意，问题陈述被一只流浪浣熊毁掉了，所以你需要先查找关于编程语言 \(HQ9+\) 的资料。资料1，有时打开较慢 资料2,大多数时间打开较快
\(HQ9+\) 一共由4个命令 \(H\) 、 \(Q\) 、 \(9\) 、 \(+\) 组成。为了浪费大家的时间，简要叙述一下 \(HQ9+\) 的四个命令：
\(H\) 命令表示打印出“ \(hello, world\) ”这个字符串。
\(Q\) 命令表示打印出完整的源程序。比如源程序为“ \(HH+QH99\) ”时，你就需要打印出“ \(HH+QH99\) ”这个字符串。拓展：这种行为也被称为“奎因”。
\(9\) 命令表示打印出著名歌曲《99瓶啤酒》的歌词。 \(C++\) 实现如下：
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++\) 实现如下：
unsigned long accumulator = 0; ...... if(c[i]=='+') accumulator++;根据题意，“在这个问题中，我们将探索它的子集——一种叫做HQ的语言……”，因此只需要考虑 \(H\) 命令和 \(Q\) 命令。根据出题人Nickolas（有时打开较慢）话说小姐姐还挺好看的的博客（有时打开较慢）所述，本题中 \(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\) 字符之后的部分的一半放入设想的源程序中。
接下来，请对设想的源程序进行验证。使用源程序得到运行结果并将其与输入的运行结果比较。若不同，则不满足条件，否则就是一个满足条件的源程序。
这道题到这里就结束了，感谢观看，如有疑问评论区见，我会尽快回复。
代码如下：
#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; }转载于:https://www.cnblogs.com/Peter0701/p/11248542.html
相关资源：JAVA上百实例源码以及开源项目