2023 xjtupc 西交校赛

Kidding_Ma的博客 / 2023-05-08 / 原文

A

签到，\(O(1)\)。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    cout << (n <= 6 ? "water" : "dry") << '\n';

    return 0;
}

B

签到, \(O(1)\)。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    i64 a, b;
    cin >> a >> b;
    cout << fixed << setprecision(15) << (1.0 * a) / (1.0 * b) << '\n';

    return 0;
}

C

签到,\(O(1)\)。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 x, y, z;
    cin >> x >> y >> z;
    cout << fixed << setprecision(6) << (1.0 / x) * (1.0 / y) * z << '\n';

    return 0;
}

D

没有 \((0,0)\) 就不行，发现每次操作都在一个矩形里，\(O(n)\)。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }

    bool ok = 0;
    for (int i = 0; i < n; i++) {
        if (x[i] == 0 && y[i] == 0) {
            ok = 1;
        }
    }

    if (!ok) {
        cout << -1 << '\n';
        return 0;
    }

    int xmx = *max_element(x.begin(), x.end());
    int xmn = *min_element(x.begin(), x.end());
    int ymx = *max_element(y.begin(), y.end());
    int ymn = *min_element(y.begin(), y.end());

    int a = xmx - xmn, b = ymx - ymn;
    if (n != (a + 1) * (b + 1)) {
        cout << -1 << '\n';
        return 0;
    }
    cout << a + b << '\n';

    return 0;
}

E

最后必须形成 \(k\) 个大小大于 \(1\) 的环，\(O(n^{2})\)。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n;
    double b;
    cin >> n >> b;
    vector<vector<double>> a(n, vector<double>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }

    if (n == 1) {
        cout << "kono jinsei, imi ga nai!\n";
        return;
    }

    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        int k = -1;
        double mx = -1E9;
        for (int j = 0; j < n; j++) {
            if (i == j) {
                continue;
            }
            if (a[i][j] < b) {
                continue;
            }
            if (a[i][j] > mx) {
                mx = a[i][j];
                k = j;
            }
        }
        if (k == -1) {
            cout << "hbxql\n";
            return;
        }
        p[i] = k;
    }

    vector<int> vis(n);
    for (int i = 0; i < n; i++) {
        int j = i;
        int cnt = 0;
        while (!vis[j]) {
            vis[j] = 1;
            j = p[j];
            cnt++;
        }
        if (cnt == 1 || j != i) {
            cout << "hbxql\n";
            return;
        }
    }

    cout << "wish you the best in your search\n";
}

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

    return 0;
}

F

同层剩一个且不为 \(2\) 就平衡打破，\(O(3\cdot n-3)\)。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<bitset<3>> a(n);
    for (int i = 0; i < n; i++) {
        a[i].set();
    }

    vector<array<int, 3>> b(3 * n - 3);
    for (int i = 0; i < 3 * n - 3; i++) {
        auto &[u, v, w] = b[i];
        cin >> u >> v >> w;
    }

    for (int i = 0; i < 3 * n - 3; i++) {
        auto &[u, v, w] = b[i];
        u--;
        v--;
        w--;
        a[u][v] = 0;
        if ((a[u].count() == 1 && a[u][1] == 0) || a[u].count() == 0) {
            cout << ((i % 2) ? "Sheauhaw" : "Nocriz") << '\n';
            return 0;
        }
    }
    return 0;
}

G

\(k\) 为边权上界。

输出 \(k,k-1,k-2,\cdots,k-n+2\) 的一条链，\(O(n)\)。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;

    vector<array<int, 3>> ans;
    int k = (n + 1) * (n + 1) / 4;
    for (int i = 1; i <= n - 1; i++) {
        ans.push_back({i, i + 1, k--});
    }
    
    cout << (int)ans.size() << '\n';
    for (auto &[u, v, w] : ans) {
        cout << u << ' ' << v << ' ' << w << '\n';
    }

    return 0;
}

H

找一个字母在每条串中出现次数不同，把他留到最后操作就行，\(O(26\cdot n)\)。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int vis[1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector<vector<int>> c(26, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (auto &si : a[i]) {
            c[si - 'a'][i]++;
        }
    }

    int b = -1;
    for (int i = 0; i < 26; i++) {

        int cnt = 0;
        for (int j = 0; j < n; j++) {
            vis[c[i][j]]++;
            if (vis[c[i][j]] == 1) {
                cnt++;
            } else {
                cnt--;
            }
        }

        for (int j = 0; j < n; j++) {
            vis[c[i][j]]--;
        }
        
        if (cnt == n) {
            b = i;
            break;
        }
    }

    if (b == -1) {
        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";
    for (int i = 0; i < 26; i++) {
        if (i != b) {
            cout << char(i + 'a');
        }
    }

    cout << char(b + 'a');

    return 0;
}

J

莫队，\(O(m\cdot \sqrt{m})\)。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
using u32 = unsigned int;

constexpr int N = 2E6;
int cnt[N + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

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

    vector<int> p(n, -1);
    vector<int> pre(n, -1);
    for (int i = 0; i < n; i++) {
        pre[i] = p[a[i]];
        p[a[i]] = i;
    }

    p.assign(n, n);
    vector<int> nex(n, n);
    for (int i = n - 1; i >= 0; i--) {
        nex[i] = p[a[i]];
        p[a[i]] = i;
    }

    struct node {
        int l, r, id;
    };
    vector<node> q(m);
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        q[i] = { l, r, i };
    }

    int bk = sqrt(m);
    sort(q.begin(), q.end(), [&](node a, node b) {
        return ((a.l / bk) ^ (b.l / bk)) ? a.l < b.l : (((a.l / bk) & 1) ? a.r < b.r : a.r > b.r);
    });

    int l = 0, r = -1;
    u32 res = 0;
    u32 Lres = 0, Rres = 0;
    u32 Cnt = 0;

    vector<u32> ans(m);
    auto add = [&](int pos, bool flag) {
        int num = a[pos];
        ++cnt[num];
        if (cnt[num] == 1) {
            ++Cnt;
        }
        if (flag) {
            Rres += pos - max(pre[pos], l - 1);
            res += Rres;
            Lres += Cnt;
        } else {
            Lres += min(r, nex[pos] - 1) - pos + 1;
            res += Lres;
            Rres += Cnt;
        }
    };
    auto del = [&](int pos, bool flag) {
        int num = a[pos];
        if (flag) {
            res -= Rres;
            Lres -= Cnt;
            Rres -= pos - max(pre[pos], l - 1);
        } else {
            res -= Lres;
            Rres -= Cnt;
            Lres -= min(r, nex[pos] - 1) - pos + 1;
        }
        --cnt[num];
        if (cnt[num] == 0) {
            --Cnt;
        }
    };

    for (int i = 0; i < m; i++) {
        auto &[ql, qr, qid] = q[i];
        while (r < qr) add(++r, 1);
        while (l > ql) add(--l, 0);
        while (l < ql) del(l++, 0);
        while (r > qr) del(r--, 1);
        ans[qid] = res;
    }

    for (int i = 0; i < m; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

M

考虑离线，考虑每个点在哪个时间段满足条件，然后差分前缀和，\(O(n)\)。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 1; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }

    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        g[a[i]].push_back(i);
    }

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

    vector<int> k(n);
    for (int i = 0; i < n; i++) {
        k[p[i]] = i;
    }
    vector<int> ans(n);
    function<pair<int, int>(int, int)> dfs = [&](int cur, int pre) {
        vector<pair<int, int>> t;
        for (auto &nex : g[cur]) {
            if (nex != pre) {
                t.push_back(dfs(nex, cur));
            }
        }
        int L = k[cur], R = k[cur];
        for (auto &[u, v] : t) {
            L = min(L, u);
            R = max(R, v);
        }
        ans[L]++;
        if (R < n) {
            ans[R]--;
        }
        return pair(L, R);
    };

    dfs(0, -1);
    for (int i = 1; i < n; i++) {
        ans[i] += ans[i - 1];
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " \n"[i == n - 1];
    }
    
    return 0;
}

N

两种情况，一开始就执行切换操作，不执行操作的话必须是连续的一段，\(O(n)\)。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, a, b, c;
    cin >> n >> m >> a >> b >> c;

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

    auto get1 = [&]() {
        i64 res = c;
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                res += 1LL * x[i] * (a + b);
                res += a;
                continue;
            } 

            res += 1LL * (x[i] - x[i - 1] + m - 1) % m * (a + b);
            res += a;
        }

        return res;
    };

    i64 inf = 9E18;

    auto get2 = [&]() {
        bool ok = 1;
        for (int i = 1; i < n; i++) {
            if (x[i] != (x[i - 1] + 1) % m) {
                ok = 0;
            }
        }
        if (!ok) {
            return inf;
        }
        return 1LL * x[0] * (a + b) + n * a;
    };

    cout << min(get1(), get2()) << '\n';

    return 0;
}

O

\(n!\)。QAQ

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int P = 19961;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;

    int ans = 1;
    for (int i = 1; i <= n; i++) {
        ans = ans * i;
        ans %= P;
    }

    cout << ans << '\n';
    
    return 0;
}