P8050 [ZYOI Round1] Chessboard game/棋盘游戏 题解

· · 题解

一道很经典的小学奥数题

思路

第一眼看到这道题，这不染色吗，让我们回顾一下小学学的知识。

染色方法是一种对题目所研究的对象用直观形象的染色来进行分类的方法。象国际象棋的棋盘那样,我们可以把研究的对象染上不同的颜色,使问题变得浅显明了，方便研究 。 ----------- 百度。

就拿样例来说，把棋盘黑白染色（这里用 01 代替），得到如下的图。

1 0
0 1
1 0 1 0
0 1 0 1
1 0 1 0

可以看出相邻的两个格子必然是一黑一白，那么每次操作完黑格之和与白格之和的差显然是不变的，那么根据这个，我们不算未知格，计算一开始黑格的和与白格的和的差，然后计除未知格之外黑格的和与白格的和的差，用后者减去前者就得到了未知格的数。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,m,n_,m_,k;
int h,w,a,b,flag,l[205][105]; 
int main(){
    cin>>n>>m>>n_>>m_>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>l[i][j];
            if(l[i][j]==999999){  
                if(i%2!=j%2){ 
                    a+=k;
                    flag=1;
                }
                else{
                    b+=k;
                    flag=0;
                }
            }
            else{ 
                if(i%2!=j%2){
                    a+=k;
                    h+=l[i][j];
                }
                else{
                    b+=k;
                    w+=l[i][j];
                }
            }
        }
    }
    for(int i=n+1;i<=n+n_;i++){
        for(int j=1;j<=m_;j++){
            cin>>l[i][j];
            if(l[i][j]==999999){
                if(i%2!=j%2){
                    a+=k;
                    flag=1;
                }
                else{
                    b+=k;
                    flag=0;
                }
            }
            else{ 
                if(i%2!=j%2){
                    a+=k;
                    h+=l[i][j];
                }
                else{
                    b+=k;
                    w+=l[i][j];
                }
            }
        }
    }
    if(flag)cout<<w-h-(b-a);
    else cout<<h-w-(a-b); 
    return 0;
}