1991(div1+div2)

A. Maximize the Last Element

给你一个由 $n$ 个整数组成的数组 $a$ ，其中 $n$ 是多。

在一次操作中，你将从数组 $a$ 中删除两个相邻的元素，然后将数组的剩余部分连接起来。例如，在数组 $[4, 7, 4, 2, 9]$ 中，我们可以通过操作 $[\underset{―}{4, 7}, 4, 2, 9] \to [4, 2, 9]$ 和 $[4, 7, \underset{―}{4, 2}, 9] \to [4, 7, 9]$ 分别得到数组 $[4, 2, 9]$ 和 $[4, 7, 9]$ 。然而，我们无法得到数组 $[7, 2, 9]$ ，因为它需要删除非相邻元素 $[\underset{―}{4}, 7, \underset{―}{4}, 2, 9]$ 。

重复执行这个操作直到 $a$ 中只剩下一个元素。

求 $a$ 中剩余元素的最大可能值。

易得：只有奇数位置的元素可以留下

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    int mx = 0;
    for (int i = 1;i <= n;i += 2) {
        mx = max(mx, a[i]);
    }
    cout << mx << '\n';
}
}

B. AND Reconstruction

给你一个由 $n - 1$ 个整数组成的数组 $b$ 。

构造 $a$ 数组，使得 $b_{i} = a_{i} & a_{i + 1}$ 为 $1 \leq i \leq n - 1$ ，若不存在，输出 -1

Question

如何将条件化简？
有条件： $b_{i} = a_{i} & a_{i + 1}$ ，如何推导到 $a_{i} & a_{i + 1} = (b_{i - 1} | b_{i}) & (b_{i} | b_{i + 1}) = b_{i} | (b_{i - 1} & b_{i + 1})$

void solve() {
    int n;cin >> n;
    vector<int> b(n), a(n);
    for (int i = 1;i < n;i++)cin >> b[i];
    for (int i = 1;i < n;i++) {
        for (int j = __lg(b[i]);j >= 0;j--) {
            if ((b[i] >> j) & 1) {
                a[i - 1] |= (1 << j);a[i] |= (1 << j);
            }
        }
    }
    for (int i = 1;i < n;i++) {
        if ((a[i - 1] & a[i]) != b[i]) {
            cout << "-1\n";return;
        }
    }

    for (auto x : a)cout << x << ' ';
    cout << '\n';
}

jiangly：

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> b(n - 1);
    for (int i = 0; i < n - 1; i++) {
        std::cin >> b[i];
    }
    
    std::vector<int> a(n);
    for (int i = 0; i < n - 1; i++) {
        a[i] |= b[i];
        a[i + 1] |= b[i];
    }
    for (int i = 0; i < n - 1; i++) {
        if ((a[i] & a[i + 1]) != b[i]) {
            std::cout << -1 << "\n";
            return;
        }
    }
    for (int i = 0; i < n; i++) {
        std::cout << a[i] << " \n"[i == n - 1];
    }
}

C. Absolute Zero

给你一个由 $n$ 个整数组成的数组 $a$ 。

在一次操作中，您将执行以下两步移动：

选择一个整数 $x$ ( $0 \leq x \leq 10^{9}$ )。
将每个 $a_{i}$ 替换为 $| a_{i} - x |$ 。

构造一个操作序列，使 $a$ 中的所有元素在最多 $40$ 次操作中等于 $0$ ，或者确定这是不可能的。无需尽量减少运算次数。

Solution

proof:

最初 $0 \leq a_{i} \leq 10^{9} < 2^{30}$ 即 $a_{i} \in [0, 2^{30}]$ ，若 $x = 2^{29}$ ，则可以将所有的 $a_{i}$ 范围缩小到 $[0, 2^{29}]$ ，后面则依次令 $x = 2^{28}, 2^{27}, \dots 2, 1$ 则可以将所有 $a_{i}$ 的范围缩小到 $[0, x]$ ，最终到 $[0, 1]$ 。

