Codeforces Round 1005 (Div. 2)](httpsmirror.codeforces.comcontest2064)

Codeforces Round 1005 (Div. 2)

Brogramming Contest

One day after waking up, your friend challenged you to a brogramming contest. In a brogramming contest, you are given a binary string $^{\text{∗}}$ $s$ of length $n$ and an initially empty binary string $t$ . During a brogramming contest, you can make either of the following moves any number of times:

remove some suffix $^{\text{†}}$ from $s$ and place it at the end of $t$ , or
remove some suffix from $t$ and place it at the end of $s$ .

To win the brogramming contest, you must make the minimum number of moves required to make $s$ contain only the character $\texttt{0}$ and $t$ contain only the character $\texttt{1}$ . Find the minimum number of moves required.

$^{\text{∗}}$ A binary string is a string consisting of characters $\texttt{0}$ and $\texttt{1}$ .

$^{\text{†}}$ A string $a$ is a suffix of a string $b$ if $a$ can be obtained from deletion of several (possibly, zero or all) elements from the beginning of $b$ .

Input

The first line contains an integer $t$ ( $\le t \le 100$ ) — the number of test cases.

The first line of each test case is an integer $n$ ( $\le n \le 1000$ ) — the length of the string $s$ .

The second line of each test case contains the binary string $s$ .

The sum of $n$ across all test cases does not exceed $1000$ .

Output

For each testcase, output the minimum number of moves required.

Example

input

output

Note

An optimal solution to the first test case is as follows:

$\texttt{00}\color{red}{\texttt{110}}$ , $t =$ empty string.
$\texttt{00}$ , $\texttt{11}\color{red}{\texttt{0}}$ .
$\texttt{000}$ , $\texttt{11}$ .

It can be proven that there is no solution using less than $2$ moves.

In the second test case, you have to move the whole string from $s$ to $t$ in one move.

In the fourth test case, you don’t have to do any moves.

题解略

代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 5e5 + 10;int n;
string s;void solved()
{char t = '1';cin >> n;cin >> s;int ans = 0;for (char c : s){if (c == t){t = '1' - t + '0';ans++;}}cout << ans << endl;
}signed main()
{BoBoowen;int T = 1;cin >> T;while (T--){solved();}
}

Variety is Discouraged

Define the score of an arbitrary array $b$ to be the length of $b$ minus the number of distinct elements in $b$ . For example:

The score of $[1, 2, 2, 4]$ is $1$ , as it has length $4$ and only $3$ distinct elements ( $1$ , $2$ , $4$ ).
The score of $[1, 1, 1]$ is $2$ , as it has length $3$ and only $1$ distinct element ( $1$ ).
The empty array has a score of $0$ .

You have an array $a$ . You need to remove some non-empty contiguous subarray from $a$ at most once.

More formally, you can do the following at most once:

pick two integers $l$ , $r$ where $\le l \le r \le n$ , and
delete the contiguous subarray $[a_l,\ldots,a_r]$ from $a$ (that is, replace $a$ with $[a_1,\ldots,a_{l - 1},a_{r + 1},\ldots,a_n]$ ).

Output an operation such that the score of $a$ is maximum; if there are multiple answers, output one that minimises the final length of $a$ after the operation. If there are still multiple answers, you may output any of them.

Input

The first line contains an integer $t$ ( $\le t \le 10^4$ ) — the number of testcases.

The first line of each testcase contains an integer $n$ ( $\le n \le 2 \cdot 10^5$ ) — the length of the array $a$ .

The second line of each testcase contains $n$ integers $a_1,a_2,\ldots,a_n$ ( $\le a_i \le n$ ).

The sum of $n$ across all testcases does not exceed $\cdot 10^5$ .

Output

For each testcase, if you wish to not make a move, output $0$ .

Otherwise, output two integers $l$ and $r$ ( $\le l \le r \le n$ ), representing the left and right bound of the removed subarray.

The removed subarray should be chosen such that the score is maximized, and over all such answers choose any of them that minimises the final length of the array.

Example

input

output

1 1
0
2 3

Note

In the first testcase, we have two options:

do nothing: the score of $[1]$ is $1 - 1 = 0$ .
remove the subarray with $l = 1$ , $r = 1$ : we remove the only element, and we get an empty array with score $0$ .

