https://vjudge.net/contest/325913#overview
A.Threehouses
题意:一直二维平面上的$n$个点中,前$e$个点落在小岛周围,并且有$p$条边已经连接,问最少花费使得所有点都可以通过一些边到达小岛,两点之间建边的花费为两点间的欧式距离。
思路:根据$kruskal$求最小生成树的方法将前$e$个点合并起来,再将已有$p$条边的两点合并,之后做一次$kruskal$把所有点合并即可。
#include<bits/stdc++.h> using namespace std; const int maxn = 1000 + 10; int fa[maxn]; double x[maxn], y[maxn], dist[maxn][maxn]; int tot; struct node { int u, v; double val; bool operator < (const node &rhs) const { return val < rhs.val; } }edge[maxn * maxn]; int fr(int x) { if(fa[x] == x) return x; return fa[x] = fr(fa[x]); } void uni(int x, int y) { x = fr(x), y = fr(y); if(x != y) fa[x] = y; } void init(int n) { tot = 0; for(int i = 0; i <= n; i++) { fa[i] = i; } } double cal(int i, int j) { double ret = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])); return ret; } int main() { int n, e, p; scanf("%d%d%d", &n, &e, &p); init(n + 1); for(int i = 1; i <= n; i++) { scanf("%lf%lf", &x[i], &y[i]); } for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) { dist[i][j] = dist[j][i] = cal(i, j); node now; now.u = i, now.v = j, now.val = dist[i][j]; edge[tot++] = now; } } sort(edge, edge + tot); for(int i = 1; i <= e; i++) { uni(0, i); } double ans = 0.0; for(int i = 0; i < p; i++) { int u, v; scanf("%d%d", &u, &v); uni(u, v); } for(int i = 0; i < tot; i++) { node now = edge[i]; int fu = fr(now.u), fv = fr(now.v); if(fu != fv) { ans += now.val; fa[fu] = fv; } } printf("%.6f\n", ans); return 0; }
C.Cops ans Robbers
题意:给定图中只有字母点可以设立障碍,问让小偷所在的位置$B$无法达到边界所需设立障碍的最小花费。
思路:先说做法。考虑最小割,对每个点拆点,让$u$到$u^{‘}$的流量为该点对应的值,如果该点不能设立障碍则为$inf$,然后对一个点$u$的相邻点连一条$u^{‘}$到$v$流量为$inf$的边,如果越界那么就连向汇点$T$,流量依旧为$inf$。这样做使得每个格点所在的路径流向$T$的最小割只会被其上的价值最小的点所限制,由于建图时所有相邻格点都有连边,所以从源点出发时不会漏边。
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1000 + 5; const int inf = 0x3f3f3f3f; const LL linf = 0x3f3f3f3f3f3f3f3f; int n, m, c, T; LL val[26]; char mp[N][N]; struct Dinic { static const int maxn = 1e6 + 5; static const int maxm = 4e6 + 5; struct Edge { int u, v, next; LL flow, cap; } edge[maxm]; int head[maxn], level[maxn], cur[maxn], eg; void addedge(int u, int v, LL cap) { edge[eg] = {u, v, head[u], 0, cap}, head[u] = eg++; edge[eg] = {v, u, head[v], 0, 0}, head[v] = eg++; } void init() { eg = 0; memset(head, -1, sizeof head); } bool makeLevel(int s, int t, int n) { for(int i = 0; i < n; i++) level[i] = 0, cur[i] = head[i]; queue<int> q; q.push(s); level[s] = 1; while(!q.empty()) { int u = q.front(); q.pop(); for(int i = head[u]; ~i; i = edge[i].next) { Edge &e = edge[i]; if(e.flow < e.cap && level[e.v] == 0) { level[e.v] = level[u] + 1; if(e.v == t) return 1; q.push(e.v); } } } return 0; } LL findpath(int s, int t, LL limit = linf) { if(s == t || limit == 0) return limit; for(int i = cur[s]; ~i; i = edge[i].next) { cur[edge[i].u] = i; Edge &e = edge[i], &rev = edge[i^1]; if(e.flow < e.cap && level[e.v] == level[s] + 1) { LL flow = findpath(e.v, t, min(limit, e.cap - e.flow)); if(flow > 0) { e.flow += flow; rev.flow -= flow; return flow; } } } return 0; } LL max_flow(int s, int t, int n) { LL res = 0; while(makeLevel(s, t, n)) { LL flow; while((flow = findpath(s, t)) > 0) { if(res >= linf) return res; res += flow; } } return res; } } di; int id(int r, int c) { if(r < 1 || r > n || c < 1 || c > m) return T; return (r - 1) * m + c; } LL getVal(int r, int c) { if(r < 1 || r > n || c < 1 || c > m) return linf; if(mp[r][c] == ‘.‘ || mp[r][c] == ‘B‘) return linf; else return val[mp[r][c] - ‘a‘]; } int main() { scanf("%d%d%d", &m, &n, &c); for(int i = 1; i <= n; i++) scanf("%s", mp[i] + 1); for(int i = 0; i < c; i++) scanf("%lld", &val[i]); T = 2*n*m + 5; di.init(); di.addedge(id(1, 1) + n*m, T, linf); di.addedge(id(1, m) + n*m, T, linf); di.addedge(id(n, 1) + n*m, T, linf); di.addedge(id(n, m) + n*m, T, linf); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { di.addedge(id(i, j), id(i, j) + n*m, getVal(i, j)); if((i == 1 || i == n) && (j == 1 || j == m)) continue; di.addedge(id(i, j) + n*m, id(i+1, j), linf); di.addedge(id(i, j) + n*m, id(i-1, j), linf); di.addedge(id(i, j) + n*m, id(i, j+1), linf); di.addedge(id(i, j) + n*m, id(i, j-1), linf); } } LL ans = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(mp[i][j] == ‘B‘) { ans = di.max_flow(id(i, j), T, T+10); } if(ans) break; } if(ans) break; } printf("%lld\n", ans >= linf ? -1 : ans); return 0; } /* 10 10 1 .......... .......... .......... ...a.a.... ..a.a.a... .a..B.a... ..aaaaa... .......... .......... .......... 1 */
E.Coprime Integers
题意:给定$a,b,c,d$,求$\sum_{i=a}^{b}\sum_{j=c}^{d}[gcd(i,j)=1]$,$[t=1]$表示$t$等于$1$时的值为$1$,否则为$0$。
思路:容斥原理+莫比乌斯反演,考虑$solve(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]$,可以发现$ans=solve(b,d)-solve(a-1,d)-solve(c-1,b)+solve(a-1,c-1)$。接着考虑如何计算$solve(n,m)$
$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]$
$=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{t|i,t|j}u(t)$
$=\sum_{t=1}^{min(n,m)}u(t)\sum_{i=1}^{\left \lfloor \frac{n}{t} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{t} \right \rfloor}1$
$=\sum_{t=1}^{min(n,m)}u(t)\left \lfloor \frac{n}{t} \right \rfloor\left \lfloor \frac{m}{t} \right \rfloor$
预处理莫比乌斯函数前缀和之后整除分块即可在$O(\sqrt n)$复杂度内求出一次$solve$。
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e7 + 5; int p[N / 10], cnt, mu[N]; bool tag[N]; void getPrime() { mu[1] = 1; for(int i = 2; i < N; i++) { if(!tag[i]) { mu[i] = -1; p[cnt++] = i; } for(int j = 0; j < cnt && 1LL * p[j] * i < N; j++) { tag[i * p[j]] = 1; if(i % p[j] == 0) { mu[i * p[j]] = 0; break; } mu[i * p[j]] = -mu[i]; } } for(int i = 1; i < N; i++) mu[i] += mu[i - 1]; } LL solve(LL n, LL m) { LL res = 0; for(LL l = 1, r; l <= min(n, m); l = r + 1) { r = min(n / (n / l), m / (m / l)); res += (mu[r] - mu[l - 1]) * (n / l) * (m / l); } return res; } int main() { getPrime(); LL a, b, c, d; scanf("%lld%lld%lld%lld", &a, &b, &c, &d); printf("%lld\n", solve(b, d) - solve(a - 1, d) - solve(c - 1, b) + solve(a - 1, c - 1)); return 0; }
H.Heir‘s Dilemma
题意:求$L$到$H$之间满足位数是$6$位,且没有某一位是$0$,且能被每一位的数字整除的数的个数。
思路:数据范围很小,暴力枚举每个数$check$是否可行即可。
#include <bits/stdc++.h> using namespace std; bool ck(int x) { bool vis[10]; for(int i = 0; i < 10; i++) vis[i] = false; int xx = x, xxx = x, xxxx = x; while(xxx) { if(xxx % 10 == 0) return false; xxx /= 10; } while(xxxx) { if(vis[xxxx % 10] == true) return false; vis[xxxx % 10] = true; xxxx /= 10; } while(xx) { int now = xx % 10; if(x % now != 0) return false; xx /= 10; } return true; } int main() { int cnt = 0, a, b; cin >> a >> b; for(int i = a; i <= b; i++) cnt += (int)ck(i); cout << cnt << endl; }