- 技术
- Codeforces Round #654 (Div. 2) D. Grid-00100（构造）
题目链接
思路：题目要求价值最小，怎么放价值最小？每次放的地方行和列最大值最小值之差为1，那么当行或者列%n==0时就从头开始此时的行列最大值最小值之差依旧是1
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
using namespace std
;
typedef long long ll
;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair
<int,int> PII
;
const int mod
=1e4+7;
const int N
=2e5+10;
const int inf
=0x7f7f7f7f;
ll
gcd(ll a
,ll b
)
{
return b
==0?a
:gcd(b
,a
%b
);
}
ll
lcm(ll a
,ll b
)
{
return a
*(b
/gcd(a
,b
));
}
template <class T>
void read(T
&x
)
{
char c
;
bool op
= 0;
while(c
= getchar(), c
< '0' || c
> '9')
if(c
== '-')
op
= 1;
x
= c
- '0';
while(c
= getchar(), c
>= '0' && c
<= '9')
x
= x
* 10 + c
- '0';
if(op
)
x
= -x
;
}
template <class T>
void write(T x
)
{
if(x
< 0)
x
= -x
, putchar('-');
if(x
>= 10)
write(x
/ 10);
putchar('0' + x
% 10);
}
int a
[305][305],R
[305],C
[305];
int main()
{
SIS
;
int t
;
cin
>>t
;
while(t
--)
{
memset(R
,0,sizeof R
);
memset(C
,0,sizeof C
);
memset(a
,0,sizeof a
);
int n
,k
;
cin
>>n
>>k
;
int x
=0,y
=0;
int cnt
=0;
while(k
--)
{
a
[x
][y
]=1;
R
[x
]++;
C
[y
]++;
x
++;
y
++;
cnt
++;
x
%=n
;
y
%=n
;
if(cnt
==n
){
y
++;y
%=n
;cnt
=0;
}
}
int mxr
=0,mnr
=inf
,mxc
=0,mnc
=inf
;
for(int i
=0;i
<n
;i
++)
{
mxr
=max(mxr
,R
[i
]);
mnr
=min(mnr
,R
[i
]);
mxc
=max(mxc
,C
[i
]);
mnc
=min(mnc
,C
[i
]);
}
int ans
=(mxr
-mnr
)*(mxr
-mnr
)+(mxc
-mnc
)*(mxc
-mnc
);
cout
<<ans
<<endl
;
for(int i
=0;i
<n
;i
++)
{
for(int j
=0;j
<n
;j
++)
cout
<<a
[i
][j
];
cout
<<endl
;
}
}
return 0;
}
Processed:
0.019, SQL:
9
