1937(div2)

A. Shuffle Party

给你一个数组 $a_{1}, a_{2}, \dots, a_{n}$ 。最初，每个 $1 \leq i \leq n$ 都有 $a_{i} = i$ 。

整数 $k \geq 2$ 的运算 $swap (k)$ 定义如下：

设 $d$ 是不等于 $k$ 本身的 $k$ 的最大除数 $^{†}$ 。然后交换元素 $a_{d}$ 和 $a_{k}$ 。

假设你按照这样的顺序对每一个 $i = 2, 3, \dots, n$ 进行 $swap (i)$ 。找出 $1$ 在数组中的位置。换句话说，在执行这些操作后，找出 $j$ 和 $a_{j} = 1$ 的位置。

$^{†}$ 如果存在一个整数 $z$ 使得 $y = x \cdot z$ 是 $y$ 的整除数，那么整数 $x$ 就是 $y$ 的整除数。

很容易发现当 n 到 $2^{k}$ 时 1 才会变一次位置

void solve(){
    int n; cin >> n;
    int ans = 1;
    while(ans <= n){
        if(ans * 2 > n){
            cout << ans << endl;
            return;
        }
        ans *= 2;
    }
}

B. Binary Path

给你一个 $2 \times n$ 网格，网格中充满了 0 和 1。假设第 $i$ 行和第 $j$ 列的交叉点上的数字是 $a_{i j}$ 。

在左上角的 $(1, 1)$ 格中有一只蚱蜢，它只能向右或向下跳一格。它想到达右下方的 $(2, n)$ 单元。考虑长度为 $n + 1$ 的二进制字符串，它由写在路径单元格中的数字组成，且不改变它们的顺序。

您的目标是

通过选择任意一条可用路径，找出词典上最小的 $^{†}$ 字符串；
找出能得到这个词典最小字符串的路径数。

$^{†}$ 如果两个字符串 $s$ 和 $t$ 的长度相同，那么当且仅当在 $s$ 和 $t$ 不同的第一个位置上，字符串 $s$ 的元素小于 $t$ 中的相应元素时， $s$ 在词法上小于 $t$ 。

毒瘤

我的想法是列出所有的情况

由于 map 会自动排序复杂度会 $\times ∣ l e n ∣$ TLE

void solve() {
    int n;cin >> n;
    string a[2];
    cin >> a[0] >> a[1];
    map<string, int> mp;
    string m = a[0][0] + a[1];
    mp[m]++;
    for (int i = 1;i < n;i++) {
        m[i] = a[0][i];
        mp[m]++;
    }
    for (auto [x, y] : mp) {
        cout << x << "\n";
        cout << y << "\n";
        return;
    }
}

用 vector 发现 ${2 e 5}^{2}$ 的数据量 MLE

void solve() {
    int n;cin >> n;
    string a[2];
    cin >> a[0] >> a[1];
    vector<string> mp;
    string m = a[0][0] + a[1];
    mp.push_back(m);
    for (int i = 1;i < n;i++) {
        m[i] = a[0][i];
        mp.push_back(m);
    }
    sort(mp.begin(), mp.end());
    cout << mp[0] << '\n';
    cout << count(mp.begin(), mp.end(), mp[0]) << '\n';
}

按照官方的题解，AC

void solve() {
    int n;cin >> n;
    string a[2];
    cin >> a[0] >> a[1];
    ll ans = 1;
    string res = "";res += a[0][0];
    int i;
    for (i = 0;i < n - 1;i++) {
        char m1 = a[0][i + 1], m2 = a[1][i];
        res += min(m1, m2);
        if (m1 == m2)ans++;
        if (m1 < m2)ans = 1;
        if (m1 > m2) {
            i++; break;
        }
    }
    for (;i < n;i++)res += a[1][i];
    
    cout << res << "\n" << ans << '\n';
}

C. Bitwise Operation Wizard

有一个秘密序列 $p_{0}, p_{1}, \dots, p_{n - 1}$ ，它是 ${0, 1, \dots, n - 1}$ 的排列组合。

你需要找到任意两个索引 $i$ 和 $j$ 使 $p_{i} \oplus p_{j}$ 最大化

为此，您可以提出查询。每个查询的形式如下：选取任意索引 $a$ 、 $b$ 、 $c$ 和 $d$ （ $0 \leq a, b, c, d < n$ ）。接下来，评审团计算 $x = (p_{a} ∣ p_{b})$ 和 $y = (p_{c} ∣ p_{d})$ ，最后，你会得到 $x$ 和 $y$ 的比较结果。

请找出任意两个索引 $i$ 和 $j$ ( $0 \leq i, j < n$ )，使得 $p_{i} \oplus p_{j}$ 在所有这样的索引对中最大，最多使用 $3 n$ 个查询。如果有多对索引满足条件，您可以输出其中任何一个。

Solution

互动问题

先找到这个隐藏数组的最大值 $m x$ ，然后再找到与 $m x$ 相或的最大值的集合，在集合中找最小的一个即可。

char query(int a, int b, int c, int d) {
    char x;
    printf("? %d %d %d %d\n", a, b, c, d);
    fflush(stdout);
    cin >> x;
    fflush(stdout);
    return x;
}
void solve() {
    int n;cin >> n;
    int mx = 0;
    for (int i = 1;i < n;i++) {
        int c = query(mx, mx, i, i);
        if (c == '<')mx = i;
    }
    vector<int> ans;ans.push_back(0);
    for (int i = 1;i < n;i++) {
        int j = *ans.begin();
        char v = query(i, mx, j, mx);
        if (v == '>') {
            ans.clear();ans.push_back(i);
        } else if (v == '=') {
            ans.push_back(i);
        }
    }
    int p = *ans.begin();
    for (int i = 1;i < ans.size();i++) {
        char v = query(p, p, ans[i], ans[i]);
        if (v == '>')p = ans[i];
    }
    printf("! %d %d\n", mx, p);
    fflush(stdout);
}