最终操作后的序列为 0 或 1。若所有元素都为 0 则已经满足要求，都为 1 则还需要操作 1 次。

若最初的数字为奇数，则最终操作后的序列 $a_{i}$ 一定已经全为 0 了。(由于最后的操作是 1，本来每个数字都为奇数，则操作后每个数字都为偶数了，即为 0，则已经满足要求不需要再进行操作)

若最初的数字为偶数，则操作后的 $a_{i}$ 也为偶数，需要再操作一次 1。(原因同理)

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    for (int i = 2;i <= n;i++) {
        if (abs(a[i] - a[i - 1]) & 1) {
            cout << "-1\n";return;
        }
    }
    cout << 30 + (a[1] % 2 == 0) << '\n';
    for (int i = 29;i >= 0;i--) {
        cout << (1 << i) << " ";
    }
    if (a[1] % 2 == 0) {
        cout << 1;
    }
    cout << '\n';
}

D. Prime XOR Coloring

给你一个无向图，图中有 $n$ 个顶点，编号从 $1$ 到 $n$ 。顶点 $u$ 和 $v$ 之间有一条边，当且仅当 $u \oplus v$ 是一个质数

用最少的颜色给图中的所有顶点着色，使得由边直接连接的两个顶点没有相同的颜色。

Solution

若 $n \geq 6$ ，可以 1 2 3 4 轮流交替，这样每两个相同的数字之间就相差 4，两个数相异或则不可能是质数 (这样二进制后两位一定是相等的，异或后后两位则都为 0，不可能为质数)

若 $n < 6$ ，输出样例

void solve() {
    int n;
    cin >> n;
    if (n < 6) {
        if (n == 1)
            cout << 1 << '\n' << "1" << '\n';
        else if (n == 2)
            cout << 2 << '\n' << "1 2" << '\n';
        else if (n == 3)
            cout << 2 << '\n' << "1 2 2" << '\n';
        else if (n == 4)
            cout << 3 << '\n' << "1 2 2 3" << '\n';
        else if (n == 5)
            cout << 3 << '\n' << "1 2 2 3 3" << '\n';
    } else {
        cout << 4 << '\n';
        for (int i = 1; i <= n; i++)
            cout << i % 4 + 1 << ' ';
        cout << '\n';
    }
}

E. Coloring Game

这是一个互动问题。

考虑一个由 $n$ 个顶点和 $m$ 条边组成的无向连接图。每个顶点可以用三种颜色中的一种着色： $1$ 、 $2$ 或 $3$ 。初始时，所有顶点都未着色。

爱丽丝和鲍勃正在玩一个由 $n$ 轮组成的游戏。在每一轮中，都会发生以下两个步骤：

爱丽丝选择两种不同的颜色。
鲍勃选择一个未着色的顶点，并用爱丽丝选择的两种颜色之一为其着色。

如果存在连接两个相同颜色顶点的边，则爱丽丝获胜。否则，鲍勃获胜。

我们给你这个图。您的任务是决定您想扮演哪位玩家并赢得游戏。

Solution

二分图

若给定图不是二分图(即含有奇环)，Alice 必赢，Alice 不断输出 1 2 即可，由于是奇环，最终必然会有矛盾

若给定图是二分图，Bob 必赢，将 1 ，2 的部分分开顺序填入即可。

EDU：本题的二分图判定方式值得学习

