【题解】[CodePlus 2017 12 月赛] 可做题 1 loj6256 ——quhengyi11

传送门

吐槽

突然想起来 CodePlus 似乎过几天有比赛，然后就发现自己已经忘记了 CodePlus 的网址，接着在网上查了半天不小心点进了这道题，最后就被吸引住了 (

这题虽然比较简单但是感觉思想还是蛮有趣的所以有了这篇题解

题解

首先作为一只正常的猫，你会去想想这种特殊的限制会不会决定了一个合法方阵中是否有一些数会被强制取等。

然后你看看题目你就知道了这样想是错误的。

但是你还是会很容易注意到一件事情，一个 $n$ 阶方阵中的任意一个低于 $n$ 阶的子方阵一定是巧妙的，由 $n$ 阶子方针的定义便可以证明。

注意到所有一阶方阵都是巧妙的，所以我们就容易想到，如果一个 $n$ 阶方阵巧妙，是否等价于里面的所有二阶子方阵都巧妙

必要性上面已经证明了，充分性只需要一点脑子就能往下推完了。

考虑调整法，我们需要证明，如果所有二阶子方阵巧妙，则 $a_{1,b_1}+a_{2,b_2}+\cdots + a_{n,b_n} = a_{1,1}+a_{2,2}+\cdots+a_{n,n}$ ，其中 $b_1$ 到 $b_n$ 是一个 $n$ 的排列。

我们只需要证明， $a_{1,b1}+a_{2,b2}=a_{1,b2} + a_{2,b1}$

感谢 $Remmina$ 大佬的绘图 ( $qhy$ 不用放灵魂图了)

由二阶子方阵定义，红线内数字和=绿线内数字和，所以 $A+B=C+D$ ，得证。

你这样就相当于证明了排列 $b$ 中的数是可交换的，所以所有排列是必定能通过交换有限次变为顺序列的。

$Q.E.D.$

所以二维前缀和预处理一下就行了，代码超短

#include<bits/stdc++.h>
#define N 3005
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define Re register
#define mod 998244353
#define ll long long
ll a[N][N], b[N][N], k, n, m, T, x, y;
inline ll sum (ll x, ll y, ll x1, ll y1)
{
    return b[x1][y1] - b[x1][y] - b[x][y1] + b[x][y];
}
int main()
{
    scanf("%lld %lld %lld", &n, &m, &T);
    fo (i, 1, n) fo (j, 1, m) scanf("%lld", &a[i][j]);
    fo (i, 2, n) fo (j, 2, m) b[i][j] = (a[i][j] + a[i - 1][j - 1]) == (a[i - 1][j] + a[i][j - 1]);
    fo (i, 2, n) fo (j, 2, m) b[i][j] = b[i][j] + b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
    while (T--)
    {
        scanf("%lld %lld %lld", &x, &y, &k);
        bool flag = sum(x, y, x + k - 1, y + k - 1) == (k - 1) * (k - 1);
        flag ? printf("Y\n") : printf("N\n");
    }
}

【题解】[CodePlus 2017 12 月赛] 可做题 1 loj6256 ——quhengyi11

于2019年3月4日2019年3月4日由HomuraCat发布

吐槽

题解

HomuraCat

3 条评论

quhengyi11 · 2019年3月4日 6:54 下午

Remmina · 2019年3月4日 9:27 下午

quhengyi11 · 2019年3月4日 10:22 下午

发表回复取消回复

【题解】[CodePlus 2017 12 月赛] 可做题 1 loj6256 ——quhengyi11

于2019年3月4日2019年3月4日由HomuraCat发布

吐槽

题解

HomuraCat

3 条评论

quhengyi11 · 2019年3月4日 6:54 下午

Remmina · 2019年3月4日 9:27 下午

quhengyi11 · 2019年3月4日 10:22 下午

发表回复 取消回复

发表回复取消回复