当前位置: 首页 > news >正文

2024西安铁一中集训DAY26 ---- 模拟赛(最短路 + 实数域二分 + 线段树 + 并查集(平面图欧拉定理))

文章目录

  • 前言
  • 时间安排与成绩
  • 题解
    • A. 江桥的蓝紫灯(最短路)
    • B. 江桥的破坏行动(实数域二分)
    • C. 江桥的最小值(线段树)
    • D. 江桥的山谷(并查集,平面图欧拉定理)

前言

感觉是做的比较顺的一场?除了最后一题一点都看不懂。。。

时间安排与成绩

  • 7:40 开题
  • 7:40 - 7:50 看完了T1,感觉T1好复杂啊。可能是把一个点的状态拆成多个。数据规模也是不知所以。
  • 7:50 - 8:05 又想了15min T1,感觉还是不会。突然听见有人说T2简单,果断开T2。
  • 8:05 - 8:30 把T2题意读懂了,开始想到了之前ABC的一道G题,以为是维护凸包dp啥的??感觉不是很简单啊。后来一直在想怎么转移,感觉好像不满足最优子结构??想啊想,卡住了。
  • 8:30 - 8:35 再读一遍题,woc,发现我是唐诗,读错题了,题上只让破坏一段啊。那就是在实数上二分一下就行了。
  • 8:35 - 8:45 10min写完了,样例都是一遍过。就先不管了。
  • 8:45 - 8:55 感觉T1还是不太好搞,先开T3!10min把题意读懂了,感觉也不简单。
  • 8:55 - 9:15 去上厕所里,在厕所里想到可以按照 x x x 从大到小离线处理每条信息。然后就是维护一个区间取min,查询区间最大值的东西。这个可以用线段树处理。
  • 9:15 - 9:55 开写。过了编译,测试发现样例都过不去。慌了,重新看了一遍题,发现又看错题了。每个位置上的数都不一样!!!
  • 9:55 - 10:05 想了想我是不是假了。发现把每一组信息的区间取一个交应该就行。然后内部的排序需要按照时间顺序排。
  • 10:05 - 10:25 改了改,把样例都过了。这时还有1h35min,但是我A题还没写。
  • 10:25 - 10:45 一直在想从一个点到另一个点会不会等待时间很短,这样我就可以可行性转移拿到一部分分了。
  • 10:45 - 10:55 想了挺多,但都不严谨。又想到它最多只有三段,就感觉结论很正确了。突然又想到可以在一个点等待因此越早到肯定不劣。那这不是直接跑 d i j k s t r a dijkstra dijkstra 就好了吗?加上刚才推的性质,复杂度正好跑满。直接就写了。
  • 10: 55 - 11:25 写完了,样例都过了。这时去开T4了,感觉还能拿点部分分。
  • 11:25 - 12:00 出乎意料,T4的题意根本看不懂,看来20min才勉强明白,但一定部分分都不会。罚坐。

估分:100 + 100 + 100 + 0 = 300
分数:100 + 100 + 85 + 0 = 285
rk10

题解

A. 江桥的蓝紫灯(最短路)

原题链接
在这里插入图片描述

简要题意:
给你一张 N N N 个点, M M M 条边的图。每个点都有一个初始颜色 c o l i col_i coli,要么是蓝色,要么是紫色。还会给你一个当前颜色剩余持续时间 r i r_i ri。同时有一个颜色变化周期:蓝色持续时间 b i b_i bi 和紫色持续时间 p i p_i pi。某一时刻 t t t 能从 x x x 前往 y y y 当且仅当 t t t 时刻 x x x y y y 颜色相同。从 x x x y y y 的用时为 T x , y T_{x, y} Tx,y,边是双向的。你要从 S S S 到达 T T T,问最小的到达时刻。

1 ≤ N ≤ 1000 , 1 ≤ M ≤ 20000 , 1 ≤ T i , j ≤ 100 , 1 ≤ S , T ≤ N , 1 ≤ r i , b i , p i ≤ 100 1 \leq N \leq 1000,1 \leq M \leq 20000,1 \leq T_{i, j} \leq 100,1 \leq S,T \leq N,1 \leq r_i,b_i,p_i \leq 100 1N10001M200001Ti,j1001S,TN1ri,bi,pi100

