[数据结构与算法]ccpc网络赛（重赛）E - Monopoly

考试的时候被这题搞得心态有点炸裂，一直没想明白怎么优化，调了一下午终于出来了

Problem - 7130 (dingbacode.com)

思路就是先用前缀把所有数遍历后，按照余数储存（这步很重要）。

在实现过程中遇到的问题不限于：1、stl好多，写着写着就乱了；2、排序过程中存实值还是存下标；3、对于s正负处理不一样

贴个官方题解：

?来到这里的肯定或多或少对于题解有点不解，我们分阶段解释

?先初始化（记录前缀）

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+100;
int m,n,a,sp=1;
typedef long long ll;
map<ll,ll>mp,mm;//mp是第一遍遍历时储存，mm存下标
vector<ll>dis[N];
ll ss[N];
void start(){
	mp.clear();
	mm.clear();
	for(int i=0;i<=N;i++){
		dis[i].clear();
	}
	memset(ss,0,sizeof(ss));
	cin>>n>>m;
	sp=1;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		start();
		for(int i=1;i<=n;i++){
			scanf("%d",&a);
			ss[i]=ss[i-1]+a;
			//cout<<ss[i]<<endl;
			if(mp[ss[i]]==0&&ss[i]!=0){
				mp[ss[i]]=i;
			}
		}

这一步还好理解，然后每个数对于整个数列的和肯定存在一个余数，当询问的数存在于这个余数之中的时候就存在，所以我们要同时记录余数和它们的位置

	if(ss[n]!=0){
			ll lst=abs(ss[n]);
			for(int i=1;i<=n;i++){
				ll pls=(ss[i]%lst+lst)%lst;//同时处理正负数的余数
				if(mm[pls]==0)mm[pls]=sp++;
				dis[mm[pls]].push_back(ss[i]);//分开储存而已，sp没啥特殊意义
			}
		
			for(map<ll,ll>::iterator it=mm.begin();it!=mm.end();it++){
				int x=it->second;
				sort(dis[x].begin(),dis[x].end());//小的排前面
			}//这一步不知道能不能用优先队列感觉写复杂了
		}

这步的储存位置不好理解，理解之后本题还有最后一步障碍

void judge(){
			ll p;
			scanf("%lld",&p);
			ll lst=abs(ss[n]);
			if(p==0)cout<<0<<endl;
			else if(lst==0){
				if(mp[p]!=0)cout<<mp[p]<<endl;
				else cout<<-1<<endl;
			}
			
			else {
				ll s=ss[n];
				ll num=(p%lst+lst)%lst;
				if(mm[num]!=0){
					if(s>0){
						int sz=dis[mm[num]].size();
						if(dis[mm[num]][0]>p)cout<<-1<<endl;
						else {
							int nn=upper_bound(dis[mm[num]].begin(),dis[mm[num]].end(),p)-dis[mm[num]].begin();
							ll ans=(p-dis[mm[num]][nn-1])/s*n+mp[dis[mm[num]][nn-1]];//余数处理
							cout<<ans<<endl;
						}
					}
					else if(s<0){
						int sz=dis[mm[num]].size();
						if(dis[mm[num]][sz-1]<p)cout<<-1<<endl;
						else {
							int nn=lower_bound(dis[mm[num]].begin(),dis[mm[num]].end(),p)-dis[mm[num]].begin();
                            ll ans=(p-dis[mm[num]][nn])/s*n+mp[dis[mm[num]][nn]];
                            cout<<ans<<endl;
						}
					}
				}else cout<<-1<<endl;
			}
			
		}

分开处理两种情况的原因：由于我们前面处理了负数对于数列和的余数，所以我们后边也同时也得处理s为负数的情况。

这道题在理解题意上没有刻意难为人，在思维和实现上存在一些难度（建议自己debug）

最后给出ac代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+100;
int m,n,a,sp=1;
typedef long long ll;
map<ll,ll>mp,mm;//mp是第一遍遍历时储存，mm存下标
vector<ll>dis[N];
ll ss[N];
void start(){
	mp.clear();
	mm.clear();
	for(int i=0;i<=N;i++){
		dis[i].clear();
	}
	memset(ss,0,sizeof(ss));
	cin>>n>>m;
	sp=1;
}
void judge(){
	ll p;
	scanf("%lld",&p);
	ll lst=abs(ss[n]);
	if(p==0)cout<<0<<endl;
	else if(lst==0){
		if(mp[p]!=0)cout<<mp[p]<<endl;
		else cout<<-1<<endl;
	}
			
	else {
		ll s=ss[n];
		ll num=(p%lst+lst)%lst;
		if(mm[num]!=0){
			if(s>0){
				int sz=dis[mm[num]].size();
				if(dis[mm[num]][0]>p)cout<<-1<<endl;
				else {
					int nn=upper_bound(dis[mm[num]].begin(),dis[mm[num]].end(),p)-dis[mm[num]].begin();
					ll ans=(p-dis[mm[num]][nn-1])/s*n+mp[dis[mm[num]][nn-1]];//余数处理
					cout<<ans<<endl;
					}
			}
			else if(s<0){
				int sz=dis[mm[num]].size();
				if(dis[mm[num]][sz-1]<p)cout<<-1<<endl;
				else {
					int nn=lower_bound(dis[mm[num]].begin(),dis[mm[num]].end(),p)-dis[mm[num]].begin();
                    ll ans=(p-dis[mm[num]][nn])/s*n+mp[dis[mm[num]][nn]];
                        cout<<ans<<endl;
				}
			}
		}else cout<<-1<<endl;
	}
}
int main(){
	int t;
	cin>>t;
	while(t--){
		start();
		for(int i=1;i<=n;i++){
			scanf("%d",&a);
			ss[i]=ss[i-1]+a;
			//cout<<ss[i]<<endl;
			if(mp[ss[i]]==0&&ss[i]!=0){
				mp[ss[i]]=i;
			}
		}
		
		if(ss[n]!=0){
			ll lst=abs(ss[n]);
			for(int i=1;i<=n;i++){
				ll pls=(ss[i]%lst+lst)%lst;//同时处理正负数的余数
				if(mm[pls]==0)mm[pls]=sp++;
				dis[mm[pls]].push_back(ss[i]);//分开储存而已，sp没啥特殊意义
			}
		
			for(map<ll,ll>::iterator it=mm.begin();it!=mm.end();it++){
				int x=it->second;
				sort(dis[x].begin(),dis[x].end());//小的排前面
			}//这一步不知道能不能用优先队列感觉写复杂了
		}
		
		
		while(m--){
			judge();
		}
	}
}

ccpc网络赛要我狗命啊！！！！！