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

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

A

先考虑怎么判断区间 排序后是否能构成等差数列。

假设最后构成等差为 的等差数列 ,充要条件就是:

如果最后能构成等差数列,就可以将数列 中每个元素减去 (这样仍是等差数列),然后除以次小值(最小值一定是 ),得到的一定是 的排列。否则,一定不能构成等差数列。

考虑第二个条件,可以用辗转相除法变成 ,设答案为 , 则两两的差一定是 的倍数。

问题就转化为

因为 ,所以用线段树维护这个值的最小值以及最小值个数。

每次移动右端点,可以用单调栈来维护极值,每个数只会弹出一次。若固定某个点为区间左端点,那么随着右端点的移动, 最多只会变化 次,因为每次减至少除以 。对于每一个右端点,从右往左枚举左端点更新 ,一旦更新不了,就可以 了。然后会有 段不同的 ,对着 个区间减去相应的 。总时间复杂度是

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9;
int read() {
    int f = 0, x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f ? -x : x;
}
int t, n, w[N];
long long ans;
int mn[N << 2], cnt[N << 2], tag[N << 2], d[N << 2];
int sa[N], ta;
int sb[N], tb;
void push_down(int p) {
    tag[p << 1] += tag[p];
    mn[p << 1] += tag[p];
    tag[p << 1 | 1] += tag[p];
    mn[p << 1 | 1] += tag[p];
    tag[p] = 0;
}
void push_up(int p) {
    cnt[p] = 0;
    mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
    if (mn[p] == mn[p << 1])
        cnt[p] += cnt[p << 1];
    if (mn[p] == mn[p << 1 | 1])
        cnt[p] += cnt[p << 1 | 1];
    d[p] = (d[p << 1] == d[p << 1 | 1] ? d[p << 1] : 0);
}
void build(int p, int l, int r) {
    tag[p] = 0;
    mn[p] = 0;
    d[p] = 0;
    cnt[p] = r - l + 1;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
}
void add(int p, int l, int r, int nl, int nr, int v) {
    if (nl <= l && r <= nr) {
        mn[p] += v;
        tag[p] += v;
        return;
    }
    int mid = (l + r) >> 1;
    push_down(p);
    if (nl <= mid)
        add(p << 1, l, mid, nl, nr, v);
    if (nr > mid)
        add(p << 1 | 1, mid + 1, r, nl, nr, v);
    push_up(p);
}
void change(int p, int l, int r, int nl, int nr, int v) {
    if (nl <= l && r <= nr && d[p] && v % d[p] == 0) {
        mn[p] -= d[p];
        tag[p] -= d[p];
        return;
    }
    if (l == r) {
        mn[p] += (nr - r) * d[p];
        d[p] = __gcd(d[p], v);
        mn[p] -= (nr - r + 1) * d[p];
        return;
    }
    int mid = (l + r) >> 1;
    push_down(p);
    if (nl <= mid)
        change(p << 1, l, mid, nl, nr, v);
    if (nr > mid)
        change(p << 1 | 1, mid + 1, r, nl, nr, v);
    push_up(p);
}
int get(int p, int l, int r, int nl, int nr) {
    if (nl <= l && r <= nr)
        return (mn[p] == 0) * cnt[p];
    int mid = (l + r) >> 1;
    int res = 0;
    push_down(p);
    if (nl <= mid)
        res += get(p << 1, l, mid, nl, nr);
    if (nr > mid)
        res += get(p << 1 | 1, mid + 1, r, nl, nr);
    return res;
}
signed main() {
    t = read();
    while (t--) {
        scanf("%d", &n);
        ans = 0;
        for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
        build(1, 1, n);
        ta = tb = 0;
        for (int i = 1; i <= n; ++i) {
            while (ta && w[sa[ta]] < w[i]) {
                add(1, 1, n, sa[ta - 1] + 1, sa[ta], -w[sa[ta]]);
                ta--;
            }
            while (tb && w[sb[tb]] > w[i]) {
                add(1, 1, n, sb[tb - 1] + 1, sb[tb], w[sb[tb]]);
                tb--;
            }
            sa[++ta] = i;
            add(1, 1, n, sa[ta - 1] + 1, sa[ta], w[sa[ta]]);
            sb[++tb] = i;
            add(1, 1, n, sb[tb - 1] + 1, sb[tb], -w[sb[tb]]);
            if (i != 1)
                change(1, 1, n, 1, i - 1, abs(w[i] - w[i - 1]));
            ans += get(1, 1, n, 1, i);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

B

个炮的一行中吃一次方案数为 ,因为有方向。

所以吃 次的方案数就是

为了方便

第一种情况对于某个次数 方案数就是

然后在第一行选择 次,第二行选择 次。

考虑后面一部分的组合意义,就是从 个数里,有序地选择 个数。那么可以化简为

所以第一种方案数就是 ,可以直接递推

第二种情况的方案数就是
$$

最后一步是换成了枚举 。然后就是组合数的前缀和问题。
$$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int p = 1e9 + 9;
const int N = 1e7 + 5;
int x, y;
int fac[N], ifac[N], sum[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;
}
int C(int n, int m) { return n >= m && m >= 0 ? fac[n] * ifac[m] % p * ifac[n - m] % p : 0; }
void init(int n = N - 1) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % p;
    ifac[n] = inv(fac[n]);
    for (int i = n - 1; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1) % p;
    assert(fac[10] * ifac[10] % p == 1);
}
signed main() {
    scanf("%lld%lld", &x, &y);
    x -= 2;
    y -= 2;
    init();
    int ans1 = 0, ans2 = 0;
    int p2 = 1;
    sum[0] = 1;
    for (int i = 1; i <= x + y; ++i) {
        sum[i] = sum[i - 1] * 2 % p;
        sum[i] = ((sum[i] - C(i - 1, x) - C(i - 1, y)) % p + p) % p;
    }
    for (int i = 0; i <= x + y; ++i) {
        int res = p2 * fac[i] % p * C(x + y, i) % p;
        ans1 ^= res;
        res = p2 * fac[x] % p * fac[y] % p * ifac[x + y - i] % p * sum[x + y - i] % p;
        ans2 ^= res;
        p2 = p2 * 2 % p;
    }
    printf("%lld %lld\n", ans1, ans2);
    return 0;
}

C

首先有结论若 则先手必胜,否则后手必胜。证明如下:

,则先手无论选择哪一条边 ,后手都以被选过一次的 为起点,走向另一个从来没被连过的点 。这样 次就会覆盖所有 个点。下次一定会连接两个被选过的点,从而形成闭环。否则,先手随便走一步,就变成了 的局面了。

#include <bits/stdc++.h>
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    printf("%s\n", (n * m) & 1 ? "NO" : "YES");
    return 0;
}

D

直接按照题意模拟即可。也可以把每一个特征赋一个权,最后就可以直接比较,减少分类讨论。

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
    int T;
    int a1, a2, b1, b2;
    int va = 0, vb = 0;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cin >> a1 >> a2 >> b1 >> b2;
        if (a1 > a2)
            swap(a1, a2);
        if (b1 > b2)
            swap(b1, b2);
        if (a1 == 2 && a2 == 8)
            va += 10000;
        if (b1 == 2 && b2 == 8)
            vb += 10000;
        if (a1 == a2)
            va += 1000 * a1;
        if (b1 == b2)
            vb += 1000 * b1;
        if (a1 != a2)
            va += 100 * ((a1 + a2) % 10) + a2;
        if (b1 != b2)
            vb += 100 * ((b1 + b2) % 10) + b2;
        if (va > vb)
            cout << "first" << endl;
        if (va < vb)
            cout << "second" << endl;
        if (va == vb)
            cout << "tie" << endl;
        va = 0;
        vb = 0;
    }
    return 0;
}

