恩情故事之 MAX0810 使用画图击落 N=100 构造 n^2 方案

野蛮题目，下次别出了，，，

经过手玩，奇数猜测是

n^2

，偶数是

n^2-2

（显然这是一个上界）。还可以发现在

n

小的时候（大的没试过）相当程度地乱放就可以达到这个上界，所以题目留给我们构造的空间非常宽松。

奇数一个想法是

n\to n+2

，可以如下构造（图为

n=3

）：

从两边没填的两行每次移动两格走到中心，每次调换先左/先右（先上/先下），最终剩下的

3\times 3

涂了左上角图形，此时除了这个左上角的已涂色格子加起来没有影响；随便构造（例如代码中 COL）一个方案。

偶数的一种较有规律的填法是在中间四个格子选一个填（如果

n=6

特殊处理，

n\equiv 0\pmod 4

则取

(n/2+1,n/2+1)

否则

(n/2,n/2)

）再从右下角填到选择格子的行列，每次把最右列最下行填了，然后递归到子问题。

每次填涂最右列最下行的方法是每次尽量选更靠近右下角的，懒得证明，反正这样确实是可以填完并且 AC 的。

应该是

O(n^3)

但是出题人素质高开

2^{10}

所以就通过了，，，

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn=1050;
int n,a[1050][1050];
int b[maxn],c[maxn],d[maxn*10],e[maxn*10],B=maxn*5;
inline void Pt(int x,int y){
	cout<<x<<" "<<y<<endl;
	if(n%2==0){
		a[x][y]=2;
		b[x]^=1,c[y]^=1,d[x+y+B]^=1,e[x-y+B]^=1;
	}
}
inline void COL(int x,int y){
	Pt(x+1,y+2);
	Pt(x+2,y+2);
	Pt(x+2,y+1);
	Pt(x+1,y+1);
	Pt(x+2,y);
	Pt(x,y+1);
	Pt(x,y+2);
	Pt(x+1,y);
}
inline void F(int n){
	if(n==4){
		if(a[4][4]!=2)Pt(4,4);
		Pt(2,3);Pt(3,4);Pt(4,1);Pt(4,3);
		Pt(1,4);Pt(2,4);Pt(4,2);Pt(3,3);
		Pt(3,1);Pt(1,2);Pt(2,1);Pt(2,2);
		Pt(1,1);
		return ;
	}
	if(n%4==0){
		Pt(n/2+1,n/2+1);
		for(int i=n;i>n/2;i--){
			for(int j=1;j<=2*i-1-(i==n/2+1);j++){
				int x=-1,y;
				for(int k=i;k>=1;k--){
					if(a[k][i]==0&&(b[k]^c[i]^d[k+i+B]^e[k-i+B])==0){x=k,y=i;break;}
					if(a[i][k]==0&&(b[i]^c[k]^d[k+i+B]^e[i-k+B])==0){x=i,y=k;break;}
				}	
				if(x==-1)exit(2);
				Pt(x,y);
			}
		}
		F(n/2);
	}else if(n!=6){
		Pt(n/2,n/2);
		for(int i=n;i>=n/2;i--){
			for(int j=1;j<=2*i-1-(i==n/2);j++){
				int x=-1,y;
				for(int k=i;k>=1;k--){
					if(a[k][i]==0&&(b[k]^c[i]^d[k+i+B]^e[k-i+B])==0){x=k,y=i;break;}
					if(a[i][k]==0&&(b[i]^c[k]^d[k+i+B]^e[i-k+B])==0){x=i,y=k;break;}
				}	
				Pt(x,y);
			}
		}
		F(n/2-1);
	}else{
		Pt(n/2+1,n/2+1);
		for(int i=n;i>n/2+1;i--){
			for(int j=1;j<=2*i-1;j++){
				int x=-1,y;
				for(int k=i;k>=1;k--){
					if(a[k][i]==0&&(b[k]^c[i]^d[k+i+B]^e[k-i+B])==0){x=k,y=i;break;}
					if(a[i][k]==0&&(b[i]^c[k]^d[k+i+B]^e[i-k+B])==0){x=i,y=k;break;}
				}	
				Pt(x,y);
			}
		}
		F(4);
	}
}
signed main(){
	cin>>n;
	if(n&1){
		cout<<n*n<<endl;
		Pt(1,1);
		for(int i=1;i<n;i+=2){
			int cur=0;
			for(int j=1;j<=i-1;j++){
				if(cur){
					Pt(j,i+1);Pt(j,i+2);Pt(i+2,j);Pt(i+1,j);
				}else{
					Pt(j,i+2);Pt(j,i+1);Pt(i+1,j);Pt(i+2,j);
				}
				cur^=1;
			}
			COL(i,i);
		}
	}else{
		if(n==2){
			cout<<1<<endl<<1<<" "<<1<<endl;
			return 0;
		}
		cout<<n*n-2<<endl;		
		F(n);
	}
	return 0;
}

恩情故事之 MAX0810 使用画图击落 N=100 构造 n^2 方案

文章操作

相关推荐

评论

恩情故事之 MAX0810 使用画图击落 N=100 构造 n^2 方案