题解 | #2023牛客暑期多校训练营8#

H

考虑单调栈。

$O (n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int N = 1E6;

vector<int> p[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    i64 ans = 0;
    vector<int> st;
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) {
            st.push_back(i);
            p[0].push_back(i);
        } else {
            int cur = -1;
            if (!p[a[i] - 1].empty()) {
                cur = p[a[i] - 1].back();
                p[a[i] - 1].pop_back();
                p[a[i]].push_back(cur);
            }
            while (!st.empty() && st.back() > cur) {
                st.pop_back();
            }
        }
        ans += st.size();
    }
    cout << ans << '\n';
    
    return 0;
}

J

考虑从后向前， $|a_{i}-a_{i+1}|=3$ 或 $|a_{i}-a_{i+1}|=5$ 。

\begin{aligned} a_{n-1}&=n\\ a_{n-2}&=n-3\\ a_{n-3}&=n-6\\ a_{n-4}&=n-1\\ a_{n-5}&=n-4\\ a_{n-6}&=n-7\\ a_{n-7}&=n-2\\ a_{n-8}&=n-5\\ a_{n-9}&=n-8\\ &\dots \end{aligned}

$8$ 个为一循环，前面的 $n\mod{8}$ 个数打个表，只需保证 $a_{(n\mod{8}) - 1}=n$ 。

$O (n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

vector<vector<int>> p = {
    {},
    {1},
    {1, 2}, 
    {1, 2, 3},
    {1, 2, 3, 4},
    {1, 4, 3, 2, 5},
    {5, 2, 1, 4, 3, 6},
    {5, 6, 1, 2, 3 ,4 ,7}
};

void solve() {
    int n;
    cin >> n;
    int k = n % 8;
    vector<int> a(k);
    for (int i = 0; i < (int) p[k].size(); i++) {
        a[i] = p[k][i];
    }
    for (int i = k; i < n; i += 8) {
        a.push_back(i + 3); // n-5
        a.push_back(i + 6); // n-2
        a.push_back(i + 1); // n-7
        a.push_back(i + 4); // n-4
        a.push_back(i + 7); // n-1
        a.push_back(i + 2); // n-6
        a.push_back(i + 5); // n-3
        a.push_back(i + 8); // n
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << " \n"[i == n - 1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

K

如果无论怎么操作都不能还原就 NSFW。

若先手能一次还原就 FOX。

若先手不能一次还原且 $n\ge 3,m\ge 3$ 就 NSFW。

若 $n< 3,m\ge 3$ ，后手捣乱，要么 CAT，要么 NSFW。

若 $n\ge 3,m<3$ ，先手捣乱，要么 FOX，要么 NSFW。

$O (n m)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

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

    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            a[i][j]--;
        }
    }

    vector<int> r(n, -1), c(m, -1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            r[i] = a[i][j] / m;
            c[j] = a[i][j] % m;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] / m != r[i] || a[i][j] % m != c[j]) {
                cout << "NSFW\n";
                return;
            }
        }
    }

    vector<int> visr(n), visc(m);
    int Fox = n;
    for (int i = 0; i < n; i++) {
        if (!visr[i]) {
            for (int j = i; !visr[j]; j = r[j]) {
                visr[j] = 1;
            }
            Fox--;
        }
    }

    int Cat = m;
    for (int i = 0; i < m; i++) {
        if (!visc[i]) {
            for (int j = i; !visc[j]; j = c[j]) {
                visc[j] = 1;
            }
            Cat--;
        }
    }

    if (Fox == 1 && Cat == 0) {
        cout << "FOX\n";
        return;
    }

    if (n >= 3 && m >= 3) {
        cout << "NSFW\n";
        return;
    }

    if (n >= 3) {
        if ((Fox + Cat) % 2 == 0) {
            cout << "NSFW\n";
        } else {
            cout << "FOX\n";
        }
        return;
    } 

    if (m >= 3) {
        if ((Fox + Cat) % 2 == 0) {
            cout << "CAT\n";
        } else {
            cout << "NSFW\n";
        }
        return;
    }
    
    if ((Fox + Cat) % 2 == 0) {
        cout << "CAT\n";
    } else {
        cout << "FOX\n";
    }
}

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