竞赛讨论区 > 【题解】2021牛客暑期多校训练营1
头像
王清楚
发布于 2022-07-21 14:28
+ 关注

【题解】2021牛客暑期多校训练营1

A

设 表示两堆石头数量分别为 时是必胜态（ ） 还是必败态（）。初始有 。因为能到达一种必败态的状态是必胜的，所以对于 的状态，暴力枚举 ，令 。这样的时间复杂度是 ，是过不了的！

这里有一个结论，对于一个 ，只存在至多一个 使得 是必败态，证明如下：

若 都是必败态，因为 可以通过选择 转移到 ，所以 是必胜态，与假设矛盾。

这样时间复杂度就是 ，需要略微卡常。

#include <bits/stdc++.h>
using namespace std;
const int N = 5003;
bool f[N][N];
signed main() {
    int T;
    scanf("%d", &T);
    for (int i = 0; i <= 5000; i++)
        for (int j = 0; j <= 5000; j++)
            if (!f[i][j]) {
                for (int k = 1; k <= 5000 - i; k++)
                    for (int s = 0; s <= 5000 - j; s += k) f[i + k][j + s] |= 1;
                for (int k = 1; k <= 5000 - j; k++)
                    for (int s = 0; s <= 5000 - i; s += k) f[i + s][j + k] |= 1;
            }
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        if (f[n][m])
            puts("Alice");
        else
            puts("Bob");
    }
    return 0;
}

B

如果圆的直径大于 就掉不下去。

把梯形补全成等腰三角形。根据勾股定理可知，斜边

图中有 ，所以
$$

#include <bits/stdc++.h>
using namespace std;
int main() {
    long double r, a, b, h, x, c;
    scanf("%Lf%Lf%Lf%Lf", &r, &a, &b, &h);
    if (a < b)
        swap(a, b);
    if ((r * 2) <= b) {
        puts("Drop");
        return 0;
    }
    puts("Stuck");
    x = b * h / (a - b);
    c = sqrt((a * a / 4) + (x + h) * (x + h));
    printf("%Lf", c * r / (a / 2) - x);
    return 0;
}

D

因为放 的位置必须是横着连续 个，所以行与行之间是无关的。我们就把每一行若出来分别求答案

对于一行从 到 遍历，记录 表示当前最后出现了多少个连续的 。如果下一个是 ， 加一，否则 。当 的时候，答案就可以加一。代表以当前这个位置结尾的一个合法方案。时间复杂度 

#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
char s[N][N], t[N];
signed main() {
    int n, m, ans = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    scanf("%s", t + 1);
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int j = 1; j <= n; j++) {
            if (s[i][j] == '0')
                cnt++;
            else
                cnt = 0;
            if (cnt >= m)
                ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

E

从起点到终点，记录来的方向。然后从终点反向找回到起点的路径，根据正确的方向旋转格子即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 9;
int T, n, m, a[N][N];
int vis[N][N][5];
int dir[5][2] = { 0, 0, -1, 0, 0, -1, 0, 1, 1, 0 };
struct node {
    int x, y, d;
};
queue<node> q;
vector<int> A;
bool in(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; }
void bfs() {
    while (q.size()) q.pop();
    q.push(node{ 1, 1, 1 });
    while (q.size()) {
        int x = q.front().x;
        int y = q.front().y;
        int d = q.front().d;
        q.pop();
        if (x == n && y == m && ((a[n][m] <= 3 && d == 2) || (a[n][m] > 3 && d == 1))) {
            vis[n][m][1] = d;
            break;
        }
        if (a[x][y] <= 3) {
            for (int i = 1; i <= 4; i++) {
                if (i == d || i + d == 5)
                    continue;
                int tx = x + dir[i][0], ty = y + dir[i][1];
                if (in(tx, ty) && vis[x][y][5 - i] == -1) {
                    vis[x][y][5 - i] = d;
                    q.push(node{ tx, ty, 5 - i });
                }
            }
            continue;
        }
        int tx = x + dir[5 - d][0], ty = y + dir[5 - d][1];
        if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && vis[x][y][d] == -1)
            vis[x][y][d] = d, q.push(node{ tx, ty, d });
    }
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);
                memset(vis[i][j], -1, sizeof vis[i][j]);
            }
        bfs();
        if ((a[n][m] <= 3 && vis[n][m][1] == 2) || (a[n][m] > 3 && vis[n][m][1] == 1)) {
            A.clear();
            puts("YES");
            int x = n, y = m;
            A.push_back(4);
            int d, dd = 1;
            while (!(x == 1 && y == 1)) {
                d = vis[x][y][dd];
                A.push_back(5 - d);
                x = x + dir[d][0], y = y + dir[d][1];
                dd = d;
            }
            cout << 2 * A.size() << endl;
            A.push_back(4);
            reverse(A.begin(), A.end());
            x = 0, y = 1;
            for (int i = 1; i < A.size(); i++) {
                int tx = x + dir[A[i - 1]][0], ty = y + dir[A[i - 1]][1];
                int now = A[i], last = 5 - A[i - 1];
                int D, k;
                if (now > last)
                    swap(now, last);
                if (now == 1 && last == 2)
                    k = 0;
                if (now == 1 && last == 3)
                    k = 1;
                if (now == 3 && last == 4)
                    k = 2;
                if (now == 2 && last == 4)
                    k = 3;
                if (now == 2 && last == 3)
                    k = 4;
                if (now == 1 && last == 4)
                    k = 5;
                D = ((k + 4 - a[tx][ty]) % 4) * 90;
                a[tx][ty] = k;
                printf("1 %d %d %d\n", D, tx, ty);
                printf("0 %d %d\n", tx, ty);
                x = tx, y = ty;
            }
        } else
            puts("NO");
    }
    return 0;
}

