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

题意:给一个n*m的矩阵  里面初始是黑白相间的格子,两坐标和为偶数的都是白格子,奇数的为黑格子,现在有次操作,第一次操作时将给定

区域内的格子全部变成白色,第二次操作时将给定区域内的操作全部变为黑格子 问最后的白格子有多少,黑格子有多少

思路:算出总的白格子  然后用总数减去黑格子即可

关键在于 重合部分的处理  就是用min和max 包括4种情况 减少代码量  

还有就是 思考到 让第一次操作避免操作到重合部分, 即 +上后 又进去那一部分, 然后第二次的操作就不用处理了

Codeforces Round #524 (Div. 2) C. Masha and two friends
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn =1e5+5;
 5 
 6 int main()
 7 {
 8     ios::sync_with_stdio(false);
 9     cin.tie(0);
10     int t;
11     cin>>t;
12     while(t--)
13     {
14         ll n,m;
15         cin>>n>>m;
16         ll x1,y1,x2,y2;
17         ll x3,y3,x4,y4;
18         cin>>x1>>y1>>x2>>y2;
19         cin>>x3>>y3>>x4>>y4;
20         ll tot=(n*m+1)/2;//总的白  只算白的 总的减去白为黑
21         ll shu=(x2-x1+1)*(y2-y1+1);
22         tot+=shu/2;//第一次的占据增加了多少白格子   也就是+上区域内的黑格子数
23         if(shu%2&&(x1+y1)%2)  // 判断多出来的一个格子是黑是白
24             tot++;
25         ll shu2=(x4-x3+1)*(y4-y3+1);
26         tot-=shu2/2;//第二次占据减少了多少白格子   也就是减去区域内的白格子数
27         if(shu2%2&&(x3+y3)%2==0)
28             tot--;
29         //处理重合的部分  这里是关键
30         ll xx1=max(x1,x3);
31         ll xx2=min(x2,x4);
32         ll yy1=max(y1,y3);
33         ll yy2=min(y2,y4);
34         if(xx2>=xx1&&yy2>=yy1)  // 这样的话可以包括重合的四种情况 无需讨论
35         {
36             ll shu1=(xx2-xx1+1)*(yy2-yy1+1);
37             //处理重合的时候 只需要让第一次操作增加的白格子中多增加
38             // 的那部分白格子减去就好,那么就是减去重合部分中的黑格子数
39             tot-=shu1/2+(shu1%2&&(xx1+yy1)%2);
40         }
41         cout<<tot<<" ";
42         cout<<n*m-tot<<'\n';
43 
44 
45     }
46 
47 
48 }
View Code

 

上一篇:最优化算法python实现篇(1)——进退法


下一篇:LeetCode算法题解 1037-有效的回旋镖