王清楚

发布于 2022-07-21 14:48

+ 关注

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

A

先考虑怎么判断区间 $[1,n]$ 排序后是否能构成等差数列。

假设最后构成等差为 $d$ 的等差数列 $b$ ，充要条件就是：

$(n-1)d=\max\{a_i\}-\min\{a_i\}$ 。
$\gcd(|a_1-a_2|,|a_2-a_3|,|a_3-a_4|...)=d$

如果最后能构成等差数列，就可以将数列 $a$ 中每个元素减去 $\min\{a_i\}$ （这样仍是等差数列），然后除以次小值（最小值一定是 $0$ ），得到的一定是 $0\sim n-1$ 的排列。否则，一定不能构成等差数列。

考虑第二个条件，可以用辗转相除法变成 $\gcd(|a_1-a_2|,|a_1-a_3|,|a_1-a_4|...)$ ，设答案为 $d$ , 则两两的差一定是 $d$ 的倍数。

问题就转化为 $\max a_i-\min a_i=(r-l)\gcd(|a_l-a_{l+1}|...|a_{r-1}-a_r|)$ 。

因为 $\max a_i-\min a_i-(r-l)\gcd(|a_l-a_{l+1}|...|a_{r-1}-a_r|)\geq 0$ ，所以用线段树维护这个值的最小值以及最小值个数。

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

#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

在 $n$ 个炮的一行中吃一次方案数为 $2(n-2)$ ，因为有方向。

所以吃 $m$ 次的方案数就是 $2^m\times (n-2)\times (n-3)\times ...\times (n-1-m)=2^m\frac{(n-2)!}{(n-2-m)!}$

为了方便 $n=n-2,m=m-2$

第一种情况对于某个次数 $k$ 方案数就是 $2^k\sum_{i=0}^k\binom{k}{i}\frac{n!}{(n-i)!}\frac{m!}{(m-(k-i))!}$

然后在第一行选择 $i$ 次，第二行选择 $k-i$ 次。

考虑后面一部分的组合意义，就是从 $n+m$ 个数里，有序地选择 $k$ 个数。那么可以化简为 $k!\binom{n+m}{k}$

所以第一种方案数就是 $2^kk!\binom{n+m}{k}$ ，可以直接递推

第二种情况的方案数就是
$ $\begin{aligned} &=2^k\sum_{i=0}^k\frac{n!}{(n-i)!}\frac{m!}{(m-(k-i))!}\\ &=2^k\frac{n!m!}{(n+m-k)!}\sum_i^k\binom{n+m-k}{n-i}\\ &=2^k\frac{n!m!}{(n+m-k)!}\sum_{i=n}^{n-k}\binom{n+m-k}{i} \end{aligned}$ $

最后一步是换成了枚举 $n-i$ 。然后就是组合数的前缀和问题。
$ $S(n,m)=\sum_{i=0}^m\binom{n}{i}\\ S(n,m+1)=S(n,m)+\binom{n}{m+1}\\ S(n+1,m)=2S(n,m)-\binom{n}{m}\\$ $

#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

首先有结论若 $(nm-1)\%2=1$ 则先手必胜，否则后手必胜。证明如下：

若 $(nm-1)\%2=0$ ，则先手无论选择哪一条边 $(x,y)$ ，后手都以被选过一次的 $y$ 为起点，走向另一个从来没被连过的点 $z$ 。这样 $nm-1$ 次就会覆盖所有 $nm$ 个点。下次一定会连接两个被选过的点，从而形成闭环。否则，先手随便走一步，就变成了 $(nm-1)%2=0$ 的局面了。

#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

假设某个人在点 $A(x,y,z)$ ，另外两个人坐标分别是 $B(x_1,y_1,z_1),C(x_2,y_2,z_2)$ ，则：
$ $(x-x_1)^2+(y-y_1)^2+(z-z_1)^2\geq k_1^2\times [(x-x_2)^2+(y-y_2)^2+(z-z_2)^2]$ $把同类项合并一下$ $k_1^2(x^2+y^2+z^2)-(2k_1^2x_2-2x_1)x-(2k_1^2y_2-2y_1)y-(2k_1^2z_2-2z_1)z+k_1^2(x_2^2+y_2^2+z_2^2)-x_1^2-y_1^2-z_1^2\leq 0$ $

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

一般方程： $x^2+y^2+z^2+2ax+2by+2cz+d=0$

标准方程： $(x+a)^2+(y+b)^2+(z+c)^2=a^2+b^2+c^2-d$

所以球心坐标为 $O(-a,-b,-c),r=\sqrt{a^2+b^2+c^2+d}$

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

#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

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

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

观察 $dp$ 转移式子
$ $\begin{aligned} dp[i][j]&=\max_k\{dp[i-1][k]+R[k+1]-L[j][k<j\and R[k]>L[j]]\}\\ &=\max_k\{dp[i-1][k]+R[k+1][k<j\and R[k]>L[j]]\}-L[j] \end{aligned}$ $

把 $L[j]$ 提出来后，就发现是经典的可以用单调队列来解决的转移方程。具体的，只需要从小到大枚举 $j$ 然后 $i$ 从大到小避免后效性，对于每一个 $i$ 都维护一个单调队列即可，维护 $dp[i-1][k]+R[k]$ 的最大值，每次把队尾 $R[k]\leq L[j]$ 的 $k$ 都弹掉，这样总时间复杂度是 $\mathcal O(n^2)$ .

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

#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

枚举 $\gcd$ ，然后求有多少个大小为 $k$ 的子集 $\gcd$ 为 $d$

枚举 $d$ 的倍数，若为 $sum_d$ 个，方案数就为 $\binom{sum_d}{k}$ 。但是这样会包含 $\gcd$ 是 $d$ 的倍数的方案，只需要枚举倍数，减掉他就可以了。设求得的答案为 $a_d$

最终的答案就是 $\prod_i^Vi^{a_d}$

$a_d$ 很大，但根据扩展欧拉定理：
$ $a^b\ \rm mod\ c=\begin{cases} a^b\ \rm mod \ c&b< \phi(c)\\ a^{b\ \rm mod\ \phi(c)+\phi(c)}\ \rm mod\ c&b\geq \phi(c) \end{cases}$ $让$ 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

我们根据单调栈的操作来连边。具体的，如果 $a_i$ 令 $a_j$ 弹出，那么 $add(i,j)$ 表示 $a_i>a_j$ 。否则 $add(j,i)$ 表示 $a_i<a_j$

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

#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

注意到两个信息

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

按照 $\sqrt m$ 对每个点的度数进行分治，度数大于 $\sqrt m$ 的点称为大点，剩下的称为小点。

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

注意到总 $push$ 个数是 $q\sqrt m$ 级别，所以是没有问题的。时间复杂度 $\mathcal O(q\sqrt m)$

#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;
}

2024最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(0) 回帖

加载中...

话题同步到我的动态回帖

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

A

B

C

D

F

G

I

J

K

L

已采纳

精彩回帖

全部评论

本文相关内容

等你来战

热门推荐