23.7.25 杭电暑期多校3部分题解

1005 - Out of Control

题目大意

解题思路

code

1009 - Operation Hope

题意、思路待补

code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
struct lol {int x, id;} e[3][N * 2];
int t, n, a[3][N * 2], hd[3], tl[3], vis[N * 2], q[N * 2], num, f[N * 2], ans;
bool cmp(lol a, lol b) {return a.x < b.x;}
int getx(int x, int p, int k) {if (hd[k] <= tl[k]) {int y = e[k][hd[k]].x, id = e[k][hd[k]].id;if (y < x - p) {++ hd[k]; return id;}y = e[k][tl[k]].x; id = e[k][tl[k]].id;if (y > x + p) {-- tl[k]; return id;}}return 0;
}
void dfs(int x, int p) {vis[x] = 1;for (int k = 0; k < 3; ++ k) while (1) {int y = getx(a[k][x], p, k);if (!y) break;if (y <= n) if (!vis[y + n]) dfs(y + n, p); else;else if (!vis[y - n]) dfs(y - n, p); else;}q[++ num] = x;
}
void dfs1(int x, int p) {vis[x] = 0; f[x] = ans;for (int k = 0; k < 3; ++ k) while (1) {int y = getx(a[k][x <= n ? x + n : x - n], p, k);if (!y) break;if (vis[y]) dfs1(y, p);}
}
int chk(int p) {num = ans = 0;for (int i = 1; i <= 2 * n; ++ i) vis[i] = 0;for (int k = 0; k < 3; ++ k) hd[k] = 1, tl[k] = 2 * n;for (int k = 0; k < 3; ++ k)for (int i = 1; i <= 2 * n; ++ i)if (!vis[i]) dfs(i, p);for (int k = 0; k < 3; ++ k) hd[k] = 1, tl[k] = 2 * n;for (int k = 0; k < 3; ++ k)for (int i = num; i >= 1; -- i)if (vis[q[i]]) ++ ans, dfs1(q[i], p);for (int i = 1; i <= n; ++ i) if (f[i] == f[i + n]) return 0;return 1;
}
int main() {scanf("%d", &t);while (t --) {scanf("%d", &n);for (int i = 1; i <= n; ++ i) {for (int j = 0; j < 3; ++ j)scanf("%d", &a[j][i]),e[j][i].x = a[j][i],e[j][i].id = i;for (int j = 0; j < 3; ++ j)scanf("%d", &a[j][i + n]),e[j][i + n].x = a[j][i + n],e[j][i + n].id = i + n;}for (int k = 0; k < 3; ++ k)sort(e[k] + 1, e[k] + 2 * n + 1, cmp);int l = 0, r = 1e9;while (l <= r) {int mid = (l + r) >> 1;if (chk(mid)) r = mid - 1;else l = mid + 1;}printf("%d\n", l);}return 0;}