2020牛客暑期多校训练营（第三场）

https://ac.nowcoder.com/acm/contest/5668

A - Clam and Fish

 

题意：有 n 天，每天可能 有/无🐟，有/无蚯蚓。在有🐟的时候可以直接拿一条🐟，有鱼饵时可以拿一个鱼饵。如果有鱼儿可以钓一条鱼。每天只能进行一个操作，问最终最多有几条鱼。

显然有鱼直接拿🐟，什么都没有可以用存的鱼饵钓鱼，其它时候可能拿鱼饵也可能钓鱼。

但是鱼饵不能拿太多，否则就没有时间钓鱼了。

先在所有有鱼饵的日子里拿鱼饵，看多出几个，这里的一半日子可以用来钓鱼。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e6 + 10;
int T;
int n;
char s[N];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        scanf("%s", s);
        int ans = 0, c1 = 0, c2 = 0;
        for (int t = 0; t < n; t++) {
            if (s[t] == '0') {
                if (c1 > 0) {
                    ans++;
                    c1--;
                }
            }
            else if (s[t] == '1') {
                c1++;
            }
            else if (s[t] == '2') {
                ans++;
            }
            else {
                ans++;
            }
        }
        ans += c1 / 2;
        printf("%d\n", ans);
    }
    return 0;
}

 

C - Operation Love

 

题意：如下图为右手，左手与之对称。给定20个点，可能是左手或右手旋转得到，问是左手还是右手。

如图，暴力判断长度找到 A，B，C，再判断 这两个向量的叉乘，右手从AB到AC逆时针旋转，叉积为正。

注意eps大小。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e6 + 10;
const double eps = 1e-5;
int T;
double x[100], y[100];
bool same(double a, double b) {
    return abs(a - b) < eps;
}
double dist(int i, int j) {
    return sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
}
int main() {
    scanf("%d", &T);
    while (T--) {
        for (int i = 1; i <= 20; i++) {
            scanf("%lf%lf", &x[i], &y[i]);
        }
        bool fg = 0;
        int a, b, c;
        for (int i = 1; i <= 20 && !fg; i++) {
            for (int j = i + 1; j <= 20; j++) {
                if (same(dist(i, j), 9.0)) {
                    fg = 1;
                    a = i, b = j;
                    break;
                }
            }
        }
        fg = 0;
        for (int i = 1; i <= 20; i++) {
            if (same(dist(b, i), 8.0)) {
                c = i;
                fg = 1;
                break;
            }
        }
        if (!fg) {
            swap(a, b);
            for (int i = 1; i <= 20; i++) {
                if (same(dist(b, i), 8.0)) {
                    c = i;
                    break;
                }
            }
        }
        double ax = x[c] - x[a], ay = y[c] - y[a];
        double bx = x[b] - x[a], by = y[b] - y[a];
        double ans = ax * by - ay * bx;
        if (ans < 0)puts("right");
        else puts("left");
    }
    return 0;
}

 

F - Fraction Construction Problem

 

题意：给定 a，b。求一组 c，d，e，f，使得 $\frac{c}{d}-\frac{e}{f}=\frac{a}{b}$，且 $d,f<b$，所有数都是正整数。

当 a，b 不互质时，可以直接构造出一组解。 a / gcd + b / gcd, b / gcd, 1, 1。

当 a，b 互质时，如果 b 只有一种质因子，则无解。否则可以得到两个互质的因子，乘积为 b。扩展欧几里得解一个二元不定方程得到 e，f。

注意扩欧得到的是ax+by=1的解，应该直接乘c，不能取模，否则就不是原方程的解了（太蠢了）。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e6 + 10;
const double eps = 1e-5;
int T;
ll a, b;
int prime[N];     //记录质数
bool is_prime[N];
int vis[N];      //记录最小质因子
int euler_sieve(int n) {
    int cnt = 0;
    memset(vis, 0, sizeof(vis));
    memset(prime, 0, sizeof(prime));
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) { vis[i] = i; prime[cnt++] = i; is_prime[i] = true; }    //vis[]记录x的最小质因子
        for (int j = 0; j < cnt; j++) {
            if (i*prime[j] > n)  break;
            vis[i*prime[j]] = prime[j];              //vis[]记录x的最小质因子
            if (i%prime[j] == 0)
                break;
        }
    }
    return cnt;
}
 
void ex_gcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1;
        y = 0;
    }
    else {
        ex_gcd(b, a%b, x, y);
        ll temp = x;
        x = y;
        y = temp - a / b * y;
    }
}
void cal(ll a, ll& x, ll b, ll& y, ll c) {
    ex_gcd(a, b, x, y);
    y = -y;
    ll cnt = (-y) / a + 1;
    y += cnt * a;
    x += cnt * b;
    x *= c;
    y *= c;
}
ll gcd(ll a, ll b) {
    if (a < b)swap(a, b);
    return b == 0 ? a : gcd(b, a%b);
}
int main() {
    scanf("%d", &T);
    euler_sieve(2000000);
    is_prime[1] = 1;
    while (T--) {
        scanf("%lld%lld", &a, &b);
        ll m = gcd(a, b);
        if (m != 1) {
            printf("%lld %lld %d %d\n", a / m + b / m, b / m, 1, 1);
            continue;
        }
        if (is_prime[b]) {
            puts("-1 -1 -1 -1");
            continue;
        }
        ll td = vis[b], d = vis[b], tb = b / d;
        while (tb%td == 0) {
            tb /= td;
            d *= td;
        }
        ll f = b / d;
        if (d > f)swap(d, f);
        if (f == b) {
            puts("-1 -1 -1 -1");
            continue;
        }
        ll c, e;
        cal(f, c, d, e, a);
        printf("%lld %lld %lld %lld\n", c, d, e, f);
    }
    return 0;
}

 