D. Pinball

有一个长度为 $n$ 的一维网格。网格的 $i$ /th 单元格包含一个字符 $s_{i}$ ，这个字符要么是"<"，要么是">"。

当一个弹球被放置在其中一个单元格上时，它会按照以下规则移动：

如果弹球位于 $i$ /th 单元格上，且 $s_{i}$ 为"<"，那么弹球会在下一秒向左移动一格。如果 $s_{i}$ 为">"，则向右移动一格。
弹球移动后，字符 $s_{i}$ 会被反转（即如果 $s_{i}$ 原来是'<'，则会变成'>'，反之亦然）。
当弹球离开网格时就会停止移动：无论是从左边界还是从右边界。

您需要回答 $n$ 个个独立查询。在 $i$ -th 查询中，弹球将被放置在 $i$ -th 单元格中。请注意，我们总是在初始网格上放置一个弹球。

对于每个查询，计算弹球离开网格需要多少秒。可以证明，弹球总是会在有限步数内离开网格。

Solution

原： Problem - E - Codeforces

Codeforces Round 930 (Div. 2) A~D - 知乎

对于需要记录 > 的下标，个数的前缀和以及下标
对于需要记录 < 的下标，个数的后缀和以及下标

只有左边的 > ，右边的 < 能让 s[i] 返回, 如果没有的话就直接出去了

当 s[i]=='>' 时

若 $c n t_{1} [i - 1] = c n t_{2} [i + 1]$ ，则答案为 $i + 2 \times (s u f [i + 1] - p r e [i - 1])$
若 $c n t_{1} [i - 1] > c n t_{2} [i + 1]$ ，这时 $i$ 位置一定从右边出来，当左边比右边多 1 的时候才能将路径走满，其他情况都会有路径没走，所以需要减去多余部分。走满时，答案为 $i + n + 1 + 2 \times (s u f [i + 1] - p r e [i - 1])$ ，有多余部分时，答案为 $i + n + 1 + 2 \times (s u f [i + 1] - (p r e [i - 1] - p r e [p o s_{1} [c n t_{1} [i - 1] - c n t_{2} [i + 1] - 2]]))$
若 $c n t_{1} [i - 1] < c n t_{2} [i + 1]$ ，这时 $i$ 位置一定从左边出来，右边的有些多余部分根本不走，所以需要减去多余的部分。答案为 $i + 2 \times (s u f [i + 1] - (p r e [i - 1] - p r e [p o s_{1} [c n t_{1} [i - 1] - c n t_{2} [i + 1] - 1]]))$

当 s[i]=='>' 时，同理。

#define int long long
void solve() {
    int n;cin >> n;string s;cin >> s;s = ' ' + s;
    vector<int> pre(n + 2), suf(n + 2), pos1, pos2, cnt1(n + 2), cnt2(n + 2), ans(n + 1);
    for (int i = 1;i <= n;i++) {
        if (s[i] == '>') {
            pre[i] = i;cnt1[i] = 1;
        } else {
            suf[i] = i;cnt2[i] = 1;
        }
    }
    for (int i = 1;i <= n;i++) {
        cnt1[i] += cnt1[i - 1];
        pre[i] += pre[i - 1];
        if (s[i] == '>')pos1.push_back(i);
    }
    for (int i = n;i >= 1;i--) {
        cnt2[i] += cnt2[i + 1];
        suf[i] += suf[i + 1];
        if (s[i] == '<')pos2.push_back(i);
    }
    for (int i = 1;i <= n;i++) {
        if (s[i] == '<') {
            if (cnt1[i - 1] > cnt2[i + 1]) {//向右边
                int num2 = suf[i + 1], num1 = 0;
                if (cnt1[i - 1] == cnt2[i + 1] + 1) {
                    num1 = pre[i - 1];
                } else {
                    num1 = pre[i - 1] - pre[pos1[cnt1[i - 1] - cnt2[i + 1] - 2]];
                }
                ans[i] = i + n + 1 + 2 * (num2 - num1);
            } else if (cnt1[i - 1] < cnt2[i + 1]) {//向左边
                int num1 = pre[i - 1];
                int num2 = suf[i + 1] - suf[pos2[cnt2[i + 1] - cnt1[i - 1] - 1]];
                ans[i] = i + 2 * (num2 - num1);
            } else {
                int num1 = pre[i - 1], num2 = suf[i + 1];
                ans[i] = i + 2 * (num2 - num1);
            }
        } else {
            if (cnt1[i - 1] < cnt2[i + 1]) {
                int num1 = pre[i - 1], num2 = 0;
                if (cnt2[i + 1] == cnt1[i - 1] + 1) {
                    num2 = suf[i + 1];
                } else {
                    num2 = suf[i + 1] - suf[pos2[cnt2[i + 1] - cnt1[i - 1] - 2]];
                }
                ans[i] = 2 * (num2 - num1) - i;
            } else if (cnt1[i - 1] > cnt2[i + 1]) {
                int num1 = pre[i - 1] - pre[pos1[cnt1[i - 1] - cnt2[i + 1] - 1]];
                int num2 = suf[i + 1];
                ans[i] = n + 1 - i + 2 * (num2 - num1);
            } else {
                int num1 = pre[i - 1], num2 = suf[i + 1];
                ans[i] = n + 1 - i + 2 * (num2 - num1);
            }
        }
    }
    for (int i = 1;i <= n;i++) {
        cout << ans[i] << " \n"[i == n];
    }
}