CodeForces 835C - Star sky
題意:
天上有n個星星座標各自為(xi, yi)，初始亮度為si；還有全部星星共通的最大亮度c。在t時的亮度為x的星星，若x+1<c，在t+1時的亮度為x+1，否則為0。現在你要觀察天空q次，分別在ti時觀察從(x1, y1)到(x2, y2)之間的星星，問這區間的總亮度是多少？
思路:
用積分圖(integral image)的方式記錄整個天空的初始亮度跟每個亮度的星星數量，之後快速得到輸入區間每個亮度的星星數量後計算指定時間的亮度後加總就是答案。
程式碼:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| using namespace std; | |
| const int AMAX = 1e5 + 7; | |
| struct Star | |
| { | |
| int x; | |
| int y; | |
| int s; | |
| }; | |
| int main() | |
| { | |
| int N, Q, C, n[107][107][17], f[107][107][11]; | |
| Star star[AMAX]; | |
| for(int i = 0; i < 107; ++i) | |
| { | |
| for(int j = 0; j < 107; ++j) | |
| { | |
| for(int k = 0; k < 11; ++k) | |
| { | |
| n[i][j][k] = 0; | |
| } | |
| } | |
| } | |
| cin >> N >> Q >> C; | |
| int x, y, s; | |
| for(int i = 0; i < N; ++i) | |
| { | |
| cin >> x >> y >> s; | |
| ++n[x][y][s]; | |
| } | |
| for(int i = 1; i < 107; ++i) | |
| { | |
| for(int j = 1; j < 107; ++j) | |
| { | |
| for(int k = 0; k < 11; ++k) | |
| { | |
| f[i][j][k] = n[i][j][k] + f[i - 1][j][k] + f[i][j - 1][k] - f[i - 1][j - 1][k]; | |
| } | |
| } | |
| } | |
| int t, x1, y1, x2, y2, a[11]; | |
| for(int q = 0; q < Q; ++q) | |
| { | |
| cin >> t >> x1 >> y1 >> x2 >> y2; | |
| int ans = 0; | |
| for(int i = 0; i < 11; ++i) | |
| { | |
| a[i] = f[x2][y2][i] - f[x1 - 1][y2][i] - f[x2][y1 - 1][i] + f[x1 - 1][y1 - 1][i]; | |
| ans += ((i + t % (C + 1)) % (C + 1)) * a[i]; | |
| } | |
| cout << ans << endl; | |
| } | |
| return 0; | |
| } | |