sgu293：Game with Q an C(構造)

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;
}