题目传送门
题意：给你一个长为 2n 的 01 序列 a，你可以选择它的一个子序列，将这个子序列循环右移一位。问是否能使得最终序列满足：可以严格分成两个完全相同的子序列。
显然，当 0/1 的个数为奇数时一定无解。于是只考虑为偶数的情况。
我们可以发现一个性质：我们选中的子序列一定是严格 01 交替的（相邻两个不同、第一位和最后一位也不同），否则一定可以删除一些元素使得效果完全不变。而当我们选中 01 交替的子序列循环右移时，相当于将这个子序列中元素取反。
思考发现，“可以严格分成两个完全相同的子序列”这个限制本身比较复杂，难以判断，于是我们可以猜测有一种平凡的操作策略满足条件。有一种显然能严格分开的序列，即第 ∀1≤i≤n,a2i−1=a2i。想到这个之后就比较简单了，我们将原序列两两分组，如果这个组的两个元素相同，则可以忽略，否则我们在这个 01 中选一个“与上次选的不同”的数字（为了满足 01 交替）。如果元素不同的组数量为偶数，则可以形成一个 01 交替的序列，那么奇数情况怎么办呢？显然如果有奇数组不同的，本身就不满足最开始的限制了（0/1 的个数为偶数），一定无解。
By Vercingetorix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| int main()
{
#ifdef LOCAL
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
#endif
int ta;
cin>>ta;
forn(ifa,0,ta) {
int n;
string s;
cin>>n>>s;
vi ans;
int cur = 0;
for(int i = 1; i < 2*n; i+=2) {
if(s[i] != s[i-1]) {
if((s[i] - '0') == cur) ans.pb(i);
else ans.pb(i-1);
cur ^= 1;
}
}
if(ans.size()%2) {
cout<<"-1\n";
continue;
}
cout<<ans.size();
for(auto x : ans) cout<<' '<<x+1; cout<<'\n';
forn(i,0,n) cout<<2*i+1<<' '; cout<<'\n';
}
}
|