CodeForces

CodeForces 做题记录

Codeforces Global Round 27

A Sliding

当 \((r, c)\) 被取走时：

• \(\forall i \in [r + 1, n], (i, 1)\) 会移动到 \([i - 1, m]\)，曼哈顿距离为 \(m\)。
• \(\forall i \in [r + 1, n], j \in [2, m], (i, j)\) 会移动到 \((i, j - 1)\)，曼哈顿距离为 \(1\)。
• \(\forall i \in [c + 1, m], (r, i)\) 会移动到 \((r, i - 1)\)，曼哈顿距离为 \(1\)。

统计起来即可，答案为 \((m - 1) * (n - r) + (n - r) * m + (m - c)\)。

代码

A题写的也太慢了……
该推快一些的。

B Everyone Loves Tres。

有一个数学结论：一个用十进制表示的数，如果其奇数位的和与偶数位的和的差的绝对值为 \(11\) 的倍数，那么这个数为 \(11\) 的倍数。

那么构造 \(n\) 位的最小的 \(11\) 的倍数，再乘上 \(3\) 即可，很显然 \(n = 1\)，或 \(n = 3\) 时不可能成立。

又因为 \(2 \mid 66\)，所以最后两位应该为 \(66\)。

如果 \(2 \mid n\)，容易发现只需要最后两位为 \(66\) 其他均为 \(33\) 即可，此时满足数学结论。

否则，因为奇数位比偶数位多一位，所以可以用两位 \(3\) 合成一个 \(6\)。那么只需最后四位为 \(6366\)，其他均为 \(3\) 即可。

代码

很显然的题目，但是 \(14\) 分钟才写出来。而且还不知道有数学结论。

D Yet Another Real Number Problem。

思路很显然。

考虑前 \(i\) 位时，一定会把前 \(i\) 项 \(2\) 的次幂和给到一些数，记第 \(k\) 个被给 \(2\) 的数的下标为 \(g_k\)。

记一个区间 \([i, j]\)，\(2\) 的次幂的和为 \(t(i, j)\)。

对于当前考虑的 \(a_i\)，如果将 \(a_i \times 2^{(g_k + 1, i - 1)} \gt a[g_k]\)，那么令 \(g_k = i\) 即可。

又因为 \(a_i \le 1\times 10^9\)，故 \(g_{k} - g_{k - 1} \lt 30\)，否则直接合并即可。

重复执行上述操作，直到不满足为止。

因为会不断删去前面的 \(g\)，最多跳 \(30\) 次，故从左向右执行上述操作的时间复杂度大概为 \(O(n\log a_i)\)。

发现删去 \(g\) 类似维护单调性，故可以用单调栈维护。

代码。

没有想到用单调栈是真做的少了……