说句实话,如果不是先写了 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