洛谷 SCP-S 2024 第一轮模拟赛（提高级 C++）

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

set<int> s1 = {1, 2, 3}, s2 = {2, 3, 1, 1},
         s3 = {1, 2, 100}, s4 = {3, 4, 5};
map<set<int>, int> mp1, mp2;

set<int> intersection(set<int> a, set<int> b) {
    if (a.size() > b.size()) swap(a, b);
    set<int> res = a;
    for (int i : a)
        if (b.count(i) == 0)
            res.erase(i);
    return res;
}

int main() {
    cout << (s1 == s2) << endl;
    mp1[s3] = 9; mp1[s1] = 1;
    mp2[s2] = 1; mp2[s4] = 5;
    cout << (mp1 < mp2) << ' ';
    cout << mp2[s3] << ' ';
    cout << (mp1 <= mp2) << endl;
    mp1.clear();
    int n, l, t;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        set<int> tmp;
        for (cin >> l; l; l--) {
            cin >> t;
            tmp.emplace(t);
        }
        mp1[tmp] = i;
    }
    set<int> res = mp1.begin()->first;
    for (auto i : mp1)
        res = intersection(i.first, res);
    cout << res.size();
    return 0;
}

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

constexpr int mod = 998244353;
int n, k, a[12], b[12], ans[12], fa[12];

int findfa(int u) { return u == fa[u] ? u : fa[u] = findfa(fa[u]); }

int functionUnknown(int a[], int n) {
    if (n <= 1) return 0;
    int i = n - 1, j, k;
    while (true) {
        j = i; --i;
        if (a[i] < a[j]) {
            for (k = n; a[i] >= a[--k];);
            swap(a[i], a[k]);
            reverse(a + j, a + n);
            return 1;
        }
        if (!i) {
            reverse(a, a + n);
            return 0;
        }
    }
    return -1;
}

int F(int x) {
    int ans = 0;
    for (int i = k - 1; ~i; --i)
        ans = (1ll * ans * x % mod + a[i]) % mod;
    return ans;
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < k; ++i) scanf("%d", a + i);
    for (int m = 1; m <= n; ++m) {
        for (int i = 0; i < m; ++i) b[i] = i;
        do {
            for (int i = 0; i < m; ++i) fa[i] = i;
            int res = m;
            for (int i = 0, u, v; i < m; ++i) {
                u = findfa(i); v = findfa(b[i]);
                if (u == v) continue;
                --res; fa[u] = v;
            }
            int flag = 0;
            for (int i = 0; i < m; ++i)
                if (b[i] == i) flag = 1;
            if (flag) continue;
            ans[m] = (ans[m] + F(res)) % mod;
        } while (functionUnknown(b, m));
        printf("%d%c", ans[m], " 
"[m == n]);
    }
    return 0;
}

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

unsigned f(unsigned x) {
    x ^= x << 3;
    x ^= x >> 5;
    return x;
}

unsigned g(unsigned x) {
    return (x >> 5) ^ (x >> 2) ^ x ^ (x << 3);
}

int main() {
    unsigned y, l, r;
    cin >> y >> l >> r;
    for (unsigned long long i = l; i <= r; i++)
        if (f(i) == y)
            cout << i % 11 << endl;
    return 0;
}

（1）（最小垄断集）问题：你有一张 n 个结点（结点编号从 1 到 n），m 条边的无问无权图 $G = (V, E)$，其中 V 为点集，E 为边集。称 V 的一个子集 S 垄断了图 G，当且仅当 $\forall (u, v) \in E$，u, v 中必然恰有一个结点在 S 内。求垄断了 G 的子集 S 至少有多少个元素，或报告不存在这样的子集。试补全程序。

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

int n, m, is[100005];
vector<int> g[100005];
queue<int> q;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    int tot = 0;
    for (int k = 1; k <= n; k++) {
        if (①) continue;
        q.emplace(k);
        is[k] = 1;
        int cnt[3] = ②;
        while (q.size()) {
            for (int i = 0; i < g[q.front()].size(); i++) {
                int to = g[q.front()][i];
                if (is[to] == 0) {
                    is[to] = ③;
                    cnt[is[to]]++;
                    q.emplace(to);
                } else if (④) {
                    puts("No such subset."); // 报告不存在这样的子集
                    return 0;
                }
            }
            q.pop();
        }
        tot += ⑤;
    }
    cout << tot;
    return 0;
}

（2）（最长公共前缀）定义 LCP(s,t)为两个字符串的最长公共前缀。例如：s=abcde，t=abcabc，则 LCP(s,t)=abc。定义|s|为字符串s的长度，在上一例中|s|=5。

现在给定了 n 个字符串 $s_1, s_2, \ldots, s_n$。现在需要统计所有同时满足如下两个条件的

$\left| \text{LCP}(s_i, s_j) \right|$ 之和对 998244353 取模的值：条件 1：i < j。条件 2： $s_i < s_j$。

若 $1 \leq n \leq 2 \times 10^5$， $1 \leq |s_i| \leq 20$，字符串仅由小写字母构成，试补全程序。

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

const int maxn = 2e5 + 9, mod = 998244353;
char s[maxn][22];
int n;
int tmp[27][maxn], a[maxn];

int dfs(int l, int r, int p) {
    if (l >= r || p >= 20) return 0;
    int tail[27], ans = 0;
    memset(tail, 0, sizeof(tail));
    for (int i = l; i <= r; ++i) {
        int ch = ①;
        ②;
        for (int j = 0; j < ch; ++j)
            ③;
    }
    int tot = l, pos = l;
    for (int i = 0; i < 27; ++i)
        for (int j = 0; j < tail[i]; ++j)
            a[tot++] = tmp[i][j];
    for (int i = 0; i < 27; ++i) {
        ④;
        pos += tail[i];
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%s", s[i]);
    for (int i = 1; i <= n; ++i) a[i] = i;
    printf("%d
", ⑤);
    return 0;
}