The First Test
死亡回放 比赛时间线
- 5:32 开始打开题目写
T1 史莱姆排队（因为没有看到提高组只用写 3-6 所以浪费了太多时间 QAQ - 约 5:40
T1 史莱姆排队样例 & 自测样例过了，开始T2 锻炼身体的路径 - 约 6:00
T2 锻炼身体的路径的 bfs 版本写完，发现第二个样例错了 - 约 6:05 意识到 bfs 可以反复横跳，不满足题意，果断开始写 dfs
- 约 6:30 写完 dfs 版本并过掉两个样例，开始写
T3 开会正片开始 T3 开会第一眼就想到二分，但当时脑子抽了完全忘记浮点数二分，误以为T1 史莱姆排队和T2 锻炼身体的路径为签到题，于是就开始打暴力 全场最错误的选择！！！- 约 7:00 以极大的时间复杂度过掉
T3 开会的样例，开始写T4 Cow Lineup T4 Cow Lineup第一眼还是想到二分，二分一个最长段长度- 约 7:10 发现这个二分似乎不可做，果断开始 dfs 暴力枚举这个点删不删
- 约 7:20 打完了暴力，样例过不了
- 约 7:25 改正了暴力，过了样例，开始思考如何把编号都离散化
- 约 7:30 发现在需要去重的情况下离散化会把我 CPU 干烧（寄 ，果断开始写
T5 高楼大厦 - 看见
T5 高楼大厦马上想到 lxk 教我写过这个题！ %%% 马上写出代码 - 约 7:50 写完代码并且过了样例 & 自测样例，开始写
T6 星际联盟 - 本来想的是并查集，但总感觉不太对，仔细读题后发现一定要是在一个环上才是盟友，果断开始打暴力
- 约 8:20 艰难的写完了暴力，发现 dfs 计算点的数量的时候会反复横跳！ 于是加上了点的标记
- 约 8:40 艰难的加完了点标记，可以过样例了
- 后面就全在想
T4 Cow Lineup的离散化到底怎么写 —— 写不出来 QAQ
死因分析 错误点分析
- 没有仔细读题！太着急了，浪费了半个小时
- 没有去想
T3 开会正解！只想着打暴力骗分了
死亡证明 成绩
遗书 各题错误思路 & 正解
T1 开会
在 x 轴上有 n 个人，，每个人有一个移动速度 v_1,v_2,v_3...v_n，现在需要找一个地方让大家聚到一起开会，问你最少需要多少时间才可以让所有人都到达同一个点
错误思路
-
当时根本没有想到实数二分是可以做的，去打暴力是真的失策了
-
直接从 1 开始暴力枚举时间是否可行
这我为什么想不到二分捏时间复杂度直接高到飞起#include<bits/stdc++.h> using namespace std; const int maxn = 60005; int v[maxn],x[maxn],n,l = 1e9,r = 0; double ans = 1e18; int main() { scanf("%d",&n); for (int i = 1;i <= n;i ++) scanf("%d",&x[i]); for (int i = 1;i <= n;i ++) scanf("%d",&v[i]); for (int i = 1;i <= n;i ++) l = min(l,x[i]), r = max(r,x[i]); for (double i = l;i <= r;i += 0.00001) { // 超级暴力！ double sum = 0; for (int j = 1;j <= n;j ++) sum = max(sum,double(fabs(i - x[j]) * 1.0 / v[j])); ans = min(ans,sum); } printf("%.5f",ans); return 0; }
正解
-
二分时间 t ，
check的时候用 [l,r] 记录当前所有人都可以走到的共同区间 -
从 1 到 n 扫一遍，如果这个人走不到这个共同区间，直接
return false;， 否则更新公共区间 -
时间复杂度 O(n\log n)
#include<bits/stdc++.h> #define double long double using namespace std; const int maxn = 60005; const double eps = 1e-7; int x[maxn],v[maxn],n; double ans; bool check(double t) { double l = x[1] - t * v[1], r = x[1] + t * v[1]; for (int i = 2;i <= n;i ++) { double nl = x[i] - t * v[i], nr = x[i] + t * v[i]; if (l - nr > eps || nl - r > eps) return false; l = max(nl,l), r = min(nr,r); if (l - r > eps) return false; } return true; } int main() { scanf("%d",&n); for (int i = 1;i <= n;i ++) scanf("%d",&x[i]); for (int i = 1;i <= n;i ++) scanf("%d",&v[i]); double l = 0, r = 1e9; while (r - l > eps) { // 这就是实数二分 QAQ double mid = (l + r) / 2.0; if (check(mid)) ans = mid, r = mid; else l = mid; } printf("%.5Lf",ans); return 0; }
T2 Cow Lineup
农夫约翰的 N(1 <= N <= 100,000) 只奶牛排成了一队，每只牛都用编上了一个“品种编号”，该编号为范围 0...1,000,000,000 的整数。品种相同的奶牛有相同的编号，也就是可能有多头奶牛是相同的"品种编号"。
约翰觉得如果连续排列的一段奶牛有相同的品种编号的话，奶牛们看起来会更具有威猛。为了创造这样的连续段，约翰最多能选出k种品种的奶牛，并把他们全部从队列中赶走。
请帮助约翰计算这样做能得到的由相同品种编号的牛构成的连续段的长度最大是多少？
错误思路
-
没有去把这个题转换为一个更可做的模型
-
不会去重 + 离散化
一生之敌 -
dfs 枚举每种牛是否要被 ban ，纯暴力
#include<bits/stdc++.h> using namespace std; const int maxn = 100005; int n,k,a[maxn],ans = 0,tag[maxn],m; bool vis[maxn]; void dfs(int tot,int pos) { // cout << pos << ' ' << tot << '\n'; if (pos > m) { int lst = 1, res = -1, cnt = 0; for (int i = 1;i <= n;i ++) if (!vis[a[i]]) { lst = i; break; } for (int i = lst + 1;i <= n;i ++) { if (vis[a[i]]) continue; if (a[i] == a[lst]) cnt ++, res = max(res,cnt); else cnt = 1; lst = i; } ans = max(ans,res); return ; } dfs(tot,pos + 1); if (tot < k) { vis[tag[pos]] = true; dfs(tot + 1,pos + 1); vis[tag[pos]] = false; } } int main() { scanf("%d%d",&n,&k); for (int i = 1;i <= n;i ++) scanf("%d",&a[i]); for (int i = 1;i <= n;i ++) tag[i] = a[i]; sort(tag + 1,tag + n + 1); int tot = 1; for (int i = 2;i <= n;i ++) if (tag[i] != tag[i - 1]) tag[++ tot] = tag[i]; m = tot; // for (int i = 1;i <= m;i ++) cout << tag[i] << ' '; dfs(0,1); printf("%d",ans); return 0; } /* 9 1 2 7 3 7 7 3 7 5 7 */
正解
-
这玩意在洛谷上竟然有原题
-
有一种人类智慧做法：使用双指针去维护某个区间一共有多少种动物 & 每种动物有多少个
-
ans就动态更新 -
太智慧了#include<bits/stdc++.h> using namespace std; const int maxn = 100005; int n,k,a[maxn],ans; map<int,int> mp; int main() { scanf("%d%d",&n,&k); for (int i = 1;i <= n;i ++) scanf("%d",&a[i]); int l = 1, r = 1, tot = 0; while (l <= n && r <= n) { while (tot <= k + 1 && r <= n) { mp[a[r]] ++; if (mp[a[r]] == 1) tot ++; ans = max(ans,mp[a[r]]); r ++; } mp[a[l]] --; tot -= (mp[a[l]] == 0); l ++; } printf("%d",ans); return 0; }
T3 高楼大厦
作为Z省的老板，你计划开发一片产业园区，这片产业园区有 n 幢大厦，从左到右进行排列，每个大厦的初始层数为 A_i 。现在你计划盖高一些楼层，一共有 m 种施工计划，每一种计划包含一个区间 [l_i,r_i]，表示将这个区间内的所有大厦全部加盖 a 层。但是出于经济原因，你只能选择其中的 k 种施工计划。现在你想让施工之后，最大化最低的那幢大厦的楼层数。
错误思路
-
估计是我离正解最近的一份代码 -
二分最小高度，
check的时候扫一遍所有点，不断寻找区间往上加，直到该点高度满足当前的最小要求，如果区间用完了还不能解决问题就return false;#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 2e5 + 5; ll n,m,k,b,h[maxn],ans,add[maxn]; pair<ll,ll> p[maxn]; bool vis[maxn]; bool check(ll x) { for (int i = 1;i <= n;i ++) add[i] ^= add[i]; for (int i = 1;i <= m;i ++) vis[i] ^= vis[i]; ll tot = 0; for (int i = 1;i <= n;i ++) { add[i] += add[i - 1]; // chafen ! while (add[i] + h[i] < x) { bool ok = true; for (int j = 1;j <= m;j ++) if (p[j].first <= i && i <= p[j].second && !vis[j]) { add[i] += b, add[p[j].second + 1] -= b; vis[j] = true; tot ++; ok = false; break; } if (tot > k || (ok && add[i] + h[i] < x)) return false; } } return true; } int main() { ll T; scanf("%lld",&T); while (T --) { scanf("%lld%d%d%d",&n,&m,&k,&b); ll l = 2e9,r = 1e9; for (int i = 1;i <= n;i ++) { scanf("%lld",&h[i]); l = min(l,h[i]); } for (int i = 1;i <= m;i ++) scanf("%lld%d",&p[i].first,&p[i].second); while (l <= r) { ll mid = (l + r) >> 1; if (check(mid)) ans = mid, l = mid + 1; else r = mid - 1; } printf("%lld\n",ans); } return 0; } /* 1 3 3 2 114514 1 3 2 1 1 1 3 3 3 */
正解
-
需要加一个小贪心：每次要选择覆盖范围最广的去加，万一后面也可以一起用呢
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 2e5 + 5; ll n,m,k,b,h[maxn],ans,add[maxn]; pair<ll,ll> p[maxn]; bool vis[maxn]; bool check(ll x) { for (int i = 1;i <= n;i ++) add[i] ^= add[i]; for (int i = 1;i <= m;i ++) vis[i] ^= vis[i]; ll tot = 0; for (int i = 1;i <= n;i ++) { add[i] += add[i - 1]; // chafen ! while (add[i] + h[i] < x) { int mx = -1, pos; // 选择大的那个 for (int j = 1;j <= m;j ++) if (p[j].first <= i && i <= p[j].second && !vis[j] && p[j].second > mx) mx = p[j].second, pos = j; if (mx == -1 || tot == k) return false; vis[pos] = true, add[i] += b, add[p[pos].second + 1] -= b, tot ++; } } return true; } int main() { ll T; scanf("%lld",&T); while (T --) { scanf("%lld%d%d%d",&n,&m,&k,&b); ll l = 2e9,r = 1e9; for (int i = 1;i <= n;i ++) { scanf("%lld",&h[i]); l = min(l,h[i]); } for (int i = 1;i <= m;i ++) scanf("%lld%d",&p[i].first,&p[i].second); while (l <= r) { ll mid = (l + r) >> 1; if (check(mid)) ans = mid, l = mid + 1; else r = mid - 1; } printf("%lld\n",ans); } return 0; } /* 1 3 3 2 114514 1 3 2 1 1 1 3 3 3 */
T4 星际联盟
在遥远的S星系中一共有N个星球，编号为1…N。其中的一些星球决定组成联盟，以方便相互间的交流。
但是，组成联盟的首要条件就是交通条件。初始时，在这N个星球间有M条太空隧道。每条太空隧道连接两个星球，使得它们能够相互到达。若两个星球属于同一个联盟，则必须存在一条环形线路经过这两个星球，即两个星球间存在两条没有公共隧道的路径。
为了壮大联盟的队伍，这些星球将建设P条新的太空隧道。这P条新隧道将按顺序依次建成。一条新轨道建成后，可能会使一些星球属于同一个联盟。你的任务是计算出，在一条新隧道建设完毕后，判断这条新轨道连接的两个星球是否属于同一个联盟，如果属于同一个联盟就计算出这个联盟中有多少个星球。
错误思路
-
先建图，每次询问时 dfs 从其中一个点出发，如果可以回到原点就把自己携带的个数加上，且必须经过另一个点
-
还要加一些神奇特判
#include<bits/stdc++.h> #define mk make_pair using namespace std; const int maxn = 2000005; vector<pair<int,int> > mp[maxn]; bool vis[maxn << 1],vi[maxn]; int n,m,p,s,tot,res; bool flag; void addEdge(int u,int v) { mp[u].push_back(mk(v,++ tot)); mp[v].push_back(mk(u,tot)); } void dfs(int u,int sum) { if (flag) return ; // cout << u << ' ' << sum << '\n'; if (u == s) { res += sum, flag = true; for (int i = 1;i <= n;i ++) if (!vi[i]) flag = false; return ; } if (!vi[u]) sum ++; vi[u] = true; for (auto v : mp[u]) { // cout << v.first << '\n'; int id = v.second, x = v.first; if (vis[id]) continue; vis[id] = true; dfs(x,sum); vis[id] = false; } } int main() { scanf("%d%d%d",&n,&m,&p); for (int i = 1,u,v;i <= m;i ++) { scanf("%d%d",&u,&v); addEdge(u,v); } for (int i = 1,u,v;i <= p;i ++) { scanf("%d%d",&u,&v); for (int i = 1;i <= tot;i ++) vis[i] = false; for (int i = 1;i <= n;i ++) vi[i] = false; addEdge(u,v); res = 1, s = u,vi[u] = true,flag = false; for (auto x : mp[u]) { vis[x.second] = true; dfs(x.first, 0); vis[x.second] = false; } if (res != 1 && vi[v]) printf("%d\n",res); else printf("No\n"); } return 0; }
40分暴力解
- tarjan寻找连通块 + 缩点
正解
-
参考题解：星球联盟
-
用并查集维护，离线处理，先用初始的边和询问所加的边建一棵树，把加上就成环的边不要加入 ，记录下来，询问也同理。然后这时有可能是好几棵树，就加一些边把它们并到一棵树里（因为所有可加入的边都已加入，所以不会对结果产生影响）。dfs求出关于树的信息，dep和size，然后再将初始时没有加入的边加入。查询时，遇到的一条边如果是已经加入树的边，就输出No，如果没加入树，就查询并输出
#include <bits/stdc++.h> using namespace std; const int maxn = 200005; struct edge { int x, y; } e[maxn], qe[maxn]; int f[maxn], sz[maxn], dep[maxn], fa[maxn]; int n, m, p, cnt, tot, num[maxn]; vector<int> mp[maxn]; void addEdge(int x, int y) { mp[x].push_back(y); mp[y].push_back(x); } int find(int x) { if (f[x] == x) return x; f[x] = find(f[x]); return f[x]; } void dfs(int x) { dep[x] = dep[fa[x]] + 1; for (auto v : mp[x]) if (v != fa[x]) fa[v] = x, dfs(v); } void solve(int x, int y) { while (x != y) { if (dep[x] < dep[y]) swap(x, y); int f1 = find(x), f2 = find(fa[x]); if (f1 != f2) f[f1] = f2, sz[f2] += sz[f1]; x = f2; } } int main() { cnt = tot = 0; scanf("%d%d%d", &n, &m, &p); for (int i = 1; i <= n; i ++) f[i] = i; for (int i = 1, x, y; i <= m; i ++) { scanf("%d%d", &x, &y); int f1 = find(x), f2 = find(y); if (f1 != f2) f[f2] = f1, addEdge(x, y); else e[++cnt].x = x, e[cnt].y = y; } for (int i = 1, x, y; i <= p; i ++) { scanf("%d%d", &x, &y); int f1 = find(x), f2 = find(y); if (f1 != f2) f[f2] = f1, addEdge(x, y); else qe[++tot].x = x, qe[tot].y = y, num[i] = tot; } for (int i = 2; i <= n; i ++) { int f1 = find(i), f2 = find(1); if (f1 != f2) addEdge(i, 1), f[f1] = f2; } for (int i = 1; i <= n; i ++) f[i] = i, sz[i] = 1; dfs(1); for (int i = 1; i <= cnt; i ++) solve(e[i].x, e[i].y); for (int i = 1; i <= p; i ++) if (!num[i]) printf("No\n"); else { solve(qe[num[i]].x, qe[num[i]].y); printf("%d\n", sz[find(qe[num[i]].x)]); } return 0; }
葬礼 总结
- 决策错的太过分了，签到题的分都没拿到
- 下一次能一眼想到正解的一定先去写正解，实在实现困难才去打暴力
投胎转世 目标
- 拿上签到题的分，其他题部分分好拿的必须拿，但一定要先想正解！