F

对于一个数 ，可以对每一位的数做一个前缀和 （ 意义下），如果存在两个位置值相等，那么这个数就是合法的。根据鸽巢原理，当 位数大于等于 的时候，一定存在两个位置值相等。也就是说， 一定合法。只需要对 暴力判断一下即可。

#include <bits/stdc++.h>
using namespace std;
int sum[1100];
long long get(long long x) {
    if (x >= 1000)
        return x - 1000 + 1 + sum[999];
    return sum[x];
}
int sta[5], top;
int check(int x) {
    top = 0;
    while (x) sta[++top] = x % 10, x /= 10;
    for (int i = 1; i <= top; i++) {
        int k = 0;
        for (int j = i; j <= top; j++) {
            k = k * 10 + sta[j];
            if (k % 3 == 0)
                return 1;
        }
    }
    return 0;
}
signed main() {
    int T;
    scanf("%d", &T);
    for (int i = 1; i <= 999; i++) {
        sum[i] = sum[i - 1];
        sum[i] += check(i);
    }
    while (T--) {
        long long L, R;
        scanf("%lld%lld", &L, &R);
        printf("%lld\n", get(R) - get(L - 1));
    }
    return 0;
}

G

可以把问题变成在每个 前面放符号，但是要满足 号和 号各 个，最后答案就是带符号的权值和。

若 ，那么 中较大值为 ，较小值为 。

每次交换，优先考虑交换两个符号不同的数，试图交换他们的符号，（否则答案肯定不会变化）

考虑贪心，把所有 符号的数升序排序变成 ，所有 符号的数降序排列变成 。每次对于一个 ，看是否有 ，有的话交换，改变符号。考虑这样的一次交换对应在原序列上是否合法。

假设 的原位置分别是 ：

  • 交换 （假设 属于 ）有 ，等价于交换 ，交换后符号改变。
  • 交换 （假设 属于 ）有 ，等价于交换 ，交换后符号改变。

剩下情况同理。由此可知这种方法是正确的。

注意，如果 次操作多了，交换同符号的即可消耗次数。但在 时候很特殊，必须强制交换一次，特判即可。时间复杂度 

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9;
int a[N], b[N];
long long ans;
vector<int> A, B;
bool cmp(int x, int y) { return x > y; }
signed main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    if (n == 2 && k == 1) {
        cout << abs(a[1] - b[2]) + abs(a[2] - b[1]) << endl;
    }
    for (int i = 1; i <= n; i++) {
        A.push_back(max(a[i], b[i]));
        B.push_back(min(a[i], b[i]));
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end(), cmp);
    for (int i = 0; i < n; i++) {
        if (k && A[i] < B[i])
            ans += B[i] - A[i], k--;
        else
            ans += A[i] - B[i];
    }
    cout << ans << endl;
    return 0;
}