Therefore, the maximum score possible is $0$ . However, since we need to additionally minimise the final length of the array, we must output the second option with $l = r = 1$ . Note that the first option of doing nothing is incorrect, since it has a longer final length.

In the second testcase, no subarray is selected, so after which $a$ is still $[1, 1, 1, 1, 1]$ . This has length $5$ and $1$ distinct element, so it has a score of $5 - 1 = 4$ . This can be proven to be a shortest array which maximises the score.

In the third testcase, the subarray selected is $\color{red}1, \color{red}3, 2]$ , after which $a$ becomes $[2, 2]$ . This has length $2$ and $1$ distinct element, so it has a score of $2 - 1 = 1$ . This can be proven to be a shortest array which maximises the score.

题解略

代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 5e5 + 10;int n;
int a[N], cnt[N];
int l, r;void solved()
{cin >> n;for (int i = 1; i <= n; ++i){cin >> a[i];cnt[a[i]]++;}l = r = 0;for (int i = 1, j; i <= n; i = j){for (j = i; j <= n && (cnt[a[j]] == 1) == (cnt[a[i]] == 1); ++j);if (cnt[a[i]] == 1 && j - i >= r - l + 1){l = i;r = j - 1;}}if (l == 0){cout << 0 << endl;}else{cout << l << ' ' << r << endl;}for (int i = 1; i <= n; ++i){cnt[a[i]]--;}
}signed main()
{BoBoowen;int T = 1;cin >> T;while (T--){solved();}
}

Remove the Ends

You have an array $a$ of length $n$ consisting of non-zero integers. Initially, you have $0$ coins, and you will do the following until $a$ is empty:

Let $m$ be the current size of $a$ . Select an integer $i$ where $\le i \le m$ , gain $a_i|$ $^{\text{∗}}$ coins, and then:
- if $a_i < 0$ , then replace $a$ with $[a_1,a_2,\ldots,a_{i - 1}]$ (that is, delete the suffix beginning with $a_i$ );
- otherwise, replace $a$ with $[a_{i + 1},a_{i + 2},\ldots,a_m]$ (that is, delete the prefix ending with $a_i$ ).

Find the maximum number of coins you can have at the end of the process.

$^{\text{∗}}$ Here $a_i|$ represents the absolute value of $a_i$ : it equals $a_i$ when $a_i < 0$ and $a_i$ when $a_i <0$ .

Input

The first line contains an integer $t$ ( $\le t \le 10^4$ ) — the number of testcases.

The first line of each testcase contains an integer $n$ ( $\le n \le 2 \cdot 10^5$ ) — the length of $a$ .

The second line of each testcase contains $n$ integers $a_1,a_2,\ldots,a_n$ ( $-10^9 \le a_i \le 10^9$ , $a_i \ne 0$ ).

The sum of $n$ across all testcases does not exceed $\cdot 10^5$ .

Output

For each test case, output the maximum number of coins you can have at the end of the process.

Example

input

3
6
3 1 4 -1 -5 -9
6
-10 -3 -17 1 19 20
1
1

output

23
40
1

Note

An example of how to get $23$ coins in the first testcase is as follows:

$a = [3, 1, 4, -1, -5, \color{red}{-9}] \xrightarrow{i = 6} a = [3, 1, 4, -1, -5] $ , and get $9$ coins.
$a = [\color{red}{3}, 1, 4, -1, -5] \xrightarrow{i = 1} a = [1, 4, -1, -5] $ , and get $3$ coins.
$a = [\color{red}{1}, 4, -1, -5] \xrightarrow{i = 1} a = [4, -1, -5] $ , and get $1$ coin.
$a = [4, -1, \color{red}{-5}] \xrightarrow{i = 3} a = [4, -1] $ , and get $5$ coins.
$a = [4, \color{red}{-1}] \xrightarrow{i = 2} a = [4] $ , and get $1$ coin.
$a = [\color{red}{4}] \xrightarrow{i = 1} a = [] $ , and get $4$ coins.

After all the operations, you have $23$ coins.

An example of how to get $40$ coins in the second testcase is as follows:

