2021CSP-J普及组题解

今年的题目如果只会模拟的话，也是可以拿普及一等的。虽然不太明白为啥今年的题目风格变成这样，但是也说明了一点：思维比算法往往更加重要。当然不是说算法不重要，只是我觉得很多时候算法限制了我们的思维。很多题目其实不用算法也可以做，但是一味地往算法上套，对我们的能力提升是帮助不大的。

T1 分糖果

简单的模拟题。但是 $1 0^{9}$ 的数据量肯定是会炸的。因此看看有没有数学方法可以套。

可知最多可以拿的糖果数量是n-1。

那么先对k=L%n，至少是可以拿到k颗糖果的。现在考虑能多拿几颗。由于最多是R颗糖，如果n-1-k+L<=R，那么就可以拿到n-1颗糖果。否则我的数量就是R%n颗了。代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,L,R;
	cin>>n>>L>>R;
	int k=L%n;
	k=n-1-k;
	if(k+L<=R)cout<<n-1<<endl;
	else cout<<R%n<<endl;
}

T2 插入排序

这题比第三题出的好一点（个人感觉）。

主要是两种操作：

（1）修改 $a_{x} = v$ ，同时修改以后会影响后续操作。

（2）询问 $a_{x}$ 在排序后的位置

数据范围： $n < = 8000, Q < = 200000$

其中操作（1）最多5000次。

这个操作1的限制很关键，从数据范围来看，直接做肯定是会超时的。

在每次做操作（1）的时候，显然是不能直接去重新排一遍序的。最好是O(n)的复杂度能够解决掉这个改变数值大小以后的顺序问题。

这里可以借助一个新的b数组，记录下b[x]表示位置为x的数(即 $a_{x}$ )的排序后的位置。

首先我们可以知道，对于某个数字x来说，我们可以扫一遍数组元素O(n)来计算出x能排到的位置。（~~没错，这个思路我第一次是在高中vb题里遇到的~~）具体是这样的：

int pos=0;
for(int i=1;i<=n;i++){
	if(a[i]>x)pos++;
    if(a[i]==x&&i<x)pos++;
}

那么当我们执行操作1的时候，我们可以计算一次这个a[x]现在的新的排序位置ans。那么对于a[x]元素来说，原来的位置是b[x]，现在的位置要改成ans，显然我们可以分两个情况：

①ans<b[x]

②ans>b[x]

现在问题转变成了在b数组中将ans插入，将b[x]删除。有点像插入排序的感觉。那么我们只需要重新维护位置处于[ans,b[x]]或者[b[x],ans]的数字位置就可以了。具体见代码：

#include<bits/stdc++.h>
using namespace std;
int n,q;
struct node{
	int a,idx;
}p[8008];
int b[8008],c[8008];
bool cmp(node x,node y){
	if(x.a==y.a)return x.idx<y.idx;
	return x.a<y.a;
}
int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>p[i].a;
		c[i]=p[i].a;
		p[i].idx=i;
	}
	sort(p+1,p+1+n,cmp);
	for(int i=1;i<=n;i++){
		b[p[i].idx]=i;    //第一次排序
	}
	while(q--){
		int t,x,v;
		scanf("%d",&t);
		if(t==2){
			scanf("%d",&x);
			printf("%d\n",b[x]);
		}
		else {
			scanf("%d%d",&x,&v);
			c[x]=v;
			int ans=1;
			for(int i=1;i<=n;i++){
				if(c[i]<c[x])ans++;
				if(c[i]==c[x]&&i<x)ans++;
			}
			if(ans>b[x]){
				for(int i=1;i<=n;i++){
					int tmp=b[i];
					if(tmp>b[x]&&tmp<ans)b[i]--;
					if(tmp==b[x]&&i>x)b[i]--;
					if(tmp==ans&&(i<x||c[i]<c[x]))b[i]--;  //相等的时候要考虑原本的位置
				}
			}
			if(ans<b[x]){
				for(int i=1;i<=n;i++){
					int tmp=b[i];
					if(tmp>ans&&tmp<b[x])b[i]++;
					if(tmp==ans&&(i>x||c[i]>c[x]))b[i]++;
					if(tmp==b[x]&&i<x)b[i]++;
				}
			}
			b[x]=ans;
		}
	}
}

那么这样的话，操作1最多5000次，每次复杂度O(n)，5000 * 8000=4e7，是可以通过本题的。

T3 网络连接

无敌打磨你（大模拟）。

主要是3种情况的判断。注意ip地址的地方要求严格是...:的形式，顺序和数量都不能出错。

还有一个就是前导0 的判断。

具体就。。码！（我代码实在太丑了。）

