P6985 [NEERC2014] Alter Board 题解

· · 题解

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;
}