这里不讲解法，只给模板。需要自取，顺便留赞 + 转发。

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

struct hash_string {
    string S; int mod, p;
    vector<long long> h;
    vector<long long> p_pow;
    hash_string() {}
    hash_string(int mod, int p):mod(mod), p(p) { p_pow.emplace_back(1ll); h.emplace_back(0ll); }
    hash_string(string S, int mod, int p) : S(S), mod(mod), p(p) { // 初始化字符串和模数
        p_pow.emplace_back(1ll); h.emplace_back(0ll);
        for (auto c : S) {
            h.emplace_back((h.back() * p + c) % mod);
            p_pow.emplace_back(p_pow.back() * p % mod);
        }
    }
    void insert(char c) { // 插入字符
        S += c; h.emplace_back((h.back() * p + c) % mod);
        p_pow.emplace_back(p_pow.back() * p % mod);
    }
    int hash_value(int l, int r) { // 查询哈希值
        return ((h[r] - h[l - 1] * p_pow[r - l + 1] % mod) % mod + mod) % mod;
    }
};

struct double_hash {
    string S; hash_string hash1, hash2;
    double_hash() {}
    double_hash(string S) : S(S) { // 初始化。传入字符串，哈希模数为原定。
        hash1 = hash_string(S, (int)1e9 + 7, 1331);
        hash2 = hash_string(S, (int)1e9 + 9, 1331);
    }
    double_hash(string S, int mod1, int p1, int mod2, int p2) : S(S) { // 初始化，传入字符串和哈希模数
        hash1 = hash_string(S, mod1, p1);
        hash2 = hash_string(S, mod2, p2);
    }
    bool equal(int l1, int r1, int l2, int r2) { // 判断两段串是否相等。
        return (hash1.hash_value(l1, r1) == hash1.hash_value(l2, r2) and
                hash2.hash_value(l1, r1) == hash2.hash_value(l2, r2));
    }
    void insert(char c) { // 插入字符
        hash1.insert(c), hash2.insert(c);
    }
};

int main() {
    int n, m; string s;
    scanf("%d%d", &n, &m);
    cin >> s;

    hash_string hash1(s, 13331, 131); // 初始化单哈希。

    hash_string hash2(13331, 131); // 这种初始化方法和 hash1 相同。
    for (auto c : s) hash2.insert(c);

    double_hash hash3(s); // 初始化双哈希。模数是系统自定的。
    double_hash hash4(s, 13331, 131, 13331, 13); // 初始化双哈希，模数可以自设。

    while (m -- ) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        puts(hash.equal(l1, r1, l2, r2) ? "Yes" : "No");
    }
    return 0;
}

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2010, M = 6010;
int h[N], e[M], ne[M], idx;
int n, m, k, f[N];

const int SIZE = 1e6;
template<typename T>
struct hash_map {
    T Key[SIZE]; bool Val[SIZE];
    hash_map() { memset(Val, 0, sizeof Val); }
    int hash(T x) { return (x % SIZE + SIZE) % SIZE; }
    bool &operator [] (T x) {
        int index = hash(x), cnt = 1;
        while (Key[index] != x and Val[index] != 0)
            index = (index + cnt * cnt) % SIZE, cnt ++ ;
        Key[index] = x; return Val[index]; 
    }
};
void add(int a, int b) {
    e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}
int SG(int u) {
    if (~f[u]) return f[u];
    hash_map<int> hash;
    for (auto i = h[u]; i; i = ne[i]) {
        int j = e[i];
        hash[SG(j)] = true;
    }
    for (auto i = 0; ; i ++ )
        if (!hash[i]) return f[u] = i;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    while (m -- ) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    } int ans = 0;
    memset(f, -1, sizeof f);
    while (k -- ) {
        int u; scanf("%d", &u);
        ans = ans xor SG(u);
    }
    puts(ans ? "win" : "lose");
    return 0;
}

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2010, M = 6010;
int h[N], e[M], ne[M], idx;
int n, m, k, f[N];

