Codeforces Round 748
A. Elections
Type:#OI Problem
Algorithm:#Brute Force
Source:#https://codeforces.com/contest/1593/submission/131928145
Task
给定 \(a,b,c\)，对每一个数求出至少要加多少才能使这个数大于剩下两个数。
多测。
限制：\(0\leq a,b,c\leq 10^9,1\leq t\leq 10^4\)
Solution
设最大值为 \(\text{mx}\)，如果这个数是最大值且唯一，则答案为 \(0\)，若不唯一，则答案为 \(1\)，如果不是最大值，设其为 \(p\)，则需要加上 \(\text{mx} - p+1\)。
时间复杂度：\(\mathcal O(t)\)
B. Make it Divisible by 25
Type:#OI Problem
Algorithm:#Brute Force
Source:#https://codeforces.com/contest/1593/submission/131928615
Task
给定整数 \(n\)，求出最少删去其中的几个数能使 \(n\) 被 \(25\) 整除（不含前导 \(0\)，即如果给 \(2005\) 删去 \(2\) 会变成 \(5\)）。
数据保证有解，多测。
限制：\(25\le n\le 10^{18},1\le t\le 10^4\)。
Solution
考虑一个数能被 \(25\) 整除，当且仅当它的后两位数为 \(25,50,75,00\)，所以我们可以枚举是否出现这样的两位数（注意这里的两位数是需要有序的，其实很好想，你不可能把 \(5,2\) 调换位置）。
时间复杂度：\(\mathcal O(t\log^2n)\)
C. Save More Mice
Type:#OI Problem
Algorithm:#Greedy
Source:#https://codeforces.com/contest/1593/submission/131928753
Task
有一个长为 \(n+1\) 的数轴，猫在 \(0\) 号位置，洞在 \(n\) 号位置，有 \(k\) 只老鼠在猫和洞之间，第 \(i\) 只坐标为 \(x_i\)。
每一秒你可以选择一只老鼠向右移动一格，然后猫将移动一格。
如果猫和老鼠同格，那么猫会吃掉老鼠。
最大化到达洞的老鼠数量。
多测。
限制：\(2\le n\le 10^9\),\(1\le k,\sum k\le 4\times 10^5\),\(1\le t\le 10^4\)
Solution
容易发现老鼠走的步数一定小于猫的步数，那么考虑贪心，即先送离洞最近的老鼠，然后送次近的……
容易发现当走的步数和 \(\gt n\) 的时候，剩下的老鼠便葬身猫围了，答案即为当前循环到的下标 \(-1\)。
时间复杂度：\(\mathcal O(k\log k)\)（单次）
D1. All are Same
Type:#OI Problem
Algorithm:#Euclid Algorithm
Source:#https://codeforces.com/contest/1593/submission/131822562
Task
给定 \(n\) 个数，最大化 \(k\)，使得 \(a_1+p_1\times k=a_2+p_2\times k=\cdots=a_n+p_n\times k\)。
多测。
限制：\(1\le n\le 40\),\(1\le \sum n\le 100\),\(-10^6\le a_i\le 10^6\)
Solution
容易发现满足若 \(k\) 满足条件，则这 \(n\) 个数在 \(\bmod k\) 意义下同余。
则答案为 \(\gcd(a_2-a_1,a_3-a_2,a_4-a_3,\cdots,a_n-a_{n-1})\)
时间复杂度：\(\mathcal O(n\log V)\)（单次）
D2. Half of Same
Type:#OI Problem
Algorithm:#Brute Force
Source:#https://codeforces.com/contest/1593/submission/131935927
Task
给定 \(n\) 个数，最大化 \(k\)，满足 \(a_1+p_1\times k=a_2+p_2\times k=\cdots=a_m+p_m\times k(m\ge\dfrac n 2)\)，这里的 \(a\) 可以任意排列。
多测。
限制：\(1\le n\le 40\),\(1\le \sum n\le 100\),\(-10^6\le a_i\le 10^6\)
Solution
借助 D1 的结论，其实就是在 \(\bmod k\) 下同余，暴力枚举 \(k\) 即可，为了避免处理负数，可以同时加上 \(V\)（值域）。
时间复杂度：\(\mathcal O(nV)\)
E. Gardener and Tree
Type:#OI Problem
Algorithm:#Breadth First Search
Source:#https://codeforces.com/contest/1593/submission/131847135
Task
给定一棵 \(n\) 个点的无根树，每次操作会删掉所有的叶子节点，求 \(k\) 次操作后剩下的结点个数。
多测。
限制：\(1\le n,\sum n\le 4\times10^5\),\(1\le k\le 2\times 10^5\),\(1\le t\le 10^4\)
Solution
考虑 bfs，将一开始的叶子节点深度设为 \(1\)，然后进行 bfs 搜深度，第一次搜到这个点一次减一次这个点的度数，将入度为 \(0\) 的点入队并赋深度，最后深度 \(\gt k\) 的点就会留下。
时间复杂度：\(\mathcal O(\sum n)\)
F. Red-Black Number
Type:#OI Problem
Algorithm:#
Source:#
Task
给定 \(n\) 个数字，你需要将其中的一些数染成红色，一些染成黑色，使得红色数字拼接起来能被 \(A\) 整除，黑色数字拼接起来能被 \(B\) 整除，最小化染成红色的数字个数与染成黑色的数字个数的差。
限制：\(1\le n,A,B\le 40\)
G. Changing Brackets
Type:#OI Problem
Algorithm:#Prefix Sum
Source:#https://codeforces.com/contest/1593/submission/131962519
Task
给一个长度为 \(n\) 的由 [ ] ( ) 组成的括号序列 \(s\)，\(q\) 次询问，每次询问包含两个参数 l r，问最少花费多少价值能将 \(s[l...r]\) 变成匹配括号串。
你允许进行如下两种操作：
- 将
[]变成][，或是将()变成)(，这种操作花费为 \(0\)。 - 将
]变成)，或是将[变成(，这种操作花费为 \(1\)。
多测，询问之间互相独立。
限制：\(1\leq n,\sum n\leq 10^6\),\(1\leq q,\sum q\leq 2\times 10^5\)
Solution
我们要思考怎样让尽量少的 [] 被转换成 ()，考虑两个 [] 能够匹配的条件——这两个括号中间有偶数个括号。
也就是说这两个括号的奇偶性一定不同。
设 \(\text{odd}_{l,r}\) 为 $ s[l...r] $ 中中括号在奇数位置的个数，\(\text{even}_i\) ，则需为 $ s[l...r] $ 中中括号在偶数位置的个数，则要被变为圆括号的中括号个数即为：\(\text{abs}(\text{odd}_{l,r}-\text{even}_{l,r})\)，可以用前缀和优化。