abc-396 题解

A - 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 \leq i \le N-2$ such that $A_i = A_{i+1} = A_{i+2}$.

Constraints

• $3 \le N \leq 100$
• $1 \le A_i \leq 100$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

Output

If there is a place in $A$ where the same element appears three or more times in a row, print Yes. Otherwise, print No.

Sample Input 1

5
1 4 4 4 2

Sample Output 1

Yes

We have $A=(1,4,4,4,2)$. There is a place where $4$ appears three times in a row, so print Yes.

Sample Input 2

6
2 4 4 2 2 4

Sample Output 2

No

We have $A=(2,4,4,2,2,4)$. There is no place where the same element appears three or more times in a row, so print No.

Sample Input 3

8
1 4 2 5 7 7 7 2

Sample Output 3

Yes

Sample Input 4

10
1 2 3 4 5 6 7 8 9 10

Sample Output 4

No

Sample Input 5

13
1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 5

Yes

大意

给定长度为n的序列，回答是否存在一个数，在该序列中连续出现至少三次。

暴力，（不知道为啥给那么多样例…）

CODE

void solve()
{
    int n;  cin >> n;
    vector<int> v(n);
    for (auto &x : v)   cin >> x;
    bool flag = false;
    for (int i=0;i+2<n;i++)
            if (v[i] == v[i + 1] && v[i + 1] == v[i + 2])
                flag = true;
    cout << (flag ? "Yes" : "No") << _endl;
}

B - 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.

Constraints

• $1 \le Q \le 100$
• $1 \le x \le 100$
• There is at least one query of type $2$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

The $i$-th query $\text{query}_i$ starts with the query type $c_i$ ($1$ or $2$), followed by the integer $x$ if $c_i=1$.

That is, each query is in one of the following two formats:

$1$ $x$

$2$

Output

Let $q$ be the number of queries with $c_i=2$. Print $q$ lines.

The $j$-th line ($1 \le j \le q$) should contain the answer to the $j$-th such query.

Sample Input 1

6
2
1 4
1 3
2
2
2

Sample Output 1

0
3
4
0

After processing each query, the stack is as follows:

• Remove the top card of the stack. The integer on the removed card is $0$, so output $0$.
  • The stack then has $99$ cards labeled with $0$.
• Add a card labeled $4$ on top.
  • The stack then has $1$ card labeled $4$, and $99$ cards labeled $0$, from top to bottom.
• Add a card labeled $3$ on top.
  • The stack then has $1$ card labeled $3$, $1$ card labeled $4$, and $99$ cards labeled $0$, from top to bottom.
• Remove the top card. The integer on that card is $3$, so output $3$.
  • The stack then has $1$ card labeled $4$, and $99$ cards labeled $0$, from top to bottom.
• Remove the top card. The integer on that card is $4$, so output $4$.
  • The stack then has $99$ cards labeled $0$.
• Remove the top card. The integer on that card is $0$, so output $0$.
  • The stack then has $98$ cards labeled $0$.

Sample Input 2

5
2
2
2
2
2

Sample Output 2

0
0
0
0
0

大意

给一个牌堆（栈），初始时，牌堆中有一百张标号为零的牌，给定 $q$ 个询问，对于每个询问，若是类型一则将标号为 $x$ 的牌放到牌堆顶，

若是类型二则取出牌堆顶的牌，并输出其标号。

模拟，可使用stack 或 数组模拟栈。

CODE

void solve()
{
    stack<int> st;
    for (int i=1;i<=100;i++)    st.push(0);
    int n, op, x;  cin >> n;
    for (int i=1;i<=n;i++)
    {
        cin >> op;
        if (op == 1)
            cin >> x, st.push(x);
        else if (op == 2)
            cout << st.top() << _endl, st.pop();
    }
}

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.

Constraints

• $1 \leq N,M \leq 2\times 10^5$
• $-10^9 \leq B_i, W_j \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$B_1$ $B_2$ $\ldots$ $B_N$
$W_1$ $W_2$ $\ldots$ $W_M$

Output

Print the answer.

Sample Input 1

4 3
8 5 -1 3
3 -2 -4

Sample Output 1

19

If you choose the 1st, 2nd, and 4th black balls, and the 1st white ball, the sum of their values is $8+5+3+3=19$, which is the maximum.

Sample Input 2

4 3
5 -10 -2 -5
8 1 4

Sample Output 2

15

If you choose the 1st and 3rd black balls, and the 1st and 3rd white balls, the sum of their values is $5+(-2)+8+4=15$, which is the maximum.

Sample Input 3

3 5
-36 -33 -31
12 12 28 24 27

Sample Output 3

0

It is possible to choose no balls.

大意

给定两个序列，长度分别为 $n,\ m$ , 表示存在 $n$ 个黑球和 $m$ 个白球，每个球都有一个权值，回答在满足 选择的黑球数 $\geq$ 白球数 的条件下，所有被选球权值的最大值。

对两个序列分别降序排序， 找到白球选择的数量 $k$ , 再判断黑球是否可以继续选择更多。

