2024.7.15 csp-j第一场模拟赛赛后总结

题目：

T1：P1211 [USACO1.3] 牛式 Prime Cryptarithmhttps://www.luogu.com.cn/problem/P1211

T2：P2035 [USACO08JAN] iCow Bhttps://www.luogu.com.cn/problem/P2035

T3：P6207 [USACO06OCT] Cows on Skates Ghttps://www.luogu.com.cn/problem/P6207

T4：P2903 [USACO08MAR] The Loathesome Hay Baler Shttps://www.luogu.com.cn/problem/P2903

T1 ：题目分析：

        模拟三位数和两位数，判断个个位置上的数是否在序列里出现。计算两个部分的乘积得到s1,s2；将两位数和三位数相乘得到s3,同样判断这三个数是否满足各自位数要求（s1,s2三位数，s3四位数）和各个数字都由序列中的数组成。如果都满足，答案++。最后输出答案。

        代码：

#include <bits/stdc++.h>
using namespace std;
bool p[15];
bool f(int n) { 
	while(n) {
		if(p[n%10]==0)
			return 0;
		n/=10;
	}
	return 1;
}
bool check(int x,int y) {
	int a=x*(y%10),b=x*(y/10),test=x*y;
	if(a>999 || b>999 || test>9999)
		return 0;
	if(f(x)==1 && f(y)==1 && f(a)==1 && f(b)==1 && f(test)==1)
		return 1;
	else
		return 0;
}
int main() {
	int n,key,ans=0;
	cin>>n;
	for(int i=0; i<n; i++) {
		cin>>key;
		p[key]=true;
	}
	for(int i=100; i<1000; i++) {
		for(int j=10; j<100; j++) { 
			if(check(i,j)==1)
				ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

错因：未读懂题意导致判断条件不全。

T2：题目分析：重复执行T次，每次打擂台选出最大值。然后将其值平均分给其余n-1首曲子，它本身的权值清零。如果一首曲子的权值无法被平均分配（也就是说，无法被 N−1 整除），那么被除的余数部分将会以 1 为单位，顺次分配给排名靠前的曲子（也就是说，顺序为曲目 1 、曲目 2⋯ 依次下去。当然，刚播放过的那首曲子需要被跳过），直到多出的部分被分配完。

按照题目要求模拟即可。

#include<bits/stdc++.h>
using namespace std;
int n,t,a[1005],sum;
int main() {
	int i;
	cin>> n;
	cin>> t;
	for(i=1; i<=n; i++) {
		scanf("%d",&a[i]);
	}
	while(t--) {
		int mx=0,j=1;
		for(i=1; i<=n; i++) {
			if(a[i]>mx) {
				mx=a[i];
				j=i;
			}
		}
		sum=a[j]/(n-1);
		cout<< j<<endl;
		for(i=1; i<=n; i++) {
			if(i!=j)a[i]+=sum;
		}
		if(a[j]%(n-1)!=0) {
			sum=a[j]%(n-1);
			for(i=1; i<=n&&sum; i++) {
				if(i!=j) {
					a[i]++;
					sum--;
				}
			}
		}
		a[j]=0;
	}
	return 0;
}

错因：最后未平均分部分分配过程有误。

T3  运用深搜求路径，“*”不可走，“.”可走。用一个数组将沿途可行进的下标存储。到达后统一输出。搜索过程中，边界条件和结束条件和之前相同。

#include<bits/stdc++.h>
using namespace std;
int r,c,num=1,k[10000][2],vis[120][80];
char a[120][80];
int dx[4]= {1,0,-1,0};
int dy[4]= {0,1,0,-1}; 
void print() {
	for(int i=1; i<=num; i++)
		cout<<k[i][0]<<" "<<k[i][1]<<endl;
}
void dfs(int x,int y) {
	if(x==r&&y==c) {
		print();
	return ;
	}
	for(int i=0; i<4; i++) {
		int nx=x+dx[i],ny=y+dy[i];
		if(!vis[nx][ny]&&nx>0&&nx<=r&&ny>0&&ny<=c&&a[nx][ny]=='.') {
			vis[nx][ny]=1;
			num++;
			k[num][0]=nx;
			k[num][1]=ny;
			dfs(nx,ny);
			num--;
		}
	}
}
int main() {
	cin>>r>>c;
	for(int i=1; i<=r; i++)
		for(int j=1; j<=c; j++)
			cin>>a[i][j];
	vis[1][1]=1;
	k[1][0]=1;
	k[1][1]=1;
	dfs(1,1);
	return 0;
}

错因：未想到使用数组存储。

T4：先判断每个齿轮能连接的齿轮然后bfs

代码借鉴(自题解）

#include<bits/sydc++.h>
using namespace std;
int n,fx,fy,x[1055],y[1055],r[1055],sNo,fNo,Map[1055][1055],num[1055];
bool vis[1055];
struct Node {
	int No;
	double v,sum;
};
queue<struct Node> que;
void judge() {
	for(int i=1; i<=n; i++) {
		for(int j=i+1; j<=n; j++) {
			int dis=0;
			double dist;
			dis+=(x[i]-x[j])*(x[i]-x[j]);
			dis+=(y[i]-y[j])*(y[i]-y[j]);
			dist=sqrt(dis);
			if(r[i]+r[j]>=dist) {
				num[i]++;
				num[j]++;
				Map[i][num[i]]=j;
				Map[j][num[j]]=i;
			}
		}
	}
}
void bfs() {
	struct Node now;
	now.No=sNo,now.v=10000,now.sum=10000;
	que.push(now);
	vis[sNo]=true;
	while(!que.empty()) {
		struct Node now;
		now=que.front();
		que.pop();
		if(now.No==fNo) {
			cout<<(int)now.sum;
			return;
		}
		for(int i=1; i<=num[now.No]; i++) {
			if(vis[Map[now.No][i]]) continue;
			struct Node next;
			next.No=Map[now.No][i];
			next.v=now.v*r[now.No]/r[Map[now.No][i]];
			next.sum=now.sum+next.v;
			que.push(next);
			vis[Map[now.No][i]]=true;
		}
	}
}

int main() {
	cin>>n>>fx>>fy;
	for(int i=1; i<=n; i++) {
		cin>>x[i]>>y[i]>>r[i];
		if(!x[i]&&!y[i]) sNo=i;
		if(x[i]==fx&&y[i]==fy) fNo=i;
	}
	judge();
	bfs();
	return 0;
}

错因：不会

考试总结：本次考试非常糟糕。由于经验不足等原因造成了这次结果。下次努力！！