CSP-J2021试题题解

1.分糖果

原题：https://www.luogu.com.cn/problem/P7909

原代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,l,r;
int main(){
	cin>>n>>l>>r;
	if(r%n==n-1)cout<<n-1;
	else if(l%n==n-1)cout<<n-1;
	else if((r-(r%n)-1)>=l)cout<<n-1;
	else{
		ll ans=-1e9;
		for(ll i=l;i<=r;i++)ans=max(ans,i%n);
		cout<<ans;	
	}
	return 0;
}

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,l,r;
int main(){
	cin>>n>>l>>r;
	if(r-n<n)cout<<r-n; 
	else{
		ll ans=-1e9;
		for(ll i=l;i<=r;i++)ans=max(ans,i%n);
		cout<<ans;	
	}
	return 0;
}

解题思路：

当r-n<n时，直接输出r%n，否则遍历l到r，枚举每个数模n的最大值

错误原因：

直接遍历l到r，复杂度很高，所以超时

2.插入排序

原题：https://www.luogu.com.cn/problem/P7910

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4+255;
struct node{
	int id,v;
}a[N];
int w[N],n,q,op,x,y;
bool cmp(node a,node b){
	if(a.v==b.v)return a.id<b.id;
	return a.v<b.v;
}
void init(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i].v,a[i].id=i;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)w[a[i].id]=i;
}
void Solve(){
	while(q--){
		cin>>op>>x;
		if(op==1){
			cin>>y;
			int nump=w[x];
			if(a[nump].v>y){
				a[nump].v=y;
				for(int j=nump;j>1;j--){
					if(a[j].v<a[j-1].v||a[j].v==a[j-1].v&&a[j].id<a[j-1].id){
						w[a[j].id]=j-1;
						w[a[j-1].id]=j;
						swap(a[j],a[j-1]);
					}else break; 
				}
			}else if(a[nump].v<y){
				a[nump].v=y;
				for(int j=nump;j<n;j++){
					if(a[j].v>a[j+1].v||a[j].v==a[j+1].v&&a[j].id>a[j+1].id){
						w[a[j].id]=j+1;
						w[a[j+1].id]=j;
						swap(a[j],a[j+1]);
					}else break; 
				}
			}
		}else cout<<w[x]<<'\n';
	}
}
int main(){
	init();
	Solve();
	return 0;
}

解题思路：
这道题模拟会超时，可以定义一个数组，存储每个数的位置，每次更新数值时，更新排名，输出即可

3.网络连接

原题：https://www.luogu.com.cn/problem/P7911

代码：

#include<bits/stdc++.h>
#include<cstdio>
#define ll long long
using namespace std;
map<string,int>Ser;
int n;
bool isok(char s[]){
	int a=-1,b=-1,c=-1,d=-1,e=-1;
	int t=sscanf(s,"%d.%d.%d.%d:%d",&a,&b,&c,&d,&e);
	if(t!=5)return 0;
	if(a<0||a>255)return 0;
	if(b<0||b>255)return 0;
	if(c<0||c>255)return 0;
	if(d<0||d>255)return 0;
	if(e<0||e>65535)return 0;
	char s1[35];
	sprintf(s1,"%d.%d.%d.%d:%d",a,b,c,d,e);
	int len=strlen(s);
	for(int i=0;i<len;i++)if(s[i]!=s1[i])return 0;
	return 1;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		char op[35],s[35];
		cin>>op>>s;
		if(op[0]=='S'){
			if(!isok(s))cout<<"ERR\n";
			else if(Ser.count(s))cout<<"FAIL\n";
			else Ser[s]=i,cout<<"OK\n";
		}else if(op[0]=='C'){
			if(!isok(s))cout<<"ERR\n";
			else if(!Ser.count(s))cout<<"FAIL\n";
			else cout<<Ser[s]<<'\n';
		}
	}
	return 0;
}

解题思路：

大模拟，按题目要求模拟即可

4.小熊的果篮

原题：https://www.luogu.com.cn/problem/P7912

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+255;
struct node{
	int v,pre,next;
}a[N];
int n,tb[N][3],js=0;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].v);
		a[i].pre=i-1;
		a[i].next=i+1;
	}
	a[0].v=a[0].pre=-1;
	a[0].next=1;
	js=1;
	tb[1][0]=tb[1][1]=tb[1][2]=1;
	for(int i=2;i<=n;i++){
		if(a[i].v==a[tb[js][1]].v){
			tb[js][1]=i;
			tb[js][2]++;
		}else{
			tb[++js][0]=i;
			tb[js][1]=i;
			tb[js][2]=1;
		}
	}
	while(js){
		int js1=0;
		for(int i=1;i<=js;i++){
			printf("%d ",tb[i][0]);
			int p=tb[i][0];
			tb[i][0]=a[p].next;
			a[a[p].pre].next=a[p].next;
			a[a[p].next].pre=a[p].pre;
			if(tb[i][2]>=2){
				if(js1==0||a[tb[i][0]].v!=a[tb[js1][1]].v){
					tb[++js1][0]=tb[i][0];
					tb[js1][1]=tb[i][1];
					tb[js1][2]=tb[i][2]-1;
				}else{
					tb[js1][1]=tb[i][1];
					tb[js1][2]+=tb[i][2]-1;
				}
			}
		}
		puts("");js=js1;
	}
	return 0;
}

解题思路：

双向链表模拟即可