sgu293：Game with Q an C(构造)

题目大意：
有一个长度为 2n?1 的 01 序列，题目会将元素一个一个告诉你，你在每一时刻可以交换两个不同位置的元素。求出一种方案，使得在每个奇数时刻序列都是回文序列。

分析：
又见构造题一道。 ( 构造神题啥的最不会做了 QAQ)
自己想出了前一半，膜拜神?代码差不多理解了另一半。
设当前的轮数为 2i+1 ， 0,1 分别有 s0,s1 个，由于 s0,s1 中必有一个是奇数，我们不妨设 s0 是奇数，那么我们将序列第 i+1 项置为 0 ，其余的按 0101...1010 or 1010...0101 的填，假如有一个数字的个数不够了中间就都用另一个数字 ( 参见代码 ) 。我们只要证明它和之前的方案差距在两对 (0,1) 之内即可。
对于 2i?1 轮之后加入了两个数字分情况讨论。
假如加入的是两个不同的数字，那么它们之间至多交换一次。由于 s0,s1 奇偶性，中间点必定会右移变成另一个数，如果原来的 |s0?s1|=1 ，也就是说两边数字刚好足够的话，我们不需要交换，因为此时是严格满足 01 相间的，中间点直接向右移一位就会变成另一个数。如果 |s0?s1|>1 ，也就是说中间有一堆相同的，形如 100a001 ，如果这一堆与中间点数字相同，那么我们将这一堆的左边第二个与最右边的右边的那个数交换，就可以满足要求，如果这一堆与中间点的数字不同，我们只需将中间点与堆左边第二个交换即可。这种情况下至多交换两次。
假如加入的是两个相同的数，那么中间点右移一位不会改变数字，用类似的方法也可以证明至多交换两次。

AC code：

#include 
   
     #define inv(n, x) ((n)-(x)+1) #define pii pair
    
      #define X first #define Y second #define pb push_back #define mp make_pair #define clr(a, b) memset(a, b, sizeof a) #define rep(i, a, b) for(int i = (a); i <= (b); ++i) #define per(i, a, b) for(int i = (a); i >= (b); --i) typedef long long LL; typedef double DB; typedef long double LD; using namespace std; void open_init() { #ifndef ONLINE_JUDGE freopen(input.txt, r, stdin); freopen(output.txt, w, stdout); #endif ios::sync_with_stdio(0); } void close_file() { #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif } const int MAXN = 4100; int n; char str[MAXN]; bitset
     
       cur, nxt; char src; int s[2], l; inline void add(char c) { s[c==src]++, cur[++l] = c==src; } int main() { open_init(); scanf(%d %c, &n, &src); s[1]++, cur[++l] = 1; puts(Qc);puts(0 0); for(int i = 2, mid = 2; i <= n; ++i, ++mid) { add(getchar()), add(getchar()); bitset
      
        tmp; rep(k, 0, 1) { int ts[2] = {s[0], s[1]}; if(ts[0]&1) tmp[mid] = 0, ts[0]--; else tmp[mid] = 1, ts[1]--; for(int j = 1, tk = k; j < mid; ++j, tk ^= 1) if(!ts[tk]) tmp[j] = tmp[l-j+1] = tk^1, ts[tk^1] -= 2; else tmp[j] = tmp[l-j+1] = tk, ts[tk] -= 2; if(!k || (tmp^cur).count() < (nxt^cur).count()) nxt = tmp; } vector
       
         p[2]; rep(j, 1, l) if(nxt[j] != cur[j]) p[cur[j]].pb(j); rep(j, p[0].size()+1, 2) puts(0 0); rep(j, 0, (int)p[0].size()-1) printf(%d %d , p[0][j], p[1][j]); cur = nxt; } close_file(); return 0; } 
       
      
     
    
   

?