Codeforces Round 861 (Div. 2)

A

• 如果能出现 90，则是最优。如果不能，数据则很小，可以暴力
• 也可以将每个数字都算出来，存到 vector 中，然后从小到大二分找第一个大于等于 l 的数字，如果小于则代表可行

B

• 全是绝对值，发现人的顺序不是重要的，只需要对每列提出来，排序 $a[i] * i - sum$ 即可
• jiangly 没有处理前缀和 $sum$，是 $(a[i] - a[i - 1]) \times i \times (n - 1)$，可以形象地画图理解，每次统计差值贡献

C

• 注意 1e18 + 5 == 1e18

  表示最大值不能将 5 括进去

  即需要这样写 const ll INF = (long long)1e18 + 5

• 数位 DP 一定注意是否高位溢出，而且如果只是求数字，完全可以不用将其组装为 int 或 long long，直接输出字符串即可

D

• 改编自 https://atcoder.jp/contests/abc290/tasks/abc290_e

  将数与数间连一根线，就转化为不同序列中不好的线（数字不同）有多少，再容斥一下，求好的线

  然后将数字下标存储，双指针统计答案

• 而此题

• jiangly

  注意预处理 trick， 2 * a[i] - i % 2 直接将下标奇数映射到奇数，下标偶数映射到偶数，保证了奇数部分原来的相同仍然相同，但奇数和偶数部分原来相同的却不同

• 正如上题，可以容斥，先处理全部，减去相同即可。现在即想办法查询一个区间相同的数有多少（可以用上面提到的 trick 预处理一下），这里的相同也可以容斥用离线维护，将 query(l, r) 转化为 query(r) - query(l - 1)，再离线统计即可（二维点对统计思想，扫描线思想）

E1

• 即求有一位数与其他数的和在模 k 的意义下相同的数有多少，数据范围显然数位 DP

• 条件转换，一位与其他数的和，即就是一位与和减去这一位

  $a_i \equiv S - a_i (\mod k)$

  $2 \times a_i \equiv S - a_i (\mod k)$

  直接求很容易会重复，考虑容斥，总数即 $k^n$，而不同即是裸的数位 DP，枚举最终和为多少，每次枚举转移时注意不用 $2 * a_i \equiv S$ 的数即可

E2

以后再补