const int SIZE = 1e6;
template<typename T>
struct hash_map {
    T Key[SIZE]; bool Val[SIZE];
    hash_map() { memset(Val, 0, sizeof Val); }
    int hash(T x) { return (x % SIZE + SIZE) % SIZE; }
    bool &operator [] (T x) {
        int index = hash(x), cnt = 1;
        while (Key[index] != x and Val[index] != 0)
            index = (index + cnt * cnt) % SIZE, cnt ++ ;
        Key[index] = x; return Val[index]; 
    }
};
void add(int a, int b) {
    e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}
int SG(int u) {
    if (~f[u]) return f[u];
    hash_map<int> hash;
    for (auto i = h[u]; i; i = ne[i]) {
        int j = e[i];
        hash[SG(j)] = true;
    }
    for (auto i = 0; ; i ++ )
        if (!hash[i]) return f[u] = i;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    while (m -- ) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    } int ans = 0;
    memset(f, -1, sizeof f);
    while (k -- ) {
        int u; scanf("%d", &u);
        ans = ans xor SG(u);
    }
    puts(ans ? "win" : "lose");
    return 0;
}

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 10010;
int n, K, S[N], f[N];

const int SIZE = 10010;
template<typename T>
struct hash_map {
    T Key[SIZE]; bool Val[SIZE];
    hash_map() { memset(Val, 0, sizeof Val); }
    int hash(T x) { return (x % SIZE + SIZE) % SIZE; }
    bool &operator [] (T x) {
        int index = hash(x), cnt = 1;
        while (Key[index] != x and Val[index] != 0)
            index = (index + cnt * cnt) % SIZE, cnt ++ ;
        Key[index] = x; return Val[index]; 
    }
};

int SG(int x) {
    if (f[x] != -1) return f[x];
    hash_map<int> hash;
    for (int i = 1; i <= K; i ++ )
        if (x >= S[i])
            hash[SG(x - S[i])] = true;
    for (int i = 0; ; i ++ )
        if (hash[i] == false)
            return f[x] = i;
}

int main() {
    memset(f, -1, sizeof f);
    scanf("%d", &K);
    for (int i = 1; i <= K; i ++ )
        scanf("%d", &S[i]);
    scanf("%d", &n);
    int ans = 0;
    while (n -- ) {
        int x; scanf("%d", &x);
        ans ^= SG(x);
    }
    puts(ans ? "Yes" : "No");
    return 0;
}

单哈希。可以自己设哈希模数，我偷懒写的很简单。用数组的方式就可以调取。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int SIZE = 1e6;
template<typename T>
struct hash_map {
    T Key[SIZE]; bool Val[SIZE];
    hash_map() { memset(Val, 0, sizeof Val); }
    int hash(T x) { return (x % SIZE + SIZE) % SIZE; }
    bool &operator [] (T x) {
        int index = hash(x), cnt = 1;
        while (Key[index] != x and Val[index] != 0)
            index = (index + cnt * cnt) % SIZE, cnt ++ ;
        Key[index] = x; return Val[index]; 
    }
};

int n;
int main() {
    hash_map<int> h;
    scanf("%d", &n);
    while (n -- ) {
        char op[2]; int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[x] = true;
        else puts(h[x] ? "Yes" : "No");
    }
    return 0;
}

重心定义：

对于树上的每一个点，计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心。

（这里以及下文中的「子树」都是指无根树的子树，即包括「向上」的那棵子树，并且不包括整棵树自身。）

（来自 $\text{OI-wiki}$）

重心求法：

对于每个点，计算出所有与它相邻的点的子树大小。（可以理解称为以这个点为根的树，去掉这个点后每个连通块的大小）。求这些连通块大小的最大值，记为 $\max_i$。

然而实际中，换根不是个好主意。所以可以固定一个根，比如说 $1$。接下来，以 $1$ 为开始进行 $\text{dfs}$。搜到第 $u$ 个点的时候，遍历 $u$ 的所有非父亲出点，更新 $u$ 的子树大小 $\text{sz_u}$ 和最大子树大小。最后计算 $u$ 父亲出边的子树大小。这个大小就是 $n - sz_u$，即为总点数减去 $u$ 下方点数。最后统计答案即可。

另外，此题如果要求动态维护还有别的解法。有结论：在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。这个通过调整法可证明。所以搞个 $\text{LCT}$ 之类的维护一下就可以了。这里不口胡了。

