全部栏目

首页 操作系统 后端开发 数据库 前端开发 移动端开发
您的当前位置：首页正文

【非官方题解】2022牛客寒假算法基础集训营5

2024-11-25 来源：个人技术集锦

A-疫苗小孩

解题思路：考虑每一针对答案的贡献，可以发现第一针对手速提升没有贡献，只有第二针和第三针对手速提升有贡献，并且贡献值分别与第一二针的间隔、第二三针的间隔有关。可以考虑枚举第二针，这样确定第二针的情况下左右二分第一针和第三针找可以打针的最佳位置，最后再取个最大值即可。下面代码是先预处理出了所有可以打针的位置，然后进行二分查找最佳位置。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1000005;
char s[N];
int pos[N];

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, cnt = 0;
    scanf("%d%s", &n, s + 1);
    for(int i = 1; i <= n; i++){
        if(s[i] == '0') pos[cnt++] = i;
    }
    pos[0] = -0x3f3f3f3f, pos[cnt] = 0x3f3f3f3f;
    ll k, w, q;
    scanf("%lld%lld%lld", &k, &w, &q);
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ll res = 0, t1 = 0, t2 = 0;
        if(s[i] == '0'){
            int p = lower_bound(pos, pos + cnt, i - k) - pos;
            t1 = w - abs(i - k - pos[p]) * q;
            t2 = w - abs(i - k - pos[p - 1]) * q;
            res += max(max(t1, t2), (ll)0);
            p = lower_bound(pos, pos + cnt, i + k) - pos;
            t1 = w - abs(i + k - pos[p]) * q;
            t2 = w - abs(i + k - pos[p - 1]) * q;
            res += max(max(t1, t2), (ll)0);
        }
        ans = max(ans, res);
    }
    printf("%lld\n", ans);
    return 0;
}

B-乒乓小孩

原题链接：

解题思路：根据题目的要求进行简单的（不是）分类讨论即可。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>
#include <vector>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
vector<pair<int, int> > ans;

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    scanf("%d", &t);
    while(t--){
        ans.clear();
        int x, y, flag = 0;
        scanf("%d%d", &x, &y);
        if(x < y){
            swap(x, y);
            flag = 1;
        }
        if(x < 11){
            printf("NO\n");
            continue;
        }
        int q = y;
        while(q >= 11 && (x - q + 2) % 11) q--;
        if(q >= 11){
            ans.push_back({q - 2, q});
            x -= q - 2;
            y -= q;
        }
        while(y >= 11){
            if(x % 11 == 10){
                ans.push_back({9, 11});
                x -= 9;
                y -= 10;
            }
            else{
                ans.push_back({x % 11, 11});
                x -= x % 11;
                y -= 11;
            }
        }
        if(10 * x == 11 * y){
            printf("NO\n");
            continue;
        }
        q = y;
        while((x - (q + 2)) % 11 && q + 2 >= 11) q--;
        if(q + 2 >= 11){
            ans.push_back({q + 2, q});
            x -= q + 2;
            y -= q;
        }
        if(x % 11){
            printf("NO\n");
            continue;
        }
        printf("YES\n");
        while(x){
            ans.push_back({11, y});
            y = 0;
            x -= 11;
        }
        printf("%d\n", ans.size());
        if(flag){
            for(auto i : ans){
                printf("%d %d\n", i.second, i.first);
            }
        }
        else{
            for(auto i : ans){
                printf("%d %d\n", i.first, i.second);
            }
        }
    }
    return 0;
}

C-战棋小孩

原题链接：

解题思路：由于每场使用礼遇和不使用礼遇对答案的贡献是不同的，而对于不同的情况，使用礼遇和不使用礼遇对答案的贡献无法很好的判断出来，因此需要枚举每一种使用礼遇的组合，最后再将每种的上榜次数取最大值。这里枚举组合用到了状压枚举的方法，即可以令 1 代表使用礼遇，0 代表不使用礼遇，将 n 局游戏抽象成 n 位的二进制数，枚举一遍则是 

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 25;
int p[N], v[N], w[N], h[N];    // v[]存储每场不使用礼遇的最大值
                               // w[]存储每场使用礼遇的最大值
                               // h[]存储每种使用礼遇的组合中每场的最大值
int n, k, s;

int check(int x){
    int res = 0;
    while(x){
        if(x & 1) res++;
        x >>= 1;
    }
    return res;
}

