算法周赛round33

T1

已知 $a\leq b\leq c$，因此可以得到 $a\leq b\leq \ldots \leq a+b+c$。

因此得到前两个最小的数字，使用最大的数字减去前两个数字得和即可得到三个数字。

---

T2

如果可以访问农场 $i$ 则需要满足 $t_i+s<c_i$。移项可得 $s<c_i-t_i$。

定义序列 $a_i=c_i-t_i$，升序排序序列 $a$，当找到满足最小的 $j$ 使得 $s<a_j$ 依然成立。则 $a[j,n]$ 均可以被访问。

最小的 $j$ 可以使用 upper_bound 求出。判断是否有 $v$ 个农场即可。

时间复杂度：$O(n\log{n}+q\log{n})$。

---

T3

要使得序列的 mex = i，则序列中不能有 i。且 $0\sim i-1$ 的每个数字都必须存在（至少 $1$ 个）。

则对于每个 $i$，我们需要知道两个信息：

• 序列中有几个 $i$，可以用计数数组统计。记 $i$ 的个数为 $x$。
• 序列中 $[0,i-1]$ 有多少个数字不存在。记不存在的个数为 $y$。

则答案为 $\max(x,y)$。

$x$ 使用计数数组统计即可，$y$ 一边遍历一边维护即可。

---

T4

图象是关于中心点旋转对称的，因此首先一个位置 $(i,j)$ 其剩余三个对称点分别是：

• $(i,n-j+1)$
• $(n-i+1,j)$
• $(n-i+1,n-j+1)$

那么修改一个位置 $(i,j)$ 的贡献，主要取决于这四个位置中哪一个字符占比最多。

int calc(int i, int j)
{
    int x1 = i, y1 = j;
    int x2 = i, y2 = n - j + 1;
    int x3 = n - i + 1, y3 = j;
    int x4 = n - i + 1, y4 = n - j + 1;
    int sum1 = 0;
    if (a[x1][y1] == '#')
        sum1++;
    if (a[x2][y2] == '#')
        sum1++;
    if (a[x3][y3] == '#')
        sum1++;
    if (a[x4][y4] == '#')
        sum1++;
    int sum2 = 4 - sum1;
    return min(sum1, sum2);
}

那么首先我们可以求出原本需要的最小操作数 res。即：

for (int i = 1; i <= n / 2; i++)
    for (int j = n / 2 + 1; j <= n; j++)
        res += calc(i, j);

对于每次修改的位置 $(i,j)$ 先令 $res \gets res-\texttt{calc}(i,j)$，减去这个位置的贡献。然后修改 $a_{i,j}$ 的字符以后，再令 $res \gets res+\texttt{calc}(i,j)$。

时间复杂度：$O(n^n+m)$。