本文主要是介绍CodeForces - 835C Star sky，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：点击打开链接
题目大意：天空中（没有翅膀的痕迹？）有很多小星星，它们的初始亮度不一，且按周期性规律变化，并且最大亮度相等，让你求在某个时刻t，一个矩形区域中所有星星的亮度和。
解题思路：二维前缀和维护一下。sum[i][j][k]表示点(i, j)右下角的所有点中亮度为k的亮度和，那么初始化就是
sum[i][j][k] = sum[i-1][j][k] + sum[i][j-1][k] - sum[i-1][j-1][k]
查询的时候，循环遍历每一个亮度now = (i + t) % (c + 1),把这个亮度的sum加入ans即可。
看懂别人代码后我在想为什么不直接用sum[i][j][t]表示xxx在时刻t的亮度和，然后查询的时候就不用循环了
然后我发现，这样搞预处理是个大问题。。。就放弃了
代码：
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#define FAST ios::sync_with_stdio(false)
#define lowbit(x) x&(-x)
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = (int)1e9 + 7;
const int maxn = (int)105;
using namespace std;int sum[105][105][12];int main()
{int n, q, c;scanf("%d %d %d", &n, &q, &c);for(int i = 1; i <= n; i++){int x, y, v;scanf("%d %d %d", &x, &y, &v);sum[x][y][v]++;}for(int i = 1; i <= 100; i++)for(int j = 1; j <= 100; j++)for(int k = 0; k <= c; k++)sum[i][j][k] += sum[i-1][j][k] + sum[i][j-1][k] - sum[i-1][j-1][k];while(q--){int t, sx, sy, ex, ey, ans = 0;scanf("%d %d %d %d %d", &t, &sx, &sy, &ex, &ey);for(int i = 0; i <= c; i++){int x = (i + t) % (c + 1);ans += x * (sum[ex][ey][i] - sum[sx-1][ey][i] - sum[ex][sy-1][i] + sum[sx-1][sy-1][i]);}printf("%d\n", ans);}return 0;
}
这篇关于CodeForces - 835C Star sky的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
