A.Alternative Accounts
题目描述：
总共有 $ n $ 个账号参加 $ k(k \le 3) $ 场比赛，一个人可能有多个账号，但是一个人只能使用一个账号参加一场比赛。给出 $ k $ 场比赛的参与账号，问这些账号至少属于多少个人。
数据范围：
$ 1\le n \le 10^5, 1\le k \le 3, 1\le m \le n, 1\le x_i \le n $
题解：
当 $ k = 1 $ 时，有多少个账号就有多少个人
当 $ k = 2 $ 时，参加两场比赛的账号全是人， $ c $ 个，只参加第一场的为 $ a $ ，只参加第二场的为 $ b $ ，答案为 $ c + \max(a, b) $
当 $ k = 3 $ 时，参加三场比赛的全加上，参加 $ 1,2 $ 的可以和只参加 $ 3 $ 的绑定，只参加一场的可以匹配，得到答案
代码：
1 | const int maxn = 1e5 + 10; |
E. Matching Problem
题目描述：
给出两个序列 $ a1, a_2, \cdots, a_m $ 和 $ b_1, b_2, b_3, b_4 $ ，两序列匹配的条件为：
- 长度相等
- $ x_i = x_j \Leftrightarrow y_i = y_j $
输出有多少个 $ a $ 的子序列和 $ b $ 匹配
数据范围：
$ 1\le n \le 300,1\le a_i \le n, 1\le b_i \le 4 $
题解：
数据范围比较小，这里直接枚举 $ a $ 中的三个数，然后判断第四个数有多少个。需要记录 $ a $ 中每个位置的数在后缀中出现的次数。
代码：
1 | const int maxn = 1e3 + 10; |
G. Cryptographically Secure PRNG
题目描述：
给出一个素数 $ p $ ，找出所有的 $ x $ 满足 $ inv(x) = min_{i = 2}^x inv(i) $ ，其中 $ mod = p $
数据范围：
$ 1\le T \le 500, 1\le p \le 10^9 $
题解：
当 $ p $ 非常大，所以直接算不太行。
因为逆元是相互的， $ x $ 的逆元是 $ inv(x) $ ， $ inv(x) $ 的逆元是 $ x $ ，所以如果 $ inv(x) $ 是第一次出现，那么表示是出现了第一个 $ x $ 使得 $ inv(x) = x $ ，这时 $ (inv[x] = x) $ 也是一个答案，因此我们可以记录下 $ x $ 当第一次出现 $ 下标inv(x) = 下标x $ 时，将之前记录的答案再加入一遍，排序，输出。
代码：
1 | const int maxn = 1e6 + 10; |
H. Geometry PTSD
题目描述：
找出单位圆上三点 $ A, B, C $ ，满足 $ \min(|AB|,|BC|, |AC|) \ge 1.7 $ 并且原点到平面 $ ABC $ 的距离小于等于 $ 1e^{-18} $ 大于 $ 0 $
输出三行，每行三个整数 $ x_i, y_i, z_i (-10^6 \leq x_i, y_i, z_i \leq 10^6, x^2 + y^2 + z^2 \neq 0) $ 代表一个点 $ (\frac{x}{\sqrt{x^2+y^2+z^2}},\frac{y}{\sqrt{x^2+y^2+z^2}},\frac{z}{\sqrt{x^2+y^2+z^2}}). $
数据范围：
题解：
发现需要找到这个平面，而且与原点距离非常近。可以先找一个过原点的等边三角形，然后放大倍数。 $ A(0, 1, 0), B(-\frac{\sqrt{3}}{2}, -\frac{1}{2}, 0), B(\frac{\sqrt{3}}{2}, -\frac{1}{2}, 0) $ 根据输出要求，直接每个点乘 $ 10^6 $ ，乘的越大误差越小，通过强制转 int ，可以保证不是恰好过原点。
代码：
1 | import math |
I. Practice for KD Tree
题目描述：
给出一个 $ n \times n $ 的矩阵，初始全为 $ 0 $ 。执行 $ m1 $ 次子矩阵加，然后执行 $ m2 $ 查询子矩阵最大值
数据范围：
$ 1\le n \le 2000, 1\le m_1 \le 5 \times 10^4 \\\\ 1\le m_2 \le 5 \times 10^5 $
题解：
先使用二维前缀和处理出子矩阵加之后的矩阵，然后使用二维线段树，没有修改，查询最大值。
二维线段树，首先以 $ x $ 为区间建立线段树，然后每个节点也都是一个线段树，即每个节点以 $ y $ 为区间建立线段树。
代码：
1 | const int maxn = 2e3 + 10; |