自动搬运

查看原文

来自洛谷，原作者为

	indream ？

搬运于2025-08-24 22:25:40，当前版本为作者最后更新于2024-01-11 23:11:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P6985 [NEERC2014] Alter Board 题解

P6985 | AC

思路

很神奇。

这是一个棋盘：（$n=m=7$）

0101010
1010101
0101010
1010101
0101010
1010101
0101010

贪心考虑让每次翻转中同色的尽可能多，即“副作用”尽量小。

方法：可以先把每个偶数行整行翻转，得到下面的棋盘：

0101010
0101010
0101010
0101010
0101010
0101010
0101010

接下来干什么大家到知道：把所有偶数列整列翻转即可。

为什么是偶数行，偶数列？

当 $n,m\bmod2=1$ 时显然有优势：比如行，翻奇数列翻 $n\div2+0.5$ 次，而翻偶数列要少 $1$ 次。

最终显然要 $n/2+m/2$ 次（向下取整）。

代码实现只需模拟即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
    cin>>n>>m;
    cout<<n/2+m/2<<'\n';
    for(int i=2;i<=n;i+=2)
        cout<<i<<" 1 "<<i<<' '<<m<<'\n';
    for(int i=2;i<=m;i+=2)
        cout<<"1 "<<i<<' '<<n<<' '<<i<<'\n';
  return 0;
}