自学内容网 自学内容网

2023年码蹄杯专科组第一场初赛 解题报告 | 珂学家


前言

在这里插入图片描述


题解

有几道感觉还行,不过数据有些弱

  • 安全验证(字符串)
  • 旅行(图论)
    在这里插入图片描述

安全验证

难度: 钻石

思路: 字符串hash + 二分

先提炼下题意:

即存在字符串T, 它即是S的前缀, 也是S的后缀, 同时在S[1:-2]中存在子数组S'=T, 求最长的T

切入点是

  • 先找到满足要求的T(从前后缀一致),获取候选的列表 [ T 1 , T 2 , . . . , T k ] , 且 T i 为 T j 的前缀 i ≤ j {[T_1, T_2, ..., T_k], 且T_i 为 T_j 的前缀 i \le j } [T1,T2,...,Tk],TiTj的前缀ij
  • 然后枚举 i ∈ [ 1 , n − 2 ] {i \in [1, n - 2] } i[1,n2], 作为起点,二分找最长的 T i T_i Ti

为啥二分可以呢?因为存在阶段性

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

struct StringHash {

    StringHash(const string& s, int64 p, int64 mod)
        : p(p), mod(mod), pre(s.length() + 1, 0), pow(s.length() + 1, 0) {
        int n = s.length();
        pow[0] = 1;
        for (int i = 0; i < n; i++) {
            pow[i + 1] = pow[i] * p % mod;
            pre[i + 1] = (pre[i] * p % mod + s[i]) % mod;
        }
    }

    int query(int l, int r) {
        return ((pre[r + 1] - pre[l] * pow[r - l + 1] % mod) % mod + mod) % mod;
    }

    int64 mod;
    int64 p;
    vector<int64> pre;
    vector<int64> pow;
};

int main() {

    string s;
    cin >> s;

    int p1 = 13, p2 = 17;
    int64 mod = (int64)1e9 +  7;
    StringHash sh1(s, p1, mod);
    StringHash sh2(s, p2, mod);

    int n = s.length();
    vector<int> ln;
    for (int i = 0; i < n; i++) {
        if (sh1.query(0, i) == sh1.query(n - 1 - i, n - 1) 
            && sh2.query(0, i) == sh2.query(n - 1 - i, n - 1)) {
            ln.push_back(i + 1);
        }
    }

    int ans = 0;
    for (int i = 1; i < n - 1; i++) {
        int l = 0, r = ln.size() - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            int lz = ln[m];
            if (i + lz < n 
                && sh1.query(i, i + lz - 1) == sh1.query(0, lz - 1) 
                && sh2.query(i, i + lz - 1) && sh2.query(0, lz - 1)) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        if (r >= 0) {
            ans = max(ans, ln[r]);
        }
    }

    if (ans > 0) {
        cout << s.substr(0, ans) << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

旅行

难度:钻石

思路: 图论

突破口:

所有点都经过,所有边都经过 所有点都经过,所有边都经过 所有点都经过,所有边都经过

那该图必然是

  • 单条链

这两个图,有如下特点

  • 出入度都小于等于1
  • 彼此联通

因此结合这两点,通过出入度校验+并查集来求解

#include <bits/stdc++.h>

using namespace std;

struct Dsu {
public:
    Dsu(int n): m(n), arr(n, -1), gz(n, 1) {}
    int find(int u) {
        int fa = u;
        while (arr[fa] != -1) {
            fa = arr[fa];
        }
        while (arr[u] != -1) {
            int nfa = arr[u];
            arr[u] = fa;
            u = nfa;
        }
        return fa;
    }
    void merge(int u, int v) {
        int a = find(u), b = find(v);
        if (a != b) {
            arr[a] = b;
            gz[b] += gz[a];
        }
    }
    int group(int u) {
        return gz[find(u)];
    }
    int m;
    vector<int> arr;
    vector<int> gz;
};

int main() {

    int t;
    cin >> t;
    while (t-- > 0) {
        int n, m;
        cin >> n >> m;
        // 出度,入度
        vector<int> in(n), out(n);

        Dsu dsu(n);
        // 不是环,就是链表
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            u--; v--;
            in[v]++;
            out[u]++;
            dsu.merge(u, v);
        }

        bool ok = true;
        for (int i = 0; i < n; i++) {
            if (in[i] > 1 || out[i] > 1) {
                ok = false;
                break;
            }
        }

        if (ok && dsu.group(0) == n) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}


写在最后

在这里插入图片描述


原文地址:https://blog.csdn.net/m0_66102593/article/details/140671081

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!