矩形

当 $(n \le m)$ 时，使用双指针遍历上下边界，同时扫描中间的节点，如果可以更新该段的最小矩阵大小，则进行更新，等全部扫描完后再进行覆盖，同时上边界向下遍历，下边界向上遍历，可以保证数据不会重复使用，反之遍历左右界，从上到下扫描更新，复杂度为 $O(min(n, m) ·nm)$ 。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int INF = 1E9;

void solve() {
    int n, m;
    cin >> n >> m;

    vector<string> s(n);

    for (int i = 0; i < n; i ++ ) cin >> s[i];

    vector<vector<int>> ans(n, vector<int>(m, INF));
    
    if (n < m) {
        for (int i = 0; i < n; i ++ ) {
            vector<int> mi(m, INF);
            for (int j = n - 1; j > i; j -- ) {
                int last = -1;
                for (int k = 0; k < m; k ++ ) {
                    if (s[i][k] == '1' && s[j][k] == '1') {
                        if (last != -1) {
                            int cnt = (j - i + 1) * (k - last + 1);
                            for (int u = last; u <= k; u ++ ) {
                                mi[u] = min(mi[u], cnt);
                            }
                        }
                        last = k;
                    }
                }

                for (int k = 0; k < m; k ++ ) {
                    ans[j][k] = min(ans[j][k], mi[k]);
                }
            }

            for (int k = 0; k < m; k ++ ) {
                ans[i][k] = min(ans[i][k], mi[k]);
            }
        }
    } else {
        for (int i = 0; i < m; i ++ ) {
            vector<int> mi(n, INF);
            for (int j = m - 1; j > i; j -- ) {
                int last = -1;
                for (int k = 0; k < n; k ++ ) {
                    if (s[k][i] == '1' && s[k][j] == '1') {
                        if (last != -1) {
                            int cnt = (j - i + 1) * (k - last + 1);
                            for (int u = last; u <= k; u ++ ) {
                                mi[u] = min(mi[u], cnt);
                            }
                        }
                        last = k;
                    }
                }

                for (int k = 0; k < n; k ++ ) {
                    ans[k][j] = min(ans[k][j], mi[k]);
                }
            }

            for (int k = 0; k < n; k ++ ) {
                ans[k][i] = min(ans[k][i], mi[k]);
            }
        }
    }

    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < m; j ++ ) {
            if (ans[i][j] == INF) ans[i][j] = 0;
            cout << ans[i][j] << ' ';
        }
        cout << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
    
    return 0;
}

怎么还是猫娘

统计所有 'nya' 子串的位置，统计一下有那些子串可以包含这些小的 'nya'，用左端点到上一段的末端，乘上右端点到结尾的长度，就是总的结果。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int MOD = 998244353;

void solve() {
    int n;
    string s;

    cin >> n >> s;
    vector<int> ne;

    for (int i = 0; i < n - 2; i ++ ) {
        if (s[i] == 'n' && s[i + 1] == 'y' && s[i + 2] == 'a') ne.push_back(i);
    }

    LL last = -1;
    LL ans = 0;
    for (int i = 0; i < ne.size(); i ++ ) {
        ans = (ans + (ne[i] - last) * (n - ne[i] - 2) % MOD) % MOD;
        last = ne[i];
    }
    
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
    
    return 0;
}

逃离迷宫

多源BFS遍历所有出口可以到达的坐标，统计有多少人会被遍历到，复杂度为 O(n·m)；

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int main() {
    int n, m;
    cin >> n >> m;

    vector<string> s(n);
    vector<vector<bool>> st(n, vector<bool>(m, 0));
    for (int i = 0; i < n; i ++ ) {
        cin >> s[i];
    }

    int ans = 0;
    queue<PII> q;

    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < m; j ++ ) {
            if (s[i][j] == 'y') {
                q.push({i, j});
                st[i][j] = true;
            }
        }
    }

    while (q.size()) {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ ) {
            int a = t.first + dx[i], b = t.second + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (st[a][b]) continue;
            if (s[a][b] == '#') continue;
            st[a][b] = true;
            if (s[a][b] == 'x') ans ++ ;
            q.push({a, b});
        }
    }

    cout << ans << endl;

    return 0;
}

逮捕猫娘

用前缀和统计一下，同时注意边界处理。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

int main() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;

    s = " " + s;
    vector<int> sum(n + 1, 0);

    for (int i = 3; i <= n; i ++ ) {
        if (s[i - 2] == 'n' && s[i - 1] == 'y' && s[i] == 'a') sum[i] ++ ;
        sum[i] = sum[i] + sum[i - 1];
    }

    while (m -- ) {
        int l, r;
        cin >> l >> r;
        cout << sum[r] - sum[l + 1] << endl;
    }

    return 0;
}

猫娘计数

很经典的状态机dp，对于状态1，只有遇到 $n$ 才会增加，遇到 $y$ 状态 2 会加上状态 1 的个数，表示当前能组成 $ny$ 的子序列个数，状态 3 同理。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    vector<LL> f(3, 0);
    for (int i = 0; i < n; i ++ ) {
        if (s[i] == 'n') f[0] = (f[0] + 1) % MOD;
        if (s[i] == 'y') f[1] = (f[1] + f[0]) % MOD;
        if (s[i] == 'a') f[2] = (f[2] + f[1]) % MOD;
    }
    
    cout << f[2] << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
    
    return 0;
}

不再美丽

只有使两个不能被同化的元素贴在一起，才能使元素变得丑陋，也就是求和第一个元素相同的连续子串的最短长度，或者删除所有开头/结尾的相同字符，使头尾不相等。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

void solve() {
    int n;
    cin >> n;

    vector<int> a(n, 0);
    int ans = n;

    for (int i = 0; i < n; i ++ ) {
        cin >> a[i];
    }

    if (a[0] != a[n - 1]) {
        cout << 0 << endl;
        return;
    }

    for (int i = 0, last = 0; i < n; i ++ ) {
        if (a[0] == a[i]) last ++ ;
        if (i == n - 1 || a[0] != a[i]) {
            ans = min(ans, last);
            last = 0;
        }
    }

    if (ans == n) ans = -1;
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
    
    return 0;
}

年轮

分别统计月份前的天数，再加上该月已经经过的天数，如果月份大于 $3$ 且为闰年，答案需要 $+1$ 。

#include <bits/stdc++.h>
using namespace std;

int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main() {
    int y, m, d;
    cin >> y >> m >> d;

    int ans = d;
    if (m >= 3 && (y % 4 == 0 && y % 100 != 0 || y % 400 == 0)) ans ++ ;

    for (int i = 1; i < m; i ++ ) ans += day[i];

    cout << ans << endl;


    return 0;
}

变魔术

数组原本就相等时，不需要使用操作，反之可以找到一对钥匙， $s_i = s_{i - 1} + 1$ ，通过要是去调整其余数的大小，可以发现，不论是进行操作 1 还是操作 2 ，都不会改变数组中数字的奇偶个数，综上当两个数组中都纯在钥匙，且数组中所有数字奇数个数和偶数个数相同时，才有解决方案。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);

    for (int i = 0; i < n; i ++ ) {
        cin >> a[i];
    }

    for (int i = 0; i < n; i ++ ) {
        cin >> b[i];
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int flag = 1;
    vector<int> cnt1(2, 0), cnt2(2, 0), f(2, 0);
    for (int i = 0; i < n; i ++ ) {
        if (a[i] != b[i]) flag = 0;
        cnt1[a[i] % 2] ++ ;
        cnt2[b[i] % 2] ++ ;
        if (i && a[i] == a[i - 1] + 1) f[0] = 1;
        if (i && b[i] == b[i - 1] + 1) f[1] = 1;
    }

    if (flag) cout << "Yes" << endl;
    else if (f[0] && f[1] && cnt1[0] == cnt2[0] && cnt1[1] == cnt2[1]) cout << "Yes" << endl;
    else cout << "No" << endl;

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
    
    return 0;
}

疯狂星期四

直接输出 $n \times a + m \times b$ 。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, a, m, b;
    cin >> n >> a >> m >> b;
    cout << n * a + m * b << endl;

    return 0;
}

题解 | 武昌首义学院“中软杯”第七届程序设计竞赛

矩形