首页 > 其他分享 >[ARC181C] Row and Column Order 题解

[ARC181C] Row and Column Order 题解

时间:2024-08-22 10:17:31浏览次数:9  
标签:ARC181C 正方形 Column 题解 kl int MAXN 序列 return

题目大意

给你一个 \(N\),然后再给你两个长度为 \(N\) 的序列。让你构造一个仅有 \(0\) 和 \(1\) 的 \(N \times N\) 的正方形,但是要满足两个序列的顺序:

  1. 第一个序列指的是该正方形每一行所构成的二进制数的大小顺序。
  2. 第二个序列指的是该正方形每一列所构成的二进制数的大小顺序。

分析

既然要满足顺序,那么肯定都是不同的,故二进制所表示的数也不同。
接着,我们尝试猜想:可不可以让这个正方形原来是递增状态,然后直接对行和列排序得到答案呢?
(递增状态指的是满足两个序列都是严格递增的状态,不懂的可以看下面的例子)
举一个递增状态的例子:

当然还有一种:

(不好意思,图在洛谷

首先我们可以推一下小一点的样例,然后可以发现,单独排行时,对于列来说,状态仍然递减,因为排完行后,每一列的状态不过是在上一列的基础上增加一个 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

相关文章

  • 题解:AT_abc352_e [ABC352E] Clique Connect
    [题目通道]([ABC352E]CliqueConnect-洛谷)鄙人今日写人生第一篇题解希望管理大大通过首先,我们先看题:它说一共有n个点,m回操作。。。每次操作都有一个Ki和CiKi代表有Ki个点,Ci代表每条边所赋的边权一看就知道这是个最小生成树的板子我使用了著名的kruskal话......
  • P10892 题解
    思路考虑贪心策略。当剩下的猫猫数量为偶数的时候,直接取出\(\large\frac{n}{2}\)只猫猫即可。否则当剩下的猫猫数量为奇数的时候,则要尽可能保持第二天猫猫的数量为偶数。则要考虑\(n-\large\frac{n-1}{2}\)和\(n-\large\frac{n+1}{2}\)哪个是偶数。第二条化简一下就......
  • AGC003 题解
    目录A-WannagobackhomeB-SimplifiedmajhongA-Wannagobackhome注意到横纵坐标是独立的,因此可以分开考虑。考虑横坐标或纵坐标最终为零的充要条件为:没有出现任何关于它的任何操作(没有N和S,或没有W和E);出现所有关于它的任何操作(有向正方向走与往负方向走,如有......
  • CF2000 A~C 题解
    CodeforcesRound967(Div.2)A~C题解(未完待续)唐完了,B构造不会,C交互不会,整场爆切\(1\)题喜提\(-115\)rating强势上灰!我还会什么?I.2001A-MakeAllEqual先找出答案的下界。设众数为\(x\),其出现的次数为\(\operatorname{cnt}(x)\)。由于每次操作只能删除一个数,答......
  • CF889E题解
    \(\text{Problem-889E-Codeforces}\)\(\text{*3000}\)题意给一个序列,对于一个非负整数\(x\),有一个式子:\[x\bmoda_1+x\bmoda_1\bmoda_2+...+x\bmoda_1\bmoda_2...\bmoda_n\]求出上式的最大值。思路先去寻找题目的性质。首先\(x\)的值单调不增,然后如果当前\(x......
  • [SCOI2014] 方伯伯的玉米田 题解
    对于每次修改的区间以及其左边序列和右边序列,共三种情况:1.区间内比两侧低的还是低2.区间内比两侧低的变得比两侧高了3.区间内比两侧高的还是高那么现在又面临一个问题:在区间内变化后,对答案,即最长不下降子序列有什么影响。对区间左边:可能会使其最长不下降子序列增长对区间......
  • SP368 CSTREET - Cobbled streets 题解
    题意选n−1条道路连接n个城市,且使得其修建的价格最小。分析最小生成树的模板题,可以用kruskal来做。首先,先将所有的边权从小到大排序。然后,取当前没有选过的,且边权最小的边,判断它连接的两个点是否同属一个集合,如果不是就把他们加到同一个集合中,再记录答案。代码很简单,......
  • [CERC2019] ABB 题解
    题目可以转化为求最长回文子串,答案就是长度减去最长回文子串的长度。看到是求最长回文子串,一眼就容易想到马拉车。此题只需在求出回文半径的基础上储存回文串的右端点,将求出的右端点排序,只要右端点不在最后的字符就结束(不能补),如果在最后的字符就取原字符串长度与当前回文子串的差......
  • [JOISC 2023 Day3] Tourism 题解
    大家好,我喜欢珂朵莉树,所以我用珂朵莉树\(AC\)了本题。实际上,我们比较容易发现,这题实际上就是求\([l,r]\)中的所有点作为关键点时,虚树所压缩的所有点(实际上就是显现出来的点+在虚边上的点)。那么我们容易发现,一个点\(x\)作为虚树所压缩的所有点的充要条件为:\(x\)是至少......
  • 【题解】Solution Set - NOIP2024集训Day12 树上启发式合并
    【题解】SolutionSet-NOIP2024集训Day12树上启发式合并https://www.becoder.com.cn/contest/5472「CF600E」Lomsatgelral直接dsuontree。记录每一个颜色的出现次数。「IOI2011」Race之前是用点分治做的。考虑dsuontree。每个子树内维护到根节点的距离为\(x\)......