H

首先，对于两个数 ，若 ，那么这个 一定是不合法的。因为 ，两边同时加上 就有 。

否则， 一定不等于 。

那么，只需要得到所有的 并把他们的因子排除掉，输出剩下的最小的一个未被排除的数即可。

具体的，可以用减法卷积得到所有的 ，这一步时间复杂度是 。然后从小到大枚举所有 ，看是否存在 不合法。这一步时间复杂度为

总时间复杂度 

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2 * 1e6 + 10;
const int p = 998244353;
const int G = 3, Gi = 332748118;
const int M = 500001;
bool vis[M + 10], c[M + 10];
int n, len = 1, L, r[N];
int a[N], b[N];
int inv(int x, int base = p - 2) {
    int res = 1;
    while (base) {
        if (base & 1)
            res = res * x % p;
        x = x * x % p;
        base >>= 1;
    }
    return res;
}
void NTT(int* A, int op) {
    for (int i = 0; i < len; i++)
        if (i < r[i])
            swap(A[i], A[r[i]]);
    for (int mid = 1; mid < len; mid <<= 1) {
        int Wn = inv(op == 1 ? G : Gi, (p - 1) / (mid << 1));
        for (int j = 0; j < len; j += (mid << 1)) {
            for (int k = 0, w = 1; k < mid; k++, w = (w * Wn) % p) {
                int x = A[j + k], y = w * A[j + k + mid] % p;
                A[j + k] = (x + y) % p, A[j + k + mid] = (x - y + p) % p;
            }
        }
    }
}
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%lld", &x);
        a[x] = 1;
    }
    for (int i = 0; i <= M; ++i) b[i] = a[M - i];
    while (len <= 2 * M) len <<= 1, L++;
    for (int i = 0; i < len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
    NTT(a, 1);
    NTT(b, 1);
    for (int i = 0; i < len; i++) a[i] = (a[i] * b[i]) % p;
    NTT(a, -1);
    for (int i = M + 1; i <= 2 * M; i++)
        if (a[i])
            c[i - M] = true;
    for (int i = 1; i <= M; ++i)
        for (int j = i; j <= M; j += i)
            if (c[j])
                vis[i] = true;
    for (int i = 1; i <= M; ++i)
        if (!vis[i]) {
            printf("%lld\n", i);
            return 0;
        }
    return 0;
}

I

设 为上上一次选 ,上次选 的期望结束轮数。有 ，其中 表示 的位置， 是合法转移个数。

但是这样每次要枚举下一个合法的位置，时间复杂度是

我们从大到小枚举 ，从大到小枚举位置 ，若 ，我们记录 的后缀和及个数。否则更新 ，有 。时间复杂度 

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int p = 998244353;
const int N = 5e3 + 9;
int n, ans;
int f[N][N], a[N], inv[N];
signed main() {
    scanf("%lld", &n);
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; i++) inv[i] = (p - p / i) * inv[p % i] % p;
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int j = n; j >= 0; j--) {
        int sum = 0, cnt = 0;
        for (int i = n; i >= 0; i--) {
            if (a[i] == j)
                continue;
            if (a[i] > j)
                cnt++, (sum += f[j][a[i]]) %= p;
            else
                f[a[i]][j] = (sum * inv[cnt] + 1) % p;
        }
    }
    for (int i = 1; i <= n; i++) (ans += f[0][i]) %= p;
    printf("%lld", ans * inv[n] % p);
    return 0;
}

J

假设有两个点 ，假设从 最早的时间出发都无法在 点最晚的时间前到达，那么就无法从 走到 。

否则，考虑是否能把两个点看成一个整体 。

设 为 最早到达下一个点的时间， 为最迟到达 下一个点$c.dis$ 是到下一个点的距离。

（因为可能在 点中会停留一段时间，所以要和 取个 ）

（首先不能晚于 的最晚到达时间，其次到达 时不能晚于 的最晚到达时间）

