[心之碎片] - 20240823模拟赛
本帖最后由 柿子饼同学 于 2024-9-8 20:45 编辑总结与反思
B - 询问第 k 小/大 一定要想到二分, 建立 0000011111 这样的架构
D - 区间填 0/1 类的问题一般想 fi 表示前 i 个已经满足要求, i 填 1 的什么什么, 对于可以转移的区间一定要严谨
另外, 遇到 至多 1 个, 有且仅有之类的要想到差分约束,把区间转换为点(前缀和)
A - 粉刷匠
粉刷匠决定为每一行都画上一笔。 对于 n 行, 每行有 l, r, c 表示 l, r 区间填 c
不同颜色以数字表示。一开始墙面颜色都为0。
刷完之后，他想知道，色彩最丰富的是哪一列。
两种做法, 可以枚举颜色, 把同颜色的操作归为 1 类然后一起算就不会重复
也可以枚举列, 把操作按照类似扫描线的方式 +1, -1, 扫一遍得到答案
cin >> n >> m;
for(int i = 1; i <= n; i++){
int a, b, c;
cin >> a >> b >> c;
e.emplace_back(c, 1);
e.emplace_back(c, -1);
s++, s--;
s++, s--;
}
for(int i = 1; i <= m + 1; i++){
for(auto x : e) Add(x);
s += s;
ans = max(ans, res + (s > 0));
}
D - P3084 Photo G
看到这样的题是 01 填数的要会想到设计状态, 然后对于每个 i 求出转移的区间转移即可, 用单调队列
也想到差分约束, 先用前缀和把区间的条件转换为点的约束, 然后跑 spfa
“恰好”等价于“不少于并且不大于”。#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m;
// l 表示不包括 i 的区间中, l 的最大值
// r 表示包括 i 的区间中, l 的最小值
// 为什么这样设计? 因为不能遗漏任何一个区间
// l, r 单调不降, 于是用单调队列维护
int l, r, f;
struct Queue {
int q, h = 1, t = 1;
void Push(int x) {
while (h <= t && f] <= f) t--;
q[++t] = x;
}
int Front() { return f]; }
bool Cut(int x) {
while (h <= t && q < l) h++;
return (h > t);
}
} q;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("photo.in", "r", stdin);
freopen("photo.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n + 1; i++) {
r = i - 1;
}
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
l = max(l, a);
r = min(r, a - 1);
}
for (int i = n; i >= 0; i--) {
r = min(r, r);
}
for (int i = 1; i <= n + 1; i++) {
l = max(l, l);
}
int j = 1;
for (int i = 1; i <= n + 1; i++) {
for (; j <= r && j <= n; j++) q.Push(j);
if (q.Cut(i))
f = -1;
else
f = q.Front() + (i != n + 1);
}
cout << f;
return 0;
}
好的，我来帮助总结这次模拟赛中的一些要点和解题思路。
### A - 粉刷匠
**题目要求**：给定 n 行操作，每行包含区间 l, r 和颜色 c。计算每列中颜色出现的次数，最终找出色彩最丰富的列。
**解题思路**：
1. **方法一**：枚举每种颜色，把所有相同颜色的操作归为一类，然后逐步计算各列颜色的覆盖次数。
2. **方法二**：枚举每一列，使用类似扫描线的方法处理，通过 +1 和 -1 的操作来统计每列的颜色变化。
**代码框架**：
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
int l, r, c;
cin >> l >> r >> c;
// 对每种颜色操作进行记录
// e.emplace_back(c, 1);
// e.emplace_back(c, -1);
// 类似扫描线的处理方法
// s++, s--;
}
for (int i = 1; i <= m; ++i) {
// 计算每列的最大颜色种类数
}
### B - 询问第 k 小/大
**解题思路**：
- **二分查找**：可以借助二分查找找到第 k 小/大的元素，通过构建 0000011111 这样的架构。
- **腐蚀性思维**：利用数据特性和二分的思想来进行优化处理，逐层缩小搜索空间。
### D - 区间填 0/1
**解题思路**：
1. **状态转移**：设计 `fi` 表示前 `i` 个满足要求的情况，通过 `i` 填 1 或 0 的转移来进行优化。
2. **单调队列**：用单调队列来确保每个区间的转移是正确和高效的。
3. **差分约束**：使用前缀和技巧，把区间约束转换为点的约束，结合 SPFA 算法进行求解。
**代码示例**：
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
const int N = 2e5 + 5;
int n, m;
// 状态定义
int l, r, f;
struct Queue {
deque<int> q;
void Push(int x) {
while (!q.empty() & q.back() >= x) q.pop_back();
q.push_back(x);
}
void Pop(int x) {
if (!q.empty() && q.front() == x) q.pop_front();
}
};
// 主函数
int main() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int a, b;
cin >> a >> b;
l = max(l, a);
r = min(r, b);
}
for (int i = n; i >= 0; --i) {
// 状态转移和单调队列处理
}
return 0;
}
总结：
- **二分查找**能有效解决第 k 大/小问题。
- **单调队列**和**差分约束**可以帮助处理区间问题。
- 遇到特定类型的问题（如`01填数`和`区间填色`），要善于利用结构特性和数据结构来简化计算。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 Fishc 无处不在 厉害厉害 {:7_142:} {:7_142:} {:10_256:}{:10_256:} 看看{:10_254:} {:10_254:} 谢谢 谢谢楼主的鱼币 谢谢楼主的鱼币
页:
[1]