codechef： ADAROKS2 ,Ada Rooks 2

又是道原题... (HDU 6313 Hack It ，多校 ACM 里面的题)

题目说构造一个 n * n 矩阵，染色点不得构成矩形...然后染色点个数至少 8 * n

然后我们生成一个数 m ，把矩阵分成 m * m 块，每块每行都至少要有 1 个 1 ，具体构造看代码：

	fp(i,0,m-1) fp(j,0,m-1) fp(k,0,m-1)

		s[m*i+j][m*k+(j*k+i)%m]=1;

证明的话要用循环加群...具体证明可以康这里

总的来说就是抄 hdu ACM 上那题的代码就好了（玄学的构造法），要注意的就是 m 取值要是个质数，并且数字要足够大，所以要先筛出 1~100 的质数就是了（我居然在质数上调了这么久）

//by Judge

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#define Rg register

#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)

using namespace std;

const int M=1003;

typedef int arr[M];

#ifndef Judge

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

#endif

char buf[1<<21],*p1=buf,*p2=buf;

inline int read(){ int x=0,f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;

} char sr[1<<21],z[20];int C=-1,Z;

inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}

int n,m,s[M][M];

inline void check(int n){ Rg int num=0;

	fp(i,1,n) fp(j,1,n) num+=s[i][j];

	if(num<n*8) return puts("Error"),void();

	fp(r1,1,n) fp(r2,r1+1,n)

		fp(c1,1,n) fp(c2,c1+1,n)

			if(s[r1][c1]&&s[r2][c1]&&s[r1][c2]&&s[r2][c2])

				return printf("%d , %d -> %d , %d\n",r1,c1,r2,c2),void();

	puts("win");

}

int cnt; arr p,vis;

inline void prep(Rg int n){ vis[1]=1;

	fp(i,2,n){ if(!vis[i]) p[++cnt]=i;

		for(Rg int j=1;j<=cnt&&p[j]*i<=n;++j){

			vis[i*p[j]]=1; if(!(i%p[j])) break;

		}

	}

}

int main(){ prep(100);

	fp(stp,1,read()){ n=read(),m=sqrt(n);

		while(vis[m]) ++m;

		fp(i,0,n-1) fp(j,0,n-1) s[i][j]=0;

		fp(i,0,m-1) fp(j,0,m-1) fp(k,0,m-1)

			s[m*i+j][m*k+(j*k+i)%m]=1;

		fp(i,0,n-1){

			fp(j,0,n-1) sr[++C]=s[i][j]?'O':'.';

			sr[++C]='\n';

			if(C>1<<20) Ot();

		}

	} return Ot(),0;

}

巴特西

codechef： ADAROKS2 ,Ada Rooks 2

最新文章

热门文章