A: 排列字母(签到题)

小蓝要把一个字符串中的字母按其在字母表中的顺序排列。

例如，LANQIAO 排列后为 AAILNOQ。

又如，GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY

请问对于以下字符串，排列之后字符串是什么？

WHERETHEREISAWILLTHEREISAWAY

根据ANCII值直接排序即可, 时间复杂度:(nlgn)

B: 特殊时间 (枚举)

2022 年 2 月 22 日 22:20 是一个很有意义的时间，年份为 2022，由 3 个 2 和 1 个 0 组成，如果将月和日写成 4 位，为 0222，也是由 3 个 2 和 1 个 0 组

成，如果将时间中的时和分写成 4 位，还是由 3 个 2 和 1 个 0 组成。

小蓝对这样的时间很感兴趣，他还找到了其它类似的例子，比如 111 年 10

月 11 日 01:11，2202 年 2 月 22 日 22:02 等等。

请问，总共有多少个时间是这种年份写成 4 位、月日写成 4 位、时间写成

4 位后由 3 个一种数字和 1 个另一种数字组成。注意 1111 年 11 月 11 日 11:11

不算，因为它里面没有两种数字。

由于年份没有限制, 我们只要判断枚举出来的月份和时间是否合法就行了, 然后利用乘法原理就可以计算出有多少个特殊时间了!

另外有一个更奇妙的方法: 我们可以推出实际上满足的月份日期只有16种, 再每个日期月份排列看看时间合法的数量, 再根据乘法原理相乘就会得出答案:

C.纸张尺寸 (模拟)

在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm × 841mm，将 A0 纸沿长边对折后为 A1 纸，大小为 841mm × 594mm，在对折的过程中长度直接取下整（实际裁剪时可能有损耗）。将 A1 纸沿长边对折后为 A2 纸，依此类推。 

输入纸张的名称，请输出纸张的大小。 

样例输入

A0

样例输出

1189 841

直接模拟, 时间复杂度 O(n):

D.求和 (前缀和)

给定 n 个整数 a1, a2, · · · , an ，求它们两两相乘再相加的和，即 S = a1 · a2 + a1 · a3 + · · · + a1 · an + a2 · a3 + · · · + an-2 · an-1 + an-2 · an + an-1 · an.

对于 30% 的数据，1 ≤ n ≤ 1000，1 ≤ ai ≤ 100。

对于所有评测用例，1 ≤ n ≤ 200000，1 ≤ ai ≤ 1000。

注意到 n 的范围会达到 200000 (10^5数量级), 如果我们直接用两个 for 循环枚举的话时间复杂度会达到 O(n^2) 超出时间限制. 我们观察到S 实际上等于

a1 * (a2 + a3 + ... + an) + a2 * (a3 + a4 + ... + an) + ... + an-1(an)

假如我们计算出数组的前缀和pre, 于是答案就为 ,于是我们就可以只用一个 for 循环将时间复杂度优化到 O(n) 级别了(求和可能会溢出，C++要开long long):

E.数位排序 (模拟 + 排序)

小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。

例如，2022 排在 409 前面，因为 2022 的数位之和是 6，小于 409 的数位之和 13。

又如，6 排在 2022 前面，因为它们的数位之和相同，而 6 小于 2022。

给定正整数 n，m，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元素是多少？ 

对于 30% 的评测用例，1 ≤ m ≤ n ≤ 300。

对于 50% 的评测用例，1 ≤ m ≤ n ≤ 1000。

对于所有评测用例，1 ≤ m ≤ n ≤ 106。 

我们发现直接模拟是可行的, 因为 n 的数量级才 10 ^ 6, 我们枚举每一个数并求出它的数位和进行排序, 时间复杂度为 O(nlgn):

注意题目中的 "当数位之和相等时，将数值小的排在前面", 看漏眼不小心 WA 了一发。。。

F: 选数异或(数学 + 动态规划)

给定一个长度为 n 的数列 A1, A2, · · · , An 和一个非负整数 x，给定 m 次查

询, 每次询问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x 。

输入的第一行包含三个整数 n, m, x 。

第二行包含 n 个整数 A1, A2, · · · , An 。

接下来 m 行，每行包含两个整数 li,ri 表示询问区间 [li,ri] 。

对于每个询问, 如果该区间内存在两个数的异或为 x 则输出 yes, 否则输出