F

假设某个人在点 ,另外两个人坐标分别是 ,则:
$$

发现和球的方程非常类似。

一般方程:

标准方程:

所以球心坐标为

然后计算两个球相交部分体积即可。

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-10;
struct point {
    double x, y, z;
} a, b, c, d;
double dis(point p, point q) {
    return sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y) + (p.z - q.z) * (p.z - q.z));
}
int t, k1, k2;
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%lf%lf%lf", &a.x, &a.y, &a.z);
        scanf("%lf%lf%lf", &b.x, &b.y, &b.z);
        scanf("%lf%lf%lf", &c.x, &c.y, &c.z);
        scanf("%lf%lf%lf", &d.x, &d.y, &d.z);
        scanf("%d%d", &k1, &k2);
        double d1 = dis(a, b);
        double d2 = dis(c, d);
        double r1 = d1 / (k1 * k1 - 1) * k1, r2 = d2 / (k2 * k2 - 1) * k2;
        point o1, o2;
        o1.x = (b.x * k1 * k1 - a.x) / (k1 * k1 - 1);
        o1.y = (b.y * k1 * k1 - a.y) / (k1 * k1 - 1);
        o1.z = (b.z * k1 * k1 - a.z) / (k1 * k1 - 1);
        o2.x = (d.x * k2 * k2 - c.x) / (k2 * k2 - 1);
        o2.y = (d.y * k2 * k2 - c.y) / (k2 * k2 - 1);
        o2.z = (d.z * k2 * k2 - c.z) / (k2 * k2 - 1);
        double d = dis(o1, o2);
        if (d - r1 - r2 > eps) {
            puts("0.0000");
            continue;
        }
        if (r1 < r2) {
            swap(r1, r2);
            swap(o1, o2);
        }
        if (r1 - r2 - d > eps)
            printf("%.4f\n", 4 * pi / 3 * r2 * r2 * r2);
        else {
            double ca = (r1 * r1 + d * d - r2 * r2) / r1 / d / 2, h1 = r1 * (1.0 - ca);
            double cb = (r2 * r2 + d * d - r1 * r1) / r2 / d / 2, h2 = r2 * (1.0 - cb);
            printf("%.4f\n", pi / 3 * ((3 * r1 - h1) * h1 * h1 + (3 * r2 - h2) * h2 * h2));
        }
    }
    return 0;
}

