Codeforces Global Round 20 A-F,H

连续一个月掉小分，这把终于上大分了 好耶！

A. Log Chopping

题意：现在有 \(n\) 个木棍，第 \(i\) 根长度为 \(a_i\)，Alice和Bob两人轮流操作，可以选择一根木棍将其切成两半，且两半的长度都需要是>1的整数。最后无法操作的人失败，问谁获胜。

虚假博弈，显然能切的次数是固定的，最终会全变成长度为1的木棍，判断能切的奇偶性即可。

int n, m;

void solve(){
    cin >> n;
    int sum = 0;
    for(int i=1;i<=n;i++){
        int x; cin >> x;
        sum += x - 1;
    }
    if(sum % 2) cout << "errorgorn\n";
    else cout << "maomao90\n";
}

B. I love AAAB

题意：你有一个字符串（初始为空），操作：可以在其中任意位置插入一段形如"AA...AB"的字符串，A的数量至少为1。给定目标串b，问操作任意次，能否构造出串b。

类似括号序，出现一个B时前面要至少找到一个A与其匹配，那么从左到右扫一遍，将A视为1，B视为-1，看有无前缀和小于0即可。注意特判：不存在B也是不行的。

int n, m;

void solve(){
    string s;
    cin >> s;
    int sum = 0;
    for(int i=0;i<s.size();i++){
        if(s[i] == 'A') sum++;
        else sum--;
        if(sum < 0){
            cout << "NO\n";
            return;
        }
    }
    if(s.back() != 'B'){
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
}

C. Unequal Array

题意：给出一个序列 \(a\)，其质量定义为其中 \(a_i=a_{i+1}\) 的元素个数，现在你可以进行操作：选取两个相邻元素，将它们修改为任意的 \(x\)。问：最少多少次操作可以使得序列的"质量"小于等于1

不难发现，执行这个操作只能改变本来满足的 \(a_i=a_{i+1}\) 的位置移动，而无法直接消除。那么我们找到原序列最早和最晚出现的相邻点，只有将这两对相邻点不断逼近后合为一对，才能满足条件。那么答案即为这两对相邻点之间的距离（注意边界和0）

int n, m;
int a[maxn];

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    int mi = 0, mx = 0;
    for(int i=1;i<n;i++){
        if(a[i] == a[i+1]){
            if(!mi) mi = i;
            mx = i;
        }
    }
    if(mx == mi) cout << "0\n";
    else cout << max(mx-mi-1, 1) << '\n';
}

D. Cyclic Rotation

题意：给出一个序列 \(a\) 和它的重新排列 \(b\)，有一种操作：选取两个相同元素，将左边的移动到另一个右边。问能否对序列 \(a\) 进行任意次操作，使其变为 \(b\)？

模拟，我们从最末端开始考虑，\(a\) 和 \(b\) 的末尾元素必须相同，设他们末尾都为 \(x\)， \(a\) 末尾连续的 \(x\) 数量必须少于 \(b\) 末尾连续 \(x\) 的数量。这样才有可能从 \(a\) 前面拿若干个 \(x\) 到末尾来使得他们末尾。记录每种数被拿的次数。考虑完后，将他们末尾的 \(x\) 都删掉，继续处理下一个末尾。

遇到 \(a\) 和 \(b\) 末尾不相同时，如果 \(a\) 的末尾恰好”被拿过“，就可以忽略 \(a\) 中这个末尾，记得让计数-1。如果没有被拿过，那么NO

还有一点：当 \(a\) 的末尾连续 \(x\) 长度大于 \(b\) 末尾连续 \(x\) 长度时，如果 \(x\) 可以被拿走一些也是可行的，不用直接NO。

这样模拟能执行到最后就是YES