CODE

void solve()
{
    int n, m;   cin >> n >> m;
    vector<int> b(n), w(m);
    for (auto &x : b)   cin >> x;
    for (auto &x : w)   cin >> x;
    sort(all(b), greater<int>());
    sort(all(w), greater<int>());
    int ans = 0, i;
    for (i=0;i<min(m, n);i++)
    {
        if (b[i] >= w[i] && b[i] >= 0 && w[i] >= 0)
            ans += b[i] + w[i];
        else if (b[i] < w[i] && b[i] + w[i] > 0)        ans += b[i] + w[i];   
        else	break;
    }
    for (;i<n;i++)    ans += (b[i] > 0 ? b[i] : 0);
    cout << ans;
}

D - Minimum XOR Path

Problem Statement

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$.

Constraints

• $2 \leq N \leq 10$
• $N-1 \leq M \leq \frac{N(N-1)}{2}$
• 1 \leq u_i\ \textless\ v_i \leq N
• 0 \leq w_i\ \textless\ 2^{60}
• The given graph is a simple connected undirected graph.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$u_1$ $v_1$ $w_1$
$u_2$ $v_2$ $w_2$
$\vdots$
$u_M$ $v_M$ $w_M$

Output

Print the answer.

Sample Input 1

4 4
1 2 3
2 4 5
1 3 4
3 4 7

Sample Output 1

3

There are two simple paths from vertex $1$ to vertex $4$:

• $1 \to 2 \to 4$
• $1 \to 3 \to 4$

The XOR of the labels on the edges of the first path is $6$, and that of the second path is $3$. Therefore, the answer is $3$.

Sample Input 2

4 3
1 2 1
2 3 2
3 4 4

Sample Output 2

7

Sample Input 3

7 10
1 2 726259430069220777
1 4 988687862609183408
1 5 298079271598409137
1 6 920499328385871537
1 7 763940148194103497
2 4 382710956291350101
3 4 770341659133285654
3 5 422036395078103425
3 6 472678770470637382
5 7 938201660808593198

Sample Output 3

186751192333709144

大意

给定一个 $n$ 个点， $m$ 条边的简单无向图，每条边存在一个权值。找到从 $1\sim N$ 的简单路径中，边权异或和最小的路径，输出该异或和。

观察到 $n \in [2,\ 10]$ ， 可直接暴力 dfs 。

需注意是无向图， （因为赛时没看到，卡了好久……）。

CODE

void solve()
{
    int n, m;   cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i=1;i<=m;i++)
    {
        int u, v, w;    cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    int ans = inf;
    vector<int> vis(n + 1, false);
    auto dfs = [&](auto self, int s, int Xor) -> void
    {
        if (s == n)
        {
            ans = min(ans, Xor);
            return;
        }
        for (auto [son, val] : adj[s])
            if (!vis[son])
            {
                vis[son] = true;
                self(self, son, Xor ^ val);
                vis[son] = false;
            }
    };

    vis[1] = true;
    dfs(dfs, 1, 0);
    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_{X_i}$ and $A_{Y_i}$ is $Z_i$.

Determine whether a good sequence $A=(A_1,A_2,\ldots,A_N)$ 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$).

Constraints

• $1 \le N \le 2\times 10^5$
• $0 \le M \le 10^5$
• $1 \le X_i, Y_i \le N$
• $0 \le Z_i \le 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$X_1$ $Y_1$ $Z_1$
$X_2$ $Y_2$ $Z_2$
$\vdots$
$X_M$ $Y_M$ $Z_M$

Output

If no good sequence exists, print $-1$.

If a good sequence exists, print one good sequence that minimizes the sum of its elements, separated by spaces.

If there are multiple good sequences with the same minimum sum, printing any of them is accepted.

Sample Input 1

3 2
1 3 4
1 2 3

Sample Output 1

0 3 4

$A=(0,3,4)$ is a good sequence because $A_1 \oplus A_2 = 3$ and $A_1 \oplus A_3 = 4$.

Other good sequences include $A=(1,2,5)$ and $A=(7,4,3)$, but $A=(0,3,4)$ has the smallest sum among all good sequences.

Sample Input 2

3 3
1 3 4
1 2 3
2 3 5

Sample Output 2

-1

No good sequence exists, so print $-1$.

Sample Input 3

5 8
4 2 4
2 3 11
3 4 15
4 5 6
3 2 11
3 3 0
3 1 9
3 4 15

Sample Output 3

0 2 9 6 0

大意

给定三个长度为 $m$ 的序列 $X = (X_1, X_2, \ldots, X_M)$, $Y = (Y_1, Y_2, \ldots, Y_M)$, 和 $Z = (Z_1, Z_2, \ldots, Z_M)$.

要求构造出一个长度为 $n$ 的序列 $A=(A_1,A_2,\ldots,A_N)$ , 使得 对于所有 $i\ \in\ [1,\ m]$ , 都有 $A_{X_i} \oplus A_{Y_i} = Z_i$ .

