1991(div1+div2)

A. Maximize the Last Element

给你一个由 n 个整数组成的数组 a ,其中 n

在一次操作中,你将从数组 a 中删除两个相邻的元素,然后将数组的剩余部分连接起来。例如,在数组 [4,7,4,2,9] 中,我们可以通过操作 [4,7,4,2,9][4,2,9][4,7,4,2,9][4,7,9] 分别得到数组 [4,2,9][4,7,9] 。然而,我们无法得到数组 [7,2,9] ,因为它需要删除非相邻元素 [4,7,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

给你一个由 n1 个整数组成的数组 b

构造 a 数组,使得 bi=ai&ai+11in1 ,若不存在,输出 -1

Question

如何将条件化简?
有条件:bi=ai&ai+1,如何推导到 ai&ai+1=(bi1|bi)&(bi|bi+1)=bi|(bi1&bi+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

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

  1. 选择一个整数 x ( 0x109 )。
  2. 将每个 ai 替换为 |aix|

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

Solution

proof:

最初 0ai109<230ai[0,230],若 x=229,则可以将所有的 ai 范围缩小到 [0,229],后面则依次令 x=228,227,2,1 则可以将所有 ai 的范围缩小到 [0,x],最终到 [0,1]

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

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

若最初的数字为偶数,则操作后的 ai 也为偶数,需要再操作一次 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 个顶点,编号从 1n 。顶点 uv 之间有一条边,当且仅当 uv 是一个 质数

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

Solution

n6,可以 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 条边组成的无向连接图。每个顶点可以用三种颜色中的一种着色: 123 。初始时,所有顶点都未着色。

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

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

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

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

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

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

Solution

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

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

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

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

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