鱼C论坛

 找回密码
 立即注册
查看: 2264|回复: 11

[心之碎片] - 20240823模拟赛

[复制链接]
发表于 2024-8-23 19:02:13 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

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, 扫一遍得到答案

  1. cin >> n >> m;
  2. for(int i = 1; i <= n; i++){
  3.     int a, b, c;
  4.     cin >> a >> b >> c;
  5.     e[a].emplace_back(c, 1);
  6.     e[b + 1].emplace_back(c, -1);
  7.     s[1]++, s[a]--;
  8.     s[b + 1]++, s[n + 1]--;
  9. }

  10. for(int i = 1; i <= m + 1; i++){
  11.     for(auto x : e[i]) Add(x);
  12.     s[i] += s[i - 1];
  13.     ans = max(ans, res + (s[i] > 0));
  14. }
复制代码


D - P3084 [USACO13OPEN] Photo G

看到这样的题是 01 填数的要会想到设计状态, 然后对于每个 i 求出转移的区间转移即可, 用单调队列
也想到差分约束, 先用前缀和把区间的条件转换为点的约束, 然后跑 spfa

“恰好”等价于“不少于并且不大于”
  1. #include <bits/stdc++.h>
  2. using namespace std;

  3. const int N = 2e5 + 5;

  4. int n, m;

  5. // l[i] 表示不包括 i 的区间中, l 的最大值
  6. // r[i] 表示包括 i 的区间中, l 的最小值
  7. // 为什么这样设计? 因为不能遗漏任何一个区间
  8. // l[i], r[i] 单调不降, 于是用单调队列维护

  9. int l[N], r[N], f[N];

  10. struct Queue {
  11.     int q[N], h = 1, t = 1;

  12.     void Push(int x) {
  13.         while (h <= t && f[q[t]] <= f[x]) t--;
  14.         q[++t] = x;
  15.     }

  16.     int Front() { return f[q[h]]; }

  17.     bool Cut(int x) {
  18.         while (h <= t && q[h] < l[x]) h++;
  19.         return (h > t);
  20.     }
  21. } q;

  22. int main() {
  23.     ios::sync_with_stdio(0);
  24.     cin.tie(0);

  25.     freopen("photo.in", "r", stdin);
  26.     freopen("photo.out", "w", stdout);

  27.     cin >> n >> m;
  28.     for (int i = 1; i <= n + 1; i++) {
  29.         r[i] = i - 1;
  30.     }
  31.     for (int i = 1; i <= m; i++) {
  32.         int a, b;
  33.         cin >> a >> b;
  34.         l[b + 1] = max(l[b + 1], a);
  35.         r[b] = min(r[b], a - 1);
  36.     }

  37.     for (int i = n; i >= 0; i--) {
  38.         r[i] = min(r[i + 1], r[i]);
  39.     }
  40.     for (int i = 1; i <= n + 1; i++) {
  41.         l[i] = max(l[i], l[i - 1]);
  42.     }

  43.     int j = 1;
  44.     for (int i = 1; i <= n + 1; i++) {
  45.         for (; j <= r[i] && j <= n; j++) q.Push(j);

  46.         if (q.Cut(i))
  47.             f[i] = -1;
  48.         else
  49.             f[i] = q.Front() + (i != n + 1);
  50.     }

  51.     cout << f[n + 1];

  52.     return 0;
  53. }
复制代码

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-8-23 19:02:31 | 显示全部楼层
好的,我来帮助总结这次模拟赛中的一些要点和解题思路。

### A - 粉刷匠
**题目要求**:给定 n 行操作,每行包含区间 l, r 和颜色 c。计算每列中颜色出现的次数,最终找出色彩最丰富的列。

**解题思路**:
1. **方法一**:枚举每种颜色,把所有相同颜色的操作归为一类,然后逐步计算各列颜色的覆盖次数。
2. **方法二**:枚举每一列,使用类似扫描线的方法处理,通过 +1 和 -1 的操作来统计每列的颜色变化。

**代码框架**:
  1. cin >> n >> m;
  2. for (int i = 1; i <= n; ++i) {
  3.     int l, r, c;
  4.     cin >> l >> r >> c;
  5.     // 对每种颜色操作进行记录
  6.     // e.emplace_back(c, 1);
  7.     // e.emplace_back(c, -1);
  8.     // 类似扫描线的处理方法
  9.     // s++, s--;
  10. }
  11. for (int i = 1; i <= m; ++i) {
  12.     // 计算每列的最大颜色种类数
  13. }
复制代码


### B - 询问第 k 小/大
**解题思路**:
- **二分查找**:可以借助二分查找找到第 k 小/大的元素,通过构建 0000011111 这样的架构。
- **腐蚀性思维**:利用数据特性和二分的思想来进行优化处理,逐层缩小搜索空间。

### D - 区间填 0/1
**解题思路**:
1. **状态转移**:设计 `fi` 表示前 `i` 个满足要求的情况,通过 `i` 填 1 或 0 的转移来进行优化。
2. **单调队列**:用单调队列来确保每个区间的转移是正确和高效的。
3. **差分约束**:使用前缀和技巧,把区间约束转换为点的约束,结合 SPFA 算法进行求解。

**代码示例**:
  1. #include <iostream>
  2. #include <vector>
  3. #include <deque>
  4. using namespace std;

  5. const int N = 2e5 + 5;
  6. int n, m;

  7. // 状态定义
  8. int l, r, f;

  9. struct Queue {
  10.     deque<int> q;
  11.     void Push(int x) {
  12.         while (!q.empty() & q.back() >= x) q.pop_back();
  13.         q.push_back(x);
  14.     }
  15.     void Pop(int x) {
  16.         if (!q.empty() && q.front() == x) q.pop_front();
  17.     }
  18. };

  19. // 主函数
  20. int main() {
  21.     cin >> n >> m;
  22.     for (int i = 1; i <= m; ++i) {
  23.         int a, b;
  24.         cin >> a >> b;
  25.         l = max(l, a);
  26.         r = min(r, b);
  27.     }
  28.     for (int i = n; i >= 0; --i) {
  29.         // 状态转移和单调队列处理
  30.     }
  31.     return 0;
  32. }
复制代码


总结:
- **二分查找**能有效解决第 k 大/小问题。
- **单调队列**和**差分约束**可以帮助处理区间问题。
- 遇到特定类型的问题(如`01填数`和`区间填色`),要善于利用结构特性和数据结构来简化计算。

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-23 21:24:29 | 显示全部楼层

回帖奖励 +3 鱼币

Fishc 无处不在
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-24 09:12:56 | 显示全部楼层

回帖奖励 +3 鱼币

厉害厉害
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-24 09:53:25 | 显示全部楼层

回帖奖励 +3 鱼币

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-8-29 09:22:00 | 显示全部楼层

回帖奖励 +3 鱼币

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-8-31 16:39:24 | 显示全部楼层

回帖奖励 +3 鱼币

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-9-1 09:56:34 | 显示全部楼层

回帖奖励 +3 鱼币

看看
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-9-3 16:40:11 | 显示全部楼层

回帖奖励 +3 鱼币

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-9-4 15:47:05 | 显示全部楼层

回帖奖励 +3 鱼币

谢谢
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-9-14 17:40:44 | 显示全部楼层

回帖奖励 +3 鱼币

谢谢楼主的鱼币
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-10-7 22:49:57 | 显示全部楼层

回帖奖励 +3 鱼币

谢谢楼主的鱼币
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-4-27 17:09

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表