int n, m;
int a[maxn], b[maxn];
int rem[maxn], del[maxn];

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) rem[i] = del[i] = 0;
    for(int i=1;i<=n;i++) cin >> a[i], rem[a[i]]++;
    vector<int> tmp(n+1, 0);
    for(int i=1;i<=n;i++) cin >> b[i], tmp[b[i]]++;
    for(int i=1;i<=n;i++) if(tmp[i] != rem[i]){
        cout << "NO\n";
        return;
    }

    int r1 = n, j = n;
    while(j >= 1){
        while(a[r1] != b[j]){
            if(r1>0 && del[a[r1]]) del[a[r1]]--, r1--;
            else{
                cout << "NO\n";
                return;
            }
        }
        int lena = 1, lenb = 1;
        for(int i=r1-1;i>=0;i--){
            if(a[i] != a[r1]){
                lena = r1 - i;
                break;
            }
        }
        for(int i=j-1;i>=0;i--){
            if(b[i] != b[j]){
                lenb = j - i;
                break;
            }
        }
        if(lena > lenb){
            if(lena - del[a[r1]] > lenb){
                cout << "NO\n";
                return;
            }
            del[a[r1]] -= lena - lenb;
            r1 -= lena;
            j -= lenb;
        }else{
            del[a[r1]] += lenb - lena;
            r1 -= lena;
            j -= lenb;
        }
    }
    cout << "YES\n";
}

E. notepad.exe

题意：交互题，有一台打字机和若干个字符串，这些字符串是未知的，你可以指定最大打印宽度 \(w\)，打印机将按顺序打印这些字符串，两串之间需要一个空格，当行宽度不够即会换行，最终会返回你打印的行数 \(h\)。你需要用至多 \(n+30\) 次询问，输出可能的最小打印面积（\(w\times h\)）

首先容易想到的是，可以二分找到一行能打下所有字符串的最小宽度 \(w_1\)，此时最小打印面积为 字符串总长+n-1个空格

然后去想，如果要打印两行使得答案更优，那么这个字符串必须差不多能正好分成等长的两半，这样就能贪一个空格。只需要尝试 \(\lfloor w_1/2\rfloor\) 的宽度即可，宽度更大则不可能更优，更小则不可能两行打印完。

同理，尝试三行，四行...尝试第 \(i\) 行即询问宽度 \(\lfloor w_1/i\rfloor\)，更新答案。

int n, m;

int query(int x){
    cout << "? " << x << endl;
    cout.flush();
    int r; cin >> r;
    return r;
}

void solve(){
    cin >> n;
    int l = 1, r = 4000000;
    while(l < r){
        int mid = (l + r) / 2;
        if(query(mid) == 1){
            r = mid;
        }else{
            l = mid+1;
        }
    }
    ll ans = l;
    for(int i=2;i<=n;i++){
        int h = query(l / i);
        if(h == 0) break;
        ans = min(ans, 1ll * h * (l / i));
    }
    cout << "! " << ans << endl;
    cout.flush();
}

F. Array Shuffling & Checker for Array Shuffling

题意：给出一个序列 \(a\)，你需要将其打乱，使得其复原需要的最少交换次数尽可能多。

F1：构造一个打乱后的序列。

F2：给定打乱后的序列，判断其是否满足条件（写个spj）

首先要将问题简化，注意到这题其实 \(a\) 的顺序是不影响打乱方案的（写代码的时候要管，但逻辑上不影响结果），我们可以将 \(a\) 中相同的元素都放在一起

再进一步，对于每一种元素，记录其出现的次数，将所有元素按照出现次数排序。每个元素都依次放到下一个元素的出现位置上（有空缺，先不管），最后一个元素去填补所有空缺。这样似乎能贪心地让序列尽可能乱。

严谨地考虑：假设我们有了打乱后的序列 \(b\)，现在将每个 \(a_i\) 向 \(b_i\) 连边，那么我们发现复原的过程其实是一个走环的过程（任何排列其实都构成若干个环，不过因为我们这里有重复元素，不是几个独立环的组合，但复原过程还是可以拆成走若干次环）

对于一个长度为 \(l\) 的环，将其复原到位需要 \(l-1\) 次，那么可以想到，环越少，复原需要的次数就越多。

