2020ICPC·小米 网络选拔赛第一场 J-Matrix Subtraction

传送门：https://ac.nowcoder.com/acm/contest/7501/J

题意

给一个$n\times m$的矩阵和一个$a\times b$的单位矩阵，然后在$n \times m$的矩阵中任取$a\times b$的子矩阵，使其每一位都减1，问能否使原始矩阵变为0。

思路

用二维差分来处理原始矩阵，然后设某一位为(x1，y1)，则只需要对$a\times b$子矩阵进行更新，即(x1，y1)和(x2，y2)。

每次处理的时候都需要判断差分矩阵当前这一位是否非负，因为只能进行矩阵减法。

二维差分处理原始矩阵：

1
2
3
4
5
6
for(int i = 1;i <= n; i++) {
           for(int j = 1;j <= m; j++) {
               cin >> mp[i][j];
               p[i][j] = mp[i][j] - mp[i - 1][j] - mp[i][j - 1] + mp[i - 1][j - 1];
           }
       }

差分更新操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void update(int x1, int y1, int x2, int y2, ll k) {
    p[x1][y1] += k;
    p[x1][y2 + 1] -= k;
    p[x2 + 1][y1] -= k;
    p[x2 + 1][y2 + 1] += k;
}
bool flag = 1;
for(int i = 1;i <= n - a + 1 && flag; i++) {
    for(int j = 1;j <= m - b + 1 && flag; j++) {
        int i1 = i + a - 1, j1 = j + b - 1;
            if(p[i][j] > 0)
                update(i, j, i1, j1, -p[i][j]);
            else if(p[i][j] < 0) {
                   flag = 0;
            }
    }
}

总复杂度为$O(mn)$

Code（97MS）

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
// const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

const int N = 1005;

ll mp[N][N];
ll p[N][N];

void update(int x1, int y1, int x2, int y2, ll k) {
    p[x1][y1] += k;
    p[x1][y2 + 1] -= k;
    p[x2 + 1][y1] -= k;
    p[x2 + 1][y2 + 1] += k;
}

void solve() {
   int T;
   cin >> T;
   while(T--) {

       int n, m, a, b;
       cin >> n >> m >> a >> b;
       for(int i = 1;i <= n; i++) {
           for(int j = 1;j <= m; j++) {
               cin >> mp[i][j];
               p[i][j] = mp[i][j] - mp[i - 1][j] - mp[i][j - 1] + mp[i - 1][j - 1];
           }
       }
       bool flag = 1;

       for(int i = 1;i <= n - a + 1 && flag; i++) {
           for(int j = 1;j <= m - b + 1 && flag; j++) {
               int i1 = i + a - 1, j1 = j + b - 1;
               if(p[i][j] > 0)
                   update(i, j, i1, j1, -p[i][j]);
               else if(p[i][j] < 0) {
                   flag = 0;
               }
           }
       }

       for(int i = n - a;i <= n && flag; i++) {
           for(int j = m - b;j <= m && flag; j++) {
               p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
               if(p[i][j]) {
                   flag = 0;
               }
           }
       }
       if(flag)
           cout << "^_^" << endl;
       else
           cout << "QAQ" << endl;
   }
}

signed main() {
    ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    signed test_index_for_debug = 1;
    char acm_local_for_debug = 0;
    do {
        if (acm_local_for_debug == '$') exit(0);
        if (test_index_for_debug > 20)
            throw runtime_error("Check the stdin!!!");
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
    solve();
##endif
    return 0;
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/10/25/2020-icpc-xiaomi/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！