G

如果存在两个区间 满足 ,即大区间包含小区间,那么这个大区间相当于没有额外贡献,把他提出来单独成一个区间有可能更优。注意,不可能将两个及以上的“大区间”分成一组,否则留下一个,把剩下的分配到相应的小区间所在组会更优。

剩下来的小区间按照左端点排序,可知右端点也会单调递增(不然就会存在包含关系,而已经把把包含关系中的大区间筛去了)。设 为前 组用了前 个线段的最优答案。那么就能得到一个时间复杂度为 的算法。

观察 转移式子
$$

提出来后,就发现是经典的可以用单调队列来解决的转移方程。具体的,只需要从小到大枚举 然后 从大到小避免后效性,对于每一个 都维护一个单调队列即可,维护 的最大值,每次把队尾 都弹掉,这样总时间复杂度是 .

最后枚举这些小区间分成多少组,剩下的用大区间来补全统计答案。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 9;
struct node {
    int l, r;
} a[N], b[N];
int dp[N][N], q[N], c[N];
int n, x, y, z, ans, sum, k;
bool cmp(node A, node B) {
    if (A.l == B.l)
        return A.r > B.r;
    return A.l < B.l;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].l, &a[i].r);
    sort(a + 1, a + 1 + n, cmp);
    int aaa = 1000000000, top = 0, m = 0;
    for (int i = n; i >= 1; i--) {
        if (a[i].r >= aaa)
            c[++top] = a[i].r - a[i].l;
        else {
            aaa = a[i].r;
            b[++m] = a[i];
        }
    }
    memset(dp, -1, sizeof(dp));
    sort(c + 1, c + 1 + top, greater<int>());
    reverse(b + 1, b + 1 + m);
    dp[0][0] = 0;
    for (int i = 1; i <= k; i++) {
        int sl = 1, sr = 0;
        for (int j = 1; j <= m; j++) {
            if (dp[i - 1][j - 1] != -1) {
                while (sl <= sr && dp[i - 1][q[sr]] + b[q[sr] + 1].r <= dp[i - 1][j - 1] + b[j].r) sr--;
                q[++sr] = j - 1;
            }
            while (sl <= sr && b[q[sl] + 1].r <= b[j].l) sl++;
            if (sl <= sr)
                dp[i][j] = dp[i - 1][q[sl]] + b[q[sl] + 1].r - b[j].l;
        }
    }
    for (int i = 0; i <= min(k, n); i++) {
        sum += c[i];
        if (dp[k - i][m] != -1)
            ans = max(ans, dp[k - i][m] + sum);
    }
    cout << ans;
    return 0;
}

I