void solve() {
    int n, m;cin >> n >> m;
    vector<vector<int>> g(n + 1);
    for (int i = 1;i <= m;i++) {
        int u, v;cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bool ok = 1;
    vector<int> clr(n + 1);clr[1] = 1;

    auto dfs = [&](auto self, int u) ->void{
        for (auto v : g[u]) {
            if (!clr[v]) {
                clr[v] = 3 - clr[u];
                self(self, v);
            } else if (clr[v] + clr[u] != 3) {
                ok = 0;
            }
        }
        };
    dfs(dfs, 1);
    if (!ok) {
        cout << "Alice" << endl;
        for (int i = 1;i <= n;i++) {
            cout << 1 << " " << 2 << endl;
            int u, op;cin >> u >> op;
        }
    } else {
        cout << "Bob" << endl;
        vector<int> p1, p2;
        for (int i = 1;i <= n;i++) {
            if (clr[i] == 1) {
                p1.push_back(i);
            } else {
                p2.push_back(i);
            }
        }
        for (int i = 1;i <= n;i++) {
            int clr1, clr2;cin >> clr1 >> clr2;
            if ((clr1 == 1 || clr2 == 1) && p1.size()) {
                cout << p1.back() << " " << 1 << endl;p1.pop_back();
            } else if ((clr1 == 2 || clr2 == 2) && p2.size()) {
                cout << p2.back() << " " << 2 << endl;p2.pop_back();
            } else if (!p1.size()) {
                int op = (clr1 == 1 ? clr2 : clr1);
                cout << p2.back() << " " << op << endl;p2.pop_back();
            } else {
                int op = (clr1 == 2 ? clr2 : clr1);
                cout << p1.back() << " " << op << endl;p1.pop_back();
            }
        }
    }
}

F. Triangle Formation

给定 $a_{i}$ 代表第 $i$ 根木棒的长度，给出 $q$ 组询问，判定 $[l, r]$ 区间内能不能形成两个三角形。

Solution

若区间长度大于 $48$ ，则一定存在两个三角形。

根据极端的情况就是斐波那契数列，在 45 项的位置就已经超过 $10^{9}$ 了，所以在给出的 $45$ 个数字中一定存在一个三角形，则剩下 42 个，再加上三个数字则又一定存在一个三角形，即 48 个。

对于区间长度小于 $50$ 个的只有两种情况

考虑枚举所有可能的 6 个连续小棒，检查能否组成两个三角形
考虑枚举所有可能的 3 个连续小棒，检查能否两个不相交的集合使得分别形成三角形

若不满足这两点，就一定不存在两个三角形。

proof:

证明：？

jiangly 的代码：

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, q;
    std::cin >> n >> q;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        l--;
        
        if (r - l > 100) {
            std::cout << "YES\n";
            continue;
        }
        
        std::vector b(a.begin() + l, a.begin() + r);
        std::sort(b.begin(), b.end());
        
        bool ok = false;
        int L = 1E9, R = -1;
        for (int i = 0; i + 2 < b.size(); i++) {
            if (b[i] + b[i + 1] > b[i + 2]) {
                L = std::min(L, i);
                R = i;
            }
        }
        if (R - L >= 3) {
            ok = true;
        }
        for (int i = 0; i + 5 < b.size() && !ok; i++) {
            if (b[i] + b[i + 1] > b[i + 3] && b[i + 2] + b[i + 4] > b[i + 5]) {
                ok = true;
                break;
            }
            if (b[i] + b[i + 2] > b[i + 3] && b[i + 1] + b[i + 4] > b[i + 5]) {
                ok = true;
                break;
            }
            if (b[i + 1] + b[i + 2] > b[i + 3] && b[i] + b[i + 4] > b[i + 5]) {
                ok = true;
                break;
            }
            if (b[i] + b[i + 1] > b[i + 4] && b[i + 2] + b[i + 3] > b[i + 5]) {
                ok = true;
                break;
            }
            if (b[i] + b[i + 2] > b[i + 4] && b[i + 1] + b[i + 3] > b[i + 5]) {
                ok = true;
                break;
            }
            if (b[i + 1] + b[i + 2] > b[i + 4] && b[i] + b[i + 3] > b[i + 5]) {
                ok = true;
                break;
            }
            if (b[i] + b[i + 3] > b[i + 4] && b[i + 1] + b[i + 2] > b[i + 5]) {
                ok = true;
                break;
            }
        }
        if (ok) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
}