2020 计蒜之道 线上决赛（C，D，E，F，G）

最近很长时间都很忙，写这篇主要是挂一下代码。

A略

B略

C.攀登山峰

样例输入复制

8 3
1 2 1 4 4 5 3 3 
3 7 5
1 4 3
3 8 6

样例输出复制

4
1
4

 题解：

std：

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

const int maxn = 1e5 + 5;

int n, m, cnt, a[maxn], b[maxn], rt[maxn];
int tr[maxn << 5], ls[maxn << 5], rs[maxn << 5];

void build(int &now, int l, int r){
    tr[now = ++cnt] = 0;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    build(ls[now], l, mid);
    build(rs[now], mid + 1, r);
}

void up(int now){
    tr[now] = tr[ls[now]] + tr[rs[now]];
}

void update(int &now, int &old, int l, int r, int w){
    tr[now = ++cnt] = tr[old] + 1;
    ls[now] = ls[old], rs[now] = rs[old];
    if(l == r){
        // tr[now]++;
        return ;
    }
    int mid = (l + r) >> 1;
    if(mid >= w) update(ls[now], ls[old], l, mid, w);
    else update(rs[now], rs[old], mid + 1, r, w);
    // up(now);
}

int query(int now, int old, int l, int r, int num){
    if(l == r) return l;
    int mid = (l + r) >> 1;
    int res = 0;
    if(tr[ls[old]] - tr[ls[now]] > num){
        res = max(res, query(ls[now], ls[old], l, mid, num));
    }
    if(tr[rs[old]] - tr[rs[now]] > num){
        res = max(res, query(rs[now], rs[old], mid + 1, r, num));
    }
    return res;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + 1 + n);
    int cnt = unique(b + 1, b + 1 + n) - b - 1;
    build(rt[0], 1, cnt);
    b[0] = -1;
    for (int i = 1; i <= n; i++) update(rt[i], rt[i - 1], 1, cnt, a[i] = lower_bound(b + 1, b + 1 + cnt, a[i]) - b);
    for (int i = 1, l, r, t; i <= m; i++){
        scanf("%d %d %d", &l, &r, &t);
        int len = (r - l + 1) / t;
        printf("%d\n", b[query(rt[l - 1], rt[r], 1, cnt, len)]);
    }

    return 0;
}
/**/

 

D. 两个多项式的卷积

数据范围

样例输入复制

2
1 2 3
3 2 1
3
1 1 4
2 0 -1
1 1 4

样例输出复制

33
30

题解：

 

std：

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

const int maxn = 4e4 + 5;
const int mod = 998244353;

int lim = 1, L, G = 3, Gi = 332748118;
int n, m, cnt, a[maxn], A[maxn], b[maxn], c[maxn], rev[maxn << 1], pos[maxn], w[maxn], pre[maxn];

LL poww(LL x, LL num){
    LL res = 1;
    while(num){
        if(num & 1) res = res * x % mod;
        x = x * x % mod;
        num >>= 1;
    }
    return res;
}

void ntt(int *a, int type){
    for (int i = 0; i < lim; i++) if(i < rev[i]) swap(a[i], a[rev[i]]);
    static int x, y;
    for (int mid = 1; mid < lim; mid <<= 1){
        int len = mid << 1, wn = poww(type ? G : Gi , (mod - 1) / (mid << 1));
        for (int i = 0; i < lim; i += len){
            for (int j = 0, w = 1; j < mid; j++, w = 1LL * w * wn % mod){
                x = a[i + j], y = 1LL * w * a[i + mid + j] % mod;
                a[i + j] = (x + y) % mod, a[i + mid + j] = (x + mod - y) % mod;
            }
        }
    }
    if(!type){
        LL inv = poww(lim, mod - 2);
        for (int i = 0; i < lim; i++) a[i] = (1LL * inv * a[i] % mod + mod) % mod;
    }
}

