CSP-X复赛模拟二——补题报告

时间：2024-10-04 19:30:21

                                                      2024.10.4

                                                  S08975 徐昱瑄

一、比赛情况

T1独木桥（bridge）：AC

T2移动棋子（chess）：50

T3动物园(zoo):0   答案错误

T4摧毁(destroy):0   答案错误

二、赛中概况

第一题用时30min，感觉还可以，第二题时间长了一些，用了1h10min，一直在修改；

剩下用40min做第三题，用了两种方法，一个暴力，一个双指针，但一直不对，最后放弃了；

第四题思考了，但没对样例，就直接输出样例了

三、补题报告

T1独木桥（bridge）：

长度为 L 米的独木桥上有 n 个人，他们每个人都想以最快的时间离开危险的独木桥。已知每个人在独木桥上的行走速度为 1 米 / 秒 ，每个人只要能走到独木桥的两个端点中的其中一个就可以离开独木桥。
由于独木桥的桥面宽度很窄，只能容纳一个人通过，当两个人相遇时，他们无法交错通过，只能各自调转方向，继续沿反方向行走。
给你独木桥上的人数 n ，独木桥的长度 L， 第 i 个人的初始位置到独木桥左端点的距离ai​​ 米（每个人开始的朝向未知，但他们可以根据需要随时调转行走的方向）。
请计算出所有人同时出发，全部都离开独木桥所需的最短时间。

题目分析：

题目中的相遇情况属于无用信息，只需要把每个人最快到达桥边的时间计算出来，再求一下最大值就可以了

AC代码：
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int l;
int maxx=0;
int a[1000005],b[1000005];//b是时间 
int main(){
//	freopen("bridge.in","r",stdin);
//	freopen("bridge.out","w",stdout);
	cin>>n>>l;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(l-a[i]<a[i]){
			b[i]=l-a[i]; 
		}
		else{
			b[i]=a[i];
		}
	}
	for(int i=1;i<=n;i++){
		maxx=max(b[i],maxx);
	}
	cout<<maxx;
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

T2移动棋子（chess）：

一维的棋盘上有无限多个格子，每个格子都有一个编号，最中间的格子编号为 0 ，0 号格子向右依次编号为 1,2,3,… ，向左依次编号为 −1, −2, −3,… 。
小明的目标是要将一枚棋子从 x 号格子移动到 y 号格子。
每一次操作有两种选择：
操作 1 ：向右移动 11 个格子。
操作 2 ：从当前棋子所在的 a 号格子，直接跳到 −a 号格子（如:可以从 6 直接跳到 −6 ，也可以从 −6 直接跳到 6 ）。
可以证明，无论整数 x 和 y 的值是多少，目标总是可以实现的。
请你设计程序，帮小明计算把棋子从 x 号格子移动到 y 号格子需要的最少操作次数。

题目大意：

共有两种操作，+1操作与~操作，问至少几次操作可以把x变成y；

题目分析：

这是一个模拟题，模拟12种情况，主要考查思维

错误点：

没有模拟出所有情况

