算法周赛round27

T1¶

知识点：数组，循环嵌套。

题目分析

有 $m$ 棵树和 $m-1$ 片草坪，排列为：树 $1$，草坪 $1$，树 $2$，草坪 $2$，$\ldots$，树$m$；
两种施工操作破坏区间内的绿化：
- 类型 $1$：破坏第 $l$ 棵树和第 $r$ 棵树之间（不含 $l,r$）的所有绿化，即破坏树 $(l+1)$ 到 $(r-1)$ 和草坪 $l$ 到 $r-1$；
- 类型 $2$：破坏第 $l$ 棵树和第 $r$ 棵树之间（包含 $l,r$）的所有绿化，即破坏树 $l$ 到 $r$ 和草坪 $l$ 到 $r-1$；
施工后统计剩余未被破坏的树和草坪数量。

解题思路

维护两个数组：
- tree[1,.., m] 标记每棵树是否被破坏（0 表示存活，1 表示被破坏）；
- grass[1,.., m - 1] 标记每片草坪是否被破坏；
- 两个数组初始化均设为全局变量即可。
对每次施工，根据类型更新 tree 和 grass 的状态；
最后分别统计两个数字里 0 的个数即为剩余的树和草坪数。

实现步骤

初始化 tree 和 grass 数组，全部标记为 0；
遍历每次施工：
- 若类型为 $1$：
  - 对树：标记 tree[l + 1, .., r - 1] 为 1（若区间非空）；
  - 对草坪：标记 grass[l, .. ,r - 1] 为 1；
- 若类型为 $2$：
  - 对树：标记 tree[l, .., r] 为 1；
  - 对草坪：标记 grass[l, .., r - 1] 为 1；
统计 tree[1,.., m] 中 0 的数量为剩余树数，统计 grass[1,.., m - 1] 中 0 的数量为剩余草坪数；
输出两个结果。

T2¶

知识点：思维题。

这道题的关键点在于：标签数量变化时，标签长度随之变化。我们不需要模拟整个过程，只需关注标签长度的变化区间。

观察 1：标签长度的定义

当剩余标签数量为 $m$ 时：

\[ \text{len} = \min\left(b,\frac{a}{m}\right) \]

也就是说：

当标签很多时：$\text{len} = a/m$（被挤窄）
当标签变少时：$\text{len} = b$（变宽，但不超过 $b$）

标签右端点位置分别为：

\[ \text{len},\ 2\cdot\text{len},\ 3\cdot \text{len},\ \ldots,\ m\cdot \text{len} \]

观察 2：鼠标只可能移动到两个关键点

无论标签长度如何变化，所有右端点都只可能落在：

$a$（当 $\text{len} = a/m$ 时）
$b$（当 $\text{len} = b$ 时）

因此，鼠标最多只需要移动到 $a$ 和 $b$ 这两个位置。

这意味着：答案最多是 2

什么时候答案是 1？

要做到只移动一次鼠标，必须从始至终只需要点击 $b$ 这个位置。

也就是说：一开始标签长度必须已经是 $b$，即

\[ \frac{a}{n} \geq b \]

等价于：

\[ n \cdot b \le a \]

另外，如果 $b = a$，每个标签长度也是 $a$，显然也只需要移动一次。

时间复杂度：$O(1)$。

T3¶

知识点：思维题，分类讨论。

要放 $a$ 个车与 $b$ 个兵，满足：

每行、每列最多一个车
$(i,j)$ 有兵且 $i \ge 2$，则 $(i-1,j)$ 不能有棋子
每格最多一子

基本限制：车每行每列只能一个，因此：

\[ a > n \Rightarrow \text{No} \]

以下只讨论 $a \leq n$。

兵的可放位置规律

若某列有车，则该列不能放兵（兵头上不能有棋子）。

所以兵可用的列数为 $n - a$。

兵只能放在没有车的行上。

最优摆法：车优先占偶数行

因为兵放在行数越多越好，所以让车尽量挤在偶数行中。

共有：

偶数行数量：$\lfloor \frac{n}{2}\rfloor$
奇数行数量：$\lceil \frac{n}{2}\rceil$

情况 1：车能全部放入偶数行

\[ a \le \left\lfloor \frac{n}{2} \right\rfloor \]

