ag亚游网站ag亚游网站

ag亚游平台
ag亚游国际

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

 

, 1, 0, 9);

欢迎阅读本文章: 樊友星

环亚游戏娱乐

ag亚游平台