int cal(int x){
    for(int i = 0; i < n; i++){
        h[i + 1] = ((x >> i) & 1) ? w[i + 1] : v[i + 1];    // ((x>>1)&1)判断第i场是否使用礼遇
    }
    sort(h + 1, h + n + 1);
    int sum = s, res = 0;
    for(int i = 1; i <= n; i++){
        sum += h[n - i + 1];
        if(sum >= p[i]) res++;
    }
    return res;
}

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k >> s;
    for(int i = 1; i <= n; i++) cin >> p[i];
    for(int i = 1; i <= n; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        v[i] = max(a, b);
        w[i] = max(v[i], max(c, d));
    }
    int ans = 0;
    for(int i = 0; i < (1 << n); i++){    // 状压枚举，二进制中有1则代表使用礼遇
        if(check(i) == k) ans = max(ans, cal(i));
    }
    cout << ans << endl;
    return 0;
}

D-数位小孩

原题链接：

解题思路：从一位数开始暴搜每一个符合条件的数，每一次在当前数的末尾加上新的数，判断是否符合题目条件，符合则继续搜，否则就返回，然后只要得到的数落在所给的区间 

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
ll l, r, ans;

bool isprime(ll x){
    if(x == 0 || x == 1) return false;
    for(ll i = 2; i * i <= x; i++){
        if(x % i == 0) return false;
    }
    return true;
}

void dfs(ll x, int last, int flag){
    if(x > r) return;
    if(x >= l && flag) ans++;
    for(int i = 0; i <= 9; i++){
        if(isprime(i + last)){
            dfs(x * 10 + i, i, flag || (i == 1));
        }
    }
}

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> l >> r;
    for(int i = 1; i <= 9; i++){
        dfs(i, i, i == 1);
    }
    cout << ans << endl;
    return 0;
}

E-复苏小孩

原题链接：

题目大意：给定一个只含 1，2，3 的字符串，三个鬼的初始能量均为 1，每次遇到 1 时，鬼一吸收鬼二和鬼三各一半能量；遇到 2 时，鬼二吸收鬼一和鬼三各一半的能量；遇到 3 时，鬼三吸收鬼一和鬼二各一半的能量。然后每次询问有两种操作，一种是将字符串某点进行修改，另一种是询问进行字符串某个区间后三者的能量。

解题思路：对于每种情况，如果遇到 1，那么三者能量的变化为

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

#define mid (l + r >> 1)

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 100005;
char c;

ll quick_pow(ll a, ll b){
	ll res = 1;
	while(b){
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

ll inv(ll x){
	return quick_pow(x, mod - 2);
}

struct Matrix{    // 矩阵
    ll c[3][3] = {
        {0, 0, 0},
        {0, 0, 0},
        {0, 0, 0}
    };
}ans;
 
Matrix operator * (Matrix A, Matrix B){    // 矩阵乘法重载
    Matrix C;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            for(int k = 0; k < 3; k++){
                C.c[i][j] = (C.c[i][j] + A.c[i][k] * B.c[k][j] % mod) % mod;
            }
        }
    }
    return C;
}

void init(Matrix &m){
    ll t = 1 * inv(2) % mod;
    Matrix emp;
    m = emp;
    if(c == '1'){
        m.c[0][0] = 1;
        m.c[1][0] = t;
        m.c[1][1] = t;
        m.c[2][0] = t;
        m.c[2][2] = t;
    }
    if(c == '2'){
        m.c[0][0] = t;
        m.c[0][1] = t;
        m.c[1][1] = 1;
        m.c[2][1] = t;
        m.c[2][2] = t;
    }
    if(c == '3'){
        m.c[0][0] = t;
        m.c[0][2] = t;
        m.c[1][1] = t;
        m.c[1][2] = t;
        m.c[2][2] = 1;
    }
}

struct node{
    int l, r;
    Matrix val;
}tree[N << 2];

void sgt_build(int i, int l, int r){    // 建线段树
    tree[i].l = l;
    tree[i].r = r;
    if(l == r){
        c = getchar();
        init(tree[i].val);
        return;
    }
    sgt_build(i << 1, l, mid);
    sgt_build(i << 1 | 1, mid + 1, r);
    tree[i].val = tree[i << 1].val * tree[i << 1 | 1].val;
}

