Triple Four

Problem Statement

You are given an integer sequence of length $N$: $A = (A_1,A_2,\ldots,A_N)$.

Determine whether there is a place in $A$ where the same element appears three or more times in a row.

More formally, determine whether there exists an integer $i$ with $1 \le i \le N-2$ such that $Ai = A{i+1} = A_{i+2}$.

给定一个数组，判定是不是有三个连续相同的

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

Card Pile

Problem Statement

There is a stack of $100$ cards, each labeled with the integer $0$.

Process $Q$ queries. Each query is of one of the following:

• Type $1$: Place a card labeled with an integer $x$ on top of the stack.
• Type $2$: Remove the top card of the stack and output the integer written on that removed card. Under the constraints of this problem, the stack always has at least one card.

事实上读一遍描述就是栈操作，如果栈不为空则输出栈顶，否则为0

void solve() {
    int q;
    cin >> q;
    stack<int> st;
    while (q--) {
        int n;
        cin >> n;
        if (n == 1) {
            int x;
            cin >> x;
            st.push(x);
        } else {
            if (st.size() != 0) {
                cout << st.top() << endl;
                st.pop();
            } else {
                cout << 0 << endl;
            }
        }
    }
}

C - Buy Balls

Problem Statement

There are $N$ black balls and $M$ white balls.
Each ball has a value. The value of the $i$-th black ball ($1 \le i \le N$) is $B_i$, and the value of the $j$-th white ball ($1 \le j \le M$) is $W_j$.

Choose zero or more balls so that the number of black balls chosen is at least the number of white balls chosen. Among all such choices, find the maximum possible sum of the values of the chosen balls.

选择一部分B，一部分W，其中B的长度不少于W的长度，然后判定选定的数的和的最大值

可以很简单的考虑为B可以无限长，把所有非负数都选上，A则可以选所有的正数了

void solve() {
    int N, M;
    cin >> N >> M;

    vector<ll> B(N), W(M);
    for (int i = 0; i < N; ++i) cin >> B[i];
    for (int i = 0; i < M; ++i) cin >> W[i];

    sort(B.rbegin(), B.rend());
    sort(W.rbegin(), W.rend());

    vector<long long> pB(N + 1, 0), pW(M + 1, 0);
    for (int i = 0; i < N; ++i) pB[i + 1] = pB[i] + B[i];
    for (int i = 0; i < M; ++i) pW[i + 1] = pW[i] + W[i];

    vector<long long> c(N + 1, 0);
    for (int i = N - 1; i >= 0; --i) {
        c[i] = c[i + 1] + max(0LL, B[i]);
    }

    long long ans = 0;
    for (int k = 0; k <= min(M, N); ++k) {
        long long sum_W = pW[k];
        long long sum_B = pB[k];
        long long cnt = sum_W + sum_B + c[k];
        if (cnt > ans) ans = cnt;
    }

    cout << ans << endl;
}

D - Minimum XOR Path

You are given a simple connected undirected graph with $N$ vertices numbered $1$ through $N$ and $M$ edges numbered $1$ through $M$. Edge $i$ connects vertices $u_i$ and $v_i$, and has a label $w_i$.

Among all simple paths (paths that do not pass through the same vertex more than once) from vertex $1$ to vertex $N$, find the minimum XOR of the labels of the edges on the path.

Notes on XOR For non-negative integers $A$ and $B$, their XOR $A \oplus B$ is defined as follows:

• In the binary representation of $A \oplus B$, the digit in the place corresponding to $2^k \,(k \ge 0)$ is $1$ if and only if exactly one of the digits in the same place of $A$ and $B$ is $1$; otherwise, it is $0$.

For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).
In general, the XOR of $k$ integers $p_1, \dots, p_k$ is defined as $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$. It can be proved that it does not depend on the order of $p_1, \dots, p_k$.

因为数据范围N只有10个点，可以直接回溯dfs即可计算结果

ll ans = 8e18;
int n, m;
vector<array<ll, 2>> g[N];
vector<bool> vis(N);

void dfs(int u, ll cx, int tgt) {
    if (u == tgt) {
        ans = min(ans, cx);
        return;
    }
    vis[u] = true;

    for (auto& e : g[u]) {
        int v = e[0];
        ll w = e[1];

        if (!vis[v]) {
            dfs(v, cx ^ w, tgt);
        }
    }

    vis[u] = false;
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    dfs(1, 0, n);
    cout << ans;
}

E - Min of Restricted Sum

Problem Statement

You are given integers $N, M$ and three integer sequences of length $M$: $X = (X_1, X_2, \ldots, X_M)$, $Y = (Y_1, Y_2, \ldots, Y_M)$, and $Z = (Z_1, Z_2, \ldots, Z_M)$. It is guaranteed that all elements of $X$ and $Y$ are between $1$ and $N$, inclusive.

We call a length-$N$ sequence of non-negative integers $A = (A_1, A_2, \ldots, A_N)$ a good sequence if and only if it satisfies the following condition:

• For every integer $i$ with $1 \le i \le M$, the XOR of $A_{Xi}$ and $A{Y_i}$ is $Z_i$.

Determine whether a good sequence $A=(A_1,A_2,\ldots,AN)$ exists, and if it exists, find one good sequence that minimizes the sum of its elements $\displaystyle \sum{i=1}^N A_i$.