F - Rotated Inversions

Problem Statement

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 \leq i\ \textless\ j \le N and A_i\ \textless\ A_j.

Constraints

• $1 \le N,M \le 2\times 10^5$
• 0 \leq A_i\ \textless\ M
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$

Output

Print $M$ lines.

The $i$-th line $(1 \le i \le M)$ should contain the answer for the case $k = i-1$.

Sample Input 1

3 3
2 1 0

Sample Output 1

3
1
1

• For $k=0$: $B=(2, 1, 0)$. The inversion number is $3$.
• For $k=1$: $B=(0, 2, 1)$. The inversion number is $1$.
• For $k=2$: $B=(1, 0, 2)$. The inversion number is $1$.

Sample Input 2

5 6
5 3 5 0 1

Sample Output 2

7
3
3
1
1
5

Sample Input 3

7 7
0 1 2 3 4 5 6

Sample Output 3

0
6
10
12
12
10
6

大意

给定两个整数 $N,\ M$ , 和一个长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$ .

定义一次转变为使得 $B_i = (A_i + k) \bmod M$.

对于 $k\in [0, M-1]$ , 分别依次输出每次转变生成的序列 $B$ 的逆序对数。

思路

可先用 归并排序 / 树状数组 / 线段树 求得原给定序列 $A$ 的逆序对数。

再次观察每次的转变，以 Sample Input 2 为例：

5 3 5 0 1 
0 4 0 1 2 
1 5 1 2 3 
2 0 2 3 4 
3 1 3 4 5 
4 2 4 5 0 

可以发现， 在除了 以 $B_i$ 由 $M-1$ 变为 $0$ 组成的数对外，其余数对的相对大小是不变的，例如下面加粗的每行三个数组成的三组数对 $(3,\ 0), (3,\ 1), (0,\ 1)$ 变成了 $(4,\ 1), (4,\ 2), (1,\ 2)$ ，逆序对数依旧是两对。

5 3 5 0 1
0 4 0 1 2

根据贡献法，只有当 $B_i$ 由 $M-1$ 变为 $0$ ，其与其左侧的每个数构成的逆序对数会增加，与其右侧的每个数构成的逆序对数会减少。

且当两个数同时变小时，由于左右贡献相消，并不会导致错误。

5 3 5 0 1 
先假设两个相同数对也是逆序对：
对于第一个 5 ， 其左侧没有数，不构成逆序对，其变为零后， 仍不构成逆序对； 
			  其右侧有四个数，构成四对逆序对，其变为零后， 逆序对数减少四。
对于第二个 5 ， 其左侧有两个数，构成两对逆序对，其变为零后， 逆序对数增加二。
			  其右侧有两个数，构成两对逆序对，其变为零后， 逆序对数减少二。
因此，该轮序列变化后，总逆序对数增加了 (-4 + 2 - 2) = -4 对。
而当我们考虑正常情况：
对于第一个 5 ， 其左侧没有数，不构成逆序对，其变为零后， 仍不构成逆序对； 
			  其右侧有四个数，构成三对逆序对，其变为零后， 逆序对数减少三。
对于第二个 5 ， 其左侧有两个数，构成一对逆序对，其变为零后， 逆序对数增加一。
			  其右侧有两个数，构成两对逆序对，其变为零后， 逆序对数减少二。
因此，该轮序列变化后，总逆序对数增加了 (-3 + 1 - 2) = -4 对。

根据上面的结论：可以想到写法，将所有答案设置为初始序列逆序对数，接下来遍历每个数，计算出其对哪几轮的变化有影响（推出在什么时候有最大值变为零），在求出它的变化的答案的贡献是多少，由于影响是区间性的（即区间修改），可以用线段树，因此就有了如下代码。

CODE

void solve()
{
    int n, m, prs = 0;   cin >> n >> m;
    vector<int> v(n + 1);
    SegTree<Info, Laz> seg(m + 1);	// 线段树就是最常见的区间加 + 区间查询
    for (int i=1;i<=n;i++)
    {
        cin >> v[i];    v[i] ++;	// 由于 v[i] 是和取模有关，存在 0 ，因此先加一，进行类似离散化操作
        prs += seg.query(v[i] + 1, m).sum;	// 查询 [v[i] + 1, +∞) 在前面的序列中出现了几次，即当前数与前面数构成的逆序对数
        seg.modify(v[i], v[i], {1});	// 当前数位置加一
        v[i] --;	// 求完逆序对后还原 v[i]
    }
    SegTree<Info, Laz> ans(m + 1);
    for (int i=1;i<=m;i++)  ans.arr[i] = prs;
    ans.build();
    for (int i=1;i<=n;i++)	// 贡献的变化是从变化轮到最后的，属于区间修改
        ans.modify(m - v[i] + 1, m, {(i - 1) - (n - i)});	// 与其左侧的每个数构成的逆序对数会增加， 与其右侧的每个数构成的逆序对数会减少
    for (int i=1;i<=m;i++)	cout << ans.query(i, i).sum << _endl;
}