CF1729F Kirei and the Linear Function

2022-09-13

字数统计: 1.2k | 阅读时长≈ 5 分钟

题意

有 $T$ 组数据。给你一个长度为 $n$ 十进制的数字串 $s$ 和整数 $w$ 。定义s的一个子串的价值为 $v(l,r)=l到r的数字大小(不含前导0),1\leq l \leq r\leq n$

例如 $n=7,s=1003004$ ，则 $v(1,3)=100,v(2,3)=0,v(2,7)=3004$

处理 $m$ 个询问，第 $i$ 个询问对应三个整数 $l_i,r_i,k_i(1\leq l_i \leq r_i\leq n,0\leq k_i \leq 8)$ ，找到一组 $L_1,L_2(L_1 \neq L_2 )$ ，使得

v(L_1,L_1+w-1)\cdot v(l_i,r_i)+v(L_2,L_2+w-1) \equiv k_i \pmod 9

无解输出"-1 -1"，有解则输出 $L_1$ 最小的解，若有多组数据满足 $L_1$ 最小，输出 $L_2$ 最小的解

数据范围： $1\leq T\leq 10^4,1\leq n\leq 2\cdot 10^5,1\leq m\leq 2\cdot 10^5$ ， $T$ 组数据中所用的 $n,m$ 之和均不超过 $2\cdot 10^5$

思路

因为有我们有模 $9$ 的条件，可以快速预处理出所有的 $v(i,i+w-1)\bmod 9,i\in [1,n-w+1]$ ，但处理询问的 $v(l_i,r_i)$ 仍会让复杂度超标。

但 $9$ 是一个及其特殊的模数，设一个整数 $x$ ，那么 $x \equiv x的各位数字之和 \pmod 9$ ，因此只需要算出每一位数的前缀和就能快速算出所有的 $v(l,r),1\leq l\leq r\leq n$

解决的计算 $v(l,r)$ 的问题之后，还需要知道怎么快速找到满足条件的 $L_1,L_2$ ，暴力需要两层枚举，明显不行。我们又可以从模 $9$ 的角度出发，处理出的 $v(l,r)$ 满足 $v(l,r)\in [0,8]$ ，只用两层循环 $0$ ~ $8$ 中满足条件的数就行了，这样询问就控制在了 $O(1)$

预处理时记录 $v(i,i+w-1)$ 模 $9$ 后的数第一次出现的位置 $f[v(i,i+w-1)]$ 和第二次出现的位置 $g[v(i,i+w-1)]$ 。为什么要记录这个 $g[i]$ 呢？因为当取的两个数相同时，需要不同的 $L_1,L_2$ 。询问时枚举 $0$ ~ $8$ 中出现过的数，满足条件则记录答案。

代码

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+9;
int T,w,m,a[N],f[10],g[10];
char s[N];

int get(char c){
    return c-'0';
}
int v(int l,int r){
    return ((a[r]-a[l-1])%9+9)%9;//防止负数
}

int main(){
    scanf("%d",&T);
    while(T--){
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        scanf("%s",s+1);
        int n=strlen(s+1);
        scanf("%d%d",&w,&m);
        for(int i=1;i<=n;i++) a[i]=(a[i-1]+get(s[i]))%9;//前缀和
        for(int i=1;i<=n-w+1;i++){//预处理
            int x=v(i,i+w-1);
            if(!f[x]) f[x]=i;
            else if(!g[x]) g[x]=i;
        }
        int l,r,k;
        while(m--){
            bool flag=1;
            scanf("%d%d%d",&l,&r,&k);
            int x=v(l,r),ans1=N,ans2=N;
            for(int i=0;i<9;i++){
                for(int j=0;j<9;j++){
                    if(f[i]&&f[j]&&(x*i+j)%9==k){//出现过且满足条件
                        if(i!=j){//特判一下i=j的时候
                            //按照题意模拟就行
                            if(ans1>f[i]) ans1=f[i],ans2=f[j];
                            else if(ans1==f[i]&&ans2>f[j]) ans2=f[j];
                            flag=0;
                        }
                        else{
                            if(!g[i]) continue;
                            if(ans1>f[i]) ans1=f[i],ans2=g[j];
                            else if(ans1==f[i]&&ans2>g[j]) ans2=g[j];
                            flag=0;
                        }
                    }
                }
            }
            if(flag) printf("-1 -1\n");
            else printf("%d %d\n",ans1,ans2);
        }
    }
    return 0;
}

打赏

版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！