2021 MINIEYE杯 杭电多校4
2021/8/3 23:10:09
本文主要是介绍2021 MINIEYE杯 杭电多校4,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1008 Lawn of the Dead
原题链接
题意:在一张n x m的网格中,左上角是(1,1),右下角是(n,n)。从(1,1)开始,只能往下或往右移动,在某些点上有地雷,不能移动到有地雷的点上,且不能移动出边界,求可能到达的点的数量。
分析:当某个点的上方和左边都不可到达时,该点不可到达,并会对该点下方和右边的点造成影响。考虑从上往下对每行排序后的地雷进行处理。对于每个地雷(x,y),找到(x-1,y+1)开始的从左往右不可到达的范围,那么x这行的这个范围也不可到达。对一行可以用线段树实现区间查询和覆盖,只需用滚动数组维护该行和上一行的线段树即可。每一行处理完后查询该行可以到达的点数,累加后得到答案。
#include <bits/stdc++.h> using namespace std; #define ls(x) (x << 1) #define rs(x) (x << 1 | 1) const int inf = 0x3f3f3f3f; const int N = 100005; int n, m, k; int tr[2][N << 2], lz[2][N << 2]; long long ans; vector<int> v[N]; void push_down(int f, int x, int l, int r, int mid) { if (lz[f][x] == -1) return ; tr[f][ls(x)] = (mid - l + 1) * lz[f][x]; tr[f][rs(x)] = (r - mid) * lz[f][x]; lz[f][ls(x)] = lz[f][rs(x)] = lz[f][x]; lz[f][x] = -1; } void update(int f, int x, int l, int r, int L, int R, int v) { if (L <= l && R >= r) { tr[f][x] = (r - l + 1) * v; lz[f][x] = v; return ; } int mid = (l + r) >> 1; push_down(f, x, l, r, mid); if (L <= mid) update(f, ls(x), l, mid, L, R, v); if (R > mid) update(f, rs(x), mid + 1, r, L, R, v); tr[f][x] = tr[f][ls(x)] + tr[f][rs(x)]; } int query(int f, int x, int l, int r, int L, int R) { if (!tr[f][x]) return inf; if (l == r) return l; int mid = (l + r) >> 1; push_down(f, x, l, r, mid); if (L <= l && R >= r) { if (tr[f][ls(x)]) return query(f, ls(x), l, mid, L, R); else return query(f, rs(x), mid + 1, r, L, R); } else { if (R <= mid) return query(f, ls(x), l, mid, L, R); else if (L > mid) return query(f, rs(x), mid + 1, r, L, R); else return min(query(f, ls(x), l, mid, L, R), query(f, rs(x), mid + 1, r, L, R)); } } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d%d%d", &n, &m, &k); for (int i = 0; i <= n; i++) v[i].clear(); memset(tr, 0, sizeof tr); memset(lz, -1, sizeof lz); while (k--) { int x, y; scanf("%d%d", &x, &y); v[x].push_back(y); } ans = 0; update(0, 1, 1, m, 1, 1, 1); for (int i = 1; i <= n; i++) { sort(v[i].begin(), v[i].end()); int l = 0; for (auto &j : v[i]) { if (l + 1 <= j - 1) { int pos = query((i & 1) ^ 1, 1, 1, m, l + 1, j - 1); if (pos != inf) update(i & 1, 1, 1, m, pos, j - 1, 1); } l = j; } if (l + 1 <= m) { int pos = query((i & 1) ^ 1, 1, 1, m, l + 1, m); if (pos != inf) update(i & 1, 1, 1, m, pos, m, 1); } ans += tr[i & 1][1]; update((i & 1) ^ 1, 1, 1, m, 1, m, 0); } printf("%lld\n", ans); } return 0; }
这篇关于2021 MINIEYE杯 杭电多校4的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?