当前位置:网站首页>【luogu CF1534F2】Falling Sand (Hard Version)(性质)(dfs)(线段树 / 单调队列 / 贪心)
【luogu CF1534F2】Falling Sand (Hard Version)(性质)(dfs)(线段树 / 单调队列 / 贪心)
2022-08-10 19:01:00 【SSL_TJH】
Falling Sand (Hard Version)
题目链接:luogu CF1534F2
题目大意
给你一个网格,每个位置可能有沙子。
如果你操作了一个沙子,它会下落,并且操作它下落过程中上下左右相邻的沙子。
然后问你最少要自己操作多少个沙子才会使得所有沙子都被操作。
思路
首先一些贪心,就是肯定是点一列的最上面,然后能影响的肯定是一个区间。(就算中间隔开了你点中间还是会影响被隔开的,所以可以算不影响)
(然后被影响的也是一个区间)
考虑模拟这个过程,那就是如果一个沙子会影响到另一个沙子,就连边。
然后你就可以通过 dfs,得到一个沙子被操作的区间。
(找左边界就从左到右搜索,否则从右到左搜索得到右边界)
然后剩下就是一个区间覆盖问题,随便用啥都行。
代码
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f3f3f3f3f
#define bh(x, y) (((x) - 1) * n + (y))
using namespace std;
const int N = 4e5 + 100;
int n, m, L[N], R[N], nd[N], Rs[N], sta[N], f[N];
char c;
vector <int> a[N], up[N];
struct node {
int to, nxt;
}e[N << 3];
int le[N], KK;
bool in[N];
void add(int x, int y) {
e[++KK] = (node){
y, le[x]}; le[x] = KK;}
void dfsl(int now, int col) {
L[now] = col; in[now] = 1;
for (int i = le[now]; i; i = e[i].nxt) if (!in[e[i].to]) dfsl(e[i].to, col);
}
void dfsr(int now, int col) {
R[now] = col; in[now] = 1;
for (int i = le[now]; i; i = e[i].nxt) if (!in[e[i].to]) dfsr(e[i].to, col);
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
c = getchar(); while (c != '#' && c != '.') c = getchar();
if (c == '#') a[j].push_back(n - i + 1);
}
for (int i = 1; i <= m; i++) reverse(a[i].begin(), a[i].end());
for (int i = 1; i <= m; i++) scanf("%d", &nd[i]);
for (int i = 1; i <= m; i++) {
if (!a[i].size()) continue;
for (int j = 1; j < a[i].size(); j++) {
add(bh(i, a[i][j]), bh(i, a[i][j - 1]));
if (a[i][j - 1] + 1 == a[i][j]) add(bh(i, a[i][j - 1]), bh(i, a[i][j]));
}
for (int op = 1; op >= -1; op--) {
if (op == 0) continue;
if (!a[i + op].size()) continue;
int now = a[i + op].size() - 1; while (now >= 0 && a[i + op][now] > a[i][a[i].size() - 1]) now--;
int nowx = a[i].size() - 1;
for (int j = a[i][a[i].size() - 1]; j >= 1; j--) {
if (nowx > 0 && a[i][nowx - 1] == j) nowx--;
if (now >= 0 && a[i + op][now] == j) add(bh(i, a[i][nowx]), bh(i + op, a[i + op][now])), now--;
}
}
}
for (int i = 1; i <= m; i++)
if (a[i].size() && !in[bh(i, a[i][a[i].size() - 1])])
dfsl(bh(i, a[i][a[i].size() - 1]), i);
memset(in, 0, sizeof(in));
for (int i = m; i >= 1; i--)
if (a[i].size() && !in[bh(i, a[i][a[i].size() - 1])])
dfsr(bh(i, a[i][a[i].size() - 1]), i);
for (int i = 1; i <= m; i++)
for (int j = 0; j < nd[i]; j++)
Rs[R[bh(i, a[i][j])]] = max(Rs[R[bh(i, a[i][j])]], L[bh(i, a[i][j])]);
int l = 1, r = 1;
for (int i = 1; i <= m; i++) {
f[i] = f[sta[l]] + 1;
while (l <= r && f[sta[r]] >= f[i]) r--;
sta[++r] = i;
while (l <= r && sta[l] < Rs[i]) l++;
}
printf("%d", f[sta[l]]);
return 0;
}
边栏推荐
- The Biotin-PEG3-Br/acid/NHS ester/alcohol/amine collection that everyone wants to share
- FPGA:从0开始(安装开发环境)加破解
- RS-485多主机通信的组网方式评估
- Keras deep learning combat (17) - image segmentation using U-Net architecture
- stm32中的CAN通讯列表模式配置解析与源码
- 网络拓扑管理
- Today's bug, click on the bug that the Windows dynamic wallpaper disappears in the win10 taskbar, and no solution has been found yet.
- 【深度学习前沿应用】图像风格迁移
- 基于 RocksDB 实现高可靠、低时延的 MQTT 数据持久化
- flex&bison系列第一章:flex Hello World
猜你喜欢
第14章_MySQL事务日志
Consul Introduction and Installation
Optimizing Bloom Filter: Challenges, Solutions, and Comparisons论文总结
弘玑Cyclone与风变科技达成战略合作:优势互补聚焦数字化人才培养
「POJ 3666」Making the Grade 题解(两种做法)
【C#】WCF和TCP消息通信练习,实现群聊功能
ARouter使用自定义注解处理器,自动生成跳转Activity的代码,避免手动填写和管理path
DefaultSelectStrategy NIOEventLoop执行策略
FPGA:从0开始(安装开发环境)加破解
多种深度模型实现手写字母MNIST的识别(CNN,RNN,DNN,逻辑回归,CRNN,LSTM/Bi-LSTM,GRU/Bi-GRU)
随机推荐
GBASE 8s 高可用RSS集群搭建
宝塔部署flask项目
端口探测详解
服务器上行带宽和下行带宽指的是什么
[Teach you how to do mini-games] How to lay out the hands of Dou Dizhu?See what the UP master of the 250,000 fan game area has to say
西安Biotin-PEG8-IA_IA-PEG8-生物素供应商
瑞吉外卖学习笔记4
2022杭电多校七 Black Magic (签到)
About npm/cnpm/npx/pnpm and yarn
幕维三维动画——港珠澳大桥沉管安装三维动画实况
【C#】WCF和TCP消息通信练习,实现群聊功能
redis.exceptions.DataError: Invalid input of type: ‘dict‘. Convert to a byte, string or number first
【LeetCode】42、接雨水
mysql 中大小写问题
补坑简单图论题
【自然语言处理】【向量表示】PairSupCon:用于句子表示的成对监督对比学习
FEMRL: A Framework for Large-Scale Privacy-Preserving Linkage of Patients’ Electronic Health Rec论文总结
状态压缩dp蒙德里安的梦想
优化是一种习惯●出发点是'站在靠近临界'的地方
Keras深度学习实战(17)——使用U-Net架构进行图像分割