$a = [-10, -3, -17, \color{red}{1}, 19, 20] \xrightarrow{i = 4} a = [19, 20] $ , and get $1$ coin.
$a = [\color{red}{19}, 20] \xrightarrow{i = 1} a = [20] $ , and get $19$ coins.
$a = [\color{red}{20}] \xrightarrow{i = 1} a = [] $ , and get $20$ coins.

After all the operations, you have $40$ coins.

题面描述

给定一个由非零整数构成的数组 a，长度为 n，初始时你拥有 0 枚硬币。每一步操作中，你选择数组 a 中的一个位置 i，然后获取 |a[i]| 枚硬币。如果 a[i] 为负数，则删除从 a[i] 到数组末尾的所有元素；如果 a[i] 为正数，则删除从 a[1] 到 a[i] 的所有元素，继续进行操作，直到数组为空。

目标是找到操作的最大硬币数。

题解

思路分析：

核心任务： 我们要选择一个位置 i 来获得硬币，并且通过操作的选择最大化所获得的硬币数量。
数组处理的细节：
- 如果 a[i] > 0，则删除从 a[1] 到 a[i] 的所有元素。
- 如果 a[i] < 0，则删除从 a[i] 到数组末尾的所有元素。
前缀与后缀和：
- 我们考虑前缀和和后缀和的累计方式。前缀和可以帮助我们了解前面一段元素的正数部分如何产生硬币，后缀和则帮助我们在数组末尾收集负数部分的硬币。
具体步骤：
1. 计算每个位置 i 左边正数部分的累计和 v1[i]。
2. 计算每个位置 i 右边负数部分的累计和 v2[i]。
3. 对于每个位置 i，计算 v1[i] + v2[i] 的最大值。
4. 如果 a[0] 是负数，则计算删除后端部分的结果并比较。

代码分析

以下是题目给出的代码，并进行解释：

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 5e5 + 10;void solved()
{int n;cin >> n;int ans = 0;vector<int> v(n);vector<int> v1(n, 0), v2(n, 0);// 计算前缀和：存储正数部分的累计和for (int i = 0; i < n; ++i){cin >> v[i];if (v[i] > 0){v1[i] = v[i];}if (i > 0){v1[i] += v1[i - 1];}}// 计算后缀和：存储负数部分的累计和for (int i = n - 2; i >= 0; --i){if (v[i + 1] < 0){v2[i] = -v[i + 1];}v2[i] += v2[i + 1];}// 遍历，找出最大硬币数for (long long i = 0; i < n; ++i){ans = max(ans, v1[i] + v2[i]);}// 如果 a[0] 是负数，考虑删除后缀的情况if (v[0] < 0){ans = max(ans, v2[0] - v[0]);}cout << ans << endl;
}signed main()
{BoBoowen;int T = 1;cin >> T;while (T--){solved();}
}

代码详细解析：

输入读取和初始化：
- n 为当前测试用例中数组 a 的长度。
- v 存储当前数组，v1 用于存储从左到右累计的正数部分和，v2 用于存储从右到左累计的负数部分的绝对值。
前缀和计算：
- 对数组进行遍历，如果当前元素为正数，则将它加入到前缀和 v1[i] 中。
- 如果当前元素为正数，我们将其值与之前的累计值相加（即 v1[i] = v1[i-1] + v[i]）。
后缀和计算：
- 从右往左遍历数组，如果 a[i] 是负数，则将其绝对值加入到后缀和 v2[i] 中。
- 遍历完成后，v2[i] 存储了当前元素以及右侧负数部分的累计和。
计算最大硬币数：
- 对每个元素 i，计算前缀和与后缀和之和 v1[i] + v2[i]，选择最大值。
- 特别地，如果 a[0] 是负数，我们考虑从数组的后面部分删除负数元素，计算可能的最大值。
输出结果：
- 对每个测试用例，输出最大硬币数。

时间复杂度分析：

每个测试用例的时间复杂度为 O(n)，其中 n 是数组的长度。
总时间复杂度为 O(T * n)，其中 T 为测试用例的数量，n 为每个测试用例中数组的长度。

由于问题保证了所有测试用例的总 n 值不会超过 2 * 10^5，因此这段代码的时间复杂度是能够接受的。

Eating