Notes on XOR For non-negative integers $A$ and $B$, their XOR $A \oplus B$ is defined as follows:

• In the binary representation of $A \oplus B$, the digit in the place corresponding to $2^k \,(k \ge 0)$ is $1$ if and only if exactly one of the digits in the same place of $A$ and $B$ is $1$; otherwise, it is $0$.

For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).

给定两个已知下标数组XY和一个xor结果数组Z， 构造一个数组A，使得$A_{xi} \oplus A{y_i} = Z_i$，并且让$\sum A$最小

首先可以不考虑第二个条件，即只满足每个下标的$A_{xi} \oplus A{y_i} = Z_i$

即首先构造一个不为和最小的数组，因此我们可以考虑为每个连通分量上，相应的点之前的xor值为权重，所以先构造图，对每个联通分量进行BFS，然后对起始点赋值0，对于下一个点判定是否可以直接赋值，不可以赋值判定是否当前的3个点的关系可以满足两条边的xor结果要求。如果不满足，则-1

构造成功一种非和最优的解决方案后对每个连通分量的值进行优化减小。

对于同一个bit，如果这个联通分量中的 1和0互相取反，结果仍然保持两两xor结果不变，因此可以考虑让最终求和的数组中每个bit的1要少于0 的个数，否则取反

即统计$c1_i = \sum A_j \And (1<<i)$，则$c0_i = n - c1_i$

如果$c1_i > c0_i$， 则取反。最终得到最优的A

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, ll>>> g(n);
    for (int i = 0; i < m; i++) {
        int x, y;
        ll z;
        cin >> x >> y >> z;
        --x;
        --y;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }
    vector<ll> b(n, -1), ans(n);
    bool ok = false;
    for (int i = 0; i < n; i++) {
        if (b[i] >= 0) continue;
        b[i] = 0;
        queue<int> q;
        q.push(i);
        vector<int> comp;
        comp.push_back(i);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto &pp : g[u]) {
                int v = pp.first;
                ll w = pp.second;
                if (b[v] < 0) {
                    b[v] = b[u] ^ w;
                    q.push(v);
                    comp.push_back(v);
                } else {
                    if (b[v] != (b[u] ^ w)) {
                        ok = true;
                        break;
                    }
                }
            }
            if (ok) break;
        }
        if (ok) break;
        int sz = (int)comp.size();
        vector<int> cnt(31, 0);
        for (auto &c : comp) {
            ll val = b[c];
            for (int bit = 0; bit < 31; bit++) {
                if (val & (1LL << bit)) cnt[bit]++;
            }
        }
        ll T = 0;
        for (int bit = 0; bit < 31; bit++) {
            int ones = cnt[bit], zeros = sz - ones;
            if (zeros < ones) T |= (1LL << bit);
        }
        for (auto &c : comp) ans[c] = b[c] ^ T;
    }
    if (ok)
        cout << "-1\n";
    else {
        for (int i = 0; i < n; i++) {
            cout << ans[i] << ' ';
        }
    }
}

F - Rotated Inversions

You are given integers $N, M$ and a length-$N$ sequence of non-negative integers $A = (A_1, A_2, \ldots, A_N)$.

For $k = 0, 1, \ldots, M-1$, solve the following problem:

Define an integer sequence $B = (B_1, B_2, \ldots, B_N)$ so that $B_i$ is the remainder of $A_i + k$ when divided by $M$. Find the inversion number in $B$.

What is the inversion number? The inversion number of a sequence $(A_1, A_2, \dots, A_N)$ is the number of integer pairs $(i, j)$ satisfying $1 \le i < j \le N$ and $A_i <A_j$.

首先考虑逆序对怎么算，这个算法应该学mergesort都学过，就直接可以求出来没有经过旋转前的逆序对

然后考虑每个旋转该怎么操作

$c[x]$表示在序列中值为 $x$的元素个数，$s[x]$表示值为 $x$ 的元素的下标和。

可以推算出从 $k$到$k+1$​的反转数变化

$inv(B_k+1)=inv(B_k)+2⋅s[x]−c[x]⋅(N−1)$

void calc(vector<int> &arr, int left, int mid, int right, ll &inv_count) {
    int n1 = mid - left + 1, n2 = right - mid;
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
            inv_count += (n1 - i);
        }
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void ms(vector<int> &arr, int left, int right, ll &inv_count) {
    if (left >= right) return;
    int mid = (left + right) >> 1;
    ms(arr, left, mid, inv_count);
    ms(arr, mid + 1, right, inv_count);
    calc(arr, left, mid, right, inv_count);
}

ll gao(vector<int> arr) {
    ll inv_count = 0;
    ms(arr, 0, (int)arr.size() - 1, inv_count);
    return inv_count;
}

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> a(N);
    for (int i = 0; i < N; i++) {
        ll val;
        cin >> val;
        a[i] = (int)(val % M);
    }

    ll inv0 = gao(a);

    vector<ll> c(M, 0LL), s(M, 0LL);
    for (int i = 0; i < N; i++) {
        c[a[i]]++;
        s[a[i]] += i;
    }
    vector<ll> res(M);
    res[0] = inv0;
    for (int k = 0; k < M - 1; k++) {
        int x = (M - 1 - k) % M;
        ll delta = 2LL * s[x] - c[x] * (ll)(N - 1);
        res[k + 1] = res[k] + delta;
    }

    for (auto &val : res) {
        cout << val << "\n";
    }
}