Atcoder Beginner Contest 401 D ~ G
D - Logical Filling
由于 \(X\) 保证非空，所以一定不存在不合法的情况比如 oo。
首先所有 o 旁边的两个空一定是 .，然后就剩下一些连续的问号段。容易发现如果有一段问号 \([l, r)\)，那么它对 o 的贡献最多是 \(\frac{r - l + 1}{2}\)。
如果所有的问号段都取最大贡献才能满足 \(K\) 个 o 的限制，那么每个奇数长问号段就都是 \(o.o.o.o\) 的形式，因为问号段的左右两边不可能是 o。而偶数长问号段因为有 o.o. 和 .o.o 两种方式选择，所以都是问号。
如果所有问号段不需要都取最大贡献，那么直接原样输出即可。
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define initrand srand((unsigned)time(0))
#define random(x) ((LL)rand() * rand() % (x))
#define eb emplace_back
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
int n, k;
string s;
int main() {
cin >> n >> k >> s;
for (int i = 0; i < n; i ++)
if (s[i] == 'o') {
if (i) s[i - 1] = '.';
if (i + 1 < n) s[i + 1] = '.';
}
int d = count(s.begin(), s.end(), 'o');
if (d == k) {
for (int i = 0; i < n; i ++)
if (s[i] == '?') cout << '.';
else cout << s[i];
return 0;
}
for (int i = 0; i < n; i ++) {
int j = i;
while (j < n && s[j] == '?') j ++;
d += (j - i + 1) / 2;
i = j;
}
if (d == k) {
for (int i = 0; i < n; i ++) {
if (s[i] != '?') continue;
int j = i;
while (j < n && s[j] == '?') j ++;
if ((j - i) & 1)
for (int k = i; k < j; k ++)
s[k] = (k - i) & 1 ? '.' : 'o';
i = j;
}
}
cout << s << endl;
return 0;
}
E - Reachable Set
真比 D 简单吧。
考虑只能要 \(1 \sim k\)，那么 \(>k\) 的点就要被删掉。所以相当于问你将 \(>k\) 的点删掉后剩下的点是否能够组成一个连通块。
\(DSU\) 合并一下就做完了，具体看代码吧。
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define initrand srand((unsigned)time(0))
#define random(x) ((LL)rand() * rand() % (x))
#define eb emplace_back
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 300010;
int n, m;
int degs[N];
vector<int> G1[N], G2[N];
struct DSU {
int fa[N], sz[N];
DSU (int n) {
for (int i = 1; i <= n; i ++)
fa[i] = i, sz[i] = 1;
}
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y], fa[y] = x;
}
};
int main() {
n = read(), m = read();
while (m --) {
int a = read(), b = read();
G1[a].push_back(b); G2[b].push_back(a);
}
DSU dsu(n);
int ans = 0;
for (int u = 1; u <= n; u ++) {
if (degs[u] > 0) ans --;
for (auto v : G2[u]) dsu.merge(v, u);
for (auto v : G1[u])
if (degs[v] == 0)
degs[v] ++, ans ++;
if (dsu.sz[dsu.find(1)] == u) printf("%d\n", ans);
else puts("-1");
}
return 0;
}
F - Add One Edge 3
先考虑 \(f(i, j)\) 怎么求，显然应该是第一棵树和第二棵树的直径与从 \(i\) 最远能走的距离加从 \(j\) 能走的最远距离 \(+ 1\)。
形式化的，我们设 \(D1\) 为第一棵树的直径，\(D2\) 为第二棵树的直径，\(H1(i)\) 为第一棵树上的点 \(i\) 能走到的最远距离，\(H2(i)\) 为第二棵树上的点 \(i\) 能走到的最远距离。则 \(f(i, j) = \max(D1, D2, H1(i) + H2(j) + 1)\)。
\(D1\) 和 \(D2\) 是人都会求，所以考虑怎么求 \(H\)。我们以第一棵树举例，第二棵树与第一棵树的求法一模一样。
以 \(1\) 为根，\(G(u)\) 表示 \(u\) 往子树走能到达的最远距离，\(F(u)\) 表示 \(u\) 往上走能到的最远距离，那么 \(H(u) = \max(G(u), F(u))\)。
对于 \(G(u)\) 显然从子树转移过来即可，而对于 \(F(u)\)，我们可以从 \(F(fa) + 1\) 转移过来，也可以从 \(G2(fa) + 1\) 转移过来，其中 \(G2(fa)\) 表示 \(fa\) 往子树走的次长路。
这样你就会求 \(H1\) 和 \(H2\)，然后考虑 \(\sum f(i, j)\) 怎么求。
你会发现 \(D1, D2\) 都是定值，所以设 \(D = \max(D1, D2)\)，然后将 \(H2\) 排序。则对于一个 \(H1(i)\)，我们一定能将在 \(H2\) 中找到一个划分点使得前半部分 \(H1(i) + H2(j) + 1 < D\)，后半部分大于 \(D\)。换言之，只需要在 \(H2\) 中二分 \(D - H1(i) - 1\) 即可。
然后由于你要计算一段的 \(H2\) 值，所以前缀和优化一下就好了，还是蛮简单的（？）。
代码看起来很长其实一大部分都是重复的内容（我写的太狗屎了），而且这个方法好像也不是最优方法？看哥哥的代码是只有一个 BFS 这就有点抽象了。
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define initrand srand((unsigned)time(0))
#define random(x) ((LL)rand() * rand() % (x))
#define eb emplace_back
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
#define int long long
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 200010;
int n1, n2;
vector<int> G1[N], G2[N];
int f1[N], f2[N], g1[N], g2[N], F1[N], F2[N], s[N];
void dfs1(int u, int fa) {
g1[u] = 0;
for (auto v : G1[u]) {
if (v == fa) continue;
dfs1(v, u);
g1[u] = max(g1[u], g1[v] + 1);
}
}
void dfs2(int u, int fa) {
g2[u] = 0;
for (auto v : G2[u]) {
if (v == fa) continue;
dfs2(v, u);
g2[u] = max(g2[u], g2[v] + 1);
}
}
void dfs3(int u, int fa) {
int maxd = 0, smaxd = 0;
for (auto v : G1[u]) {
if (v == fa) continue;
int d = g1[v] + 1;
if (d > maxd) smaxd = maxd, maxd = d;
else if (d > smaxd) smaxd = d;
}
for (auto v : G1[u]) {
if (v == fa) continue;
int use = maxd;
if (use == g1[v] + 1) use = smaxd;
f1[v] = max(f1[u] + 1, use + 1);
dfs3(v, u);
}
}
void dfs4(int u, int fa) {
int maxd = 0, smaxd = 0;
for (auto v : G2[u]) {
if (v == fa) continue;
int d = g2[v] + 1;
if (d > maxd) smaxd = maxd, maxd = d;
else if (d > smaxd) smaxd = d;
}
for (auto v : G2[u]) {
if (v == fa) continue;
int use = maxd;
if (use == g2[v] + 1) use = smaxd;
f2[v] = max(f2[u] + 1, use + 1);
dfs4(v, u);
}
}
signed main() {
n1 = read();
for (int i = 1; i < n1; i ++) {
int a = read(), b = read();
G1[a].push_back(b); G1[b].push_back(a);
}
n2 = read();
for (int i = 1; i < n2; i ++) {
int a = read(), b = read();
G2[a].push_back(b); G2[b].push_back(a);
}
dfs1(1, -1); dfs2(1, -1);
dfs3(1, -1); dfs4(1, -1);
int d1 = 0, d2 = 0;
for (int i = 1; i <= n1; i ++) {
F1[i] = max(g1[i], f1[i]);
d1 = max(d1, F1[i]);
}
for (int i = 1; i <= n2; i ++) {
F2[i] = max(g2[i], f2[i]);
d2 = max(d2, F2[i]);
}
int D = max(d1, d2), ans = 0;
sort(F2 + 1, F2 + 1 + n2);
for (int i = 1; i <= n2; i ++) s[i] = s[i - 1] + F2[i];
for (int i = 1; i <= n1; i ++) {
int X = D - F1[i] - 1;
int j = lower_bound(F2 + 1, F2 + 1 + n2, X) - F2;
ans += (j - 1) * D + s[n2] - s[j - 1] + (F1[i] + 1) * (n2 - j + 1);
}
cout << ans << endl;
return 0;
}
G - Push Simultaneously
过一会儿再补。喵喵
看了下，可以考虑先二分答案出某个 \(X\)，然后就问题变成了判定是否存在人与按钮的连边方式使得任意距离不超过 \(X\)。
显然可以通过网络流解决。具体来说，我们只保留边权小于等于 \(X\) 的边，如果这些边能够形成完备匹配，则说明合法。二分图匹配问题可以通过求最大流解决。
代码等我写完再放。
写完了，然后 RE 了半小时才过。只能说看哥哥的代码总能学到一些奇怪的语法。
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 610, M = 1000010;
int n;
struct Point {double x, y; } p1[N], p2[N];
struct MaxFlow {
int s, t;
int h[N], e[M], ne[M], now[N], d[N], w[M], idx;
queue<int> q;
MaxFlow(int _s, int _t) {
memset(h, -1, sizeof h); idx = 0;
s = _s, t = _t;
}
void addedge(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}
bool bfs() {
while (!q.empty()) q.pop();
memset(d, 0, sizeof d);
q.push(s); d[s] = 1, now[s] = h[s];
while (q.size()) {
int u = q.front(); q.pop();
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (w[i] && !d[v]) {
d[v] = d[u] + 1, now[v] = h[v];
q.push(v);
if (v == t) return true;
}
}
}
return false;
}
int dinic(int u, int flow) {
if (u == t) return flow;
int rest = flow, k;
for (int i = now[u]; ~i && rest; i = ne[i]) {
int v = e[i]; now[u] = i;
if (w[i] && d[v] == d[u] + 1) {
k = dinic(v, min(rest, w[i]));
if (!k) d[v] = 0;
rest -= k, w[i] -= k, w[i ^ 1] += k;
}
}
return flow - rest;
}
int maxflow() {
int maxflow = 0, flow = 0;
while (bfs())
if (flow = dinic(s, INF)) maxflow += flow;
return maxflow;
}
};
inline double dist(Point a, Point b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++) cin >> p1[i].x >> p1[i].y;
for (int i = 1; i <= n; i ++) cin >> p2[i].x >> p2[i].y;
vector<tuple<double, int, int>> edges;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
edges.push_back({dist(p1[i], p2[j]), i, j});
sort(edges.begin(), edges.end());
int l = 0, r = n * n - 1, s = n * 2 + 1, t = n * 2 + 2;
while (l < r) {
int mid = l + r >> 1;
MaxFlow mf(s, t);
for (int i = 1; i <= n; i ++) {
mf.addedge(s, i, 1);
mf.addedge(n + i, t, 1);
}
for (int i = 0; i <= mid; i ++) {
int u = get<1>(edges[i]), v = get<2>(edges[i]);
mf.addedge(u, v + n, 1);
}
if (mf.maxflow() == n) r = mid;
else l = mid + 1;
}
printf("%.10lf\n", get<0>(edges[l]));
return 0;
}
浙公网安备 33010602011771号