no。

4 4 1

1 2 3 4

1 4

1 2

2 3

3 3

【样例输出】

yes

no

yes

no

对于 20% 的评测用例，n, m ≤ 500, 1 ≤ a1, a2, · · · , an ≤ 1000；

对于 40% 的评测用例，n, m ≤ 5000；

对于所有评测用例，1 ≤ n, m ≤ 100000, 1 ≤ a1, a2, · · · , an ≤ 100000, 1 ≤ li ≤ ri ≤ n, 1 ≤ ki ≤ n。

由于题目中的n, m数量级很高, 直接暴力会很容易超时, 假设我们在一次查询中在区间[li, ri]找到了两个数使得异或为 x, 那么对任意包含于[li, ri]的区间, 我们的答案都为yes.

我们的目标是找到两个数 a, b使得 a ^ b = x, 对于 a, b 我们唯一知道的是它在[li, ri]中, 但是只知道这一点是不够的, 我们继续来看看a,b和x 满足什么性质:

a ^ b = x

a ^ b ^ a = x ^ a

b ^ 0 = x ^ a

b = x ^ a

于是我们发现 a, b 在区间[li, ri]中,并且 b = x ^ a 也会在 区间 [li, ri]中, 于是我们可以使用map来记录 a 和 b 的位置.

于是我们定义一个 dp[i]: 在[0, i]区间中最大a的位置，并且我们确保了a,b中的a一定是前面那个元素(因为是正向 for 循环), 于是查询的时候我们只需要判断dp[r] 是否大于等于 l 就知道这个区间是否合法了。

G: 消除游戏(暴力)

在一个字符串 S 中，如果 S i = S ii 1 且 S i , S i+1 ，则称 S i 和 S i+1 为边缘

字符。如果 S i , S ii 1 且 S i = S i+1，则 S ii 1 和 S i 也称为边缘字符。其它的字符

都不是边缘字符。

对于一个给定的串 S，一次操作可以一次性删除该串中的所有边缘字符

（操作后可能产生新的边缘字符）。

请问经过 2

64 次操作后，字符串 S 变成了怎样的字符串，如果结果为空则

输出 EMPTY。

【输入格式】

输入一行包含一个字符串 S 。

【输出格式】

输出一行包含一个字符串表示答案，如果结果为空则输出 EMPTY。

【样例输入 1】

edda

【样例输出 1】

EMPTY

H: 重新排序(差分 + 前缀和 + 贪心)

给定一个数组 A 和一些查询 Li, Ri，求数组中第 Li 至第 Ri 个元素之和。

小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查

询结果的和尽可能地大。小蓝想知道相比原数组，所有查询结果的总和最多可

以增加多少?

【输入格式】

输入第一行包含一个整数 n。

第二行包含 n 个整数 A1, A2, · · · , An，相邻两个整数之间用一个空格分隔。

第三行包含一个整数 m 表示查询的数目。

接下来 m 行，每行包含两个整数 Li、Ri ，相邻两个整数之间用一个空格分

隔。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

5

1 2 3 4 5

2

1 3

2 5

【样例输出】

4

【样例说明】

原来的和为 6 + 14 = 20，重新排列为 (1, 4, 5, 2, 3) 后和为 10 + 14 = 24，增

加了 4。

【评测用例规模与约定】

对于 30% 的评测用例，n, m ≤ 50 ；

对于 50% 的评测用例，n, m ≤ 500 ；

对于 70% 的评测用例，n, m ≤ 5000 ；

对于所有评测用例，1 ≤ n, m ≤ 105，1 ≤ Ai ≤ 106，1 ≤ Li ≤ Ri ≤ 106 。

为了使得总和尽可能的大, 我们需要使得变化后的数组在频繁查询的区间尽可能大。

我们先统计数组中每个区间被查询到的次数, 再对数组进行排序, 使得大的数能够放到查询次数多的区间中去:

注意我们 num 定义刚开始是一个差分形式[0 ,..., 0](因为每个元素被查询到的次数都是 0, 0 - 0 = 0), 于是当查询到 [l, r], 其中涉及到到每一个位置+1, 我们的差分式就有: num[l]++, num[r + 1]--, 最后我们对 num 进行求和就得到每个位置被查询到的次数(有点像积分哈哈哈)。