分析:

不知道这题为啥评紫?可能是因为原题题意太难理解了??

我们考虑对于到一个点 x x x 的时间肯定越早越好。这是因为由 x x x 到其它点时,把等待时间移到 x x x 上肯定不会让答案变劣。因此我们可以直接跑 d i j k s t r a dijkstra dijkstra:如果当前对顶是 x x x,到它的时刻是 d i s x dis_{x} disx。那么用 d i s x dis_{x} disx 可以求出到他所连边的点 y y y 所需的 最短等待时间,然后直接转移即可。

至于如何计算最短等待时间,有两种做法:

  • 直接枚举 500 500 500 个单位时间,看能否由 x x x 前往 y y y。这个是我考场上猜的性质,即等待时间不会超过 2 2 2 倍周期。想象一下每个点的颜色段最多只有三段,形如 B B B B . . P P P . . B B B BBBB..PPP..BBB BBBB..PPP..BBB P P P P . . . B B . . . P P PPPP...BB...PP PPPP...BB...PP。那么只要有一个位置能对上就能前往,因此匹配不上的次数应该会很小。
  • 还有一种 O ( 1 ) O(1) O(1) 的方法:我们能够直接求出当前时刻 x x x 的颜色 和 y y y 的颜色,以及 x x x 下一次变色所用时间 n x t x nxt_x nxtx y y y 下一次变色所用时间 n x t y nxt_y nxty。如果当前 x x x y y y 颜色相同,那么答案就是当前时刻。否则如果 n x t x ≠ n x t y nxt_x \ne nxt_y nxtx=nxty,那么可以直接算出最早能前往的时刻。否则我们再考虑 从下一次变色到下下一次变色所用的时间,也是类似的方式比较。如果还想等,那么再看 从下下一次变色到下下下一次变色所用的时间,如果又相等,那么无解。这样是 O ( 1 ) O(1) O(1) 的。

时间复杂度就不算了,反正跑不满。
CODE:

// 先到肯定比玩到更优
// 直接跑dj 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int M = 2e4 + 10;
const int INF = 3e7;
int n, m, rest[N], b[N], p[N], St[N];
int head[N], tot;
int S, T, u, v, w, dis[N];
bool vis[N];
char col[N];
struct edge {int v, last, w;
}E[M * 2];
void add(int u, int v, int w) {E[++ tot].v = v;E[tot].w = w;E[tot].last = head[u];head[u] = tot;
}
struct state {int x, w;friend bool operator < (state a, state b) {return a.w > b.w;}
};
priority_queue< state > q;
int get(int T, int x, int y) { // T时刻在x,到y的最小等待时间 int p1 = (St[x] + T) % (b[x] + p[x]);int p2 = (St[y] + T) % (b[y] + p[y]);for(int i = 0; i <= 500; i ++ ) {int t1 = (p1 + i) % (b[x] + p[x]);int t2 = (p2 + i) % (b[y] + p[y]);int f1, f2;if(t1 < b[x]) f1 = 0;else f1 = 1;if(t2 < b[y]) f2 = 0;else f2 = 1;if(f1 == f2) return i;}return INF;
}
int main() {scanf("%d%d", &S, &T);scanf("%d%d", &n, &m);for(int i = 1; i <= n; i ++ ) {scanf("\n%c", &col[i]);scanf("%d%d%d", &rest[i], &b[i], &p[i]);if(col[i] == 'B') St[i] = b[i] - rest[i];else St[i] = b[i] + p[i] - rest[i];}for(int i = 1; i <= m; i ++ ) {scanf("%d%d%d", &u, &v, &w);add(u, v, w); add(v, u, w);}memset(dis, 0x3f, sizeof dis);dis[S] = 0; // 0时刻q.push((state) {S, 0});while(!q.empty()) {state tp = q.top(); q.pop();int x = tp.x;if(vis[x]) continue;vis[x] = 1;for(int i = head[x]; i; i = E[i].last) {int v = E[i].v, w = E[i].w;int tim = get(dis[x], x, v);if(dis[x] + tim + w < dis[v]) {dis[v] = dis[x] + tim + w;q.push((state) {v, dis[v]});}}}if(dis[T] < INF) printf("%d\n", dis[T]);else puts("0");return 0;
}