代码需要自取。仅供参考

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 100010, M = N << 1;

int sz[N], max_sz[N];
int n, h[N], e[M], ne[M], idx;

void add(int a, int b) {
    e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}
void dfs(int u, int fa) {
    sz[u] = 1;
    for (int i = h[u]; i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u); sz[u] += sz[j];
        max_sz[u] = max(max_sz[u], sz[j]);
    }
    max_sz[u] = max(max_sz[u], n - sz[u]);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i ++ ) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs(1, -1);
    int ans = 2e9;
    for (int i = 1; i <= n; i ++ )
        ans = min(ans, max_sz[i]);
    printf("%d\n", ans);
    return 0;
}

折半搜索是将原问题分成两半。那么是否可以将问题分成 $\sqrt{n}$ 块，每块都搜索一遍，然后块之间匹配？

我尝试了一下，结果第五个点 WA 了。不知道是哪里的问题。有没有路过的大佬帮忙解答一下？

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define int long long

using namespace std;

const int N = 47, INF = 1e18;
int n, W, G[N], ans;
vector<int> w, tmp;

int checker(int x) { // 返回小于等于 x 的最大数
    auto iter = upper_bound(w.begin(), w.end(), x);
    if (iter == w.begin()) return -INF;
    iter -- ; return *iter;
}
void dfs(int u, int lim, int now) {
    if (now > W) return;
    if (u == lim + 1) {
        w.emplace_back(now); return;
    }
    dfs(u + 1, lim, now);
    dfs(u + 1, lim, now + G[u]);
}
void dfs1(int u, int lim, int now) {
    if (now > W) return;
    int val = checker(W - now);
    if (val == -INF) return;
    tmp.emplace_back(val + now); ans = max(ans, val + now);
    if (u == lim + 1) return;
    dfs1(u + 1, lim, now);
    dfs1(u + 1, lim, now + G[u]);
}

signed main() {
    scanf("%lld%lld", &W, &n);
    for (int i = 1; i <= n; i ++ ) {
        scanf("%lld", &G[i]);
    }
    int B = (int)sqrt(n);
    sort(G + 1, G + n + 1, greater<int>());
    dfs(1, B, 0); int l = B + 1, r = min(B + B, n);
    while (r != n) {
        sort(w.begin(), w.end());
        w.resize(unique(w.begin(), w.end()) - w.begin());
        dfs1(l, r, 0); l += B, r += B; r = min(r, n);
        for (auto i : tmp) w.emplace_back(i);
        tmp.clear();
    }
    printf("%lld\n", ans);
    return 0;
}

#pragma GCC optimize(2)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define int long long

using namespace std;

const int N = 47, INF = 1e18;
int n, W, G[N], ans;
vector<int> w;

void dfs1(int u, int lim, int now) {
    if (u == lim + 1) w.emplace_back(now);
    if (u <= lim) {
        dfs1(u + 1, lim, now); // 不选当前物品
        if (now + G[u] <= W) dfs1(u + 1, lim, now + G[u]); // 选当前物品
    }
}
void checker(int x) { // 返回小于等于 x 的最大数
//  auto iter = upper_bound(w.begin(), w.end(), x);
//  if (iter == w.begin()) return -INF;
//  iter -- ; return *iter;
    int l = 0, r = w.size() - 1;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        if ((long long)x + w[mid] <= W) l = mid;
        else r = mid - 1;
    }
    ans = max(ans, x + w[l]);
}
void dfs2(int u, int lim, int now) {
    if (u == lim + 1) {
        checker(now);
        return;
    }
//  if (checker(W - now) == -INF) return; // 可行性剪枝
//  ans = max(ans, now + checker(W - now));
    if (u <= lim) {
        dfs2(u + 1, lim, now); // 不选
        if (now + G[u] <= W) dfs2(u + 1, lim, now + G[u]); // 选
    }
}

