题目大意
给你一个 \(N\),然后再给你两个长度为 \(N\) 的序列。让你构造一个仅有 \(0\) 和 \(1\) 的 \(N \times N\) 的正方形,但是要满足两个序列的顺序:
- 第一个序列指的是该正方形每一行所构成的二进制数的大小顺序。
- 第二个序列指的是该正方形每一列所构成的二进制数的大小顺序。
分析
既然要满足顺序,那么肯定都是不同的,故二进制所表示的数也不同。
接着,我们尝试猜想:可不可以让这个正方形原来是递增状态,然后直接对行和列排序得到答案呢?
(递增状态指的是满足两个序列都是严格递增的状态,不懂的可以看下面的例子)
举一个递增状态的例子:
当然还有一种:
(不好意思,图在洛谷)
首先我们可以推一下小一点的样例,然后可以发现,单独排行时,对于列来说,状态仍然递减,因为排完行后,每一列的状态不过是在上一列的基础上增加一个 1
。接下来我们尝试推广到列,然后巧妙地发现没有影响(目前没有反例),那么猜想成立。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e02+100;
int n,p[MAXN],a[MAXN],q[MAXN],t[MAXN][MAXN];
void myswap(int &w,int &kl)
{
int tt=w;
w=kl;kl=tt;
return ;
}
int mymax(int x,int y)
{
return x>y?x:y;
}
int mymin(int x,int y)
{
return x<y?x:y;
}
struct node{
int ls,rs,val;
}qwqpp[MAXN];
void qsort(int l,int r)
{
int i=l,j=r,mid=p[(l+r)/2+1];
while(i<=j)
{
while(p[i]<mid) i++;
while(p[j]>mid) j--;
if(i<=j)
{
myswap(p[i],p[j]);
for(int k=1;k<=n;k++)
myswap(t[i][k],t[j][k]);
i++,j--;
}
}
if(l<j) qsort(l,j);
if(i<r) qsort(i,r);
}
void qsort2(int l,int r)
{
int i=l,j=r,mid=p[(l+r)/2+1];
while(i<=j)
{
while(q[i]<mid) i++;
while(q[j]>mid) j--;
if(i<=j)
{
myswap(q[i],q[j]);
for(int k=1;k<=n;k++)
myswap(t[k][i],t[k][j]);
i++,j--;
}
}
if(l<j) qsort2(l,j);
if(i<r) qsort2(i,r);
}
void work()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i+j>n)
{
t[i][j]=1;
}
else
{
t[i][j]=0;
}
}
}
qsort(1,n);
qsort2(1,n);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&q[i]);
}
work();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d",t[i][j]);
}
printf("\n");
}
return 0;
}
感谢观看
标签:ARC181C,正方形,Column,题解,kl,int,MAXN,序列,return From: https://www.cnblogs.com/huhaoming/p/18373207