B. 江桥的破坏行动(实数域二分)

原题链接

在这里插入图片描述

分析:

不知道为啥其他人都被卡精度了。

实际上就是让我们求出包含左端点的连续一段,和包含右端点的连续一段(两端不交,并且长度和小于 n n n),使得两段的数的平均值最大。

实数域上二分一下,然后瞎jb检验一下就行了。
时间复杂度 O ( 二分次数 × n ) O(二分次数 \times n) O(二分次数×n)

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
typedef double db;
const db eps = 1e-7;
int n;
db a[N], b[N], res;
bool check(db x) {for(int i = 1; i <= n; i ++ ) {b[i] = a[i] - x;}int l = n - 2, r = n; db minx = b[n], sl = 0, sr = b[n];for(int i = 1; i <= n - 2; i ++ ) sl += b[i];while(l >= 1) {if(sl + minx <= 0) return 1;sl -= b[l]; l --;sr += b[r - 1]; r --;minx = min(minx, sr);}return 0;
}
int main() {scanf("%d", &n);for(int i = 1; i <= n; i ++ ) {scanf("%lf", &a[i]);}db l = 0, r = 4010.0, mid, res = -1.0;while(r - l > eps) {mid = (l + r) / (db)(2.0);if(check(mid)) res = mid, r = mid;else l = mid;}printf("%.3lf\n", res);return 0;
}

C. 江桥的最小值(线段树)

原题链接
在这里插入图片描述
分析:

好像比正解少个 l o g log log

一条信息 ( l , r , x ) (l, r, x) (l,r,x) 可以提取出 [ l , r ] [l, r] [l,r] 区间的数都大于等于 x x x
考虑一条信息 ( l , r , x ) (l, r, x) (l,r,x)为什么会矛盾:

  1. 这条信息前面的信息使 [ l , r ] [l, r] [l,r] 的数都大于 x x x。那么在这条信息能看出矛盾。
  2. 这条信息前面的信息没有使得 [ l , r ] [l, r] [l,r] 的数都大于 x x x,但是这条信息后面的信息使 [ l , r ] [l, r] [l,r] 的数都大于 x x x。那么在 第一次 [ l , r ] [l, r] [l,r] 都被比 x x x 更大的数覆盖 的那条信息上可以看出矛盾。

注意到会与一条信息矛盾的信息是比它的 x x x 大的信息。那么我们可以想到 将信息按照 x x x 从大到小排序,然后对每条信息处理出 能和它矛盾的最靠前的一条信息的位置与它的位置 更靠后的那个,记作 a n s i ans_i ansi。如果没有和它矛盾的信息,那么 a n s i = I N F ans_i = INF ansi=INF。显然, a n s i ans_i ansi表示 i i i 这条信息的贡献。那么答案就是 m i n i = 1 q a n s i min_{i = 1}^{q}ans_i mini=1qansi

考虑怎样求 a n s i ans_i ansi:我们将信息按照 x x x 分组,并按 x x x 从大到小排序。同一组内按照 t t t 从小到大排序。那么很显然同一组内的 x x x 有可能放的位置是它们区间的交。我们一组一组处理,对当前组的当前这条信息 i i i,假设这组前面信息的交是 [ n l , n r ] [nl, nr] [nl,nr]

  1. [ l i , r i ] [l_i, r_i] [li,ri] [ n l , n r ] [nl, nr] [nl,nr] 取交,设取交后的区间为 [ t l , t r ] [tl, tr] [tl,tr]。如果为空,那么 a n s i = i ans_i = i ansi=i
  2. 如果不为空,在线段树上查询 [ t l , t r ] [tl, tr] [tl,tr] 的最大值,如果最大值为 I N F INF INF,那么表示当前看不出矛盾。否则设最大值是 m x mx mx,那么 a n s i = m a x ( m x , t i ) ans_i = max(mx, t_i) ansi=max(mx,ti)
  3. 将这一组都查询完后,从前往后枚举区间里的元素 j j j,在线段树上将 [ l j , r j ] [l_j, r_j] [lj,rj] 的值与 t j t_j tj m i n min min