兵可用行数为奇数行数：

\[ \left\lceil \frac{n}{2}\right\rceil \]

每行可用列数：$n - a$

最大兵数：

\[ \left\lceil \frac{n}{2}\right\rceil (n-a) \]

情况 2：车占满偶数行并溢出到奇数行

\[ a > \left\lfloor \frac{n}{2} \right\rfloor \]

兵可用行数：

\[ n - a \]

最大兵数：

\[ (n-a)(n-a) \]

设最大可放兵数为 maxB。

若：

\[ b \le \text{maxB} \]

输出 Yes，否则输出 No。时间复杂度：$O(1)$。

T4¶

知识点：二分答案，贪心。

目标：组建最多的班级数，每个班需要：

$1$ 位班主任
对每个学科都需要 $1$ 位老师授课

第 $i$ 个老师的属性为 $(a_i, b_i, c_i)$：

教学科 $a_i$
最多带 $b_i$ 个班
若 $c_i = 1$ 表示愿当班主任，当班主任后最多带 $b_i - 1$ 个班。

二分答案

最大班级数 $x$ 具有单调性：若能组 $x$ 个班，则一定能组 $x-1$ 个班。

因此二分 $x$（$x\in [1,n]$），对每个 $x$ 判断可行性。

判定：能否组出 $x$ 个班？

对每个学科 $i$ 统计：

cnt1[i]：所有教该学科老师的可授课班数之和
cnt2[i]：愿当班主任的老师数量

先对所有老师读入：

cnt1[a] += b
cnt2[a] += c

从前往后遍历所有学科 $i$ 其中 $i\in [1,m]$。

每个学科必须至少有 $x$ 个老师愿意授课，因此当 cnt1[i] < x 可直接判定不可行。

这些老师剩余的授课能力可用于“贡献班主任”，维护一个变量 sum 记录最多有多少个老师愿意干班主任。

若学科 i 已分配 $x$ 个授课量，则剩余可贡献：cnt1[i] - x 个老师去干班主任。

但只能从愿意当班主任的教师中选，因此可以用于干班主任的老师数量为 min(cnt1[i] - x, cnt2[i])

把所有学科的可贡献班主任数量求和，最后判定 sum >= x 是否成立即可。

时间复杂度：$O(m\log n)$

T5¶

知识点：动态规划，模拟。

性质 1：

旋转操作最多执行 2 次（旋转 $3$ 次会回到原状）。

性质 2：

同层交换任意两个数的目的，是为了保证路径经过该层的 最大值。

整体流程，依次考虑三种形态：

初始三角形
旋转一次
再旋转一次

对每种形态分别求：

最大路径和
达到该路径和的最小消耗值

取最优答案。

旋转操作

示例：

1                6
2 3              7 5      
4 5 6     →      6 8 2
10 9 8 7         3 5 9 5
2 5 2 5 6        1 2 4 10 2

不难发现：

原第 1 列 → 第 $n$ 行
原第 2 列 → 第 $n-1$ 行
…

即：原 (i, j) → 旋转后 (n - j + 1, i)。

对应代码：

void rotate() 
{
    int b[N][N];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            b[n - j + 1][i] = a[i][j];
    memcpy(a, b, sizeof(b)); // 将矩阵 b 的内容复制给 a
}

如何求最大路径和与最小交换次数

从上往下走即可（与从下往上完全等价）。

要使路径和最大：每一行必须经过该行的最大值。

若走到 (i, j) 位置但 a[i][j] 不是该行最大值，则需要使用一次交换操作。

同一行是否交换不会影响后续，因此可以用 DP。

DP 设计

定义：$dp[i][j] =$ 走到 $(i, j)$ 时的最少交换次数。

预处理：$r[i] =$ 第 $i$ 行的最大值。

转移方程：

\[ dp_{i,j} = \min(dp_{i-1,j},\ dp_{i-1,j-1}) + (a_{i,j} \ne r[i]) \]

每次旋转后做一次 DP 即可。

总体时间复杂度：$O(n^2)$。

具体实现建议

void rotate()
{

}
void dp()
{

}
int main()
{
    for (int i = 1; i <= 3; i++)
    {
        rotate();
        dp();
        // 更新答案
    }
}