There are $n$ slimes on a line, the $i$ -th of which has weight $w_i$ . Slime $i$ is able to eat another slime $j$ if $w_i \geq w_j$ ; afterwards, slime $j$ disappears and the weight of slime $i$ becomes $w_i \oplus w_j$ $^{\text{∗}}$ .

The King of Slimes wants to run an experiment with parameter $x$ as follows:

Add a new slime with weight $x$ to the right end of the line (after the $n$ -th slime).
This new slime eats the slime to its left if it is able to, and then takes its place (moves one place to the left). It will continue to do this until there is either no slime to its left or the weight of the slime to its left is greater than its own weight. (No other slimes are eaten during this process.)
The score of this experiment is the total number of slimes eaten.

The King of Slimes is going to ask you $q$ queries. In each query, you will be given an integer $x$ , and you need to determine the score of the experiment with parameter $x$ .

Note that the King does not want you to actually perform each experiment; his slimes would die, which is not ideal. He is only asking what the hypothetical score is; in other words, the queries are not persistent.

$^{\text{∗}}$ Here $\oplus$ denotes the bitwise XOR operation.

Input

The first line contains an integer $t$ ( $\le t \le 10^4$ ) — the number of test cases.

The first line of each test case contains integers $n$ and $q$ ( $\le n, q \le 2 \cdot 10^5$ ) — the number of slimes and the number of queries, respectively.

The following line contains $n$ integers $w_1,w_2,\ldots,w_n$ ( $\le w_i < 2^{30}$ ) — the weights of the slimes.

The following $q$ lines contain a single integer $x$ ($ 1 \le x < 2^{30}$ ) — the parameter for the experiment.

The sum of $n$ does not exceed $\cdot 10^5$ and the sum of $q$ does not exceed $\cdot 10^5$ across all test cases.

Output

For each query, output a single integer — the score of the experiment.

Example

input

3
1 1
5
6
4 4
1 5 4 11
8
13
16
15
10 9
10 4 3 9 7 4 6 1 9 4
2
6
5
6
9
8
6
2
7

output

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

Note

For the first query of the second testcase:

A slime of weight $8$ would be added to the end, so $\color{red}8]$ .
The added slime has smaller weight than the slime to its left so it cannot eat it, and thus ends the process after eating no slimes with score $0$ .

For the second query of the second testcase:

A slime of weight $13$ would be added to the end, so $\color{red}{13}]$ .
The added slime has bigger weight than the slime to its left, and so it will eat it. Its weight will become $13 \oplus 11 = 6$ . Now $\color{red}{6}]$ .
The added slime will now eat the slime to its left, and its weight becomes $\oplus 4 = 2$ . Now $\color{red}{2}]$ .
The added slime is no longer able to eat the slime to its left, so it ends the process with a score of $2$ .

问题陈述

在一条线上有 n 个史莱姆，每个史莱姆有一个重量 $w_i$ 。当一个重量为 $w_i$ 的史莱姆遇到另一个重量为 $w_j$ 的史莱姆时，如果 $w_i >= w_j$ ，它就可以吃掉史莱姆 j，并且它的新重量变为 $w_i XOR w_j$ 。问题要求模拟一个实验，在每个查询中，向线的末尾添加一个新的史莱姆，其重量为 x。这个新史莱姆可以吃掉它左边的史莱姆，直到遇到一个比它重量更大的史莱姆。

你需要为每个查询确定新史莱姆吃掉的史莱姆数量。

问题分解

初始史莱姆：史莱姆们排成一行，每个史莱姆有一个给定的重量。
实验过程：对于每个查询，添加一个重量为 x 的新史莱姆到行的末尾。这个新史莱姆会尝试吃掉它左边的史莱姆。如果史莱姆的重量小于等于它的重量，它就可以吃掉这个史莱姆。吃掉一个史莱姆后，它的重量会变成 $w_i XOR w_j$ ，这个过程会持续进行，直到遇到一个无法吃掉的史莱姆。
目标：对于每个查询，确定新史莱姆吃掉的史莱姆数量。

输入格式

第一行包含一个整数 t —— 测试用例的数量。
对于每个测试用例：
- 第一行包含两个整数 n 和 q，分别表示史莱姆的数量和查询的数量。
- 第二行包含 n 个整数 $w_1, w_2, ..., w_n$ ，表示史莱姆的重量。
- 接下来的 q 行每行包含一个整数 x，表示每个查询中新增史莱姆的重量。