注意如果 区间取 m i n min min,区间求和 这样的事情线段树肯定做不到。但是 区间取 m i n min min,区间求 m a x max max 就可以用线段树维护。

时间复杂度 O ( q × l o g 2 n ) O(q \times log_2n) O(q×log2n)

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 3e4 + 10;
const int INF = 1e8;
int n, q, l, r, x;
struct SegmentTree {int l, r, mx, tag;#define l(x) t[x].l#define r(x) t[x].r#define mx(x) t[x].mx#define tag(x) t[x].tag
}t[N * 4];
struct Q {int l, r, x, t, ans;
}qq[M];
bool cmp(Q a, Q b) {return (a.x > b.x || (a.x == b.x && a.t < b.t));
}
void update(int p) {mx(p) = max(mx(p << 1), mx(p << 1 | 1));
}
void build(int p, int l, int r) {l(p) = l, r(p) = r;if(l == r) {mx(p) = INF;return ;} int mid = (l + r >> 1);build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);update(p);
}
void spread(int p) {if(tag(p)) {mx(p << 1) = min(mx(p << 1), tag(p)); mx(p << 1 | 1) = min(mx(p << 1 | 1), tag(p));if(tag(p << 1) != 0) tag(p << 1) = min(tag(p << 1), tag(p)); else tag(p << 1) = tag(p);if(tag(p << 1 | 1) != 0) tag(p << 1 | 1) = min(tag(p << 1 | 1), tag(p));else tag(p << 1 | 1) = tag(p);tag(p) = 0;}
}
void change(int p, int l, int r, int c) {if(l <= l(p) && r >= r(p)) {mx(p) = min(mx(p), c);if(tag(p) == 0) tag(p) = c;else tag(p) = min(tag(p), c);return ;}spread(p);int mid = (l(p) + r(p) >> 1);if(l <= mid) change(p << 1, l, r, c);if(r > mid) change(p << 1 | 1, l, r, c);update(p);
}
int ask(int p, int l, int r) {if(l <= l(p) && r >= r(p)) return mx(p);spread(p);int mid = (l(p) + r(p) >> 1);if(r <= mid) return ask(p << 1, l, r);else if(l > mid) return ask(p << 1 | 1, l, r);else return max(ask(p << 1, l, r), ask(p << 1 | 1, l, r));
}
int main() {scanf("%d%d", &n, &q);for(int i = 1; i <= q; i ++ ) {scanf("%d%d%d", &l, &r, &x);qq[i] = (Q) {l, r, x, i, -1};}build(1, 1, n);sort(qq + 1, qq + q + 1, cmp);for(int i = 1; i <= q; ) {int j = i;while(j <= q && qq[j].x == qq[i].x) j ++;int nl = 1, nr = n;for(int k = i; k < j; k ++ ) {nl = max(nl, qq[k].l);nr = min(nr, qq[k].r); // 求交 if(nl > nr) qq[k].ans = qq[k].t;else {	int c = ask(1, nl, nr);if(c == INF) qq[k].ans = -1; // 有解 else {if(c < qq[k].t) qq[k].ans = qq[k].t;else qq[k].ans = c;}}}for(int k = i; k < j; k ++ ) {change(1, qq[k].l, qq[k].r, qq[k].t);}i = j;}int Ans = INF;for(int i = 1; i <= q; i ++ ) {if(qq[i].ans != -1) Ans = min(Ans, qq[i].ans);}if(Ans == INF) puts("0");else printf("%d\n", Ans);return 0;
}

D. 江桥的山谷(并查集,平面图欧拉定理)

原题链接
在这里插入图片描述
在这里插入图片描述

分析:

前置知识:平面图欧拉定理

平面图:

  1. 平面图概念
    如果能把图G画在平面上,使得除顶点外,边与边之间 没有交叉,称G可以嵌入平面,或称G是可平面图。可平面图G的边不交叉的一种画法,称为G的一种平面嵌入,G的平面嵌入表示的图称为平面图。例如下图所示:

在这里插入图片描述

  1. 一个平面图G把平面分成若干连通片,这些连通片称为G的区域,或G的一个面。G的面组成的集合用Φ表示。如图:
    在这里插入图片描述

平面图欧拉定理:

G G G联通平面图, V V V G G G 的点数, E E E G G G 的边数, F F F G G G 的面数。那么有:

V − E + F = 2 V - E + F = 2 VE+F=2

这就是平面图欧拉定理。

回到本题:

我们考虑按照高度从小到达加入每个位置,一个位置 ( x , y ) (x, y) (x,y)被加入后将它合并到 边联通 的且已经加入的点集中。那么这个点集就是 ( x , y ) (x, y) (x,y) 作为最高位置,相邻方格都比改点集中的点都高的,不一定满足没洞 的区域。那么如果这个区域没洞, ( x , y ) (x, y) (x,y) 的贡献就是点集大小。否则 ( x , y ) (x, y) (x,y) 的贡献是 0 0 0

考虑怎样判断一个点集是否有洞,我们将边联通的被加入的相邻点连边,那么不难发现一个洞就是一个 。然而按照平面图欧拉定理计算出来的面还包括了边长为 2 2 2,形如 ( x − 1 , y − 1 ) , ( x − 1 , y ) , ( x , y − 1 ) , ( x , y ) (x - 1, y - 1),(x - 1, y),(x, y - 1),(x, y) (x1,y1)(x1,y)(x,y1)(x,y) 的正方形。它们也会贡献一个面,但是这个面显然不算 。维护这样的正方形个数,拿算出来的面数减去正方形个数再减 1 1 1 就能得到洞的数量(这里减 1 1 1 是因为还有外部面)。

时间复杂度 O ( N 2 × α ( N 2 ) ) O(N^2 \times α(N^2)) O(N2×α(N2))

CODE:

// 平面图欧拉定理: V - E + F = 2
// 面:边分割出的不连通区域个数 
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 760;
const int M = N * N;
int n, x, bin[M], V[M], E[M], cnt[M]; // 点数,边数, 相邻四联通数 
LL res;
bool bok[N][N];
struct state {int x, y, h;
}mp[M];
int ID(int x, int y) {return (x - 1) * n + y;
}
bool cmp(state a, state b) {return a.h < b.h;
}
int Find(int x) {return x == bin[x] ? x : bin[x] = Find(bin[x]);}
void Merge(int tx, int ty, int x, int y) {int f1 = Find(ID(tx, ty)), f2 = Find(ID(x, y));if(f1 == f2) E[f1] ++;else {bin[f1] = f2;V[f2] += V[f1];E[f2] += E[f1] + 1;cnt[f2] += cnt[f1];}
}
int calc(int x, int y) {int res = 0;if(bok[x][y] && bok[x - 1][y] && bok[x - 1][y - 1] && bok[x][y - 1]) res ++;if(bok[x][y] && bok[x - 1][y] && bok[x - 1][y + 1] && bok[x][y + 1]) res ++;if(bok[x][y] && bok[x + 1][y] && bok[x + 1][y - 1] && bok[x][y - 1]) res ++;if(bok[x][y] && bok[x + 1][y] && bok[x + 1][y + 1] && bok[x][y + 1]) res ++;return res;
}
int main() {scanf("%d", &n);for(int i = 1; i <= n; i ++ ) {for(int j = 1; j <= n; j ++ ) {scanf("%d", &x);mp[ID(i, j)] = (state) {i, j, x};}}sort(mp + 1, mp + n * n + 1, cmp);for(int i = 1; i <= n * n; i ++ ) {int x = mp[i].x, y = mp[i].y; // 插入 x, y 这个点 bin[ID(x, y)] = ID(x, y); V[ID(x, y)] = 1;if(bok[x - 1][y]) Merge(x - 1, y, x, y);if(bok[x + 1][y]) Merge(x + 1, y, x, y);if(bok[x][y - 1]) Merge(x, y - 1, x, y);if(bok[x][y + 1]) Merge(x, y + 1, x, y);bok[x][y] = 1;int f = Find(ID(x, y));cnt[f] += calc(x, y);if(E[f] - V[f] + 2 - 1 - cnt[f] == 0) res += 1LL * V[f];}cout << res << endl;return 0;
}

相关文章:

  • 北京网站建设多少钱?
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • C端与B端 - 第一弹 - 理解和区分C端与B端软件开发
  • vardaccico前端私有库
  • Loadrunner12常用函数
  • MATLAB画散点密度图(附代码和测试数据的压缩包)
  • 14.FineReport制作带筛选按钮的报表和图表
  • Golang | Leetcode Golang题解之第295题数据流的中位数
  • 编程语言「描述符」漫谈——以C++与Rust为例的行为声明与类型描述
  • 【Go - mongodb - bson / schema】
  • mcasttest-tool组播检测工具
  • linux shell(中)
  • Flink中三种模式:YARN Session 模式、YARN Per-Job 模式和 YARN Application 模式提交任务命令
  • XML 和 SimpleXML 入门教程
  • 某视频平台关键 so vm 解释器还原
  • 解析大数据分析行业的现状与前景:全球视角下的中国力量
  • Windows 环境 batch 脚本实现 PG 数据库恢复功能
  • 「前端」从UglifyJSPlugin强制开启css压缩探究webpack插件运行机制
  • 【干货分享】SpringCloud微服务架构分布式组件如何共享session对象
  • 77. Combinations
  • bootstrap创建登录注册页面
  • C# 免费离线人脸识别 2.0 Demo
  • egg(89)--egg之redis的发布和订阅
  • ES10 特性的完整指南
  • JavaScript实现分页效果
  • JAVA之继承和多态
  • JS实现简单的MVC模式开发小游戏
  • mongo索引构建
  • MySQL几个简单SQL的优化
  • React中的“虫洞”——Context
  • Shadow DOM 内部构造及如何构建独立组件
  • SpiderData 2019年2月13日 DApp数据排行榜
  • 从@property说起(二)当我们写下@property (nonatomic, weak) id obj时,我们究竟写了什么...
  • 如何优雅地使用 Sublime Text
  • 数据科学 第 3 章 11 字符串处理
  • 网页视频流m3u8/ts视频下载
  • 微信支付JSAPI,实测!终极方案
  • 异常机制详解
  • 自定义函数
  • 通过调用文摘列表API获取文摘
  • ​决定德拉瓦州地区版图的关键历史事件
  • ​力扣解法汇总1802. 有界数组中指定下标处的最大值
  • # 飞书APP集成平台-数字化落地
  • #systemverilog# 之 event region 和 timeslot 仿真调度(十)高层次视角看仿真调度事件的发生
  • (07)Hive——窗口函数详解
  • (3)Dubbo启动时qos-server can not bind localhost22222错误解决
  • (html转换)StringEscapeUtils类的转义与反转义方法
  • (ZT)北大教授朱青生给学生的一封信:大学,更是一个科学的保证
  • (附源码)springboot太原学院贫困生申请管理系统 毕业设计 101517
  • (附源码)ssm考试题库管理系统 毕业设计 069043
  • (附源码)小程序儿童艺术培训机构教育管理小程序 毕业设计 201740
  • (每日一问)操作系统:常见的 Linux 指令详解
  • (算法)前K大的和
  • (一)【Jmeter】JDK及Jmeter的安装部署及简单配置
  • (转载)CentOS查看系统信息|CentOS查看命令
  • (最完美)小米手机6X的Usb调试模式在哪里打开的流程
  • ****Linux下Mysql的安装和配置