题解：CF1729F Kirei and the Linear Function

这是蓝？？？？？？

首先把

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

，所以要用最小值和次小值。

CPP

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;
    }
}

题解：CF1729F Kirei and the Linear Function

文章操作

相关推荐

评论

题解：CF1729F Kirei and the Linear Function