526互联

D. Matrix Cascade

发布时间 2023-09-02 19:31:44作者: KuriSh

D. Matrix Cascade

仔细想想会觉得这题的限定方式很像物理上波的传播。所以我们建立一个结构体，对于给定的n*n的表格上的每个点，都定义它具有四个属性：

  • val 该点初始的值是多少 (1/0)

  • under_wave_num 该点处于几个波下。可以知道，如果一个点处于某些波的影响下，那么该点正下方的点也一定处于这些波的影响下

  • lnum 每个波除了向下传播之外，还会向左下和右下传播。所以记录每个点会替几个波向左下传播，替几个波向右下传播，然后把这两个属性赋给该点左下/右下的点，同时更新被传播的点的under_wave_num：既然这些点被一些额外的波影响了，那么影响该点的波的数量自然会增加上这些波的数量。

  • rnum

根据定义的这些属性和传播规律，把n*n的表打完，同时记录答案即可。每次检测一个点是，val += under_wave_num，然后判断val % 2 是否等于1。如果是，那么让答案加一并且让under_wave_num, lnum, rnum 加一，即表示产生了新的波。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 struct point{
 5     int under_wave_num = 0;
 6     int val = 0;
 7     int lnum = 0;
 8     int rnum = 0;
 9 };
10 
11 void solve(){
12     int n;
13     cin >> n;
14     vector<vector<point>> grid(n + 2, vector<point>(n + 2));
15     for(int i = 1; i <= n; i++){
16         for(int j = 1; j <= n; j++){
17             char ch;
18             cin >> ch;
19             grid[i][j].val = ch - '0';
20         }
21     }
22 
23     int ans = 0;
24     for(int i = 1; i <= n; i++){
25         for(int j = 1; j <= n; j++){
26             grid[i][j].val += grid[i][j].under_wave_num;
27             if(grid[i][j].val % 2 == 1){
28                 ans++;
29                 grid[i][j].under_wave_num++;
30                 grid[i][j].lnum++;
31                 grid[i][j].rnum++;
32             }
33 
34             grid[i+1][j].under_wave_num += grid[i][j].under_wave_num;
35             
36             grid[i+1][j-1].lnum += grid[i][j].lnum;
37             grid[i+1][j-1].under_wave_num +=grid[i][j].lnum;
38 
39             grid[i+1][j+1].rnum += grid[i][j].rnum;
40             grid[i+1][j+1].under_wave_num += grid[i][j].rnum;
41         }
42     }
43 
44     cout << ans << endl;
45 }
46 
47 int main(){
48     int t;
49     cin >> t;
50     while(t--){
51         solve();
52     }
53     return 0;
54 }