题解：CF1729F Kirei and the Linear Function

lgx57 · 2024-12-18 19:25:03 · 题解

这是蓝？？？？？？

首先把 v(l,r) 转化成 (\sum_{i=l}^r s_i) \bmod 9。然后前缀和预处理，后面可以 O(1) 查询。

考虑到 w 固定，所以把所有长度为 w 的子串的 v 值插入到一个 map 中。然后暴力枚举 v(L_1,L_1+w-1) 和 v(L_2,L_2+w-1) 的值，判断是否满足条件，然后更新答案即可。

注意需要在 map 中插入 2 个数：最小值和次小值，因为可能会出现 v(L_1,L_1+w-1)=v(L_2,L_2+w-1) 的情况，这时不能取相同的 L ，所以要用最小值和次小值。

int query(int l,int r){
    return (sum[r]-sum[l-1]+9)%9;// 前缀和查询
}
void sol(){
    string s;
    cin>>s;
    int n=s.size();
    s=" "+s;
    for (int i=1;i<=n;i++){
        sum[i]=sum[i-1]+s[i]-'0';
        sum[i]%=9;
    }
    int len,q;
    cin>>len>>q;
    map<int,pii> mp;
    for (int i=1;i+len-1<=n;i++){
        int x=query(i,i+len-1);
        if (!mp.count(x)) mp[x]={i,0};
        else if (mp[x].se==0) mp[x].se=i;
    }
//  for (pair<int,pii> kk:mp) cout<<kk.fi<<' '<<kk.se.fi<<' '<<kk.se.se<<endl;
    while (q--){
        int l,r,x;
        cin>>l>>r>>x;
        int num=query(l,r);
        int ans1=1e9,ans2=1e9;
        for (int _=0;_<9;_++){
            for (int __=0;__<9;__++){
                if (!mp.count(_)) continue;
                if (!mp.count(__)) continue;
                if ((_*num%9+__)%9==x){
                    if (_==__&&mp[_].se==0) continue;//相等却只有一个数不能取
                    int xx=mp[_].fi;
                    int yy=(_==__?mp[_].se:mp[__].fi);//相等时要取次小值
//                  cout<<"!!! "<<_<<' '<<__<<' '<<xx<<' '<<yy<<endl;
                    if (xx<ans1) ans1=xx,ans2=yy;
                    else if (xx==ans1) ans2=min(ans2,yy);
                }
            }
        }
        if (ans1==1e9&&ans2==1e9) cout<<-1<<' '<<-1;
        else cout<<ans1<<" "<<ans2;
        cout<<endl;
    }
}