传送门：点击打开链接
题意：小刀和大刀是双胞胎兄弟。今天他们玩一个有意思的游戏。 大刀给小刀准备了一个长度为n的整数序列。小刀试着把这个序列分解成两个长度为n/2的子序列。
这两个子序列必须满足以下两个条件：
1.他们不能相互重叠。
2.他们要完全一样。
如果小刀可以分解成功，大刀会给小刀一些糖果。
然而这个问题对于小刀来说太难了。他想请你来帮忙。(n <= 40)
思路：调整了几天，今天手感好到爆啊，好久没有连编译错误都没有一次性写完的了。
这道题很有意义，n的大小为40，会比较容易想到，如果为20时就可以枚举子集，那么40是不是应该考虑折半的方法。
这题的折半非常有意思，先取前n/2个数字，去枚举所有状态，把前n/2个数字分到两个串中，如果一个串是另一个串的前缀，那么就把非前缀的后面部分插入到hash表中。
再考虑后n/2个数字，枚举所有状态，把后n/2个数字放到两个串中，如果一个串是另一个串的后缀，那么去hash表中查找非后缀部分是否存在，如果存在，那么就是有解了，否则就是无解
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout<<"["<<x<<"]";
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w+",stdout);
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;const int MX = 1e5 + 5;
const int HMAX = 1000007;
const int sed = 131;int n;
int A[100], B[100], S[2][MX];
struct HData {ULL x;int nxt;
} HA[MX];
int Head[HMAX], rear;
void Hash_init() {rear = 0;memset(Head, -1, sizeof(Head));
}
void Hash_add(ULL x) {int h = x % HMAX;for(int i = Head[h]; ~i; i = HA[i].nxt) {if(x == HA[i].x) return;}HA[rear].x = x;HA[rear].nxt = Head[h];Head[h] = rear++;
}
bool Hash_query(ULL x) {int h = x % HMAX;for(int i = Head[h]; ~i; i = HA[i].nxt) {if(x == HA[i].x) return true;}return false;
}int main() {int T; //FIN;scanf("%d", &T);while(T--) {Hash_init();scanf("%d", &n);for(int i = 1; i <= n; i++) {scanf("%d", &A[i]);B[i] = A[i];}sort(B + 1, B + 1 + n);int sz = unique(B + 1, B + 1 + n) - B - 1;for(int i = 1; i <= n; i++) {A[i] = lower_bound(B + 1, B + 1 + sz, A[i]) - B;}int hn = n / 2;for(int s = 0; s < (1 << hn); s++) {int cur[2] = {0, 0}, sign = true;for(int i = 0; i < hn; i++) {int t = s >> i & 1;S[t][++cur[t]] = A[i + 1];if(cur[t] <= cur[t ^ 1] && S[t][cur[t]] != S[t ^ 1][cur[t]]) {sign = false; break;}}if(sign) {ULL x = 0;int id = cur[0] >= cur[1] ? 0 : 1;for(int i = cur[id ^ 1] + 1; i <= cur[id]; i++) {x = x * sed + S[id][i];}Hash_add(x);}}bool ans = false;for(int s = 0; s < (1 << hn); s++) {int cur[2] = {0, 0}, sign = true;for(int i = 0; i < hn; i++) {int t = s >> i & 1;S[t][++cur[t]] = A[n - i];if(cur[t] <= cur[t ^ 1] && S[t][cur[t]] != S[t ^ 1][cur[t]]) {sign = false; break;}}if(sign) {ULL x = 0;int id = cur[0] >= cur[1] ? 0 : 1;for(int i = cur[id]; i != cur[id ^ 1]; i--) {x = x * sed + S[id][i];}if(Hash_query(x)) {ans = true; break;}}}printf("%s\n", ans ? "Good job!!" : "What a pity!");}return 0;
}