这样，两个点就能合并成一个点了！接下来我们需要一个能快速合并区间信息的数据结构，于是就能想到线段树。每次修改时递归到底层更新即可。

时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 21;
const int inf = 2e9;
struct node {
    int x, y, dis;
    node(int X = 0, int Y = 0, int Dis = 0) { x = X, y = Y, dis = Dis; }
} t[N], no, res;
node merge(node a, node b, int c) {
    node p;
    if (a.x + c > b.y)
        return no;
    return node(min(inf, max(b.x, a.x + c + b.dis)), max(-inf, min(b.y - c - a.dis, a.y)), a.dis + b.dis + c);
}
int n, q;
int a[N], b[N], c[N];
struct tree {
    void build(int p, int l, int r) {
        if (l == r) {
            t[p] = node(a[l], b[l], 0);
            return;
        }
        int mid = l + r >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        t[p] = merge(t[p << 1], t[p << 1 | 1], c[mid]);
    }
    node query(int L, int R, int p, int l, int r) {
        if (L <= l && r <= R)
            return t[p];
        int mid = l + r >> 1;
        node res;
        if (L <= mid) {
            res = query(L, R, p << 1, l, mid);
            if (mid < R)
                res = merge(res, query(L, R, p << 1 | 1, mid + 1, r), c[mid]);
        } else if (mid < R)
            res = query(L, R, p << 1 | 1, mid + 1, r);
        return res;
    }
    void add1(int x, int p, int l, int r) {
        int mid = l + r >> 1;
        if (x < mid)
            add1(x, p << 1, l, mid);
        if (x > mid)
            add1(x, p << 1 | 1, mid + 1, r);
        t[p] = merge(t[p << 1], t[p << 1 | 1], c[mid]);
    }
    void add2(int x, int p, int l, int r) {
        if (l == r) {
            t[p] = node(a[l], b[l]);
            return;
        }
        int mid = l + r >> 1;
        if (x <= mid)
            add2(x, p << 1, l, mid);
        else
            add2(x, p << 1 | 1, mid + 1, r);
        t[p] = merge(t[p << 1], t[p << 1 | 1], c[mid]);
    }
} T;
int main() {
    int x, y, op, cases;
    no = node(inf, -inf, 0);
    scanf("%d", &cases);
    while (cases--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", a + i);
        for (int i = 1; i <= n; i++) scanf("%d", b + i);
        for (int i = 1; i < n; i++) scanf("%d", c + i);
        T.build(1, 1, n);
        scanf("%d", &q);
        for (int i = 1; i <= q; i++) {
            scanf("%d%d%d", &op, &x, &y);
            if (op == 0) {
                res = T.query(x, y, 1, 1, n);
                if (res.y < 0)
                    puts("No");
                else
                    puts("Yes");
            } else {
                if (op == 1) {
                    c[x] = y;
                    T.add1(x, 1, 1, n);
                } else {
                    scanf("%d", &op);
                    a[x] = y, b[x] = op;
                    T.add2(x, 1, 1, n);
                }
            }
        }
    }
    return 0;
}

K

这里有个做法，多做几次暴力枚举两两数对，如果更优就交换。时间复杂度 

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 9;
int T, n, a[N];
signed main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        for (int k = 1; k <= 3; k++)
            for (int i = 0; i < n; i++)
                for (int j = i + 1; j < n; j++)
                    if (sqrt(abs(a[i] - i)) + sqrt(abs(a[j] - j)) > sqrt(abs(a[i] - j)) + sqrt(abs(a[j] - i)))
                        swap(a[i], a[j]);
        for (int i = 0; i < n; i++) printf("%d ", a[i]);
        puts("");
    }
    return 0;
}
2024最新求职资料大礼包领取
真题
历年笔试真题附答案
图森未来2020校招笔试卷（三）
商汤科技校招算法研究大类A卷
去哪儿23春招编程题
全部 >
面经
面试常考问题整理
面试真题：经典海量数据处理题最详解析（下）
23届联想面经分享： 秋招上岸
22届-国企上岸经验分享
全部 >
内推
员工内推码获取
拼多多内推拼多多内推拼多多内推
小鹏内推来了！共1000多个岗位！
体验中心实习生招募 - 淘天集团
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(0) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”