CSP模拟赛day1
T1 纸张（paper）¶
知识点：模拟
维护两个二维数组 $a,b$。其中 $a_{i,j}$ 记录 $(i,j)$ 的颜色，$b_{i,j}$ 记录 $(i,j)$ 是否存在遮蔽胶带。
- 操作一：对四个格子进行涂色操作，前提是所涂格子并未被遮蔽胶带覆盖。
- 操作二：对四个格子进行覆盖操作，将对应位置的 $b_{i,j}$ 置为 $1$ 表示存在遮蔽胶带。
操作完成后，遍历整个矩阵输出所有 $a_{i,j}$ 的值即可。（若没有颜色就是 $0$）
时间复杂度：$O(q+nm)$
T2 寒冬暖炉（stove）¶
知识点：贪心
因为客人在的时刻是零零散散的，所以就会存在一些无客人的时间间隔，而要想使炉子运行总时间最短，那么我们应尽可能地在合适的时刻及时关闭炉子，避免在无客人时造成炉子浪费，即尽可能做到只有有客人在时炉子才开着。
而在下一次来客人时再打开炉子是需要消耗火柴的，而火柴数量又有限，所以有时我们可能需要保持炉子运行（即使此时无客人）。
当第一位客人前来时我们必须消耗一根火柴打开炉子，但如果一直保持运行到最后一名客人走显然是不理智的。我们需要尽可能的避免较长时间无客人间隔运行炉子，此时我们就可在当前客人走时关闭炉子，在下一名客人来时再开炉子。即每多一根火柴，我们就可尽可能的避免一个无客间隔浪费。
综上分析，我们可以分别计算各无客间隔时长（共 $n−1$ 个无客间隔），然后优先依靠炉子关开避免较大无客间隔期间的浪费。
时间复杂度：$O(n\log{n})$
参考代码
int ans = a[n] - a[1] + 1; // 全程时长
for (int i = 1; i < n; i++)
{
b[i] = a[i + 1] - a[i] - 1; // 分别计算各无客间隔时长
}
sort(b + 1, b + n, greater<int>()); // 对各无客间隔时长排序
for (int i = 1; i <= k - 1; i++) // 去掉 k - 1 个较大的间隔
{
ans -= b[i];
}
cout << ans;
T3 方格染色（color）¶
知识点：二分，贡献法。
子任务 $1,2$
定义 $\text{color}[i][j]$ 表示 $(i,j)$ 的颜色。按照题目描述的染色过程去实现即可。
时间复杂度：$O(n^2)$。
首先格子有 $n^2$ 个，但不同的数值最多只有 $2n$ 个。因此需要考虑每个数值如果能作为 $\max$ 对答案的贡献是多少。
我们注意到，对于任意格子 $(i,j)$，其中 $(i,j\geq 2)$。由于染色过程具有 “最大值传递“ 的性质，有
如果先将两个序列分别求前缀 $\max$ 的更新，使得
那么网格中每个格子的颜色就可以直接写成
考虑枚举序列 $a$，即遍历行：$2\sim n$。那么就要思考：每一行的 $a_i$ 会对自己所在列产生什么贡献。
显然 $b$ 序列中 小于或等于 $a_i$ 的都可以视作是 $a_i$ 要产生贡献。而由于前缀 $\max$ 数组单调不下降。因此可以使用 upper_bound() 找到刚好大于 $a_i$ 的位置记作 $j$，则 $a_i$ 在 $2\sim j-1$ 列都是 $a_i$ 当最大值。此时答案直接更新 cnt[a[i]] += j - 2 即可。
这样考虑完以后在考虑序列 $b$ 的每个元素对答案的贡献，同理 $a$ 序列中 小于 $b_i$ 的都可以视作是 $b_i$ 要产生贡献。这部分使用 lower_bound() 求出即可。
第一行和第一列单独处理，最终时间复杂度为 $O(n\log{n})$。
参考代码
map<int, int> cnt;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], cnt[a[i]]++;
for (int i = 1; i <= n; i++)
cin >> b[i], cnt[b[i]]++;
cnt[b[1]]--;
for (int i = 2; i <= n; i++)
{
a[i] = max(a[i - 1], a[i]);
b[i] = max(b[i - 1], b[i]);
}
for (int i = 2; i <= n; i++)
{
int j = upper_bound(b + 2, b + n + 1, a[i]) - b;
cnt[a[i]] += j - 2;
}
for (int i = 2; i <= n; i++)
{
int j = lower_bound(a + 2, a + n + 1, b[i]) - a;
cnt[b[i]] += j - 2;
}
// 最后遍历 map 找一下答案即可
T4 画展（art）¶
知识点：贪心，排序。
关于画框
- 画框越大越好（可容纳更多画）。
- 实际安放时，可将画框按尺寸从大到小使用。
关于画
- 一旦确定“要用哪些画”（一个集合），它们的排列顺序就被唯一确定：
- 从左到右按价值升序排列；
- 若价值相同，则按尺寸从小到大排（反过来会出问题）。
子任务1
- 先决定要用哪些画共 $2^n$ 种。
- 画与画框的顺序就确定了（按前述规则）。
- 逐一判断每幅画能否装入对应的画框。
子任务2
- 先把所有画和画框按“将被使用的顺序”各自排序好。
- 若“第 $i$ 幅画”装进了“第 $j$ 个画框”并被展出，那么其右侧只会出现编号更大的画和编号更大的画框。
-
因而可做二维 dp。
-
定义：$\text{dp}[i][j]$：使用前 $i$ 幅画与前 $j$ 个画框时，可展出画的最大数量。
- 令
$$ temp=\max(\text{dp}[i-1][j],\ \text{dp}[i][j-1]). $$
- 转移：
- 若画 $i$ 装不进框 $j$：$\text{dp}[i][j]=temp$。
- 若装得进：$\text{dp}[i][j]=\max\big(temp,\ \text{dp}[i-1][j-1]+1\big)$。
- 复杂度 $O(nm)$。
子任务3
- 将画框按尺寸从大到小、画按价值从高到低处理。
- 依次尝试：若当前画能装进当前最大的可用画框，就装入并计数；否则跳过不合适的画或继续考虑更小的框。
- 复杂度 $O(n\log n + m\log m)$，可满分。
贪心解释
如果先尝试小价值的画匹配小尺寸的画框，会出现错误。例如：
- 画 $1$：大小 $100$，价值 $50$。
- 画 $2$：大小 $1$，价值 $99$。
- 画 $3$：大小 $2$，价值 $100$。
- 画框 $1$：尺寸 $2$。
- 画框 $2$：尺寸 $100$。
如果按照从左往右的方式匹配（画找画框），会出现：
- 第一幅画直接装进画框 $2$ 从而导致后续无法展出画 $2$ 和 $3$。
而如果从右往左考虑，则首先画 $3$ 装进框 $2$，画 $2$ 装进框 $1$，得到最大展出数：$2$。
为啥“从右往左、先大后小”能避免这个坑？
把顺序反过来（右往左）后，你面对的是一个随步缩小的“价值上界”问题：
- 初始价值上界为 $+\infty$；
- 处理当前（较大的）画框时，从“尺寸能放、且价值 $\le$ 上界”的集合里挑价值最大的；
- 选完把上界变为这个价值；下一步（更小的画框）只能选“不超过这个上界”的里边的最大值——这恰好保证了左到右的非降，同时尽量把价值“顶到上界”，不浪费位置。
一句话：
- 左→右很难“为未来留出空间”，因为你不知道后面上界会是多少；
- 右→左则把“未来”的限制变成了一个当前可见的上界，于是“取不超过上界的最大值”就成了正确贪心。
参考代码
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
int n, m, c[N];
struct picture
{
int s, v;
} a[N];
bool cmp(picture a, picture b)
{
if (a.v != b.v) return a.v > b.v;
return a.s > b.s;
}
int main()
{
freopen("art.in", "r", stdin);
freopen("art.out", "w", stdout);
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i].s >> a[i].v;
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= m; i++) cin >> c[i];
sort(c + 1, c + m + 1, greater<int>());
int ans = 0;
for (int i = 1, j = 1; i <= n && j <= m; i++)
{
if (c[j] >= a[i].s)
{
ans++;
j++;
}
}
cout << ans;
return 0;
}