2018暑假多校賽【第二場】【構造】-Hack It-YZHHHHHHH

Hack It

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 585    Accepted Submission(s): 183

Special Judge

Problem Description

Tonyfang is a clever student. The teacher is teaching he and other students "bao'sou".

The teacher drew an n*n matrix with zero or one filled in every grid, he wanted to judge if there is a rectangle with 1 filled in each of 4 corners.

He wrote the following pseudocode and claim it runs in O(n2):

let count be a 2d array filled with 0s
iterate through all 1s in the matrix:
  suppose this 1 lies in grid(x,y)
  iterate every row r:
    if grid(r,y)=1:
      ++count[min(r,x)][max(r,x)]
      if count[min(r,x)][max(r,x)]>1:
        claim there is a rectangle satisfying the condition
claim there isn't any rectangle satisfying the condition

As a clever student, Tonyfang found the complexity is obviously wrong. But he is too lazy to generate datas, so now it's your turn.
Please hack the above code with an n*n matrix filled with zero or one without any rectangle with 1 filled in all 4 corners.
Your constructed matrix should satisfy 1≤n≤2000 and number of 1s not less than 85000.
           

Input

Nothing.

Output

The first line should be one positive integer n where 1≤n≤2000.

n lines following, each line contains only a string of length n consisted of zero and one.

Sample Input

(nothing here)

Sample Output

3

010

000

000 

(obviously it's not a correct output, it's just used for showing output format)

題意：

特殊判斷

1、輸出一個n*n的矩陣

2、該矩陣被 0 和 1 填滿

3、“1” 不能形成矩形且矩陣内要有不少于85000個1

構造矩陣

5*5矩陣的前5行

對j進行

j+0 10000 10000 10000 10000 10000

j+1 10000 01000 00100 00010 00001

j+2 10000 00100 00001 01000 00010

j+3 10000 00010 01000 00001 00100

j+4 10000 00001 00010 00100 01000

下面的20行将1依次向右移一位。

需要注意的是：mod要選擇質數，46*46=2116，47*47=2209.

代碼：

#include <stdio.h>

int s = 2000;	//整個矩陣的大小 
int mod = 47;	//mod需選擇質數，防止重複 
int mapp[3000][3000];
int main(){
	//構造矩陣 
	for (int i = 0; i < mod; i++){
		for (int j = 0; j < mod; j++){
			for (int k = 0; k < mod ; k++){
				mapp[i*mod+j][k*mod + (j*k+i) % mod] = 1;
			}
		}
	}
	//輸出矩陣 
	printf("2000\n");
	for (int i = 0; i < 5; i++){
		for (int j = 0; j < s; j++){
			printf("%d",mapp[i][j]);
			//if (j % 5 == 4) printf(" ");
		}
		//if (i % 5 == 4) printf("\n");
		printf("\n");
	}
}
           

吐槽一下題目。。。

正道題目隻有紅色框的兩句話有用。。。