比赛链接：CF1883
A.Morning
题目描述
你需要输入 \(t\) 个四位数密码，每次输入时你的光标都在第一个数 \(1\) 上，在一秒内你有两种操作：
- 按下光标输入一位密码。
- 将光标移到任意与当前数字相邻的数字。
这张图显示了你输入密码的设备，可以看到，\(5\) 相邻的是 \(4\) 和 \(6\)，而 \(0\) 和 \(1\) 只有一个相邻的数，分别是 \(9\) 和 \(2\)。
计算输入给定密码需要的最少秒数。
ps.如果还是不理解题意，请看加粗的样例解释。
输入格式
第一行包含一个整数 \(t\) ( \(1 \leq t \leq 10^4\) ) - 测试用例的编号。
每个测试用例的单行描述了长度为 \(4\) 的针脚代码字符串，由 \(0\) 至 \(9\) 的数字组成。
输出格式
针对每个测试用例，输出一行，表示输入密码所需的最少秒数。
样例输入1
10
1111
1236
1010
1920
9273
0000
7492
8543
0294
8361
样例输出1
4
9
31
27
28
13
25
16
33
24
样例解释
在第一个测试案例中，光标需要按下 \(4\) 次。
在第二个测试案例中，可以在 \(9\) 秒内完成，如下所示：
- 按下光标，输入数字\(1\)。
- 将光标移至数字 \(2\) 。
- 按下光标，输入数字\(2\)。
- 将光标移至数字 \(3\) 。
- 按下光标，输入数字\(3\)。
- 将光标移至数字 \(4\) 。
- 将光标移至数字 \(5\) 。
- 将光标移至数字 \(6\) 。
- 按下光标，输入数字\(6\)。
B.Chemistry
题面描述
给定一个字符串 \(S\)，它的长度为 \(n\)，请问能否在删除 \(k\) 个字符后，对字符串重新排列(任意排列)使得其成为回文字符串？
ps.如果还是不理解题意，请看加粗的样例解释。
输入格式
每个测试由多个测试用例组成。第一行包含一个整数 \(t\) ( \(1 \leq t \leq 10^4\) ) - 测试用例的编号。随后是测试用例说明。
每个测试用例的第一行包含两个整数 \(n\) 和 \(k\) ( \(0 \leq k < n \leq 10^5\) ) - 字符串长度 \(s\) 和要删除的字符数。
每个测试用例的第二行包含一个长度为 \(n\) 的字符串 \(s\) ，由小写字母组成。
保证所有测试用例的 \(n\) 总和不超过 \(2 \times 10^5\) 。
输出格式
对于每个测试用例，如果可以从字符串 \(s\) 中删除 \(k\) 个字符，从而使剩余的字符可以排列形成一个回文字符串，则输出YES，否则输出NO。
样例输入
14
1 0
a
2 0
ab
2 1
ba
3 1
abb
3 2
abc
6 2
bacacd
6 2
fagbza
6 2
zwaafa
7 2
taagaak
14 3
ttrraakkttoorr
5 3
debdb
5 4
ecadc
5 3
debca
5 3
abaac
样例输出
YES
NO
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
NO
YES
样例解释
在第一个测试案例中，不能进行删除，字符串a本身就是一个回文。
在第二个测试案例中，不能进行删除，但字符串ab不是回文。
在第三个测试案例中，可以删除1个字符，不管删除b还是a，得到的字符串都是一个回文字符串。
在第四个测试案例中，可以删除一个出现过的字符 a，得到字符串bb，这是一个回文字符串。
在第六个测试案例中，可以去掉一个出现过的字符b和d，得到字符串acac，然后将其重新排列为字符串 acca。
在第九个测试案例中，可以去掉一个出现过的字符t和k，得到字符串aagaa，这是一个回文字符串。
C.Raspberries
题面描述
有一个长度为 \(n\) 的数组 \(a\) 和一个整数 \(k\)( $ 2 \leq k \leq 5 $ )，你每次操作可以对数组内的任意一个数加 \(1\) 。
如果要使得 \(\prod \limits_{i=1}^n a_i\) （累乘：数组中所有数字的乘积）能被 \(k\) 整除，最小操作步数是多少？
输入格式
第一行包含一个整数 \(t\) ( \(1 \leq t \leq 10^4\) ) - 测试用例的数量。
每个测试用例的第一行包含两个整数 \(n\) 和 \(k\) （ \(2 \leq n \leq 10^5\) ， \(2 \leq k \leq 5\) ）-数组的大小 \(a\) 和数字 \(k\) 。
每个测试用例的第二行包含 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\) （ \(1 \leq a_i \leq 10\) ）。
保证所有测试用例中 \(n\) 的总和不超过 \(2 \times 10^5\) 。
输出格式
针对每个测试用例，输出满足条件的最少操作步数。
样例输入
15
2 5
7 3
3 3
7 4 1
5 2
9 7 7 3 9
5 5
5 4 1 2 3
7 4
9 5 1 5 9 5 1
3 4
6 3 6
3 4
6 1 5
3 4
1 5 9
4 4
1 4 1 1
3 4
3 5 3
4 5
8 9 9 3
2 5
1 6
2 5
10 10
4 5
1 6 1 1
2 5
7 7
样例输出
2
2
1
0
2
0
1
2
0
1
1
4
0
4
3
样例解释
在第一个测试案例中，我们需要选择两次第二个数字，数组将为 \([7, 5]\) 。数组中所有数字的乘积为 \(35\)，可以被 \(5\) 整除 。
在第四个测试用例中，数组中所有数字的乘积为 \(120\) ，已经可以被 \(5\) 整除，因此不需要进行任何操作。
在第八个测试用例中，我们可以对第二个数和第三个数各进行\(1\)次操作，数组将是 \([1, 6, 10]\) 。数组中各数的乘积为 \(60\) ，可以被\(4\)整除。
D.In Love
题面描述
你有 \(q\) 次操作，每次操作分为两种：
-
$ + $ $ l $ $ r $，表示添加一条区间范围为 \([l,r]\) 的线段。
-
$ - $ $ l $ $ r $，表示删除一条区间范围为 \([l,r]\) 的线段。
问每次操作后是否存在两条线段，使得它们的区间范围没有交集。
ps.建议对着样例画图理解。
输入格式
第一行都包含一个整数 \(q\) ( \(1 \leq q \leq 10^5\) ) - 操作次数。
接下来的 \(q\) 行描述两种类型的运算。 ( \(1 \leq l \leq r \leq 10^9\) ).
输出格式
每次操作后，如果存在两条不相交的线段，则打印YES，否则打印NO。
样例输入
12
+ 1 2
+ 3 4
+ 2 3
+ 2 2
+ 3 4
- 3 4
- 3 4
- 1 2
+ 3 4
- 2 2
- 2 3
- 3 4
样例输出
NO
YES
YES
YES
YES
YES
NO
NO
YES
NO
NO
NO
E.Look Back
题面描述
给定长度为 \(n\) 的序列 \(a\)，你可以进行以下操作：选取一个 \(i\) 满足 \(1\le i\le n\)，使 \(a_i\) 变为原来的 \(2\) 倍。
求最少需要几次操作使得 \(a\) 为一个不递减的序列。
输入格式
第一行包含一个整数 \(t\) ( \(1 \leq t \leq 10^4\) ) - 测试用例的数量。
每个测试用例的第一行包含一个整数 \(n\) ( \(1 \leq n \leq 10^5\) ) - 数组的大小 \(a\) 。
每个测试用例的第二行包含 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\) ( \(1 \leq a_i \leq 10^9\) )。
保证所有测试用例的 \(n\) 之和不超过 \(2 \times 10^5\) 。
输出格式
针对每个测试用例，输出使数组不递减所需的最少操作数。
样例输入
9
1
1
2
2 1
3
3 2 1
4
7 1 5 3
5
11 2 15 7 10
6
1 8 2 16 8 16
2
624323799 708290323
12
2 1 1 3 3 11 12 22 45 777 777 1500
12
12 11 10 9 8 7 6 5 4 3 2 1
样例输出
0
1
3
6
10
3
0
2
66
样例解释
在第一个测试用例无需进行任何操作。
在第二个测试用例中，我们需要选择 \(i = 2\) ，之后数组将是 \([2, 2]\) 。
在第三个测试用例中，我们可以进行以下操作：
- 选择 \(i = 3\) ，然后数组将变为 \([3, 2, 2]\)
- 选择 \(i = 3\) ，之后数组将变为 \([3, 2, 4]\)
- 选择 \(i = 2\) ，之后数组为 \([3, 4, 4]\)
F.You Are So Beautiful
题目描述
给定数列 \(a\)，定义一个子数组 \(S\) 是合法的：从 \(a\) 中有且仅有一种选法能选出子数组\(S\)（选法相同定义为最终选出的位置集合相同），求其有多少非空合法子序列。
ps.如何不理解，清看加黑的样例解释。
输入格式
第一行包含一个整数 \(t\) ( \(1 \leq t \leq 10^4\) ) - 测试用例的数量。
每个测试用例的第一行包含一个整数 \(n\) ( \(1 \leq n \leq 10^5\) ) - 数组的大小 \(a\) 。
每个测试用例的第二行包含 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\) ( \(1 \leq a_i \leq 10^9\) )。
保证所有测试用例的 \(n\) 之和不超过 \(2 \times 10^5\) 。
输出格式
对于每个测试用例，输出合法的子数组的数量。
样例输入 #1
6
1
1
2
1 1
3
1 2 1
4
2 3 2 1
5
4 5 4 5 4
10
1 7 7 2 3 4 3 2 1 100
样例输出 #1
1
1
4
7
4
28
提示
在第一个测试案例中，子数组1是合法的。
在第二个测试案例中，子数组1 1是合法的，因为仅有一种选法选出1 1。子数组1是不合法的，因为选第一个和选第二个都能选出子数组1。
在第三个测试案例中，子数组1 2 和2 1和1 2 1和2是合法的，因为他们都仅有一种选法。
G1. Dances (Easy version)
题目描述
这是问题的简单版本，与下个题唯一不同的是，在这个版本中m=1，而且不需要用到m。
给定两个长度为 \(n\) 的序列 \(a,b\)，其中 \(a_1=1\)， \(a_2\cdots a_n\) 与 \(b_1\cdots b_n\) 由输入得到。你可以对两个数组任意排序，你需要在两个序列中分别删除 \(k\) 个数，即剩下 \(n-k\) 个数，使得对于任意的 \(i(1\leq i\leq n-k)\)，都有\(a_i<b_i\)
求最少删除数\(k\)是多少？
输入格式
第一行包含一个整数 \(t\) ( \(1 \leq t \leq 10^4\) ) - 输入数据集的数量。
每个测试用例的第一行包含两个整数 \(n\) 和 \(m\) ( \(2 \leq n \leq 10^5\) , \(m = 1\) ) - 数组的大小和整数\(m\)（简单版本的题用不到m）。
每个测试用例的第二行包含 \(n - 1\) 个整数 \(a_2, \ldots, a_n\) ( \(1 \leq a_i \leq 10^9\) )。
每个测试用例的第三行包含 \(n\) 个整数 \(b_1, b_2, \ldots, b_n\) （ \(1 \leq b_i \leq 10^9\) ）。
保证所有测试用例中 \(n\) 的总和不超过 \(10^5\) 。
输出格式
对于每组测试用例，输出一行表示最少操作数。
样例输入
4
2 1
1
3 2
4 1
5 1 5
3 8 3 3
8 1
4 3 3 2 2 1 1
1 1 1 1 3 3 3 3
9 1
9 2 8 3 7 4 6 5
1 2 3 2 1 4 5 6 5
样例输出
0
1
4
4
样例解释
第一个测试用例中，数组是 \([1, 1]\)和\([3, 2]\) ，答案是 \(0\) ，不需要对元素进行删除操作。
G2. Dances (Hard Version)
题面描述
**这是问题的困难版本。唯一不同的是，在这个版本中 **\(m\le 10^9\)
给定两个长度为 \(n\) 的序列 \(a,b\)，其中 \(a_1=1\)， \(a_2\cdots a_n\) 与 \(b_1\cdots b_n\) 由输入得到。
你需要根据 \(a\) 数组求出 \(m\) 个 \(c\) 数组的值，具体地：
- \(c[i]_1 = i\)
- \(c[i]_j = a_j (2 \le j \le n)\)
对于每一个独立的 \(c[i]\) 数组与互不影响的 \(b\) ，你可以将 \(b\) 、 \(c[i]\) 数组中的数字随意排序，再随意删除 \(c[i]\) 与 \(b\) 中的 \(k\) 个数，对于每一个 \(c[i]\) 数组，求最小的 \(k[i]\) 使得对于任意\(1\le j \le n\), 都有\(c[i]_j < b_j\)，输出所有 \(c[i]\) 的删除数 \(k[i]\) 的和。
输入格式
第一行包含一个整数 \(t\) ( \(1 \leq t \leq 10^4\) ) - 输入数据集的数量。
每个测试用例的第一行包含两个整数 \(n\) 和 \(m\) ( \(2 \leq n \leq 10^5\) , \(1 \leq m \leq 10^9\) ) - 数组的大小和整数\(m\)。
每个测试用例的第二行包含 \(n - 1\) 个整数 \(a_2, \ldots, a_n\) ( \(1 \leq a_i \leq 10^9\) )。
每个测试用例的第三行包含 \(n\) 个整数 \(b_1, b_2, \ldots, b_n\) （ \(1 \leq b_i \leq 10^9\) ）。
保证所有测试用例中 \(n\) 的总和不超过 \(10^5\) 。
输出格式
对于每一个测试用例，输出所有 \(c[i]\) 的删除数 \(k[i]\) 的和。
样例输入
4
2 4
1
3 2
4 7
5 1 5
3 8 3 3
8 4
4 3 3 2 2 1 1
1 1 1 1 3 3 3 3
9 1
9 2 8 3 7 4 6 5
1 2 3 2 1 4 5 6 5
样例输出
2
12
16
4
样例解释
在第一个测试案例中
- 对于一对数组 \(([1, 1], [3, 2])\) ，答案是 \(0\) 。不需要对元素进行操作或重新排序。
- 对于一对数组 \(([2, 1], [3, 2])\) ，答案是 \(0\) 。第一个数组的元素可以通过重新排列得到 \([1, 2)\) 。无需进行任何操作。
- 对于一对数组 \(([3, 1], [3, 2])\) ，答案是 \(1\) 。可以从第一个数组中删除元素 \(3\) ，从第二个数组中删除元素 \(2\) 。
- 对于一对数组 \(([4, 1], [3, 2])\) ，答案是 \(1\) 。元素 \(4\) 可以从第一个数组中删除，元素 \(3\) 可以从第二个数组中删除。