求助
查看原帖
求助
1147171
Merge_all楼主2024/8/7 13:59

自己创的所有数据都过了,但为什么是零分???

#include<bits/stdc++.h>
using namespace std;
const int N=1<<11,M=40;
int h,r,n,m;
char mp[N][N],ans[N][N];
bool vis[M][M];
/*
层数  高度n  宽度m
  1     1      1
  --------------
  2     3      5
  3     6=3*2      11=5*2+1
  4     12=6*2     23=11*2+1
  5     24=12*2     47=23*2+1
*/
int inv[N],tmp[N],len,cnt[N];
void init_map(){
	cnt[1]=1;
	n=3;for(int i=2;i<h;i=-~i) n<<=1;
	m=5;for(int i=2;i<h;i=-~i) m<<=1,m=-~m;
	for(int i=1;i<=n;i=-~i) for(int j=1;j<=m;j=-~j) mp[i][j]=' ';
	int nn=n-3,res=2;
	tmp[++len]=1;
	while(res<=nn&&nn){
		nn=nn-res-1;
		tmp[++len]=res;
		res<<=1,res=-~res;
	}
	for(int i=1;i<=len;i=-~i) inv[i]=tmp[len-i+1];
//	for(int i=1;i<=len;i=-~i) cout<<inv[i]<<"\n";
}
/*
                       o
                      / \
                     /   \
                    /     \
                   /       \
                  /         \
                 /           \
                /             \
               /               \
              /                 \
             /                   \ 
            /                     \                  11
		   o             		   o            
		  / \           		  / \          
	     /   \          	     /   \         
        /     \                 /     \        
       /       \               /       \       
      /         \             /         \            5
     o           o           o           o     
    / \         / \         / \         / \    
   /   \       /   \       /   \       /   \         2
  o     o     o     o     o     o     o     o  
 / \   / \   / \   / \   / \   / \   / \   / \       1
o   o o   o o   o o   o o   o o   o o   o o   o
*/
//当前节点的位置,当前是o还是/,当前点在哪个部分,dir=1则是右,反之为左
#define Check(x,y) (x>=1&&x<=n&&y<=m&&y>=1)
void dfs(int x,int y,int k,int dir){
//	cout<<"true";
	if(x==1&&y==m/2+1&&k==1&&!dir){
		mp[x][y]='o';
		dfs(x+1,y-1,1,0),dfs(x+1,y+1,1,1);
		return ;
	}
	if(!Check(x,y)||vis[x][y]) return ;
//	cout<<"x="<<x<<" y="<<y<<"\n";
	if(x-inv[k]>=1&&y+inv[k]<=m+1){
		if(dir){
			if(mp[x-inv[k]-1][y-inv[k]-1]=='o'){
				mp[x][y]='o';
				dfs(x+1,y+1,k+1,1),dfs(x+1,y-1,k+1,0);
			}
			else{
				mp[x][y]='\\';
				dfs(x+1,y+1,k,1);
			}
		}
		else{
			if(mp[x-inv[k]-1][y+inv[k]+1]=='o'){
				mp[x][y]='o';
				dfs(x+1,y+1,k+1,1),dfs(x+1,y-1,k+1,0);
			}
			else{
				mp[x][y]='/';
				dfs(x+1,y-1,k,0);
			}
		}
	}
	else{
		if(dir){
			mp[x][y]='\\';
			dfs(x+1,y+1,k,1);
		}
		else{
			mp[x][y]='/';
			dfs(x+1,y-1,k,0);
		}
	}
}
struct Node{
	int x;
	int y;
}rk[N][N];
void draw_map(int x,int y,int k){
	if(x==1&&y==m/2+1&&k==1){
		ans[x][y]='o';
		Node tp=rk[x+inv[k]+1][y-inv[k]-1],tp1=rk[x+inv[k]+1][y+inv[k]+1];
		if(!vis[tp.x][tp.y]) draw_map(x+1,y-1,k);
		if(!vis[tp1.x][tp1.y]) draw_map(x+1,y+1,k);
		return ;
	}
	if(!Check(x,y)) return ;
	if(mp[x][y]=='/'){
		ans[x][y]='/';
		draw_map(x+1,y-1,k);
	}
	else if(mp[x][y]=='\\'){
		ans[x][y]='\\';
		draw_map(x+1,y+1,k);
	}
	else{
		ans[x][y]='o';
//		cout<<"x="<<x<<" y="<<y<<" k="<<k<<"\n";
		Node tp=rk[x+inv[k+1]+1][y-inv[k+1]-1],tpp=rk[x+inv[k+1]+1][y+inv[k+1]+1];
		if(!vis[tp.x][tp.y]) draw_map(x+1,y-1,k+1);
		if(!vis[tpp.x][tpp.y]) draw_map(x+1,y+1,k+1);
	}
}
int main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0),cout.tie(0);
	cin>>h>>r;
	for(int i=1,x,y;i<=r;i=-~i){cin>>x>>y;vis[x][y]=true;}
	if(h==1||vis[1][1]){if(!vis[1][1]) cout<<"o";return 0;}
	init_map();
	dfs(1,m/2+1,1,0);
	int rt=0,rp=0;
	bool flag=true;
	for(int i=1;i<=n;i=-~i){
		if(flag) rt++;
		flag=false;
		rp=0;
		for(int j=1;j<=m;j=-~j){
			if(mp[i][j]=='\\'||mp[i][j]=='/') break;
			if(mp[i][j]=='o') rk[i][j].x=rt,rk[i][j].y=++rp,flag=true;
		}
	}
//	cout<<"n="<<n<<" m="<<m<<"\n";
//	for(int i=1;i<=n;i=-~i){
//		for(int j=1;j<=m;j=-~j){
//			cout<<mp[i][j];
//		}
//		cout<<"\n";
//	}
//	for(int i=1;i<=n;i=-~i){
//		for(int j=1;j<=m;j=-~j){
//			cout<<rk[i][j].x<<" "<<rk[i][j].y<<" ";
//		}
//		cout<<"\n";
//	}
	draw_map(1,m/2+1,1);
	for(int i=1;i<=n;i=-~i){
		for(int j=1;j<=m;j=-~j){
			cout<<ans[i][j];
		}
		cout<<"\n";
	}
	return 0;
}
2024/8/7 13:59
加载中...