ccpc网络赛（重赛）E - Monopoly

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

Problem - 7130 (dingbacode.com)

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

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

贴个官方题解：

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

 先初始化（记录前缀）

#include
using namespace std;
const int N=5e5+100;
int m,n,a,sp=1;
typedef long long ll;
mapmp,mm;//mp是第一遍遍历时储存，mm存下标
vectordis[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< 
这一步还好理解，然后每个数对于整个数列的和肯定存在一个余数，当询问的数存在于这个余数之中的时候就存在，所以我们要同时记录余数和它们的位置
 
	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::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<0){
						int sz=dis[mm[num]].size();
						if(dis[mm[num]][0]>p)cout<<-1< 
分开处理两种情况的原因：由于我们前面处理了负数对于数列和的余数，所以我们后边也同时也得处理s为负数的情况。
 
这道题在理解题意上没有刻意难为人，在思维和实现上存在一些难度（建议自己debug）
 
最后给出ac代码
 
#include
using namespace std;
const int N=5e5+100;
int m,n,a,sp=1;
typedef long long ll;
mapmp,mm;//mp是第一遍遍历时储存，mm存下标
vectordis[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<0){
				int sz=dis[mm[num]].size();
				if(dis[mm[num]][0]>p)cout<<-1<t;
	while(t--){
		start();
		for(int i=1;i<=n;i++){
			scanf("%d",&a);
			ss[i]=ss[i-1]+a;
			//cout<::iterator it=mm.begin();it!=mm.end();it++){
				int x=it->second;
				sort(dis[x].begin(),dis[x].end());//小的排前面
			}//这一步不知道能不能用优先队列感觉写复杂了
		}
		
		
		while(m--){
			judge();
		}
	}
}
 
ccpc网络赛要我狗命啊！！！！！