游记

CSP-J2021总结

2021-10-26 CSP-J2021总结

这次考试心态还可以，但是四道题只对了一道，两道超时，一道答案错误。做得不好，没有达到预期。除了第三题之外，其他题对拍全过，时间复杂度太高。

洛谷自测分数

分糖果 插入排序 网络连接 小熊的果篮 总分
AC 100 TLE 72 WA 25 TLE 70 267

1.分糖果

这道题做的还不错，想的时候没有花太多时间。

L和R数据范围达到了恐怖的$10^9$，很明显不能暴力，只能考虑$O(1)$。 首先求出一个数$t$，$t$是$R$左边的第一个满足$t$ $mod$ $n=n-1$的数。 然后再判断，这个$t$在不在$L$到$R$的区间内。 如果在，答案为$t$ $mod$ $n$。 如果不在，可以证明，答案为$R$ $mod$ $n$。

考场代码（AC代码） 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,l,r;
	scanf("%d%d%d",&n,&l,&r);
	int t=(n-1-l%n)+l;
	if(t<=r){
		printf("%d",t%n);
	}else{
		printf("%d",r%n);
	}
}

2.插入排序

考场上找出规律：可以用结构体+sort，先按照数值排序，数值相同的情况下按编号排序，于是就有了考场上$O(1)$修改的代码。 但是我忽略了一点，修改次数不超过5000，然后就悲剧了…… 下次一定要认真审题，不要忽略题目给你的任何一点提示或要求。

考场代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include<bits/stdc++.h>
using namespace std;
int n,q;
struct node{
	int x,y;
	bool operator <(const node &t)const{
		return x<t.x||(x==t.x&&y<t.y);
	}
}b[8001];
int a[8001];
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=q;i++){
//		memset(b,0,sizeof(b));
//		memset(num,0,sizeof(num));
		int t,x,y;
		scanf("%d",&t);
		if(t==1){
			scanf("%d%d",&x,&y);
			a[x]=y;
		}
		if(t==2){
			scanf("%d",&x);
			for(int j=1;j<=n;j++){
				b[j].x=a[j];
				b[j].y=j;
			}
			sort(b+1,b+n+1);
			for(int j=1;j<=n;j++){
				if(b[j].y==x){
					printf("%d\n",j);
				}
			}
		}
	}
}
【正解】

既然题目说了，排序不产生影响，那么我们不必在数组中进行排序，可以用$vector$。 其次，每次只修改一个数，也就意味着之前的排序结果可以重用，从而降低时间复杂度。 对于每一次修改，我们只需要：

  • 在$vector$中找到并删除这个数
  • 往$vector$中推入一个新的数，并维护数列单调性。 但是，这个数列是单调递增的，于是可以使用二分来降低时间复杂度。 于是就有了优秀的$O(nlogn)$的AC代码：
AC代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

//参考网址：https://www.cnblogs.com/chy12321/p/15456919.html#%E9%A2%98%E8%A7%A3
#include<bits/stdc++.h>
using namespace std;
int n,q;
struct node{
    int v,id;
    bool operator <(const node &t)const{
        return v<t.v||(v==t.v&&id<t.id);
    }
}a[8001];
vector<node> f;
int main(){
  scanf("%d%d",&n,&q);
  for(int i=1;i<=n;i++){
      scanf("%d",&a[i].v);
      a[i].id=i;
      f.insert(lower_bound(f.begin(),f.end(),a[i]),a[i]);
  }
  int tt,x,v;
  for(int i=1;i<=q;i++){
      scanf("%d",&tt);
      if(tt==1){
          scanf("%d%d",&x,&v);
          f.erase(lower_bound(f.begin(),f.end(),a[x]));
          a[x].v=v;
          f.insert(lower_bound(f.begin(),f.end(),a[x]),a[x]);
      }else{
          scanf("%d",&x);
          printf("%d\n",lower_bound(f.begin(),f.end(),a[x])-f.begin()+1);
      }
  }
}

网络连接

赤裸裸的大模拟，码农题，思路、判断什么的看题就行。 考场上一次性打完了，样例只有一个没过，实在调不出来了。

考场代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

