Codeforces Round #524 (Div. 2) C. Masha and two friends 思路

题目:题目链接

思路:直接计数显然是不好处理的,但分情况讨论只要不写错这题是一定可以出的,但这样基本做完这个题就没时间做其他题了,但当时我就这么蠢的这样做了,比赛一个半小时的时候突然发现一个似乎可行的规律,但因为时间问题没有证,当时那个思路已经快写完了也没有换思路写,就杯具了,最后那个写了一坨的代码耗了我所有时间还错到了第四组样例。比赛结束用不到二十分钟证明并写出了那个规律的思路。最后赛后交题收获一发AC。

  首先没有涂色时白色和黑色数量我们可以直接算出,然后只考虑涂白色时,我们算这个区域内黑色方块数量,更新白色和黑色方块数量,然后只考虑涂黑色方块,我们计算不考虑上次涂白色的情况下有多少白色被更新为黑色,最后考虑黑白重合的区域,对于这个区域,我们计算有多少最开始是黑色,然后被涂成白色,然后被涂成黑色并且没有在上一步计数的方块数量,这个区域坐标为(max(x1, x3),max(y1, y3)),(min(x2, x4), min(y2, y4))。

  自己还是心态太差了,做题很容易紧张,尤其当时间很紧迫时,组队赛甚至因为时间问题吼过队友,,,回想自己在时间紧迫时太容易急躁了,不只是在比赛方面,生活各方面都是这样,明知道急躁时没用的还是很难改,这个题当时静下来想一下当时是可以直接换思路过的,要改呀。

AC代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <set>

#define INF 0x3f3f3f3f

#define FRER() freopen("in.txt", "r", stdin);
#define FREW() freopen("out.txt", "w", stdout);

using namespace std;

int main()
{
    //FRER();
    int t;
    cin >> t;
    long long n, m, black, white, x1, y1, x2, y2, x3, y3, x4, y4;
    while(t--) {
        cin >> n >> m;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
        black = n * m / 2;
        white = n * m - black;

        if((x1 + y1) & 1) {
            white += ((x2 - x1 + 1) * (y2 - y1 + 1) + 1) / 2;
            black -= ((x2 - x1 + 1) * (y2 - y1 + 1) + 1) / 2;
        }
        else {
            white += ((x2 - x1 + 1) * (y2 - y1 + 1)) / 2;
            black -= ((x2 - x1 + 1) * (y2 - y1 + 1)) / 2;
        }

        if((x3 + y3) & 1) {
            black += (x4 - x3 + 1) * (y4 - y3 + 1) / 2;
            white -= (x4 - x3 + 1) * (y4 - y3 + 1) / 2;
        }
        else {
            black += ((x4 - x3 + 1) * (y4 - y3 + 1) + 1) / 2;
            white -= ((x4 - x3 + 1) * (y4 - y3 + 1) + 1) / 2;
        }

        long long x5 = max(x1, x3), y5 = max(y1, y3), x6 = min(x2, x4), y6 = min(y2, y4);
        if(x6 >= x5 && y6 >= y5) {
            if((x5 + y5) & 1) {
                black += ((x6 - x5 + 1) * (y6 - y5 + 1) + 1) / 2;
                white -= ((x6 - x5 + 1) * (y6 - y5 + 1) + 1) / 2;
            }
            else {
                black += ((x6 - x5 + 1) * (y6 - y5 + 1)) / 2;
                white -= ((x6 - x5 + 1) * (y6 - y5 + 1)) / 2;
            }
        }
        cout << white << " " << black << endl;
    }
    return 0;
}