第二次双周赛(搜索)

发布于 2022-12-26  147 次阅读


T1 输出全排列

很典的一道题(在某哈算法一书里作为dfs的例题)

代码如下:

#include <iostream>
using namespace std;
int n;
int a[11],vis[11];
void dfs(int step){
	if(step==n+1){
		for(int i=1;i<=n;i++){
			cout<<a[i];
		}
		cout<<endl;
		return;
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==0){
			a[step]=i;
			vis[i]=1;
			dfs(step+1);
			vis[i]=0;
		}
	}
	return;
}
int main(){
	cin>>n;
	dfs(1);
	return 0;
}

T2 山

我写的很懒,主要是感觉会重复标记所以一直在想怎么优化。(但其实并不会重复标记)

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
queue<int> x1;
queue<int> y1;
queue<int> tx;
queue<int> ty;
int world[2005][2005];
int color[2005][2005];
int vis[2005][2005];
int n,m;
int ans;
int movex[5]={0,0,0,1,-1};
int movey[5]={0,1,-1,0,0};
int main(){
	memset(world,0x3f,sizeof(world));
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int l=1;l<=m;l++){
			cin>>world[i][l];
			if(world[i][l]==1){
				x1.push(i);
				y1.push(l);
			}
		}
	}
	while(!x1.empty()){
		int xx=x1.front();
		int yy=y1.front();
		if(vis[xx][yy]==1){
			x1.pop();
			y1.pop();
			continue;
		}
		vis[xx][yy]=1;
		tx.push(xx);
		ty.push(yy);
		while(!tx.empty()){
			int x2=tx.front();
			int y2=ty.front();
			for(int i=1;i<=4;i++){
				int x3=x2+movex[i];
				int y3=y2+movey[i];
				if(x3>=1&&x3<=n&&y3>=1&&y3<=m&&world[x3][y3]==1&&vis[x3][y3]==0){
					tx.push(x3);
					ty.push(y3);
					vis[x3][y3]=1;
				}
			}
			tx.pop();
			ty.pop();
		}
		ans++;
		x1.pop();
		y1.pop();
	}
	cout<<ans;
}

根本没必要写这么长,也用了将近半个小时的时间。


T3 跳跃

非常像奇怪的电梯那道题,但是因为没有确认下标的问题,一直卡在这道题。

#include <iostream>
#include <queue>
using namespace std;
const int N=5e5+5;
int start,n;
int num[N];
int step[N];
int vis[N];
queue<int> x;
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>num[i];
	}
	cin>>start;
	if(num[start]==0){
		cout<<"True";
		return 0;
	}
	vis[start]=1;

	x.push(start);
	while(!x.empty()){

		int x1=x.front();

		if(num[x1]==0){
			cout<<"True";
			return 0;
		}
		int s=num[x1];
		int l=x1-s;
		int r=x1+s;
		if(l>=0){
			if(vis[l]==0){
				vis[l]=1;
				x.push(l);
			}
		}
		if(r<n){
			if(vis[r]==0){
				vis[r]=1;
				x.push(r);
			}
		}
		x.pop();
	}
	cout<<"False";
	return 0;
}

T4 回文数回文

其实是一道数学题哒!(数据范围给的比较小)

思路是前四位数对称过去然后再比较。)

#include <iostream>
using namespace std;
int ans;
int getnum(int n){
	int temp=n;
	int a[6];
	n/=10;
	for(int i=1;i<=4;i++){
		a[i]=n%10;
		n/=10;
	}
	for(int i=1;i<=4;i++){
		temp*=10;
		temp+=a[i];
	}
	return temp;
}
int main(){
	int a;
	cin>>a;
	for(int i=10000;i<=99999;i++){
		if(getnum(i)<=a){
			ans++;
		}
	}
	cout<<ans;
}

T5 最长光路

看到输入就不太想做了。)

但是想了想某书上有一道水管工的题,要定义四个朝向和四个状态,感觉还是做一做还是蛮有用的。

(其实做了半天没做出来还是看了题解)

#include <iostream>
#include <cstring>
using namespace std;
const int INF=0x3f3f;
//1为上,2为右,3为下,4为左。
//  \可以用\\来表示。
//  \ 1->4 2->3 3->2 4->1

//  / 1->2 2->1 3->4 4->3
char world[505][505];
int vis[505][505][6];
int n,m;
int sx,sy;
int nx,ny;
long long int ans;
char ansdir;
long long int len;
bool check(int x,int y){
	if(x<1||y<1) return 0;
	if(x>n||y>m) return 0;
	if(world[x][y]=='C') return 0;
	return 1;
}
void go(int x,int y,int status){
	if(status==1){
		nx=x-1, ny=y;
	}
	else if(status==2){
		nx=x, ny=y+1;
	}
	else if(status==3){
		nx=x+1, ny=y;
	}
	else if(status==4){
		nx=x, ny=y-1;
	}
}

void dfs(int x,int y,int status){
	++len;
	if(vis[x][y][status]){
		len=INF;
		return;
	}
	else vis[x][y][status]=1;
	if(world[x][y]=='/'){
		if     (status==1) status=2;
		else if(status==2) status=1;
		else if(status==3) status=4;
		else if(status==4) status=3;
	}
	if(world[x][y]=='\\'){
		if     (status==1) status=4;
		else if(status==2) status=3;
		else if(status==3) status=2;
		else if(status==4) status=1;
	}
	go(x,y,status);//更新x和y的值。
	if(!check(nx,ny)) return;
	dfs(nx,ny,status);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int l=1;l<=m;l++){
			cin>>world[i][l];
		}
	}
	cin>>sx>>sy;
	memset(vis,0,sizeof(vis));
	len=0;
	dfs(sx,sy,1);
	if(len>ans) ansdir='U',ans=len;
	
	memset(vis,0,sizeof(vis));
	len=0;
	dfs(sx,sy,2);
	if(len>ans) ansdir='R',ans=len;
	
	memset(vis,0,sizeof(vis));
	len=0;
	dfs(sx,sy,3);
	if(len>ans) ansdir='D',ans=len;
	
	memset(vis,0,sizeof(vis));
	len=0;
	dfs(sx,sy,4);
	if(len>ans) ansdir='L',ans=len;
	
	cout<<ansdir<<endl;
	if(ans!=INF){
		cout<<ans;
	}
	else cout<<"COOL"<<endl;
	return 0;
}

是我第一次周赛做三道好耶(好锤子哦)