状态记录两只企鹅的位置状态,保存上一步的位置,直接广搜,然后根据路径构造答案。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
const int M = 30;
const int inf = 0x3f3f3f3f;
char s1[M][M], s2[M][M], sta[N * 10];
char c[4] = { 'D', 'L', 'R', 'U' };
int top;
struct node {
    int x1, y1, x2, y2;
};
int d[M][M][M][M], p[M][M][M][M];
node pre[M][M][M][M];
int dir[4][4] = { 1, 0, 1, 0, 0, -1, 0, 1, 0, 1, 0, -1, -1, 0, -1, 0 };
queue<node> q;
void bfs() {
    memset(d, inf, sizeof(d));
    d[20][20][20][1] = 0;
    q.push(node{ 20, 20, 20, 1 });
    while (!q.empty()) {
        node now = q.front();
        q.pop();
        int x1 = now.x1, y1 = now.y1, x2 = now.x2, y2 = now.y2;
        int dis = d[x1][y1][x2][y2];
        for (int i = 0; i < 4; i++) {
            int u1 = x1 + dir[i][0], v1 = y1 + dir[i][1], u2 = x2 + dir[i][2], v2 = y2 + dir[i][3];
            if (s1[u1][v1] != '.')
                u1 -= dir[i][0], v1 -= dir[i][1];
            if (s2[u2][v2] != '.')
                u2 -= dir[i][2], v2 -= dir[i][3];
            if (dis + 1 < d[u1][v1][u2][v2]) {
                d[u1][v1][u2][v2] = dis + 1;
                pre[u1][v1][u2][v2] = node{ x1, y1, x2, y2 };
                p[u1][v1][u2][v2] = i;
                q.push(node{ u1, v1, u2, v2 });
            }
        }
    }
}
void solve(node u) {
    int x1 = u.x1, y1 = u.y1, x2 = u.x2, y2 = u.y2;
    s1[x1][y1] = s2[x2][y2] = 'A';
    if (x1 == 20 && y1 == 20 && x2 == 20 && y2 == 1)
        return;
    solve(pre[x1][y1][x2][y2]);
    sta[top++] = c[p[x1][y1][x2][y2]];
}
signed main() {
    for (int i = 1; i <= 20; i++) scanf("%s%s", s1[i] + 1, s2[i] + 1);
    bfs();
    solve(node{ 1, 20, 1, 1 });
    printf("%d\n", top);
    printf("%s\n", sta);
    for (int i = 1; i <= 20; i++) printf("%s %s\n", s1[i] + 1, s2[i] + 1);
}

J

枚举 ,然后求有多少个大小为 的子集

枚举 的倍数,若为 个,方案数就为 。但是这样会包含 的倍数的方案,只需要枚举倍数,减掉他就可以了。设求得的答案为

最终的答案就是

