两次CSP-J模拟

我该说什么

Posted by ethan-zhou on November 1, 2019

P.S. 本博客好像好久都没更了。。不是博主弃坑了,只是最近忙于各种比赛,没啥时间,有时间会更的。

另外因为种种原因我没报上提高组csp,十分悲痛QAQ


第一次模拟赛

t1

我用了一种不是很暴力的模拟,即按照1位,2位,3位…来统计长度,却莫名其妙的错了一个点,也许是极端情况程序被卡了。

t2

纯暴力题目,枚举所有可能的a,b算出c,再计算不同的位数,最后取最小即可

t3

这题爆炸了。。。 本来期望用二分加上搜索得到60分,在适当加优化。结果脑子抽抽,二分的逻辑搞混了,加上搜索时写成了找路径的搜索,最后只得15分,很不满意。

t4

这题没太理解题意,也没算出来,于是输出样例,0分

虽然排名还行(大家都炸了),但自我感觉这次考试发挥很不理想,主要因为第3题调太久了,结果最后还错了。加上好久没弄noilinux,环境不熟悉,还忘记了我的vimrc。现场重新想的,十分浪费时间,以后要搞清轻重主次,记不住就用guide吧。

第二次模拟赛

t1

字符串处理题,就直接一位一位判断

t2

模拟,读入第i位时,如果这位不是零,就将数组的第i项和n-i+1项赋值为这个数即可

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int NR=20005;
int a,b;
int arr[NR];
int main(){
				memset(arr,0,sizeof(arr));
				scanf("%d%d",&a,&b);
				for(int i=0;i<b;i++)
							for(int j=0;j<a;j++){
											int tmp;
											scanf("%d",&tmp);
											if(tmp)
															arr[j]=tmp,arr[a-j-1]=tmp;
							}
				for(int i=0;i<a-1;i++)printf("%d ",arr[i]);
				printf("%d\n",arr[a-1]);
				return 0;
}

t3

这题因为数学不好所以没算出来。 老师说这个数列跟肥不拉几数列有许多关联,包括第i个数列的0与1的个数等等。最后正解好像是利用每个数列都等于前两个数列之和进行二分。然而我连暴力模拟都没敲出来,有些可惜。

t4

搜索题,我首先用floyd(简单易学)预处理出来了每两个宝藏之间的距离,接着用dfs全排列求出所有的路径(路上经过宝藏的顺序),接着用前面预处理出来的东西计算总路程。

最坏复杂度\(\O(a^3\times b^3+N!)\),t了一个点,90分(劲爆6重循环)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MXN=15;
const int NR=55;
const int nxto[4][2]={
	{1,0},{-1,0},{0,1},{0,-1}
};
int s,p;
int n,a,b;
int sx,sy;
int tx[MXN],ty[MXN],dt[MXN];
bool map[NR][NR];
int dis[NR][NR][NR][NR];
bool vis[MXN];
int mx=-1;
void dfs(int curx,int cury,int curf,int curcnt){
				if(curcnt==0){
								if(dis[curx][cury][sx][sy]*p>curf)return;
								mx=max(mx,curf-dis[curx][cury][sx][sy]*p);
								return;
				}
				for(int i=1;i<=n;i++){
								if(vis[i])continue;
								if(dis[curx][cury][tx[i]][ty[i]]*p>curf)continue;
								vis[i]=1;
								dfs(tx[i],ty[i],curf+dt[i]-dis[curx][cury][tx[i]][ty[i]]*p,curcnt-1);
								vis[i]=0;
				}
				return;
}
int main(){
				scanf("%d%d%d",&s,&p,&n);
				for(int i=1;i<=n;i++)
								scanf("%d%d%d",tx+i,ty+i,dt+i);
				scanf("%d%d",&a,&b);
				for(int i=1;i<=a;i++)
								for(int j=1;j<=b;j++)
												scanf("%d",&map[i][j]);
				scanf("%d%d",&sx,&sy);
				//floyd
				memset(dis,0x3f,sizeof(dis));
				for(int i=1;i<=a;i++)
								for(int j=1;j<=b;j++){
												dis[i][j][i][j]=0;
												if(!map[i][j])continue;
												for(int tmp=0;tmp<4;tmp++){
																int nx=i+nxto[tmp][0];
																int ny=j+nxto[tmp][1];
																if(nx<1 || ny<1 || nx>a || ny>b)continue;
																if(map[nx][ny])dis[i][j][nx][ny]=1;
												}
								}
				//mid
				for(int kx=1;kx<=a;kx++)
								for(int ky=1;ky<=b;ky++){
												if(!map[kx][ky])continue;
												//start
												for(int x1=1;x1<=a;x1++)
																for(int y1=1;y1<=b;y1++){
																				if(!map[x1][y1])continue;
																				//end
																				for(int x2=1;x2<=a;x2++)
																								for(int y2=1;y2<=b;y2++){
																												if(!map[x2][y2])continue;
																												dis[x1][y1][x2][y2]=min(\
																												dis[x1][y1][x2][y2],\
																												dis[x1][y1][kx][ky]+dis[kx][ky][x2][y2]);
																								}
																}
								}
				memset(vis,0,sizeof(vis));
				dfs(1,1,s,n);
				printf("%d\n",mx);
				return 0;
}

感觉这次发挥还可以,程序没出什么毒瘤的调不出的bug,而且没有在希望不大的题上浪费太长时间(主要是因为我路上看了看我的vimrc?)


作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接