题解：P9297 [POI 2020/2021 R1] Licznik długu / 债务计数器

snowfallen · 2026-06-23 15:13:49 · 题解

https://www.luogu.com.cn/discuss/1309091

花了 10min 乱实现了一下，一遍过了。

就是求两个高精度数的和的第 i 位的值，还会修改这两个数。

考虑压位，将 18 位压进一个 long long。

首先，先预处理 10 的幂。

前两个操作就是在对应位进行修改，因为这两个操作是 O(1)，常数写大了没关系，你随便写都可以，好像甚至可以直接把那个位置对应的大整数展开之后直接修改后再压回去。

如果你用 10 进制位运算写就会得到下面这一坨。

inline void updatea(int x,int v){
    A[x/18]+=(v-(A[x/18]/p[x%18])%10)*p[x%18];
}
inline void updateb(int x,int v){
    B[x/18]+=(v-(B[x/18]/p[x%18])%10)*p[x%18];
}

查询操作，从最低位开始遍历，只用处理到下一位是否进位，直接暴力遍历算就行了。

inline int ask(int x){
    int u=x/18,v=x%18;
    bool q=0;
    for(int i=0;i<u;i++) q=(A[i]+B[i]+q>=p[18]);
    return ((A[u]+B[u]+q)/p[v])%10;
}

然后就用 C++11 开 O2 一遍写过了，时间复杂度 O(n^2)，常数极小。

通过记录。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int A[100010/18+1],B[100010/18+1],p[19];
inline void updatea(int x,int v){
    A[x/18]+=(v-(A[x/18]/p[x%18])%10)*p[x%18];
}
inline void updateb(int x,int v){
    B[x/18]+=(v-(B[x/18]/p[x%18])%10)*p[x%18];
}
inline int ask(int x){
    int u=x/18,v=x%18;
    bool q=0;
    for(int i=0;i<u;i++) q=(A[i]+B[i]+q>=p[18]);
    return ((A[u]+B[u]+q)/p[v])%10;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m,p[0]=1;
    for(int i=1;i<=18;i++) p[i]=p[i-1]*10;
    for(int i=1;i<n;i++){
        char ch;
        cin>>ch;
        updatea(n-i,ch-'0');
    }
    for(int i=1;i<n;i++){
        char ch;
        cin>>ch;
        updateb(n-i,ch-'0');
    }
    while(m--){
        char opt;
        cin>>opt;
        if(opt=='W'){
            int x,y;
            cin>>x>>y;
            updatea(x,y);
        }
        if(opt=='Z'){
            int x,y;
            cin>>x>>y;
            updateb(x,y);
        }
        if(opt=='S'){
            int x;
            cin>>x;
            cout<<ask(x)<<"\n";
        }
    }
    return 0;
}