E - Two Matchings

 

题意：给定一个数组，要求重新排列，全错位且 $p_{p_i}=i$。一次变换得到变换后的数组，代价为新旧数组每个位置上值差的绝对值之和。要求给出两个完全不同的变换，代价之和最小。

可以发现一次变换就是选出 n/2 对不相交的数每对内部交换位置。排序后，代价就是每一对的后一个减前一个。

dp

$dp[i]$ 表示前 i 个，最小代价。

因为要两个变换，所以每个数与两个数配对，有一种朴素的配对方式，即每个数和前一个以及后一个配对，这样求出的总代价就是这个数列的 2*（最大值-最小值）。

并且还能发现其它的配对方式总是把一个数列拆成几部分，对于每一部分内部都采用上面这种朴素的配对方式。

所以只要知道怎么把数列分成几块。

考虑第 i 个作为一块中的最后一个，枚举块的左端 j 。则代价为 $\min_{i-j\ge 4}(dp[j]+2(a[i]-a[j]))$，再维护一个 $mn=dp[j]-2a[j]$，每次只要取最小 mn 即可。

这种dp就是枚举最后一块大小时的套路，很常用。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e6 + 10;
const double eps = 1e-5;
int T;
int n;
ll a[N];
ll dp[N];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
        sort(a + 1, a + n + 1);
        dp[2] = 0ll;
        ll mn = inf;
        dp[4] = 2 * (a[4] - a[1]);
        for (int i = 6; i <= n; i += 2) {
            dp[i] = min((a[i] - a[1]) * 2, mn + 2 * a[i]);
            mn = min(mn, dp[i - 2] - 2 * a[i - 1]);
        }
        printf("%lld\n", dp[n]);
    }
    return 0;
}

 

G - Operating on a Graph

 

题意：给定一张无向图，初始时每点颜色为 i，每次操作选一种颜色，把所有与这种颜色有连接的颜色都变成这种颜色。问最终每点的颜色。

链表+并查集+bfs

这里的染色和普通染色不一样，由于初始时每点颜色都不同，所有每次染色都是染出一团，和缩点有些类似。每次染色时发挥作用的其实只有这团最外一圈。所以只要链表维护每种颜色最外的一层即可。染色时并查集合并，且颜色 v 的最外层变成 u 的最外层，加入 u 的链表中。

由于一种颜色如果变成其它颜色了，就永远不会再用它操作了，所以只有当这种颜色是并查集的根时才操作。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e6 + 10;
const double eps = 1e-5;
int T;
int n, m, q;
vector<int>G[N];
list<int>ls[N];
int par[N], vis[N];
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void uni(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y)return;
    par[x] = y;
    ls[y].splice(ls[y].end(), ls[x]);
}
void bfs(int s) {
    if (find(s) != s)return;
    int n = ls[s].size();
    for (int i = 0; i < n; i++) {
        int u = ls[s].front();
        if (vis[u])continue;
        vis[u] = 1;
        for (int v : G[u]) {
            if (vis[v])continue;
            uni(v, s);
        }
        ls[s].pop_front();
    }
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            G[i].clear();
            ls[i].clear();
            ls[i].push_back(i);
            vis[i] = 0;
        }
        for (int i = 0; i < m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        scanf("%d", &q);
        while (q--) {
            int x;
            scanf("%d", &x);
            bfs(x);
        }
        for (int i = 0; i < n; i++)printf("%d%s", find(i), i == n - 1 ? "\n" : " ");
    }
    return 0;
}

 

D - Points Construction Problem

 

题意：给定 n，m。无限的二维平面上的整点，初始全是白色，选 n 个点涂成黑色，满足恰有 m 对点相邻，且颜色不同。一点与四周四个点相邻。

构造

参考 https://blog.csdn.net/weixin_45750972/article/details/107443283

每点最多贡献4，再多了就是NO，否则是YES。

如果m >= 2 * n + 2，可以用一些散点和一条直线凑出。

如上图，对一个L形的构造，从下向上填充，总的贡献是和原来的L形一样的，就是长+宽，所以可以先得到L形的长和宽，两者相同时面积最大，再填充多出来的黑点。

所以还有一种NO的形式，就是黑点太多，多于这个L形最大容量了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e6 + 10;
int T;
int n, m;
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        if ((m & 1) || m > 4 * n || m * m < 16 * n)puts("No");
        else {
            puts("Yes");
            if (m >= 2 * n + 2) {
                int x = (4 * n + 2 - m) / 2, y = n - x;
                for (int i = 1; i <= x; i++)printf("1 %d\n", i);
                for (int i = 1; i <= y; i++)printf("3 %d\n", i * 2);
            }
            else {
                int x = m / 4, y = m / 2 - x;
                for (int i = 1; i <= x; i++)printf("%d 1\n", i);
                for (int i = 2; i <= y; i++)printf("1 %d\n", i);
                int cnt = n - x - y + 1;
                int t = 2;
                while (cnt > 0) {
                    for (int i = 2; i <= y && cnt > 0; i++, cnt--) {
                        printf("%d %d\n", t, i);
                    }
                    t++;
                }
            }
        }
    }
    return 0;
}