很大,但根据扩展欧拉定理:
$a_d\phi(p)\rm int128$ ,或者龟速乘。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 80000;
int vis[80005], pr[80005], len;
int T, n, k, a[80005], res, b[35];
int p, ans;
int mul(int a, int b) {
    int s = (long double)a / p * b, t = a * b - s * p;
    return t < 0 ? t + p : t;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int inv(int x, int base = p - 2) {
    int res = 1;
    while (base) {
        if (base & 1)
            res = mul(res, x);
        base >>= 1, x = mul(x, x);
    }
    return res;
}
int calc(int N, int m, int t) {
    for (int i = 1; i <= m; ++i) b[i] = N - i + 1;
    for (int i = 2; i <= m; ++i) {
        int now = i;
        for (int j = 1, g; now > 1 && j <= m; ++j) {
            g = gcd(b[j], now);
            b[j] /= g, now /= g;
        }
    }
    int res = inv(t, b[1]);
    for (int i = 2; i <= m; ++i) res = inv(res, b[i]);
    return res;
}
void init() {
    for (int i = 2; i <= N; ++i) {
        if (!vis[i])
            pr[++len] = i;
        for (int j = 1; j <= len && i * pr[j] <= N; ++j) {
            vis[i * pr[j]] = 1;
            if (i % pr[j] == 0)
                break;
        }
    }
}
signed main() {
    init();

    scanf("%d", &T);
    while (T--) {
        cin >> n >> k >> p;
        memset(a, 0, sizeof(a));
        for (int i = 1, x; i <= n; ++i) {
            cin >> x;
            a[x]++;
        }
        ans = 1;
        for (int i = 1; i <= len; ++i) {
            for (int now = pr[i]; now <= N; now *= pr[i]) {
                res = 0;
                for (int j = now; j <= N; j += now) res += a[j];
                if (res < k)
                    continue;
                ans = mul(ans, calc(res, k, pr[i]));
            }
        }
        cout << ans << endl;
    }
    return 0;
}

K

我们根据单调栈的操作来连边。具体的,如果 弹出,那么 表示 。否则 表示

然后做一遍拓扑排序,按照遍历的顺序赋值一定满足题目要求。如果图不是一张 ,说明有环无解,直接输出

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 9;
int n, k;
PII p[N];
int a[N], b[N], to[N], d[N], sta[N], q[N];
bool check() {
    for (int i = 0; i < k; i++) {
        int pos = p[i].first, val = p[i].second;
        int pp = p[i + 1].first, vv = p[i + 1].second;
        if (pos < val)
            return true;
        if (i == k - 1)
            break;
        if (val + pp - pos < vv)
            return true;
    }
    return false;
}
void topsort() {
    int l = 0, r = -1;
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q[++r] = i;
    while (l <= r) {
        int x = q[l++];
        d[to[x]]--;
        if (d[to[x]] == 0)
            q[++r] = to[x];
    }
    int x = n;
    for (int i = 0; i <= r; i++) {
        int pos = q[i];
        a[pos] = x--;
    }
    for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n];
}
void solve() {
    int top = 0;
    for (int i = 1; i <= n; i++) {
        if (b[i]) {
            bool flag = false;
            while (top > b[i] - 1) top--, flag = true;
            if (flag)
                to[sta[top + 1]] = i;
        }
        sta[++top] = i;
        to[i] = sta[top - 1];
    }
    for (int i = 1; i <= n; i++) d[to[i]]++;
    topsort();
}
int main() {
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        int pos, val;
        cin >> pos >> val;
        p[i] = { pos, val };
        b[pos] = val;
    }
    if (check())
        puts("-1");
    else
        solve();
    return 0;
}

L

注意到两个信息

  • 每次只改一个点权值
  • 最大权值小于等于

按照 对每个点的度数进行分治,度数大于 的点称为大点,剩下的称为小点。

  • 修改小点的时候,可以暴力遍历与它相邻的点,并维护相应的答案。
  • 对于大点,先暴力遍历与他相邻的大点,至多有 个点。但是却不能枚举小点。这时候就要利用权值不超过 的性质了。假设更改前点权为 ,更改后为 ,那么会改变夺冠情况的只有点权位于 的,是冠军的小点,他们会失去冠军。用 表示与点 相邻的小点,权值是 并且是冠军的集合。所以当一个小点 是冠军的时候,不妨枚举相邻的大点 ,把 塞进 。当更改的时候就可以暴力遍历 里面的点并修改状态

注意到总 个数是 级别,所以是没有问题的。时间复杂度

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m, q, S;
vector<int> e[N], big[N];
int walk[N], mx[N];
int ans[N], chmp[N];
vector<pair<int, int>> had[10005];
int main() {
    cin >> n >> m >> q;
    S = 2 * sqrt(m) + 1;
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        for (int v : e[i])
            if (e[v].size() >= S)
                big[i].push_back(v);
    for (int i = 1; i <= q; i++) {
        int u, w;
        scanf("%d%d", &u, &w);
        walk[u] += w;
        had[walk[u]].push_back({ u, i });
    }
    vector<int> f(n + 1, q), last(n + 1, q), mn(n, q);
    for (int w = 10000; w >= 1; w--) {
        for (int i = 0; i < had[w].size(); i++) {
            int u = had[w][i].first, t = had[w][i].second;
            for (auto v : big[u]) mn[v] = min(mn[v], t);
            last[u] = f[u], f[u] = t;
        }
        for (int i = 0; i < had[w].size(); i++) {
            int u = had[w][i].first, t = had[w][i].second;
            if (e[u].size() < S) {
                int r = last[u];
                for (auto v : e[u]) r = min(r, f[v]);
                ans[u] += max(0, r - t);
            } else
                ans[u] += max(0, min(last[u], mn[u]) - t);
        }
    }
    for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
    return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