#include<bits/stdc++.h>
using namespace std;
struct node{
	int t,idx,a[26];
	string ans;
}p[1111];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		string op,ad;
		cin>>op>>ad;
		ad+='#';
		p[i].idx=i;
		int tmp=0,tt=0,dian=0,mao=0,flag=0,qian=0;
		for(int j=0;j<ad.size();j++){
			if(flag)break;
			if(ad[j]>='0'&&ad[j]<='9'){
				tmp=tmp*10+ad[j]-'0';
				if(qian==0&&ad[j]=='0'){
					if(ad[j+1]>='0'&&ad[j+1]<='9'){
						flag=1;break;
					}	
					qian=1;
				}
				else qian=1;
				if(tmp>65535){
					flag=1;break;
				}
			}
			else {
				if(qian==0)flag=1;
				qian=0;
				p[i].a[++tt]=tmp;
				if(tt<=4){
					if(tmp>255)flag=1;
				}
				if(tt==5){
					if(tmp>65535)flag=1;
				}
				if(tt>5)flag=1;
				tmp=0;
				if(ad[j]=='.')dian++;
				if(ad[j]==':'){
					if(dian!=3)flag=1;
					mao++;
				}
			}
		}
		if(dian!=3||mao!=1)flag=1;
		if(flag){
			p[i].t=-1;
			p[i].ans="ERR";
			cout<<p[i].ans<<endl;
			continue;
		}	
		if(op[0]=='S'){
			p[i].t=1;
			int flag2;
			for(int j=1;j<i;j++){
				if(p[j].t==1){
					flag2=0;
					for(int k=1;k<=5;k++){
						if(p[j].a[k]!=p[i].a[k])flag2=1;
					}
					if(flag2==0){
						flag2=-1;
						p[i].ans="FAIL";
						cout<<p[i].ans<<endl;
						p[i].t=-2;
						break;
					}
				}
			}
			if(flag2!=-1){
				p[i].ans="OK";
				cout<<p[i].ans<<endl;
				p[i].t=1;
			}
		}
		else {
			p[i].t=2;
			int flag2;
			for(int j=1;j<=n;j++){
				if(i==j)continue;
				flag2=0;
				if(p[j].t==1){
					//cout<<i<<endl;
					for(int k=1;k<=5;k++){
					
						if(p[j].a[k]!=p[i].a[k])flag2=1;
					}
					if(flag2==0){
						flag2=-1;
						cout<<j<<endl;
						break;
					}
				}
			}
			if(flag2!=-1)cout<<"FAIL"<<endl;
		}
	}


	return 0;
}

T4 小熊的果篮

这题模拟也能拿70分。其实我觉得给个50分差不多了吧。。自己模拟了个双向链表，80分。原来要两个链表，因为如果一个链表的话，合并以后就很难记录编号，所以两个链表比较合理。

在洛谷上看了个用set的做法，感觉挺好的。具体是这样：

先记录下0和1出现的位置，分别放入到两个set中。

例如样例1：

0出现的位置： 3 4 8 11 12

1出现的位置： 1 2 5 6 7 9 10

第一次我们从0和1中找到最小的那个数字，这里是1(1)，并且令now=1。

那么下一次我们从set0中选最小的大于now的，这里是3(0)，令now=3。

下一次从set1中选最小的大于now的，这里是5(0)，令now=5。

这样我们可以发现每次交替从两个set中找大于now的数，并且及时更新now。

当找不到大于now的值时，说明当前这趟结束了。可以继续下一趟。

上面这个过程我们可以用set来模拟，复杂度为O(nlogn)

#include<bits/stdc++.h>
using namespace std;
set<int>st0,st1;
int main()
{
	int n,t1,t0;
	t1=t0=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		if(x==0)st0.insert(i);
		else st1.insert(i);
	}
	st0.insert(n+1);
	st1.insert(n+1);
	while(st0.size()>1||st1.size()>1){
		int f=0;
		int p=0,q=0;
		int now=0;
		p=*st0.upper_bound(now);
		q=*st1.upper_bound(now);
		while(p!=n+1||q!=n+1){
			p=*st0.upper_bound(now);
			q=*st1.upper_bound(now);
			if(now==0){		
				if(p==n+1){
					printf("%d ",q);
					now=q;
					st1.erase(q);
					f=0;
				}
				else if(q==n+1){
					printf("%d ",p);
					now=p;
					st0.erase(p);
					f=1;
				}
				else {
					if(q<p){
						printf("%d ",q);
						now=q;
						st1.erase(q);
						f=0;
					}
					else {
						printf("%d ",p);
						now=p;
						st0.erase(p);
						f=1;
					}
				}
			}
			else {
				if(f==0){
					f=1;
					p=*st0.upper_bound(now);
					if(p!=n+1){
						printf("%d ",p);
						now=p;
						st0.erase(p);
					}
					else break;
					
				}
				else {
					f=0;
					q=*st1.upper_bound(now);
					if(q!=n+1){
						printf("%d ",q);
						now=q;
						st1.erase(q);
					}
					else break;
					
				}
			}
		}
		cout<<endl;
		
	}
}