CSPJ组冲刺Day2

userId_undefined
深圳信奥中心-禹云龙

2026-10-02 15:50:56

发布于：广东

33阅读
0回复
0点赞

迷宫

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=45;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int vis[N][N];
string s[N];
int n,m,tx,ty;
int dfs(int x,int y){
	if(x==tx&&y==ty)return 1;
	vis[x][y]=1;
	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<1||nx>n||ny<1||ny>m)continue;
		if(s[nx][ny]=='#'||vis[nx][ny])continue;
		if(dfs(nx,ny))return 1;
	}
	return 0;
}

void solve(){
	cin>>n>>m;
	int sx,sy;
	cin>>sx>>sy>>tx>>ty;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		s[i]=" "+s[i];
	}
	if(dfs(sx,sy))cout<<"YES\n";
	else cout<<"NO\n";
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int _=1;
	// cin>>_;
	while(_--){
		solve();
	}
}

求细胞数量

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e2+5;
int mp[N][N];
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
string s[N];
int n,m;
void dfs(int x,int y){
	mp[x][y]=1;
	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<1||nx>n||ny<1||ny>m)continue;
		if(s[nx][ny]=='0'||mp[nx][ny])continue;
		dfs(nx,ny);
	}
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		s[i]=" "+s[i];
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i][j]!='0'&&!mp[i][j]){
				ans++;
				dfs(i,j);
			}
		}
	}
	cout<<ans<<"\n";
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int _=1;
	// cin>>_;
	while(_--){
		solve();
	}
}

全排列问题

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e2+5;
int vis[N];
int a[N];
int n,m;
void dfs(int step){
	if(step==n+1){
        for(int i=1;i<=n;i++){
            printf("%5lld",a[i]);
        }
        cout<<"\n";
        return;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            vis[i]=1;
            a[step]=i;
            dfs(step+1);
            vis[i]=0;
        }
    }
}
void solve(){
	cin>>n;
    dfs(1);
}
signed main(){
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr);
	int _=1;
	// cin>>_;
	while(_--){
		solve();
	}
}

营救

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=1005;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int mp[N][N],dis[N][N];
int n;
struct str{
    int x,y;
};
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			char c;
			cin>>c;
			mp[i][j]=c-'0';
            dis[i][j]=-1;
		}
	}
	int sx,sy,tx,ty;
	cin>>sx>>sy>>tx>>ty;
	queue<str> q;
	q.push({sx,sy});
	dis[sx][sy]=0;
	while(!q.empty()){
		str u=q.front();
		q.pop();
		int x=u.x,y=u.y;
		if(x==tx&&y==ty){
			cout<<dis[x][y]<<"\n";
			return;
		}
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(nx<1||nx>n||ny<1||ny>n)continue;
			if(mp[nx][ny]||dis[nx][ny]!=-1)continue;
			dis[nx][ny]=dis[x][y]+1;
			q.push({nx,ny});
		}
	}
	cout<<-1<<"\n";
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int _=1;
	// cin>>_;
	while(_--){
		solve();
	}
}

高塔

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int dis[N];
void solve(){
	int a,b;
	cin>>a>>b;
	if(a>=b){
		cout<<a-b<<"\n";
		return;
	}
	for(int i=1;i<N;i++)dis[i]=-1;
	queue<int> q;
	q.push(a);
	dis[a]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		if(x==b){
			cout<<dis[x]<<"\n";
			return;
		}
		int nxt[]={x-1,x+1,2*x};
		for(int i=0;i<3;i++){
			int y=nxt[i];
			if(y<0||y>=N||dis[y]!=-1)continue;
			dis[y]=dis[x]+1;
			q.push(y);
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int _=1;
	// cin>>_;
	while(_--){
		solve();
	}
}

滑雪

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e2+5;
int a[N][N],f[N][N];
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int n,m;
int ans=0;
int dfs(int x,int y){
	if(f[x][y])return f[x][y];
	f[x][y]=1;
	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<1||nx>n||ny<1||ny>m)continue;
		if(a[nx][ny]<a[x][y]){
            f[x][y]=max(dfs(nx,ny)+1,f[x][y]);
		}
	}
	return f[x][y];
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)cin>>a[i][j];
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
            ans=max(ans,dfs(i,j));
            // dfs(i,j,1);
        }
	}
	cout<<ans<<"\n";
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int _=1;
	// cin>>_;
	while(_--){
		solve();
	}
}

最大异或和

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int a[N];
int n,k,r,ans;
void dfs(int st,int cnt,int val){
	if(cnt==r){
		ans=max(ans,val);
		return;
	}
    //st 表示第cnt+1个要选的数字 从那里开始选
    //ed 表示的是最后一个可选的数字
	int ed=n-(r-cnt)+1;
	for(int i=st;i<=ed;i++){
		dfs(i+1,cnt+1,val^a[i]);
	}
}
void solve(){
	cin>>n>>k;
	int all=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		all^=a[i];
	}
	r=min(k,n-k);
	ans=0;
	int bg=0;
	if(k>n-k)bg=all;
	dfs(1,0,bg);
	cout<<ans<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int _=1;
	// cin>>_;
	while(_--){
		solve();
	}
}

卡牌游戏

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=20;
int b[N];
int n,m,sa,ans;

void dfs(int pos,int cnt,int sum){
	if(pos==n+1){
		if(cnt>m||(cnt==m&&sum>sa))ans++;
		return;
	}
	dfs(pos+1,cnt,sum);
	dfs(pos+1,cnt,sum+b[pos]);
}
void solve(){
	cin>>m>>n;
	sa=0;
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		sa+=x;
	}
	for(int i=1;i<=n;i++)cin>>b[i];
	ans=0;
	dfs(1,0,0);
	cout<<fixed<<setprecision(6)<<(double)ans/(1LL<<n)<<"\n";
    
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int _=1;
	// cin>>_;
	while(_--){
		solve();
	}
}
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论