当前位置:网站首页>B - 代码派对(女生赛)
B - 代码派对(女生赛)
2022-07-06 09:25:00 【是小张张呀 zsy】
B - 代码派对
Sample Input
2
3
3 1 3 1
1 1 2 3
2 1 3 2
5
1 1 4 5
2 1 3 2
2 2 3 3
4 5 4 5
1 2 2 4
Sample Output
0
4
//现在时刻,2021年10月28号00:38我终于ac了,,,,呜呜呜呜
/*解题思路 利用差分和二维前缀和求出每个格子上覆盖的区间数g[i][j]。 如果这个时候求C(g[i][j],3)的和,那么会产生很多的重复,因为同样的三个区间可以覆盖多个格子。 所以我们只保留覆盖区域左上角的那个格子,因为这个格子一定在区间的上边和左边上,所以最后答案为: 总和 - 删掉左边后的和 - 删掉上边后的和 + 删掉上边和左边后的和(前面重复减了这一块,所以加回去)。 */
#include<iostream>
#include<cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#define N 1005
using namespace std;
typedef long long ll;
int a1[N][N],a2[N][N],a3[N][N],a4[N][N];
ll c3[100005];
ll wo(int a[N][N])
{
for(int i=1;i<=1000;i++){
for(int j=1;j<=1000;j++){
a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];//求和;
}
}
ll ans=0;
for(int i=1;i<=1000;i++){
for(int j=1;j<=1000;j++){
ans+=c3[a[i][j]]; //一共(包扣)重叠的有ans;
}
}
return ans;
}
int main(){
int T;
c3[3]=1;
cin>>T;
for(int i=4;i<=100000;i++){
c3[i]=(ll)i*(i-1)*(i-2)/6;//如果有i人选同一个格可组队情况
}
while(T--)
{
int n;
cin>>n;
memset(a1,0,sizeof(a1));//每次循环赋值0;
memset(a2,0,sizeof(a2));
memset(a3,0,sizeof(a3));
memset(a4,0,sizeof(a4));
int x1,y1,x2,y2;
for(int i=1;i<=n;i++){
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);//这用cin就超时了,以后比赛再无cin;
a1[x1][y1]++,a1[x2+1][y1]--,a1[x1][y2+1]--,a1[x2+1][y2+1]++;
//二维差分,给以(x1,y1)到(x2,y2)的矩阵都加1;
a2[x1+1][y1]++,a2[x2+1][y1]--,a2[x1+1][y2+1]--,a2[x2+1][y2+1]++;
//每个矩阵减去左边(除了第一行),x1+1;
a3[x1][y1+1]++,a3[x2+1][y1+1]--,a3[x1][y2+1]--,a3[x2+1][y2+1]++;
//每个矩阵减去上边(除了第一列),y1+1;
a4[x1+1][y1+1]++,a4[x2+1][y1+1]--,a4[x1+1][y2+1]--,a4[x2+1][y2+1]++;
//加上多减的;
}
cout<<wo(a1)-wo(a2)-wo(a3)+wo(a4)<<endl;
}
return 0;
}
边栏推荐
- Accounting regulations and professional ethics [3]
- F - Birthday Cake(山东省赛)
- STM32 learning record: input capture application
- LeetCode#62. Different paths
- Research Report on market supply and demand and strategy of China's land incineration plant industry
- 动态规划前路径问题优化方式
- Market trend report, technical innovation and market forecast of lip care products in China and Indonesia
- 学习记录:STM32F103 时钟系统概述工作原理
- Research Report on medical anesthesia machine industry - market status analysis and development prospect prediction
- Cost accounting [17]
猜你喜欢
随机推荐
ucore Lab 1 系统软件启动过程
Cost accounting [21]
LeetCode#204. Count prime
Scoring system based on 485 bus
Research Report on pharmaceutical R & D outsourcing service industry - market status analysis and development prospect forecast
基于485总线的评分系统
学习记录:STM32F103 时钟系统概述工作原理
C语言学习笔记
Perinatal Software Industry Research Report - market status analysis and development prospect forecast
力扣刷题记录--完全背包问题(一)
0-1背包问题(一)
Flex --- detailed explanation of flex layout attributes
Interface test interview questions and reference answers, easy to grasp the interviewer
JS --- all knowledge of JS objects and built-in objects (III)
Take you to use wxpy to create your own chat robot (plus wechat interface basic data visualization)
TCP的三次握手与四次挥手
Lab 8 file system
LeetCode#53. Maximum subarray sum
用C语言写网页游戏
ucorelab4