AC代码：
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int x,y;
int a,b;
int ans;
int main(){
//	freopen("chess.in","r",stdin);
//	freopen("chess.out","w",stdout);
	cin>>x>>y;
	if(x*y<0){//x y异号
		ans=abs(abs(x)-abs(y))+1; 
	} 
	else if(x*y>0){
		if(x>y){
			ans=x-y+2;
		}
		else if(x<y){
			ans=y-x;
		}
	}
	else{
		ans=abs(x-y);
		if(x>y){
			ans=ans+1;
		}
	}
	cout<<ans;
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}
我的50分代码：
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int x,y;
int a,b;
int t;
int main(){
//	freopen("chess.in","r",stdin);
//	freopen("chess.out","w",stdout);
	cin>>x>>y;
	if(abs(x)==abs(y)){
		cout<<1;
		return 0;
	}
	else if(x<y){
		if(x>=0&&y>=0||x<0&&y<0){
			cout<<y-x;
		}
		else if(x<0&&y>=0){
			b=~y;
			t+=(b-x);
			t+=1;
			cout<<t;
		}
		return 0;
	}
	else if(x>y){
		if(x>=0){
			a=~x;
		}
		else{
			a=x;
		}
		if(y>=0){
			b=~y;
		}
		else{
			b=y;
		}
		t+=1;
		t+=b-a+1;
		cout<<t;
//		cout<<a<<" "<<b<<" "<<t<<endl;
	} 
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

T3动物园(zoo):

某动物园里有n个场馆和m种动物(m≤n)。

n个场馆的编号分别用 1,2,3,..,n 表示；m种动物的编号分别用 1,2,3,..,m 表示。每一个场馆中只饲养了一只动物，不同的场馆可能饲养着相同种类的动物。

这个动物园的门票比较特殊，游客在购买门票时必须说明要参观的场馆的起止编号a和b（起止编号会打印到游客购买的门票上），代表游客只能参观动物园的第a个场馆至第b个场馆（包含 a,b）里的动物，其他的场馆不能去。门票按一个场馆十元收费。

如果你购买的门票的起止场馆编号是 3 到 8，那么你需要花 60 元钱购买门票，只能观看3,4,5,6,7,8号场馆的动物。

小明希望看到动物园内所有种类的动物，同时小明是个非常节约的孩子，他希望花最少
的钱买门票。 请你帮小明计算：他最少需要花费多少钱买门票才能看到所有种类的动物（同
一种动物他可能不止看一个）。注意：小明只能买一张门票。

题目大意：

n个场馆，m种动物，问至少去几个场馆能看到所有动物

题目分析：

使用双指针解决本题，两个指针均在第一位。枚举可以选的情况，选最小值

错误点：

对于双指针何时移动不清楚

AC代码：
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
using namespace std; 
int n,m,a[1000005],v[1000005];
int main(){
//	freopen("zoo.in","r",stdin);
//	freopen("zoo.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int l=1,r=0,cnt=0,ans=0x3f3f3f3f;
	while(r<n){
		while(cnt<m&&r<n){
			r++;
			v[a[r]]++;
			if(v[a[r]]==1){
				cnt++;
			}
		}
		while(cnt==m){
			ans=min(ans,r-l+1);
			v[a[l]]--;
			if(v[a[l]]==0){
				cnt--;
			}
			l++;
		}
	}
	cout<<ans*10;
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}
我的代码：
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
using namespace std; 
int n,m,x[1000005];
int l=1,r;
int qian=0x3f3f3f3f;
bool b[2005],f=0;
int main(){
//	freopen("zoo.in","r",stdin);
//	freopen("zoo.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>x[i];
 	}
	r=n;
	while(l<r){ 
		bool f=1;
		for(int i=l;i<=r;i++){
			b[x[i]]=1;
			cout<<i<<" "<<b[x[i]]<<"  ";
		}
		for(int i=1;i<=m;i++){
			if(b[i]==0){
				f=0;
			}
		}
		cout<<l<<" "<<r<<"  ";
		if(f==0){
			l++;
			r--;
			continue;
		}
		else{
			qian=min
			((r-l+1)*10,qian);
			l++;
			r--;
		}
		cout<<qian<<"\n"; 
	}
	cout<<qian;
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

T4摧毁(destroy):

坐地日行八万里，巡天遥看一千河。

2077年，人类不仅仅是赛博科技得到了发展，太空技术也已经得到了极大的发展。地球的不同外轨道上已经充斥着各种功能用途的人造卫星。因为一个轨道上的卫星数量是有上限的，且卫星更新换代速度很快，如果想要发射新的卫星，需要把所有旧的卫星摧毁。

人类有两种不同的武器可以摧毁卫星，具体如下（其中PW为新的能量单位）：
(1)使用定点激光武器花费 1 PW 的代价摧毁任意轨道上指定的一个卫星。
(2)使用脉冲轨道武器花费 c PW 的代价把某一轨道上的所有卫星摧毁。

现在有n个旧卫星分布在不同的外轨道上，你的任务是摧毁这些旧卫星。给出这n个卫
星的轨道编号，求将这些卫星全部摧毁的最小代价是多少？

题目大意：

n个卫星，摧毁他们有两种操作，一个一个摧毁与一起摧毁，问最小代价是？

题目分析：

对于每个卫星，将其加入ai轨道；

对于每一个轨道，对比两种方式的代价，取较小值累加

错误点：

1.for循环下标不对

2.累加的数组下标不对

3.轨道数组开小

AC代码：
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
int t,n,c,x[1000005],k=1;
int d;
int s[1000005];
int main(){
//	freopen("destroy.in","r",stdin);
//	freopen("destroy.out","w",stdout);
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>n>>c;
		d=0;
		memset(s,0,sizeof(s));
		for(int j=1;j<=n;j++){
			cin>>x[j];
			s[x[j]]++;
		}
		for(int j=1;j<=n;j++){
			d+=min(s[j],c);
		}
		cout<<d<<"\n";
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}
我的代码：
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
int t,n,c,x[1000005],k=1;
int d;
int s[100005];
int main(){
//	freopen("destroy.in","r",stdin);
//	freopen("destroy.out","w",stdout);
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>n>>c;
		memset(s,0,sizeof(s));
		for(int j=1;j<=n;j++){
			cin>>x[j];
			s[x[j]]++;
		}
		for(int j=1;i<=n;i++){
			d+=min(s[k],c);
		}
		cout<<d<<"\n";
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

四、赛后总结：

这一次的经验是检查，对于每个题不要花费太多时间进行修改。第四个题完全可以AC的，但因为第二题时间太长，后面没时间了。

相关文章