首页 > 其他分享 >CF1162B Double Matrix 题解

CF1162B Double Matrix 题解

时间:2024-04-10 21:33:18浏览次数:24  
标签:fr ch Matrix 题解 ll p1 Double include buf

传送门

说句实话,如果不是先写了 Showstopper 这道题的话,我应该会在这里卡很久,因为做 Showstopper 我就卡了很久 QwQ。

思路

太像了,实在是太像了,与 Showstopper 想比,仅仅就是换成二维数组,求最大值变为找递增矩阵,处理方法一模一样:将数组 \(a\) 和 \(b\) 中较小的值存在一个数组里,较大的值存在一个数组里就行了。

为什么要这样存呢?举个例子:

当满足 \(a_{i,j}<a_{i,j+1}\) 且 \(a_{i,j}<b_{i,j+1}\),\(a_{i,j+1}>b_{i,j+1}\) 时,此时无论是 \(a_{i,j+1}\) 还是 \(b_{i,j+1}\) 都会比 \(a_{i,j}\) 大,那么将这两个数较小的一个来满足递增,这样对于另外一个数组而言,满足递增的几率才会更大。这里的几率如果看不明白,可以自己将位置 \((i,j)\) 所有情况列出来进行比较,不是很多,这里就不一一列出来了。(其实主要是懒得写

代码

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cstring>
#include<algorithm>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<stdio.h>
#define ll long long
#define inf 0x3f3f3f3f
#define fr(i , a , b) for(ll i = a ; i <= b ; ++i)
#define fo(i , a , b) for(ll i = a ; i >= b ; --i)
using namespace std;
inline char gchar()
{
    static char buf[1000000] , *p1 = buf , *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 1000000 , stdin) , p1 == p2) ? EOF : *p1++;
}
inline ll read()
{
    ll x = 0 , f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
	  {
        if(ch == '-')
        {
        	f = -1;
		}
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
	  {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
ll n , m , a[55][55] , b[55][55];
signed main()
{
    n = read();
    m = read();
    fr(i , 1 , n)
    {
        fr(j , 1 , m)
        {
            a[i][j] = read();
        }
    }
    fr(i , 1 , n)
    {
        fr(j , 1 , m)
        {
            b[i][j] = read();
            if(a[i][j] > b[i][j])
            {
                swap(a[i][j] , b[i][j]);
            }
        }
    }
    fr(i , 1 , n)//判断行
    {
        fr(j , 1 , m - 1)
        {
            if(a[i][j] >= a[i][j + 1] || b[i][j] >= b[i][j + 1])
            {
                printf("Impossible");
                system("pause");
                return 0;
            }
        }
    }
    fr(j , 1 , m)//判断列
    {
        fr(i , 1 , n - 1)
        {
            if(a[i][j] >= a[i + 1][j] || b[i][j] >= b[i + 1][j])
            {
                printf("Impossible");
                system("pause");
                return 0;
            }
        }
    }
    printf("Possible");
    system("pause");
    return 0;
}

标签:fr,ch,Matrix,题解,ll,p1,Double,include,buf
From: https://www.cnblogs.com/xhqdmmz/p/18127522

相关文章

  • 【华为笔试题汇总】2024-04-10-华为春招笔试题-三语言题解(Python/Java/Cpp)
    ......
  • 关于淘宝镜像过期问题解决方案
    问题:将项目拷贝到另一台电脑启动时报错Error:Theprojectseemstorequireyarnbutit'snotinstalled解决方法:1.删除项目中的yarn.lock文件2.终端执行npminstall-gyarn再次启动项目npmrunserve就可以了......
  • Codeforces Round 938 (Div. 3) A-H 题解
    A-YogurtSaleSolution当\(2a>b\)时,显然用\(a\)来买两个比较好,否则就用\(b\)来买两个比较好Code#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn;cin>>n;inta,b;cin>>a>>b;b=min(b,a*2);int......
  • AT_agc038_e [AGC038E] Gachapon 题解
    比较基础的一道题。很容易想到Min-Max容斥:\[E(\max(S))=\sum_{T\subeS}(-1)^{|T|-1}\timesE(\min(T))\]然后发现\(E(\min(T))=\sum_{k\ge0}P(\min(T)\gek)\)。考虑dp,记\(f_{i,j,k}\)表示从前\(i\)个数中选出\(T\),\(\sum_{i\inT}A_i=j,\sum_{i\inT}c_i=k\)且每个......
  • MHY1001. [崩三]椰子树题解
    #include<bits/stdc++.h>usingnamespacestd;constintN=1010,M=20010;intq[M];//s的最大值为20000,v的最小值为1,所以队列里面最多是会有200010个元素的intn,m;intf[M],g[M];intmain(){cin>>n>>m;for(inti=1;i<=n;++i){......
  • CF1804C Pull Your Luck 题解
    题面。翻译清晰,这里就不吐槽了。根据轮盘转动的方法,可以看出这是一个简单的高斯求和。因为这是一个轮盘,在轮盘中转动了\(now\)个格子与转动了\(now\bmodn\)所到达的格子是一样的(这就没必要证明了吧),因此我们很容易就能得到一个最朴素的代码: cin>>T; while(T--) { c......
  • P3891 [GDOI2014] 采集资源 题解
    题面。看到大家都是两个动态规划的写法,来给大家讲一下只用一次动态规划的写法。思路设\(f_{i,j}\)表示工作效率为\(i\),获取\(j\)点资源所需的最短时间,不以苦工设状态是因为苦工会因为后面购买而改变,不太现实。\(tme\)表示答案,即到达\(t\)点资源所需的最短时间。从\(0......
  • P8661 [蓝桥杯 2018 省 B] 日志统计 题解
    好久没写题解了,水一篇。这里主要想讲的是不同的处理方法,在阅读本篇题解前请确保读完题。详解一,排序这很好理解,题目要求将热帖从小到大输出,同时题目中还有相对的时间这一概念,因此将输入的\(id\)与\(ts\)按照优先\(id\)其次\(ts\)的排序方式从小到大,排序,这样输出时就没......
  • CF133B Unary 题解
    题面。在考虑如何优化程序时,不要忽略了这题的纯暴力做法。对于样例2此处样例2的输入应该是++++[>,.<-],也许是翻译问题,但并不重要。思路依据题意,将输入的字符串\(s\)转为其对应的二进制串\(str\),在暴力将\(str\)由二进制转为十进制即可。代码为了防止因为幂运算而......
  • CF1913C Game with Multiset 题解
    翻译初始时你有一个空序列,共\(m\)次操作,每次操作读入两个数\(t_i\),\(v_i\),分为以下两种操作:当\(t_i=1\)时,在空序列中加入\(2^{v_i}\)这一元素。(此时\(0\lev_i\le29\))当\(t_i=2\)时,询问是否存在:取当前序列的某些元素,使它们的的和等于\(v_i\)(此时\(0\lev_i\l......