void init(){
    while(lim <= n) lim <<= 1, L++;
    for (int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
}

void doNTT(){
    for (int i = 0; i < lim; i++) A[i] = a[i];
    ntt(A, 1);
    for (int i = 0; i < lim; i++) c[i] = (1LL * A[i] * b[i] % mod + mod) % mod;
    ntt(c, 0);
    for (int i = 1; i < lim; i++) c[i] = (c[i] + c[i - 1]) % mod;
}

LL cal(int x){
    if(x < 0) return 0LL;
    LL sum = c[x];
    for (int i = 1; i <= cnt; i++){
        int r = x - pos[i];
        // printf("===%d %d %d\n", i, r, pre[r]);
        if(r >= 0) sum = (sum + 1LL * w[i] * pre[r] % mod + mod) % mod;
    }
    return sum;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    scanf("%d", &n);
    for (int i = 0; i <= n; i++) scanf("%d", &a[i]), a[i] = (a[i] % mod + mod) % mod;
    for (int i = 0; i <= n; i++){
        scanf("%d", &b[i]);
        b[i] = (b[i] % mod + mod) % mod;
        if(i) pre[i] = (pre[i - 1] + b[i]) % mod;
        else pre[i] = b[i];
    }
    scanf("%d", &m);
    n <<= 1;
    for (int i = n / 2 + 1; i <= n; i++) pre[i] = pre[i - 1];
    init();
    ntt(b, 1);
    doNTT();
    int mx = sqrt(n * log10(1.0 * n) / log10(2.0)) + 1;
    cnt = 0;
    for (int i = 1, op, l, r; i <= m; i++){
        scanf("%d %d %d", &op, &l, &r);
        if(op == 1){
            printf("%lld\n", (cal(r) - cal(l - 1) + mod) % mod);
        }else{
            pos[++cnt] = l;
            a[l] += (w[cnt] = r);
            a[l] = (a[l] % mod + mod) % mod;
            if(cnt == mx + 1){
                doNTT();
                cnt = 0;
            }
        }
    }

    return 0;
}
/**/

E.矩阵

样例输入复制

2
11
10

样例输出复制

5

样例输入2

5
11100
11100
11110
11111
10000

样例输出 2

73

题解： 

 我写的复杂度似乎有点问题？ 再说吧，先把过的代码贴上来

std：

/**/
#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

const int maxn = 1005;

int n, a[maxn][maxn], up[maxn][maxn], sk[maxn], sum[maxn][maxn], l[maxn];
char s[maxn][maxn];

void init(){
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            sum[i][j] = (i % j == 0 || j % i == 0);
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
}

int cal(int n, int m){
    return sum[n][m];
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    scanf("%d", &n);
    init();
    for (int i = 1; i <= n; i++){
        scanf("%s", s[i] + 1);
        for (int j = 1; j <= n; j++) a[i][j] = s[i][j] - '0';
    }
    for (int j = 1; j <= n; j++){
        for (int i = 1; i <= n; i++){
            if(a[i][j] == 1) up[i][j] = up[i - 1][j] + 1;
            else up[i][j] = 0;
        }
    }
    LL ans = 0;
    for (int i = 1; i <= n; i++){
        int top = 0;
        for (int j = 1; j <= n; j++) l[j] = 0;
        for (int j = 1; j <= n; j++){
            while(top && up[i][sk[top]] >= up[i][j]) top--;
            sk[++top] = j;
            l[j] = j - sk[top - 1];
            if(!up[i][j]) continue;
            int sum = l[j];
            for (int k = top - 1; k >= 1; k--){
                ans += cal(up[i][sk[k]], sum += l[sk[k]]);
                ans -= cal(up[i][sk[k]], sum - l[sk[k]]);
            }
            ans += cal(up[i][j], l[j]);
            // printf("%d %d %d %lld\n", i, j, l[j], ans);
        }
    }
    printf("%lld\n", ans);

    return 0;
}
/*
7
1000000
1101110
1111111
0000000
0000000
0000000
0000000

5
00100
01110
11111
01110
00100
*/

F. 格子

样例输入复制

3 2

样例输出复制

6

题解：

 

std：

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

const long long mod = 998244353;
const int maxn = 2e6 + 5;

int n, m;
LL a[maxn];

LL poww(LL x, LL num){
    LL res = 1;
    while(num){
        if(num & 1) res = res * x % mod;
        x = x * x % mod;
        num >>= 1;
    }
    return res;
}

LL C(int n, int m){
    return a[n] * poww(a[m] * a[n - m] % mod, mod - 2) % mod;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    a[0] = 1;
    for (int i = 1; i < maxn; i++) a[i] = a[i - 1] * i % mod;
    scanf("%d %d", &n, &m);
    printf("%lld\n", C(n + m - 1, n - 1));

    return 0;
}
/**/

 

G. 宝藏

样例输入复制

5 3
1 2 3 4 5
1 2 3
2 4 6
1 5 9

样例输出复制

36
1638
183600

题解：

std：

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

const int maxn = 1e5 + 5;
const long long mod = 998244353;

int n, m, p[maxn][32], a[maxn];
LL pw2;

LL poww(LL x, LL num){
    LL res = 1;
    while(num){
        if(num & 1) res = res * x % mod;
        x = x * x % mod;
        num >>= 1;
    }
    return res;
}

LL cal(int a, int b, int x){
    return poww(x + 1, a) * (poww(1 + x, b) - poww((1 - x + mod) % mod, b) + mod) % mod * pw2 % mod;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    pw2 = poww(2, mod - 2);
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < 30; j++){
            p[i][j] = p[i - 1][j];
            if(1 << j & a[i]) p[i][j]++;
        }
    }
    for (int i = 1, l, r, x; i <= m; i++){
        scanf("%d %d %d", &l, &r, &x);
        LL ans = 0;
        for (int j = 0; j < 30; j++){
            int b = p[r][j] - p[l - 1][j];
            int a = r - l + 1 - b;
            ans = (ans + 1LL * (1 << j) * cal(a, b, x) % mod) % mod;
        }
        printf("%lld\n", ans);
    }

    return 0;
}
/**/

 

本文地址：https://blog.csdn.net/oneplus123/article/details/109267743