这次是 div1 + div2 的比赛
九题里写了四题
排在 1116 名，掉了 36 分
最近不管是 LeetCode 还是 Codeforces 都一直掉分 :(
https://codeforces.com/contest/1782
A. Parallel Projection
往四个方向都试一试就可以了
B. Going to the Cinema
从看到不需要 mod 就大概可以猜的出来应该有某种单调性存在
可以发现，假如 a_i >= a_j
则不可能发生需要选 a_i 却不需要选 a_j 的情形
所以假如对 a_1, ..., a_n 排好序
最后的选法一定是
1 1 ... 1 1 0 0 .... 0 0
这种形式（1 代表去），只会有 n + 1 种可能
而合不合法只需要观察 0 跟 1 交界的两个点即可
所以不算排序可以 O(n) 解决
C. Equal Frequencies
以前写 LeetCode 有被这种要相同 frequency 的题目坑过几次
坑人的点在于，如果出现次数变成 0 的话就不会被计算在内
例如 [1, 9, 10, 10] 可以把那个 1 移到 9 变成 [10, 10, 10]
我的作法是假设可以分成 k 堆
取前 k 多的来看要搬多少次
因为只有小写字母数量很少所以没什么影响
D. Many Perfect Squares
x 可能的范围太大了也没有单调性，不太可能是从这边做
因为 n <= 50 ，对于两个点 A[i] 及 A[j]
如果这两个点都是平方数，则存在
a^2 = A[i] 及 b^2 = A[j]
则有
A[j] - A[i] = b^2 - a^2 = (b + a)(b - a)
显然 (b - a) <= sqrt(A[j] - A[i]) <= sqrt(10^9)
对 (b - a) 可能的值都试一遍，每个 (b - a) 对应到相应的 x
代表这个 x 可以让 A[i] 和 A[j] 同时是平方数
用一个 map<int, set<int>> 来纪录每个 x 总共能让多少人是平方数
取最高的即可
复杂度：O(n^2 * sqrt(C) * log(n) * log(nC))
其中 C 是 a_1, ..., a_n 的最大值，最多是 10^9