假设出现次数最多的元素出现了 \(x\) 次，那么显然环不可能少于 \(x\) 个，上述构造方案恰恰可以令环数仅为 \(x\)（即除了出现最多的那个元素涉及的环之外，不存在其他环）

F2就是这个结论，将最多的那个元素删去后，拓扑判断是否存在环即可。

F1：

int n, m;
int a[maxn];

struct sss{
    vector<int> pos;
    int val;
}s[maxn];

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) s[i].pos.clear(), s[i].val = i;
    int mxa = 0;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        s[a[i]].pos.push_back(i);
    }
    vector<int> ans(n+1, 0);
    sort(s+1, s+n+1, [](sss x, sss y){
        return x.pos.size() < y.pos.size();
    });
    for(int i=1;i<n;i++){
        if(s[i].pos.empty()) continue;
        for(int j=0;j<s[i].pos.size();j++){
            ans[s[i+1].pos[j]] = s[i].val;
        }
    }
    for(int i=1;i<=n;i++) if(!ans[i]) ans[i] = s[n].val;
    for(int i=1;i<=n;i++) cout << ans[i] << " \n"[i == n];
}

F2：

int n, m;
int a[maxn], b[maxn];
int cnt[maxn];
int mxp;

vector<int> vp[maxn];

void solve(){

    cin >> n;
    for(int i=1;i<=n;i++) cnt[i] = 0;
    for(int i=1;i<=n;i++){
        vp[i].clear();
        cin >> a[i];
        cnt[a[i]]++;
    }
    for(int i=1;i<=n;i++) cin >> b[i];
    mxp = 1;
    for(int i=1;i<=n;i++) if(cnt[i] > cnt[mxp]) mxp = i;
    vector<int> du(n+1, 0);
    for(int i=1;i<=n;i++){
        if(a[i] == mxp || b[i] == mxp) continue;
        vp[a[i]].push_back(b[i]);
        du[b[i]]++;
    }
    queue<int> q;
    for(int i=1;i<=n;i++) if(du[i] == 0) q.push(i);

    int ans = 0;
    while(!q.empty()){
        int p = q.front();
        q.pop();
        ans++;
        for(int v: vp[p]){
            du[v]--;
            if(du[v] == 0) q.push(v);
        }
    }

    if(ans == n) cout << "AC\n";
    else cout << "WA\n";
}

H. Zigu Zagu

题意：有一个01字符串，你可以操作：选择一段01交互出现的区间（不存在连续0或连续1），删去这个区间。有Q个询问，每次询问 \(s[l..r]\) 这个子串需要最少几次操作使得其被删为空。

贪心地考虑不难发现，一定删尽可能长的区间，我们可以首先把整串拆成几个可删的区间。

决策点在于：如果先删去中间的一个形如 0...1 或 1...0的区间，就能使两端区间合并，从而减少删的次数。

我们用一个区间的结尾来标记（指代）这个区间，区间的开头即为上一个区间的结尾（不然上一个区间应该扩展）

比如我用 01101 表示这样的一个整串：..0 0..1 1..1 1..0 0..1

即当我删去一个1时，如果前一位为0，这个0会自动和下一位合并，相当于一同被删去。也就是说，我们有删1，删0，删01，删10这四种操作

那么删除需要的次数即为0和1中较多的那个数！

最后考虑一下边界即可

int n, m;
int sum[maxn][2];
string s;

void solve(){
    cin >> n >> m >> s;
    s = ' ' + s;
    s += s.back();
    for(int i=1;i<=n;i++){
        sum[i][0] = sum[i-1][0];
        sum[i][1] = sum[i-1][1];
        if(s[i] == s[i+1]) sum[i][s[i]-'0']++;
    }
    while(m--){
        int l, r;
        cin >> l >> r;
        cout << max(sum[r-1][1]-sum[l-1][1], sum[r-1][0]-sum[l-1][0]) + 1 << '\n';
    }
}