hdu 多校赛 Hack It

【题目链接】

题目意思就是说要求一个边长为 n (1<=n<=2000) 的正方形，其中每一个点的值为0或1，要求1的数目不少于85000个，并且任意四个可以构成矩形的点不全为1，求满足条件的任意一个正方形，先输出一行边长，再输出正方形。

我们先考虑当n=25时，满足任意四个可以构成矩形的点不全为1的正方形之一如下图所示，找一下规律可以发现，（设 1 出现的位置为 s ）前五行， s = 0，1 的起始位置都在第0列，每输出5个数字，s = ( s + 行数 ) % n，这样就输出了前五行数字，通过观察前五行数字满足任意四个可以构成矩形的点不全为 1 ，由此推广到n=36 , 49 , 64···

n=25时情况

10000 10000 10000 10000 10000
10000 01000 00100 00010 00001
10000 00100 00001 01000 00010
10000 00010 01000 00001 00100
10000 00001 00010 00100 01000

01000 01000 01000 01000 01000
01000 00100 00010 00001 10000
01000 00010 10000 00100 00001
01000 00001 00100 10000 00010
01000 10000 00001 00010 00100

00100 00100 00100 00100 00100
00100 00010 00001 10000 01000
00100 00001 01000 00010 10000
00100 10000 00010 01000 00001
00100 01000 10000 00001 00010

00010 00010 00010 00010 00010
00010 00001 10000 01000 00100
00010 10000 00100 00001 01000
00010 01000 00001 00100 10000
00010 00100 01000 10000 00001

00001 00001 00001 00001 00001
00001 10000 01000 00100 00010
00001 01000 00010 10000 00100
00001 00100 10000 00010 01000
00001 00010 00100 01000 10000

这里有一点注意一下，sqrt(n)必须要求是一个素数，假设sqrt(n)是一个合数，在循环的时候会出现后面两点重合的情况，导致出现矩形四个点为1。
当n = 16，前四行
1000 1000 1000 1000
1000 0100 0010 0001
1000 0010 1000 0010
1000 0001 0010 0100
所以要求sqrt(n)必须是素数

加一个count标记出现1的次数，推导一下发现只有当n = 47 * 47时，满足以上所有条件，但是当n = 47 * 47时，n > 2000，这个时候判断一行输出的数字数组个数，当输出了2000个数字后，跳出循环，开始下一行。

下面是AC代码。

#include <iostream>
using namespace std;
int count = 0;
int main()
{
    int n;
    n = 47;
    //cin>>n;
    puts("2000");
    for (int l = 0; l<n; l++)
    {
        int s = l;
        for (int i = 0; i<n; i++)
        {
            for (int j = 0; j<n; j++)
            {
                for (int k = 0; k<n; k++)
                {
                    if (j*n + k >= 2000)
                        goto qwe;
                    if (k == s)
                        cout << "1";
                    else
                        cout << "0";
                }
                //cout<<" ";
                s += i;
                if (s >= n)
                    s %= n;
            }
        qwe:;
            cout << endl;
        }
    }
}