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
本文为作者原创,转载请注明出处:本文链接
阅读量: