Star sky -每天一把CF - 20201028

2020-10-28

dp

835C 1600

题目

原题链接:https://codeforces.com/problemset/problem/835/C

思路

题目大意：一个无限大的矩阵中随机散布着一些星星，这些星星有自己独特的初始亮度以及统一的最大亮度，每过一秒星星亮度就会增加1，当星星亮度超过最大亮度时就再次从0开始计数，问t时刻时某个给定的小矩阵内的星星总的亮度时多少。

思路：二维差分，去统计从1,1到x，y的矩阵中各种亮度的灯各有多少，然后用二维差分计算要求的小矩阵中各种亮度的星星有多少，然后就是数量*（（亮度+时间）%最大亮度）。

一开始脑子抽了，没看x，y的取值范围只是1-100，以为是随机分布在一个1e5*1e5的矩阵中，不能拿二维数组去存星星，自己还去拿结构体存，还用到原点的距离进行排序，以减少查询时的复杂度。结果测试10直接n=q=1e5，当场TLE。。。。

搞到最后才知道把x,y范围看错了.吐了。

代码实现

TLE款

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;#define mes0(c) memset((c),0,sizeof(c))typedef long long ll;
typedef struct {int x, y, l;
}node;const int MAX = 1e5 + 5;
const ll inf = 1e15;ll n, q, c1;
node st[MAX];
ll a, b, c, d, e;bool cmp(node a, node b) {return a.x * a.x + a.y * a.y < b.x * b.x + b.y * b.y;
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);while (cin >> n >> q >> c1) {mes0(st);c1++;for (int i = 1; i <= n; i++)cin >> st[i].x >> st[i].y >> st[i].l;sort(st + 1, st + 1 + n, cmp);while (q--) {cin >> a >> b >> c >> d >> e;ll ans = 0;ll tpx, tpy, tpl;for (int i = 1; i <= n; i++) {tpx = st[i].x, tpy = st[i].y, tpl = st[i].l;if (tpx > d && tpy > e) break;if (tpx >= b && tpx <= d && tpy >= c && tpy <= e)ans += (tpl + a) % c1;}cout << ans << endl;}}return 0;
}

AC

#include <iostream>
using namespace std;const int N = (int)1e5 + 123;
const int C = 101;
const int P = 11;int n, q, c;
int cnt[P][C][C];int main() {cin >> n >> q >> c;for (int i = 0; i < n; i++) {int x, y, s;cin>>x>>y>>s;cnt[s][x][y]++;}for (int p = 0; p <= c; p++) {for (int i = 1; i < C; i++) {for (int j = 1; j < C; j++) {cnt[p][i][j] += cnt[p][i - 1][j] + cnt[p][i][j - 1] - cnt[p][i - 1][j - 1];}}}for (int i = 0; i < q; i++) {int t, x1, y1, x2, y2;cin >> t >> x1 >> y1 >> x2 >> y2;int ans = 0;for (int p = 0; p <= c; p++) {int brightness = (p + t) % (c + 1);int amount = cnt[p][x2][y2] - cnt[p][x1 - 1][y2] - cnt[p][x2][y1 - 1] + cnt[p][x1 - 1][y1 - 1];ans += brightness * amount;}cout << ans << "\n";}return 0;
}