void sgt_modify(int i, int x, int y){  // 单点修改
    int l = tree[i].l, r = tree[i].r;
    if(l == r){
        c = (char)y + '0';
        init(tree[i].val);
        return;
    }
    if(x <= mid) sgt_modify(i << 1, x, y);
    else sgt_modify(i << 1 | 1, x, y);
    tree[i].val = tree[i << 1].val * tree[i << 1 | 1].val;
}

void sgt_query(int i, int x, int y){   // 区间查询
    int l = tree[i].l, r = tree[i].r;
    if(l >= x && r <= y){
        ans = ans * tree[i].val;
        return;
    }
    if(x <= mid) sgt_query(i << 1, x, y);
    if(y > mid) sgt_query(i << 1 | 1, x, y);
}

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    scanf("%d%d", &n, &m);
    getchar();
    sgt_build(1, 1, n);
    for(int i = 1; i <= m; i++){
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if(op == 1){
            sgt_modify(1, x, y);
        }
        if(op == 2){
            for(int i = 0; i < 3; i++){
                for(int j = 0; j < 3; j++){
                    ans.c[i][j] = (i == j) ? 1 : 0;
                }
            }
            sgt_query(1, x, y);
            Matrix p;
            p.c[0][0] = p.c[0][1] = p.c[0][2] = 1;
            p = p * ans;
            cout << p.c[0][0] << ' ' << p.c[0][1] << ' ' << p.c[0][2] << endl;
        }
    }
    return 0;
}

F-飞车小孩

原题链接：

解题思路：按照九峰胜率将每个地图进行排序，如果九峰选图，那么一定是从最右边开始选；如果K0u1e选图，那么一定是从最左边开始选。假设当前是第一条信息，游戏进行到第x局，九峰选了第y张图，那么根据排序后这张图的位置就可以判断之前进行的 x - 1 局中九峰选择的局数，设选择过 t 局，那么 t = n - pos + 1。那么在这之前的选图情况一共就有 

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 100005;
ll t[N], fac[N], invfac[N];    // t[i]存储第i张地图位于胜率排序后的位置
                               // fac[]存储阶乘,invfac[]存储阶乘的逆元

struct graph{    // 地图信息
    ll id, x, y;
    bool operator < (const graph &u) const{
        return x * u.y < u.x * y;
    }
}g[N];

struct message{    // 比赛信息
    ll op, x, y;
    bool operator < (const message &u) const{
        return x < u.x;
    }
}m[N];

ll quick_pow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

ll C(ll a, ll b){
    return fac[a] * invfac[b] % mod * invfac[a - b] % mod;
}

void init(){
    fac[0] = invfac[0] = 1;
    for(int i = 1; i <= N; i++){
        fac[i] = fac[i - 1] * i % mod;
        invfac[i] = invfac[i - 1] * quick_pow(i, mod - 2) % mod;
    }
}

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    init();
    for(int i = 1; i <= n; i++){
        cin >> g[i].x >> g[i].y;
        g[i].id = i;
    }
    sort(g + 1, g + n + 1);
    for(int i = 1; i <= n; i++){
        t[g[i].id] = i;
    }
    for(int i = 1; i <= k; i++) cin >> m[i].op >> m[i].x >> m[i].y;
    sort(m + 1, m + k + 1);
    int l = 0, r = n + 1;
    ll ans = 1;
    for(int i = 1; i <= k; i++){
        int lastl = l, lastr = r;
        if(m[i].op == 1){
            r = t[m[i].y];
            l += m[i].x - m[i - 1].x - (lastr - r);
            ans = ans * C(m[i].x - m[i - 1].x - 1, lastr - r - 1) % mod;
        }
        if(m[i].op == 2){
            l = t[m[i].y];
            r -= m[i].x - m[i - 1].x - (l - lastl);
            ans = ans * C(m[i].x - m[i - 1].x - 1, l - lastl - 1) % mod;
        }
    }
    ans = ans * quick_pow(2, r - l - 1) % mod;
    cout << ans << endl;
    return 0;
}

G-163小孩

原题链接：

解题思路：在自己的编译器上暴力枚举出答案即可（当然也可以用排列组合计算答案）。

暴力代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;

