ComWin’ round 11部分题解

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;

}

巴特西

ComWin’ round 11部分题解

最新文章

热门文章