Codeforces Round #524 (Div. 2) C. Masha and two friends 思路
2024-08-26 02:05:28
题目:题目链接
思路:直接计数显然是不好处理的,但分情况讨论只要不写错这题是一定可以出的,但这样基本做完这个题就没时间做其他题了,但当时我就这么蠢的这样做了,比赛一个半小时的时候突然发现一个似乎可行的规律,但因为时间问题没有证,当时那个思路已经快写完了也没有换思路写,就杯具了,最后那个写了一坨的代码耗了我所有时间还错到了第四组数据。比赛结束用不到二十分钟证明并写出了那个规律的思路。最后赛后交题收获一发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 / ;
white = n * m - black; if((x1 + y1) & ) {
white += ((x2 - x1 + ) * (y2 - y1 + ) + ) / ;
black -= ((x2 - x1 + ) * (y2 - y1 + ) + ) / ;
}
else {
white += ((x2 - x1 + ) * (y2 - y1 + )) / ;
black -= ((x2 - x1 + ) * (y2 - y1 + )) / ;
} if((x3 + y3) & ) {
black += (x4 - x3 + ) * (y4 - y3 + ) / ;
white -= (x4 - x3 + ) * (y4 - y3 + ) / ;
}
else {
black += ((x4 - x3 + ) * (y4 - y3 + ) + ) / ;
white -= ((x4 - x3 + ) * (y4 - y3 + ) + ) / ;
} 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) & ) {
black += ((x6 - x5 + ) * (y6 - y5 + ) + ) / ;
white -= ((x6 - x5 + ) * (y6 - y5 + ) + ) / ;
}
else {
black += ((x6 - x5 + ) * (y6 - y5 + )) / ;
white -= ((x6 - x5 + ) * (y6 - y5 + )) / ;
}
}
cout << white << " " << black << endl;
}
return ;
}
最新文章
- windows 7(32/64位)GHO安装指南(U盘制作篇)~
- gpu对任意长度的矢量求和
- 用excel绘制基因芯片热力图
- sp转dp dp转px
- [原创]Android中LocationManager的简单使用,获取当前位置
- h2database源码浅析:MVTable与MVIndex
- ionic 安装教程
- 初识 Angular 体会
- Linux系统编程(23)——信号的阻塞
- javascript每日一练(十二)——运动框架
- 项目中的Git七步精髓
- Zabbix3.0基础教程之二:item、trigger、action、graph配置
- 通过nginx反向代理接收应用宝回调
- 小程序 lazy-load 不生效的问题
- vim 插件 -- NERDTree
- yum install --downloadonly 下载依赖包到本地 但不安装
- 纯C:url base64
- system表空间空间不足解决办法
- 集合类List、Set、Map的区别、联系和遍历方式
- Emmet (前身为 Zen Coding)
热门文章
- POJ 1797 ——Heavy Transportation——————【最短路、Dijkstra、最短边最大化】
- HDU 5505——GT and numbers——————【素数】
- Elasticsearch在后台启动
- eclipse 中安装spring tool suite 插件100%成功率
- mysql登陆远程数据库
- java 千分位的添加和去除
- Codeforces 744A. Hongcow Builds A Nation
- linux 命令——9 touch (转)
- 小记:iOS 中一般对于 view 不依赖 model 的的两种代码书写形式
- js高级笔录