题意：给出一个长度为n平方串（由2个相同序列相互插入（但不改变同一序列的相对顺序）而成），输出串中的元素归属于第几个原串（组成平方串的串）（n <= 2000）。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4665
——>>dfs(int cur, int last, int R)，cur为目前已搜索到的对数，last为搜索到的第一个序列的上一个元素的位置，R为搜索到的第二个序列的上一个元素的位置。
#include <cstdio>
#include <cstring>using namespace std;const int maxn = 2000 + 10;
int n, a[maxn], ret[maxn];void read(){scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d", &a[i]);
}bool dfs(int cur, int last, int R){if(cur == n / 2) return 1;int i, j;for(i = last; i < n && ret[i] != -1; i++);ret[i] = 0;for(j = i+1; j < n; j++) if(ret[j] == -1 && a[j] == a[i] && j > R){ret[j] = 1;if(dfs(cur + 1, i + 1, j)) return 1;ret[j] = -1;}ret[i] = -1; //要修改回去，若不修改，会影响上一层dfsreturn 0; //发现i这个第1个没修改过的位置，因为它必须赋值且赋为0，而递归后发现其矛盾的话，这是无解的
}void solve(){memset(ret, -1, sizeof(ret));dfs(0, 0, 0);for(int i = 0; i < n; i++) printf("%d", ret[i]);printf("\n");
}int main()
{int T;scanf("%d", &T);while(T--){read();solve();}return 0;
}