你真的会睡觉吗

Grapher

2026-01-08 22:09:31

发布于：浙江

54阅读

0回复

0点赞

~~吐槽一下，怎么必须要 AC 了才能发题解，害的我还得先登审核号把自己赛时代码拷过来。~~

我们需要充分发挥人类智慧，仔细观察样例 1 后可以发现当我们对每一行删去最小值后每一行都是一样的。
不妨大胆猜测，如果每一行不一样那么一定不行，如果每一行一样则一定为最优方案。
很显然，当每一行相同时，只需要一直做竖向操作即可，操作唯一。
然后就有以下代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 10;
int n, m, a[maxn];
inline int getid(int i, int j) {
	return (i - 1) * m + j;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int mi = 1e18;
		for (int j = 1; j <= m; j++) cin >> a[getid(i, j)], mi = min(mi, a[getid(i, j)]);
		for (int j = 1; j <= m; j++) a[getid(i, j)] -= mi;
		ans += mi;
	}
	for (int i = 1; i < n; i++) for (int j = 1; j <= m; j++)
			if (a[getid(i, j)] != a[getid(i + 1, j)]) {
				cout << "NO";
				exit(0);
			}
	int sum = 0;
	for (int i = 1; i <= m; i++) sum += a[getid(1, i)];
	cout << "YES\n" << ans + sum;
	return 0;
}

竟然 WA 了！
也是非常神奇。

然后我们动用观察力可以发现有如下 hack。

2 1
1
1

正常应该输出 1，直接竖着做一遍即可。

于是可以找到漏洞，不一样要先把每一行的最小值减去，先减每一列也行。于是我们把行列交换再做一次，两次取最小值。
有如下代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 10;
int n, m;
int a[maxn], b[maxn];
inline int getid(int i, int j) {
	return (i - 1) * m + j;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;

	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
			cin >> a[getid(i, j)], b[getid(i, j)] = a[getid(i, j)];
	int ansa = 0;
	for (int i = 1; i <= n; i++) {
		int mi = 1e18;
		for (int j = 1; j <= m; j++) mi = min(mi, a[getid(i, j)]);
		for (int j = 1; j <= m; j++) a[getid(i, j)] -= mi;
		ansa += mi;
	}
	int ansb = 0;
	for (int j = 1; j <= m; j++) {
		int mi = 1e18;
		for (int i = 1; i <= n; i++) mi = min(mi, b[getid(i, j)]);
		for (int i = 1; i <= n; i++) b[getid(i, j)] -= mi;
		ansb += mi;
	}
	for (int i = 1; i < n; i++) for (int j = 1; j <= m; j++)
			if (a[getid(i, j)] != a[getid(i + 1, j)]) {
				cout << "NO";
				exit(0);
			}
	for (int j = 1; j <= m; j++) ansa += a[getid(1, j)];
	for (int i = 1; i <= n; i++) ansb += b[getid(i, 1)];
	cout << "YES\n" << min(ansa, ansb);
	return 0;
}

然后就过了（？）

声明：

本题解为恶搞做法，不保证思路正确，欢迎大家尝试 hack 本题解，或证明本题解正确性。

彩蛋：

比赛结束三分钟后 cjdst 在 Q 群问 T3 正解是啥，ta 给出了自己一个解方程的做法（显然太吃操作了，对于我这种不会有理数加减法的蒟蒻来讲），我也分享了我的恶搞做法，于是有了本题解。（甚至 cjdst 说以后自己也要乱搞打巅峰赛。

有帮助，赞一个

去预览

0/2000

全部评论 4

肖越腾
对于存在性，下证 $\forall0<i\leq n,0<j\leq m,$

$\begin{equation}a_{i,j}-\min\limits_{0<k\leq m}\{a_{i,k}\}=a_{1,j}-\min\limits_{0<k\leq m}\{a_{1,k}\}\end{equation}$

是存在一种方案的充要条件.

对于必要性，由存在一种方案，可设第 $i$ 行被加了 $r_i$ 次，第 $i$ 列被加了 $c_i$ 次，则 $a_{i,j}=r_i +c_j$ ，所以，

$\begin{align*}a_{i,j}-\min\limits_{0<k\leq m} \{a_{i,k}\}=&r_i+c_j-\min\limits_{0<k\leq m} \{r_i+c_k\}\\=&c_j-\min\limits_{0<k\leq m}\{c_k\}\\\end{align*}$

与 $i$ 的选择无关，必要性得证.

对于充分性，取 $r_i=\min\limits_{0<k\leq m}\{a_{i,k}\},c_j=a_{1,j}-\min\limits_{0<k\leq m}\{a_{1,k}\}$ ，结合 $(1)$ 式，易证该方案合法，充分性得证.

