Codeforces 835C [容斥]

题目

835C

题意

有n个亮度会变的星星,某人要观察星星q次,星星的最大亮度为c,初始的亮度会给出。

t时刻亮度为x,那么t+1时刻亮度为x+1,如果x+1>c,亮度归0.

每个星星有自己的坐标,现在求每一次观察的范围(范围是矩形)星星亮度的和。

输入

第一行:给出 n, q, c
之后n行:xi, yi, Si. 分别代表 横纵坐标 和 初始亮度
之后q行:观察的时刻ti, 以及两个坐标(坐标分别是矩形的 左下 和 右上)

输出

输出每一次观察的矩形范围内的亮度之和

样例输入

2 3 3
1 1 1
3 2 0
2 1 1 2 2
0 2 1 4 5
5 1 1 5 5

样例输出

3
0
3

题解分析

首先,亮度的变化周期为c+1,所以虽然 t 给的范围很大,实际上可以先模一波(t+1) ,那么有t≤10

其次给的数据量很大,需要预处理一下,具体操作就是给出初始亮度之后,就立马计算出各个时间点的状态,存下来。然后所有星星录入完之后,鉴于坐标范围只有100*100,枚举计算一下每个坐标跟x,y轴形成的矩形的亮度和,这样完成之后,根据容斥原理计算一下就好,基本上就是O(1)了?

CF835C

例如要求橙色区域的。就是 绿色 -(粉色 + 紫色 - 灰色)。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
using namespace std;
int s[11][110][110];
int main(void)
{
int n,q,c;
cin>>n>>q>>c;
for(int i=0;i<n;i++)
{
int x,y,f;
cin>>x>>y>>f;
for(int j=0;j<=10;j++)
s[j][x][y] += (f+j)%(c+1); //似乎坐标可以重复,所以使用+= ?
}
for(int t=0;t<=10;t++)
for(int x=1;x<=100;x++)
for(int y=1;y<=100;y++)
s[t][x][y] += s[t][x-1][y] + s[t][x][y-1] - s[t][x-1][y-1];
for(int i=0;i<q;i++)
{
int t,x1,x2,y1,y2;
int res;
cin>>t>>x1>>y1>>x2>>y2;
t %= (c+1);
res = s[t][x2][y2] - (s[t][x1-1][y2]+s[t][x2][y1-1]-s[t][x1-1][y1-1]);
cout<<res<<endl;
}
return 0;
}