signed main() {
    scanf("%lld%lld", &W, &n);
    for (int i = 1; i <= n; i ++ ) {
        scanf("%lld", &G[i]);
    }
    sort(G + 1, G + n + 1, greater<int>());
    dfs1(1, n >> 1, 0);
    sort(w.begin(), w.end());
    w.resize(unique(w.begin(), w.end()) - w.begin());
    dfs2((n >> 1) + 1, n, 0);
    printf("%lld\n", ans);
    return 0;
}

纯粹标题党。主要目的是推自己的博客 遗传算法详解

跑的贼慢。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define POPULATION 5000
#define TIMES 50

using namespace std;

const int N = 22;

int n, w[N][N];

int random(int l, int r) {
    return rand() % (r - l + 1) + l;
}
struct Individual {
    vector<int> chromosome;
    int fitness;

    Individual(vector<int> chro);
    Individual mate();
    int calc_fitness();

    bool operator < (const Individual& tmp)const {
        return fitness < tmp.fitness;
    }
};

Individual::Individual(vector<int> chro) {
    this -> chromosome = chro;
    this -> fitness = calc_fitness();
}

Individual Individual::mate() {
    vector<int> child = this -> chromosome;
    int P = random(1, 5);
    for (int i = 0; i < P; i ++ ) {
        int u = random(1, n - 2), v = random(1, n - 2);
        swap(child[u], child[v]);
    }
    return Individual(child);
}

int Individual::calc_fitness() {
    int ans = 0;
    for (int i = 0; i <= n - 2; i ++ )
        ans += w[chromosome[i]][chromosome[i + 1]];
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            scanf("%d", &w[i][j]);

    vector<int> Base; vector<Individual> population;
    for (int i = 0; i < n; i ++ )
        Base.emplace_back(i);

    for (int i = 0; i < POPULATION; i ++ ) {
        random_shuffle(Base.begin() + 1, Base.end() - 1);
        population.emplace_back(Base);
    }

    for (int i = 0; i < TIMES; i ++ ) {
        sort(population.begin(), population.end());
        vector<Individual> new_population;
        int s = (10 * POPULATION) / 100;
        for (int i = 0; i < s; i ++ )
            new_population.emplace_back(population[i]);
        s = POPULATION - s;
        for (int i = 0; i < s; i ++ ) {
            Individual P = population[random(0, 25)];
            new_population.emplace_back(P.mate());
        }
        population = new_population;
    }
    printf("%d\n", population[0].fitness);
    return 0;
}

#pragma GCC optimize(2)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#define x first
#define y second

using namespace std;

const int N = 1010, M = 20010;

using PII = pair<int, int>;
int dist[N], h[N], H[N], e[M], w[M], ne[M], idx;
int n, m, S, T, K, cnt[N];

void add(int *h, int &a, int &b, int &c) {
    e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx, w[idx] = c;
}
int f(int &x) { return dist[x]; }
void calc_f() {
    bool st[N] = {0};
    priority_queue<PII, vector<PII>, greater<PII>> q;
    memset(dist, 0x3f, sizeof dist); dist[T] = 0;
    q.push({0, T});
    while (q.size()) {
        auto ver = q.top().y; q.pop();
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = H[ver]; i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                q.push({dist[j], j});
            }
        }
    }
}
struct node {
    int val, w, id;
    node() { val = w = id = 0; }
    node(int val, int w, int id):val(val), w(w), id(id){}
    bool operator < (const node& tmp)const {
        return val == tmp.val ? w > tmp.w : val > tmp.val;
    }
};

int AStar() {
    using PIII = pair<int, PII>;
    priority_queue<node, vector<node>> q;
    q.push(node(f(S), 0, S));
    while (q.size()) {
        auto t = q.top(); q.pop();
        int d = t.w, ver = t.id;
        cnt[ver] ++ ;
        if (cnt[T] == K) return d;
        for (int i = h[ver]; i; i = ne[i]) {
            int j = e[i];
            if (cnt[j] < K)
                q.push(node(f(j) + w[i] + d, d + w[i], j));
        }
    }
    return -1;
}
int main() {
    scanf("%d%d", &n, &m);
    while (m -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(h, a, b, c);
        add(H, b, a, c);
    }
    scanf("%d%d%d", &S, &T, &K); if (S == T) K ++ ;
    calc_f(); printf("%d\n", AStar());
    return 0;
}