输出格式

对于每个查询，输出实验的结果，即新史莱姆吃掉的史莱姆数量。

约束

$1 ≤ t ≤ 10^4$
$1 ≤ n, q ≤ 2 * 10^5$
$1 ≤ w_i < 2^30$
1 ≤ n, q ≤ 2 * 10^5
1 ≤ w_i < 2^30
所有测试用例中 n 的总和不超过$ 2 * 10^5$。
所有测试用例中 q 的总和不超过$ 2 * 10^5$。

方法

朴素模拟：朴素的做法是每个查询逐个模拟过程。对于每个新史莱姆，从右往左尝试吃掉所有能够吃的史莱姆，直到遇到一个不能吃的史莱姆。然而，由于约束较大，直接模拟的做法效率较低。
优化策略：
- 我们注意到，史莱姆被吃掉的顺序是由异或操作和它们重量的比较来决定的。
- 为了高效地回答每个查询，我们可以预处理史莱姆，计算每个史莱姆在新增史莱姆时可以吃掉多少个史莱姆。
- 预处理：对于每个史莱姆 i，我们可以计算出它能吃掉的下一个史莱姆。利用这个信息，我们可以快速地确定新史莱姆重量 x 时会吃掉多少个史莱姆。
- 我们可以使用动态规划或其他优化技术来存储状态转换（即新史莱姆将遇到的史莱姆和它的更新重量），并在查询中复用这些状态。

代码分析

给定的代码使用动态规划来解决这个问题。通过遍历史莱姆并根据异或操作更新状态，它可以高效地计算出每个查询的答案。我们将逐步分析代码的关键点：

预处理：
- 我们计算了每个史莱姆能够吃掉的下一个史莱姆的位置，这个信息存储在 dp 数组中。通过该数组，我们可以确定新史莱姆吃掉的史莱姆。
动态规划表 dp：这个表用来存储每个史莱姆可以吃掉的第一个史莱姆的位置。具体做法是通过遍历每个史莱姆并考虑每个比特位置来计算这个表。
查询处理：
- 对于每个查询，处理新史莱姆的重量并确定它可以吃掉的史莱姆数量。我们通过查找 dp 数组来获取答案。
时间复杂度：
- 预处理每个测试用例的时间复杂度是 O(n * 30)，其中 30 是每个史莱姆重量的位数（因为 $w_i < 2^30$ ）。
- 每个查询的时间复杂度是 O(30)，因为我们需要处理最多 30 位的权重。
- 整体复杂度是 $O (n * 30 + q * 30)$ ，这个复杂度足够高效，能够处理给定的输入约束。

代码实现

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 5e5 + 10;int dp[N][35];void solved()
{int n, q;cin >> n >> q;vector<int> v(n + 1), vv(n + 1), ans(n + 1);for (int i = 1; i <= n; i++){cin >> v[i];vv[i] = vv[i - 1] ^ v[i];for (int j = 0; j < 30; j++){dp[i][j] = -1;if (v[i] & (1 << j)){ans[i] = j;}}}for (int i = 1; i <= n; i++){int cur = -1;for (int j = 29; j >= 0; j--){if (cur < 0 and v[i] & (1 << j)){cur = j;}if (j <= cur){dp[i][j] = i;}else{dp[i][j] = max(dp[i - 1][j], dp[i][j + 1]);}}}while (q--){int x;cin >> x;int id = n + 1;int cur = 0;for (int i = 0; i < 30; i++){if (x & (1 << i)){cur = i;}}while (id > 1){if (cur < 0){break;}int l = dp[id - 1][cur];if (l <= 0){id = 1;break;}if (ans[l] > cur){id = l + 1;break;}else if (v[l] > (vv[n] ^ vv[l] ^ x)){id = l + 1;break;}else{id = l;int t = vv[n] ^ vv[l - 1] ^ x;cur = -1;for (int i = 29; i >= 0; i--){if (t & (1 << i)){cur = i;break;}}}}cout << n - id + 1 << " ";}cout << endl;
}signed main()
{BoBoowen;int T = 1;cin >> T;while (T--){solved();}
}