本次作业完成了所有 Introductory Problems 的题目，并完成了 $2$ 道（$1$ 道简单题，$1$ 道困难题） Sorting and Searching 的题目。
Introductory Problems
CSES-1092 Two Sets
题意
将若干正整数划分成两个总和相等的集合。
思路
首先我们考虑数字的个数与是否存在合法划分的关系：首先我们可以简单地看出，我们可以将连续的四个数字 $i,i+1,i+2,i+3$ 划分为 $i, i + 3$ 和 $i+1, i+2$，因此当数字个数是 $4$ 的倍数时一定存在答案；接着我们观察题目的样例1，发现前三个正整数可以通过划分为 $1,2$ 和 $3$，剩下数依然按照连续四个数字的划分方案来进行，因此当数字满足 $4n+3$ 时也可以划分；那么 $4n+1$ 和 $4n + 2$ 呢？一个很简单地证明是我们对所有数字进行求和，即 $1 + 2 + \cdots+(4n+1) = \frac {(1 + 4n + 1) \times (4n + 1)} 2 = (2n + 1)\times (4n + 1)$，可以发现结果是两个奇数相乘，而 $4n+2$ 是偶数，因此 $4n+1$ 和 $4n+2$ 个数求和结果都是奇数，不可能将其划分成两个数字和相等的集合。
因此，将 $4n$ 和 $4n + 3$ 个数按照上面的思路进行划分， $4n+1$ 和 $4n+2$ 直接输出 NO 即可。
代码
n = int(input())
if n % 4 in (0, 3):
print("YES")
print(n // 2 + n % 4 // 3, end = "\n" + "1 2 " * (n % 4 // 3))
for i in range(n % 4 + 1, n + 1, 4): print(i, i + 3, end=" ")
print("\n" + str(n // 2), end = "\n" + "3 " * (n % 4 // 3))
for i in range(n % 4 + 2, n + 1, 4): print(i, i + 1, end=" ")
else:
print("NO")
CSES-1617 Bit Strings
题意
$n$ 位二进制数最多能表示多少不同的数字。
思路
每个位置都有 $0$ 和 $1$ 两个填法，因此答案为 $2 ^ n \pmod {10^9 + 7}$。对于题目中的数据范围，不断乘 $2$ 和取模以 $\mathrm O(n)$ 复杂度完全可以通过此题，另外可以通过左移位运算来加速，在支持大整数的 Python 中可以直接一行解决。而 C++ 中，为了保证尽量快的运算速度，因此使用了“快速幂”算法，此算法的原理是将幂次做二进制展开，即 $2^n = 2^{x_0\times 2^0} \times 2^{x_1\times 2^1} \times \cdots \times 2^{x_i\times 2^i}$，而通过观察可以发现连续两个乘数中 $2^{2^i}$ 刚好是 $2^{2^{i- 1}}$ 的平方，因此从 $2$ 开始每次都做平方运算并取模，然后根据 $x_i$ 的值确定是否乘到结果中。因为对 $n$ 做二进制展开的位数是 $\mathrm O(\log n)$，因此算法复杂度是 $\mathrm O(\log n)$。观察运行时间，从 Python 的 $40ms$ 优化到了 $0ms$。
代码
C++：Source code - Virtal Judge
#include <bits/stdc++.h>
long long n, ans = 1;
int main()
{
scanf("%lld", &n);
for (long long base = 2; n; n >>= 1, base = base * base % 1000000007)
if (n & 1) ans = ans * base % 1000000007;
printf("%lld", ans);
return 0;
}
Python：Source code - Virtal Judge
print((1 << int(input())) % 1000000007)
CSES-1618 Trailing Zeros
题意
计算 $n!$ 尾部有多少 $0$。
思路
我们考虑 $0$ 的个数跟什么有关，最直观的是 $10$ 的出现次数，但 $10$ 由 $2$ 和 $5$ 两个质因数组成，因此直接统计包含 $2$ 和 $5$ 的个数，然后取较小值即可。但在本题中，对于每个数去分别统计 $10^9$ 个数包含 $2$ 和 $5$ 的个数显然不能满足时限的要求，因此需要考虑更快速的算法。
首先很显然的是，最终统计结果 $5$ 的个数一定比 $2$ 的个数少，因此我们只需要统计 $5$ 的包含次数即可。接着我们来思考什么情况下会包含 $5$，可以发现只要是 $5$ 的倍数就一定包含 $5$，但个数不确定。那么其中某个数包含 $5$ 的个数是怎么确定的呢？最简单的做法是试除，看具体可以除掉多少个 $5$，即最大是 $5$ 的多少次幂的倍数。但我们注意到，在统计中 $5$ 的倍数会包含出现更多次数 $5$ 的结果，所以后面的统计都要减掉这次统计，这时我们可以发现，当统计 $5^2$ 的倍数的时候，出现的两次其中一次已经被前面统计，接着 $5^3$ 的倍数已经在前面被统计了两次，那么以此类推，之后每次都只需要统计一次即可。
这样，每次计算 $5^i$ 的倍数有多少即可， 这个可以 $\mathrm O(1)$ 计算出来，因此总复杂度为 $\mathrm O(\log_5 n)$。
代码
base, ans, n = 5, 0, int(input())
while base <= n: ans, base = ans + n // base, base * 5
print(ans)
CSES-1754 Coin Piles
题意
现在有两摞金币，每次可以从一摞中取一个，从另一摞中取两个，问能否取光。
思路
考虑 $a$ 和 $b$ 需要满足什么条件才能被全部取光，假设两种操作次数分别为 $x$ 和 $y$，则 $\begin{cases}x + 2y = a\ 2x + y = b\end{cases}$ 有非负整数解，即 $x=\frac{2b-a}3,y=\frac{2a-b}3$ 为非负整数。
代码
for _ in range(int(input())):
a, b = map(int, input().split())
print("YES" if 2 * b - a >= 0 and (2 * b - a) % 3 == 0 and 2 * a - b >= 0 and (2 * a - b) % 3 == 0 else "NO")
CSES-1755 Palindrome Reorder
题意
重排字符串使之成为回文串。
思路
回文串需要满足“最多只有一个字母出现次数是奇数”。因此直接统计出现次数然后从中间向两侧排即可。
代码
num = {}
sp = ans = ''
for i in input():
num[i] = num[i] + 1 if i in num else 1
for i in num:
if num[i] & 1 == 0: ans += i * (num[i] >> 1)
elif sp == '': sp = i * num[i]
else:
print('NO SOLUTION')
exit(0)
print(ans + sp + ans[::-1])
CSES-2205 Gray Code
题意
输出所有 $n$ 位格雷码。
思路
格雷码的一个性质是，$n$ 位格雷码可以由 $n - 1$ 位格雷码生成，具体生成方法是，将 $n - 1$ 位格雷码的所有数前面加上 $0$，然后将 $n - 1$ 位格雷码的所有数倒序，再在前面加上 $1$，即可得到 $n$ 位格雷码。简单模拟即可。
代码
ans, now, end = ['0', '1'], 1, int(input())
while now < end:
for i in range(len(ans) - 1, -1, -1):
ans.append('1' + ans[i])
ans[i] = '0' + ans[i]
now += 1
print('\n'.join(ans))
Sorting and Searching
CSES-1621 Distinct Numbers
题意
统计不同的数字个数
思路
直接插入 set 统计出现次数即可。
代码
#include<bits/stdc++.h>
using namespace std;
int n, x;
set<int> s;
int main()
{
scanf("%d", &n);
while (n--) scanf("%d", &x), s.insert(x);
printf("%d", s.size());
return 0;
}
CSES-2169 Nested Ranges Count
题意
给定 $n$ 个区间，对于每个区间，统计被该区间包含和包含该区间的区间个数。
思路
此题是 Sorting and Searching 板块过题人数最少的一题，需要结合排序、树状数组以及离散化等算法，且思路也较为巧妙。
首先，我们先考虑其中一个问题：包含该区间的区间个数。满足什么条件的区间 $b$ 可以包含当前区间 $a$ 呢？既然 $a\subset b$，那么应该满足 $b.l \le a.l$ 且 $b.r \ge a.r$。当我们统计到区间 $a$ 时，挨个检查所有区间是否满足如上条件显然不现实，需要尽量缩小待统计的区间，注意到我们可以先将满足 $b.l\le a.l$ 的区间调出来，只需要检查这些区间有多少符合 $b.r \ge a.r$ 即可。对于每个区间我们如何快速将满足 $b.l\le a.l$ 的区间选出来呢？只需要将区间按照 $l$ 的大小排个序即可，这样我们每次只需要检查位于该区间之前的所有区间即可。那现在我们只需要快速统计之前出现过的所有区间中有多少满足 $b.r \ge a.r$，这就变成了求当前 $[a.r,+\infty)$ 区间的区间和问题，使用树状数组这一数据结构（见下一段）即可 $\mathrm O(\log n)$ 解决。但现在又出现了另一个问题：$l,r$ 的数据范围是 $[1, 10^9]$，而树状数组所需要的空间是 $\mathrm O(数据范围)$，超出了空间限制。但是，我们注意到，虽然 $l,r$ 的数据范围是 $[1, 10^9]$，但区间的个数只有 $2\cdot 10^5$ 个，因此最多只有 $4\cdot 10^5$ 个不同的数字，我们完全可以将 $l,r$ 从 $[1, 10^9]$ 的数据范围映射到 $[1,4\cdot 10^5]$ 的数据范围中，这一数据范围内的树状数组便能满足题目的空间要求，这一映射缩小数据范围的操作便叫作离散化。
树状数组是一种支持以 $\mathrm O(\log n)$ 复杂度完成单点修改和区间求和的数据结构。它的主要思想是将数组中的每个元素映射到一个树状结构中。对于一个节点 $x$，$x$ 的二进制表示中的每一位，如果该位为 $1$，则向上走到父亲节点，否则向下走到儿子节点。这样，对于 $x$ 这个节点来说，其父亲节点就是 $x$ 的前缀，而它的儿子节点就是 $x$ 的后缀。这样，我们就可以通过树状结构来维护数组的前缀和，从而实现区间求和。而单点修改则可以通过修改 $x$ 的后缀来实现。因为每个节点在树状数组中前缀和后缀最多都只有 $\log n$ 个（对应二进制位有 $\log n$ 位），所以树状数组两种操作的复杂度均为 $\mathrm O(\log n)$。
现在还剩下另一个问题，有了前一个问题的思考，我们可以发现其实对于区间 $a$，它包含的所有区间 $b$ 都需要在所有满足 $b.l \ge a.l$ 的区间中统计有多少个满足 $b.r \le a.r$，只需要倒序将区间的右端点加入树状数组中求区间和即可。
自此，所有问题都得以解决。对于 $n$ 个区间中的每个区间，都需要执行两次单点修改和区间求和操作，因此这部分的复杂度为 $\mathrm O(n\log n)$ ；排序部分使用了C++ STL 中的 sort 函数，复杂度为 $\mathrm O(n\log n)$ ；离散化部分中，排序、去重以及 lower_bound 查询排名的复杂度都为 $\mathrm O(n\log n)$ 。因此总复杂度为 $\mathrm O(n\log n)$ 。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
struct node { int l, r, no; } v[maxn];
int n, val[maxn << 1], ans[2][maxn];
vector<int> u;
void add(int x, int value) { for (int ed = n << 1; x <= ed; x += x & -x) val[x] += value; }
int query(int x)
{
int ans = 0;
for (; x; x -= x & -x) ans += val[x];
return ans;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d%d", &v[i].l, &v[i].r), u.emplace_back(v[i].l), u.emplace_back(v[i].r), v[i].no = i;
sort(v + 1, v + 1 + n, [](const node &a, const node &b) { return a.l == b.l ? a.r > b.r : a.l < b.l; });
sort(u.begin(), u.end());
u.erase(unique(u.begin(), u.end()), u.end());
for (int i = 1; i <= n; ++i) v[i].l = lower_bound(u.begin(), u.end(), v[i].l) - u.begin() + 1, v[i].r = lower_bound(u.begin(), u.end(), v[i].r) - u.begin() + 1;
for (int i = 1; i <= n; ++i) ans[1][v[i].no] += query(n << 1) - query(v[i].r - 1), add(v[i].r, 1);
memset(val, 0, sizeof(val));
for (int i = n; i > 0; --i) ans[0][v[i].no] += query(v[i].r), add(v[i].r, 1);
for (int j = 0; j < 2; ++j)
for (int i = 1; i <= n; ++i) printf("%d%c", ans[j][i], " \n"[i == n]);
return 0;
}
