|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 柿子饼同学 于 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[a].emplace_back(c, 1);
- e[b + 1].emplace_back(c, -1);
- s[1]++, s[a]--;
- s[b + 1]++, s[n + 1]--;
- }
- for(int i = 1; i <= m + 1; i++){
- for(auto x : e[i]) Add(x);
- s[i] += s[i - 1];
- ans = max(ans, res + (s[i] > 0));
- }
复制代码
D - P3084 [USACO13OPEN] Photo G
看到这样的题是 01 填数的要会想到设计状态, 然后对于每个 i 求出转移的区间转移即可, 用单调队列
也想到差分约束, 先用前缀和把区间的条件转换为点的约束, 然后跑 spfa
“恰好”等价于“不少于并且不大于”。- #include <bits/stdc++.h>
- using namespace std;
- const int N = 2e5 + 5;
- int n, m;
- // l[i] 表示不包括 i 的区间中, l 的最大值
- // r[i] 表示包括 i 的区间中, l 的最小值
- // 为什么这样设计? 因为不能遗漏任何一个区间
- // l[i], r[i] 单调不降, 于是用单调队列维护
- int l[N], r[N], f[N];
- struct Queue {
- int q[N], h = 1, t = 1;
- void Push(int x) {
- while (h <= t && f[q[t]] <= f[x]) t--;
- q[++t] = x;
- }
- int Front() { return f[q[h]]; }
- bool Cut(int x) {
- while (h <= t && q[h] < l[x]) 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] = i - 1;
- }
- for (int i = 1; i <= m; i++) {
- int a, b;
- cin >> a >> b;
- l[b + 1] = max(l[b + 1], a);
- r[b] = min(r[b], a - 1);
- }
- for (int i = n; i >= 0; i--) {
- r[i] = min(r[i + 1], r[i]);
- }
- for (int i = 1; i <= n + 1; i++) {
- l[i] = max(l[i], l[i - 1]);
- }
- int j = 1;
- for (int i = 1; i <= n + 1; i++) {
- for (; j <= r[i] && j <= n; j++) q.Push(j);
- if (q.Cut(i))
- f[i] = -1;
- else
- f[i] = q.Front() + (i != n + 1);
- }
- cout << f[n + 1];
- return 0;
- }
复制代码
|
|