#include<bits/stdc++.h>
using namespace std;
int n;
int a[101],nf,nk,b[101];
int vis[2001][101],vis1[2001][101],fuwu[2001];
bool check(int x,int y,int z,int k,int w,char a1,char a2,char a3,char a4){
	if(a1=='.'&&a2=='.'&&a3=='.'&&a4==':'&&x>=0&&x<=255&&y>=0&&y<=255&&z>=0&&z<=255&&k>=0&&k<=255&&w>=0&&w<=65535){
		return true;
	}
	return false;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		memset(a,0,sizeof(a));
		char t;
		bool flag1=true;
		while(1){
			t=getchar();
			if(t=='S'){
				flag1=true;
				break;
			}
			if(t=='C'){
				flag1=false;
				break;
			}
		}
		bool flag2=false,flag3=false;
		int x=0,cnt=0,cnt1=0;
		while(1){
			if(t=='\n'&&flag3==false){
				flag3=true;
			}
			if(flag3==true&&t=='\n'){
				break;
			}
			t=getchar();
			if(t>='0'&&t<='9'){
				flag2=true;
			}
			if(flag2){
				if(t>='0'&&t<='9'){
					x=x*10+(int)(t-'0');
				}else{
					b[++cnt1]=t;
					flag2=false;
					a[++cnt]=x;
					x=0;
				}
			}
		}
		if(!check(a[1],a[2],a[3],a[4],a[5],b[1],b[2],b[3],b[4])){
			printf("ERR\n");
		}else{
			if(flag1){
				bool flag4=true;
				for(int j=1;j<=nf;j++){
					int sum=0;
					for(int k=1;k<=5;k++){
						if(vis[j][k]==a[k]){
							sum++;
						}
					}
					if(sum==5){
						flag4=false;
						break;
					}
				}
				if(!flag4){
					printf("FAIL\n");
				}else{
					printf("OK\n");
					nf++;
					for(int j=1;j<=5;j++){
						vis[nf][j]=a[j];
					}
				}
			}else{
				bool flag4=true;
				int tt;
				for(int j=1;j<=nf;j++){
					int sum=0;
					for(int k=1;k<=5;k++){
						if(vis[j][k]==a[k]){
							sum++;
						}
					}
					if(sum==5){
						flag4=false;
						tt=j;
						break;
					}
				}
				if(flag4){
					printf("FAIL\n");
				}else{
					bool flag5=true;
					int pp;
					for(int j=1;j<=nk;j++){
						int sum=0;
						for(int k=1;k<=5;k++){
							if(vis1[j][k]==a[k]){
								sum++;
							}
						}
						if(sum==5){
							flag5=false;
							pp=j;
							break;
						}
					}
					if(!flag5){
						printf("%d\n",fuwu[pp]);
					}else{
						nk++;
						fuwu[nk]=tt;
						printf("%d\n",tt);
					}
				}
			}
		}
	}
}

至今仍未AC……

小熊的果篮

考试时的想法就是直接模拟，输出过的就标记。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include<bits/stdc++.h>
using namespace std;
int n;
int a[200001];
int main(){
	scanf("%d",&n);
	int la=-1,n1=n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(la!=a[i]){
			la=a[i];
			printf("%d ",i);
			a[i]=2;
			n1--;
		}
	}
	printf("\n");
	while(n1>0){
		la=-1;
		bool flag=false;
		for(int i=1;i<=n;i++){
			if(a[i]==2)continue;
			if(la!=a[i]){
				la=a[i];
				printf("%d ",i);
				flag=true;
				a[i]=2;
				n1--;
			}
		}
		if(flag)printf("\n");
	}
}

这样写肯定超时，目前还未AC。

总结一下

这次考试后三道题某谷给出的标签都是模拟，暴力，第一题是数学，数论。 三道模拟题写挂，很不应该，应该好好反思，为什么没有优化时间复杂度？第三题这种码农题练得也不多，总的来说情况不好，下次加油。

网上发现两个题解，可以参考参考：

第一个 第二个

Licensed under CC BY-NC-SA 4.0
© 2024 zswangziye
zswangziye's Blog
使用 Hugo 构建
主题 Stack 由 Jimmy 设计