下证该算法能输出最优解.

首先，对于第 $i$ 行，记 $q=\min\{j|a_{i,j}=\min\limits_{0<k\leq m}\{a_{i,k}\}\}=\min\{j|r_i+c_j=\min\limits_{0<k\leq m}\{r_i+c_k\}\}=\min\{j|c_j=\min\limits_{0<k\leq m}\{c_k\}\}$ 与 $i$ 的选择无关，即对于第 $i$ 行，该行最左边的最小值为 $a_{i,q}$ .

取 $p$ 使得 $a_{p,q}=\min\limits_{0<k\leq n}\{a_{k,q}\}$ ，容易发现 $a_{p,q}=\min\limits_{0<i\leq n,0<j\leq m}\{a_{i,j}\}$ . 进而 $r_p\in[0,a_{p,q}],c_q\in[0,a_{p,q}]$ ，结合 $a_{i,j}$ 为最小值，两个范围两边均可以取等.

那么最少操作数 $ans$ 满足：

$\begin{align*}ans=&\min\{\sum_{i=1}^m c_i +\sum_{i=1}^n r_i\}\\=&\min\{\sum_{i=1}^m{(a_{p,i}-r_p)}+\sum_{i=1}^n{(a_{i,q}-c_q)}\}\\=&\sum_{i=1}^m a_{p,i}+\sum_{i=1}^n a_{i,q}-\min\{r_p*m+c_q*n\}\\\end{align*}$

结合 $r_p+c_q=a_{p,q}$ 为定值，容易发现最小值只会在 $(r_p,c_q)=(0,a_{p,q})$ 或 $(a_{p,q},0)$ 时取到.

当 $(r_p,c_q)=(a_{p,q},0)$ 时，

$\begin{align*}ans=&\min\{\sum_{i=1}^m{(a_{p,i}-r_p)}+\sum_{i=1}^n{(a_{i,q}-c_q)}\}\\=&\min\{\sum_{i=1}^m{c_i}+\sum_{i=1}^n{a_{i,q}}\}\\=&\min\{\sum_{i=1}^m{(a_{1,i}-r_1)}+\sum_{i=1}^n{\min\limits_{0<j\leq m}a_{i,j}}\}\\=&\min\{\sum_{i=1}^m{(a_{1,i}-(a_{1,q}-c_q))}+\sum_{i=1}^n{\min\limits_{0<j\leq m}a_{i,j}}\}\\=&\min\{\sum_{i=1}^m{(a_{1,i}-a_{1,q})}+\sum_{i=1}^n{\min\limits_{0<j\leq m}a_{i,j}}\}\\=&\min\{\sum_{i=1}^m{(a_{1,i}-\min\limits_{0<j\leq m}a_{1,j})}+\sum_{i=1}^n{\min\limits_{0<j\leq m}a_{i,j}}\}\\=&ansa \end{align*}$

同理，当 $(r_p,c_q)=(0,a_{p,q})$ 时， $ans=ansb$ ，故 $ans=\min\{ansa,ansb\}$ .
证毕.

由于 $\LaTeX$ 是为了写这篇证明现学的，且字数有限，部分内容可能解释不清或不规范，排版也一般，请见谅。

2026-02-05 来自上海
0
- 肖越腾
  回复
  肖越腾
  所有 $\min\limits_{1\leq i\leq n}$ 之类的都写成了 $\min\limits_{0<i\leq n}$ （为了省字数：\min\limits_{1\leq i\leq n} 比 \min\limits_{0<i\leq n}多了四个字符，通篇下来得省了70个字符左右，我真棒），望见谅。
  
  2026-02-05 来自上海
  0
- Grapher
  回复
  肖越腾
  强强强
  
  2026-02-05 来自浙江
  0
- 古希腊掌管AC和WA的神
  回复
  肖越腾
  %%%
  
  2026-02-05 来自上海
  0
cjdst
你真的会睡觉吗

2026-02-02 来自广东
0
咕咕咕
似乎找到了一个hack:
4 2
7 9
5 7
2 4
6 8

2026-01-10 来自江西
0
- Grapher
  回复
  咕咕咕
  这显然不是hack啊，我的代码和std（见官方题解）输出一样，都是
  
  YES 18
  2026-01-10 来自浙江
  0
- 咕咕咕
  回复
  Grapher
  为什么我测得不一样???
  
  2026-01-10 来自江西
  0
- Grapher
  回复
  咕咕咕
  你测的啥
  
  2026-01-10 来自浙江
  0
Grapher
ddd

2026-01-08 来自浙江
0