自己创的所有数据都过了,但为什么是零分???
#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;
}