2025.11.6

xz001 · 2025-11-06 14:08:46 · 个人记录

T1：

如果最大的 a_i 去干其他的 b_i 还有剩余，显然需要加上这些多余的，最大的 b_i 亦然，所以 st 表即可。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 2e5 + 5;

int n, q, s1[N], s2[N], Log2[N];

signed a[N], b[N];

pair <signed, signed> st1[N][21], st2[N][21];

pair <signed, signed> query1 (int l, int r) {
    int s = Log2[r - l + 1];
    return max(st1[l][s], st1[r - (1 << s) + 1][s]);
}

pair <signed, signed> query2 (int l, int r) {
    int s = Log2[r - l + 1];
    return max(st2[l][s], st2[r - (1 << s) + 1][s]);
}

signed main() {
//  system("fc max.out ans.out");
    freopen("max.in","r",stdin);
    freopen("max.out","w",stdout);
    for (int i = 2; i <= 2e5; ++ i ) Log2[i] = Log2[i >> 1] + 1;
    scanf("%lld%lld", &n, &q);
    for (int i = 1; i <= n; ++ i ) scanf("%d", a + i), s1[i] = s1[i - 1] + a[i], st1[i][0] = {a[i], i};
    for (int i = 1; i <= n; ++ i ) scanf("%d", b + i), s2[i] = s2[i - 1] + b[i], st2[i][0] = {b[i], i};
    for (signed j = 1; j <= 17; ++ j )
        for (signed i = 1; i + (1 << (j - 1)) - 1 <= n; ++ i )
            st1[i][j] = max(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]),
            st2[i][j] = max(st2[i][j - 1], st2[i + (1 << (j - 1))][j - 1]);

    while (q -- ) {
        signed l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2); 
        int S1 = s1[r1] - s1[l1 - 1], S2 = s2[r2] - s2[l2 - 1];
        int id1 = query1 (l1, r1).second, id2 = query2 (l2, r2).second;
        int maxn = max(a[id1] + b[id1 + l2 - l1], a[id2 - (l2 - l1)] + b[id2]);
        printf("%lld\n", max(0ll, maxn - max(S1, S2)) + max(S1, S2));
    }
    return 0;
}

T2：

不用管题目中的 f 定义，它就是 C_i^x。

对于 k 大的情况，暴力算即可。

对于 k 小的情况，考虑递推预处理。

设 f_{x,r} 表示 \sum_{i=0}^n{[i\mod k=r]C_i^x}。

然后我们画个图（杨辉三角）。

首先我们知道 C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}

因此：

即如图：

然后你发现你不知道如何得到 f_{x,0}，暴力算显然不可行。

考虑设它为 Q。

然后你就能推出 f_{x,r}=Q+b

考虑计算所有项的和，显然为 \sum_{i=0}^nC_i^x

经典结论，这个东西等于 C_{n+1}^{x+1}

#include <bits/stdc++.h>

#define int long long 

using namespace std;

const int N = 1e5 + 1, mod = 1e9 + 7;

int ksm (int a, int n) {
    int ans = 1;
    while (n) {
        if (n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

int n, k, q, jc[N], inv[N], f[N][201];

int C (int n, int m) {
    if (n < 0 || m < 0 || m > n) return 0;
    return jc[n] * inv[m] % mod * inv[n - m] % mod;
}

signed main() {
    freopen("sum.in","r",stdin);
    freopen("sum.out","w",stdout);
    jc[0] = 1;
    for (int i = 1; i < N; ++ i ) jc[i] = jc[i - 1] * i % mod;
    inv[N - 1] = ksm (jc[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; -- i ) inv[i] = inv[i + 1] * (i + 1) % mod;
    scanf("%lld%lld%lld", &n, &k, &q);
    if (k <= 200) {
        f[0][0] = n / k;
        for (int r = 1; r < k; ++ r ) f[0][r] = n / k;
        for (int x = 1; x <= n; ++ x ) {
            int sum = 0;
            for (int r = 1; r < k; ++ r ) f[x][r] = (f[x - 1][r - 1] + f[x][r - 1]) % mod, (sum += f[x][r]) %= mod; 
            int Q = (C (n, x + 1) - sum + mod) * ksm (k, mod - 2) % mod;
            for (int r = 0; r < k; ++ r ) (f[x][r] += Q) %= mod;
        }
    }
    while (q -- ) {
        int x, r;
        scanf("%lld%lld", &x, &r);
        if (k == 1) {
            printf("%lld\n", C (n + 1, x + 1));
        } else if (k > 200) {
            int ans = 0;
            for (int i = r; i <= n; i += k ) (ans += C (i, x)) %= mod;
            printf("%lld\n", ans);
        } else {
            printf("%lld\n", (f[x][r] + C (n, x) * (r == 0)) % mod);
        }
    }
    return 0;
} 

T3：

这是经典缺一分治，首先我们知道 Flogd 支持每次加入一个点 O(n^2) 更新每个点的答案，所以我们分治，每次将这个区间前半部分的点加入，递归右半区间，然后撤销这些操作，加入右边所有点，递归左半区间，当区间长度为 1 的时候更新答案，时间复杂度 O(n^3\log n)。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e6 + 5, INF = 1e18;

int n, q, a[305][305], ans[N], f[11][305][305];

struct node {
    int s, t, id;
};

vector <node> g[305];

inline void solve (const signed l, const signed r, const signed d) {
    if (l == r) {
        for (node i : g[l]) ans[i.id] = f[d][i.s][i.t];    
        return;
    }
    signed mid = (l + r) >> 1;
    for (signed i = 1; i <= n; ++ i )
        for (signed j = 1; j <= n; ++ j )
            f[d + 1][i][j] = f[d][i][j];

    for (signed k = l; k <= mid; ++ k )
        for (signed i = 1; i <= n; ++ i )
            for (signed j = 1; j <= n; ++ j )
                f[d + 1][i][j] = min(f[d + 1][i][j], f[d + 1][i][k] + f[d + 1][k][j]);

    solve (mid + 1, r, d + 1);
    for (signed i = 1; i <= n; ++ i )
        for (signed j = 1; j <= n; ++ j )
            f[d + 1][i][j] = f[d][i][j];

    for (signed k = mid + 1; k <= r; ++ k )
        for (signed i = 1; i <= n; ++ i )
            for (signed j = 1; j <= n; ++ j )
                f[d + 1][i][j] = min(f[d + 1][i][j], f[d + 1][i][k] + f[d + 1][k][j]);

    solve (l, mid, d + 1);
    return; 
}

int read() {
    int x = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    } 
    return x;
}

signed main() {
//  system("fc distance.out asd.out");
    freopen("distance.in","r",stdin);
    freopen("distance.out","w",stdout);
    n = read(), q = read();
    for (int i = 1; i <= n; ++ i )
        for (int j = 1; j <= n; ++ j )
            a[i][j] = read(), f[0][i][j] = a[i][j];

    for (int i = 1; i <= q; ++ i ) {
        int s, t, p;
        s = read(), t = read(), p = read();
        g[p].push_back({s, t, i});
    }
    solve (1, n, 0);
    for (int i = 1; i <= q; ++ i ) printf("%lld\n", ans[i]);
    return 0;
}