bool check(int i, int j, int k, int x, int y, int z){
	if(i == j && i == k && i == x && i == y) return true;
	if(i == j && i == k && i == x && i == z) return true;
	if(i == j && i == k && i == y && i == z) return true;
	if(i == j && i == x && i == y && i == z) return true;
	if(i == k && i == x && i == y && i == z) return true;
	if(j == k && j == x && j == y && j == z) return true;
	return false;
}

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int cnt = 0;
    for(int i = 1; i <= 13; i++){
    	for(int j = i; j <= 13; j++){
    		for(int k = j; k <= 13; k++){
    			for(int x = k; x <= 13; x++){
    				for(int y = x; y <= 13; y++){
    					for(int z = y; z <= 13; z++){
    						if(check(i, j, k, x, y, z)) continue;
							cnt++;
						}
					}
				}
			}
		}
	}
	cout << cnt << endl;
    return 0;
}

最终答案：18395

H-一六三小孩

原题链接：

解题思路：瞎搞题，不想补了OvO

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>
#include <vector>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
vector<int> p[14][14][14];
vector<string> s[14][14][14];

string CHG(int x){
    if(x==1) return "A";
    if(x==10) return "T";
    if(x==11) return "J";
    if(x==12) return "Q";
    if(x==13) return "K";
    return to_string(x);
}

void solve(){
    vector<int> a(6);
    for(int i = 0; i < 6; i++){
        char c;
        while(c = getchar()){
            if(c == 'A' || c == 'J' || c == 'Q' || c == 'K' || c == 'T' || c >= '2' && c <= '9') break;
        }
        if(c == 'T') a[i] = 10;
        else if(c == 'A') a[i] = 1;
        else if(c == 'J') a[i] = 11;
        else if(c == 'Q') a[i] = 12;
        else if(c == 'K') a[i] = 13;
        else a[i] = c - '0';
    }
    for(int i = 1; i <= 10; i++){
        random_shuffle(a.begin(), a.end());
        for(int j = 0; j < 13; j++)
            for(int k = 0; k < 13; k++){
                int x = p[a[0]][a[1]][a[2]][j];
                int y = p[a[3]][a[4]][a[5]][k];
                if(x + y == 163){
                    cout << s[a[0]][a[1]][a[2]][j] << '+' << s[a[3]][a[4]][a[5]][k] << endl;
                    return;
                }
                if(y - x == 163){
                    cout << s[a[3]][a[4]][a[5]][k] << '-' << s[a[0]][a[1]][a[2]][j] << endl;
                    return;
                }
                if(x - y == 163){
                    cout << s[a[0]][a[1]][a[2]][j] << '-' << s[a[3]][a[4]][a[5]][k] << endl;
                    return;
                }
                if(x * y == 163){
                    cout << s[a[0]][a[1]][a[2]][j] << '*' << s[a[3]][a[4]][a[5]][k] << endl;
                    return;
                }
            }
    }
    cout << "OvO" << endl;
}

