腾讯秋招软件笔试题8.29

1、妞妞的问题

【题目描述】妞妞公主新得到了一块黑白棋盘。这块棋盘共有n行m列，任意相邻的两个格子都是不同的颜色（黑或白），坐标为(1,1)的格子是白色的。

这一天牛牛来看妞妞公主时，妞妞公主正望着这块棋盘发呆。牛牛看妞妞公主闷闷不乐的样子，便对妞妞公主说：“只要你告诉我n和m，我能马上算出黑色方块和白色方块的数量。”

“这太简单了。”妞妞公主想了一会儿，“我会在这n行m列中选择一个左下角坐标为(x0,y0)。右上角坐标为（x1,y1）的矩形，把这个矩形里的共（x1-x0+1）*(y1-y0+1)个方块全部涂白。你还能马上算出黑色方块和白色方块的数量吗？”

“这太简单了。”牛牛自信一笑，“你可以在执行涂白操作后再选一个左下角坐标为（x2,y2），右上角坐标为(x3,y3)的矩形，把这个矩形里的方块全部涂黑。我依然能马上算出黑色方块和白色方块的数量。”

妞妞公主终于惊讶地睁大了眼，于是抛出了她的T次提问。

聪明的牛牛当然会做了，但是他想把这个问题交给你，请帮牛牛算出每次提问棋盘的黑白方块数目吧。

输入描述:

第一行一个整数T，表示妞妞公主一共提问了T次。

接下来3*T行，

第（1+3*i）行两个整数n，m。表示第i次提问时棋盘的大小；

第（2+3*i）行四个整数x0，y0，x1，y1。表示第i次提问时涂白操作选取的两个坐标。

第（3+3*i）行四个整数x2，y2，x3，y3。表示第i次提问时涂黑操作选取的两个坐标。

1<=T<=10000，1<=x<=n<=1000000000，1<=y<=m<=1000000000，x0<=x1，y0<=y1，x2<=x3，y2<=y3。

输出描述:

共T行，每行两个整数分别表示白色方块的数量和黑色方块的数量。

更多题目尽在《2024校招笔试真题合集》，点击免费领取：https://www.nowcoder.com/link/campus_xzbs5

输入样例：

3
1 3
1 1 1 3
1 1 1 3
3 3
1 1 2 3
2 1 3 3
3 4
2 1 2 4
1 2 3 3

输出样例：

0 3
3 6
4 8

【解题思路】

格子的个数可以快速维护，然后对应维护出来即可。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
long long x[8], y[8];
int main() {
	int T;
	long long n, m, black, white, a, b, c, d, e;
	scanf("%d", &T);
	while(T--) {
		scanf("%lld%lld", &n, &m);
		black = n * m / 2;
		white = n * m - black;
		for(int i = 0; i <= 3; i++)
			scanf("%lld%lld", &x[i], &y[i]);
		if((x[0] + y[0]) & 1)
			d = ((x[1] - x[0] + 1) * (y[1] - y[0] + 1) + 1) / 2;
		else d = (x[1] - x[0] + 1) * (y[1] - y[0] + 1) / 2;
		white += d;
		black -= d;
		if((x[2] + y[2]) & 1)
			d = (x[3] - x[2] + 1) * (y[3] - y[2] + 1) / 2;
		else d = ((x[3] - x[2] + 1) * (y[3] - y[2] + 1) + 1) / 2;
		white -= d;
		black += d;
		a = max(x[0], x[2]);
		b = max(y[0], y[2]);
		c = min(x[1], x[3]);
		d = min(y[1], y[3]);
		if(c < a || d < b) e = 0LL;
		else{
			if((a + b) & 1)
				e = ((c - a + 1) * (d - b + 1) + 1) / 2;
			else e = (c - a + 1) * (d - b + 1) / 2;
		}
		white -= e;
		black += e;
		printf("%lld %lld\n", white, black);
	}
	return 0;
}

资料全部内容请看《2024校招笔试真题秘籍》

不收费，3人组团即可免费领取！已经发出1000份了，涵盖各大公司历年笔试真题+答案，助你事半功倍！

资料包含：

• 30+大厂笔试真题
• 腾讯、阿里、华为、字节、小米、美团、拼多多......
• 100+道技术真题解析&答案

全网独家资料

手机端点击领取：https://www.nowcoder.com/link/campus_xzbs5

电脑端请扫描领取：

资料部分内容展示↓