int main(){
    for(int i = 1; i <= 13; i++)
        for(int j = 1; j <= 13; j++)
            for(int k = 1; k <= 13; k++){
                p[i][j][k].emplace_back(i + j + k); s[i][j][k].emplace_back("(" + CHG(i) + "+" + CHG(j) + "+" + CHG(k) + ")");
                p[i][j][k].emplace_back(i + j - k); s[i][j][k].emplace_back("(" + CHG(i) + "+" + CHG(j) + "-" + CHG(k) + ")");
                p[i][j][k].emplace_back(i + j * k); s[i][j][k].emplace_back("(" + CHG(i) + "+" + CHG(j) + "*" + CHG(k) + ")");
                p[i][j][k].emplace_back(i - j + k); s[i][j][k].emplace_back("(" + CHG(i) + "-" + CHG(j) + "+" + CHG(k) + ")");
                p[i][j][k].emplace_back(i - j - k); s[i][j][k].emplace_back("(" + CHG(i) + "-" + CHG(j) + "-" + CHG(k) + ")");
                p[i][j][k].emplace_back(i - j * k); s[i][j][k].emplace_back("(" + CHG(i) + "-" + CHG(j) + "*" + CHG(k) + ")");
                p[i][j][k].emplace_back(i * j + k); s[i][j][k].emplace_back("(" + CHG(i) + "*" + CHG(j) + "+" + CHG(k) + ")");
                p[i][j][k].emplace_back(i * j - k); s[i][j][k].emplace_back("(" + CHG(i) + "*" + CHG(j) + "-" + CHG(k) + ")");
                p[i][j][k].emplace_back(i * j * k); s[i][j][k].emplace_back("(" + CHG(i) + "*" + CHG(j) + "*" + CHG(k) + ")");
                p[i][j][k].emplace_back((i + j) * k); s[i][j][k].emplace_back("((" + CHG(i) + "+" + CHG(j) + ")" + "*" + CHG(k) + ")");
                p[i][j][k].emplace_back((i - j) * k); s[i][j][k].emplace_back("((" + CHG(i) + "-" + CHG(j) + ")" + "*" + CHG(k) + ")");
                p[i][j][k].emplace_back(i * (j + k)); s[i][j][k].emplace_back("(" + CHG(i) + "*" + "(" + CHG(j) + "+" + CHG(k) + "))");
                p[i][j][k].emplace_back(i * (j - k)); s[i][j][k].emplace_back("(" + CHG(i) + "*" + "(" + CHG(j) + "-" + CHG(k) + "))");
            }
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

I-兔崽小孩

原题链接：

解题思路：由于每次睡着需要 k 分钟，因此需要处理出每两条说说的间隔时间，才能判断这期间是否睡着，将间隔时间排序，每次询问二分查找第一个大于 k 时间的间隔，将该点之后的间隔时间累加减去这若干次入睡时间即为总睡眠时间，可以用前缀和进行处理，每次询问查找，计算。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1000005;
ll t[N], dif[N], sum[N];
int n, q;

void init(){
    for(int i = 1; i < n; i++){
        dif[i] = t[i + 1] - t[i];
    }
    sort(dif + 1, dif + n);
    for(int i = 1; i < n; i++){
        sum[i] = sum[i - 1] + dif[i];
    }
}

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++) scanf("%lld", &t[i]);
    init();
    while(q--){
        ll k, p, ans = 0;
        scanf("%lld%lld", &k, &p);
        int pos = upper_bound(dif + 1, dif + n, k) - dif;
        ans = sum[n - 1] - sum[pos - 1] - k * (n - pos);
        if(ans >= p) puts("Yes");
        else puts("No");
    }
    return 0;
}

J-三国小孩

原题链接：

解题思路：对方为了存活，无论我发出杀还是决斗，对方必定要出一张牌（可以是闪、桃、决斗），因此在不知道手牌的情况下，对方可能存活的条件就是他的手牌数大于等于我方杀加决斗的数量，反之对手必败。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n, m, k;
    cin >> n >> m >> k;
    if(k >= n + m) cout << "NO" << endl;
    else cout << "YES" << endl;
    return 0;
}

K-造梦小孩

原题链接：

解题思路：对于水魔爆技能单点操作，可以直接用树状数组存储伤害值；对于玄冰阵技能，多个单点操作，如果 len 很大，那么也可以看作是几个单点操作，和水魔爆操作相同；如果 len 很小，操作很密集，那就不好直接操作了，这时候就需要用到分块操作。记表示最左端点为 j 的块的长度为 i 的伤害量，注意 x 位置不受伤害，故需要进行特判，或者直接单独对 x 点进行伤害减少的操作。对于查询，那些单点操作的查询可直接用树状数组的前缀和查询完成；对于分块的查询，枚举 len，对 x 来说，不满整块的贡献有 x / len + 1，整块的贡献有 x / len，令 k = x % len，则前缀和的贡献为。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

#define lowbit(x) (x & -x)

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 100005, M = 500;
ll tree[N];
ll block[M + 5][M + 5];
int n, m;

void add(int x, int y){
    while(x <= n){
        tree[x] += y;
        x += lowbit(x);
    }
}

ll ask(int x){
    ll res = 0;
    while(x > 0){
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}

ll query(int x){
    ll res = 0;
    for(int i = 1; i <= M; i++){
        if(x % i == 0) res += block[i][i] * (x / i);
        else res += block[i][x % i] * (x / i + 1) + (block[i][i] - block[i][x % i]) * (x / i);
    }
    return res;
}

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    while(m--){
        int op, x, y, len, l, r;
        cin >> op;
        if(op == 1){
            cin >> x >> y;
            add(x, y);
        }
        if(op == 2){
            cin >> x >> y >> len;
            if(len > M){
                for(int i = x % len == 0 ? len : x % len; i <= n; i += len){
                    add(i, y);
                }
            }
            else{
                for(int i = x % len == 0 ? len : x % len; i <= len; i++){
                    block[len][i] += y;
                }
            }
            add(x, -y);
        }
        if(op == 3){
            cin >> l >> r;
            cout << query(r) - query(l - 1) + ask(r) - ask(l - 1) << endl;
        }
    }
    return 0;
}
显示全文