模板——杂项

发表于 2025-11-06 更新于 2025-11-07 分类于 ACM ，模板阅读次数：作者 Pomelorin

模板——杂项

Clion 配置快捷键，KMP，LCA，SG 函数，二进制相关，数位 DP，费马平方和定理，对抗搜索。

Clion 配置快捷键

输入全称反而出不来。

Duplicate Entire Lines —— Alt+Shift+向下箭头
Add Selection for Next Occurrence —— CtrI+D
Move Line Down —— Alt+向下箭头
Move Line Up —— Alt+向上箭头
Delete Line —— Ctrl+Q
Run —— F5
Debug —— F6

KMP

kmp[i] 即为 border。长度减去 border 为循环节。

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

string s1, s2;
int n, m;

void solve() {
    //字符串s2是否存在于s1中，如果存在，返回匹配的位置
    cin >> s1 >> s2;
    n = s1.length();
    m = s2.length();
    int kmp[m + 5] = {};
    int x = 0;
    kmp[0] = 0;
    for (int i = 1; i < m; i++) {
        while (x != 0 && s2[i] != s2[x])x = kmp[x - 1];
        if (s2[i] == s2[x]) {
            x++;
            kmp[i] = x;
        }
    }
    int j = 0;
    int flag = 0;
    for (int i = 0; i < n; i++) {
        while (j != 0 && s1[i] != s2[j])j = kmp[j - 1];
        if (s1[i] == s2[j])j++;
        if (j == m) {
            cout << i - m + 2 << endl;//输出位置
            j = kmp[j - 1];
            flag = 1;
        }
    }
    for (int i = 0; i < m; i++) {
        cout << kmp[i] << ' ';
    }
    return;
}

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

LCA

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

namespace name {
    typedef int ll;
    const ll N = 500000 + 10, L = 18;

    struct edge {
        ll nxt, to;
    } e[N * 2];

    ll n, m, head[N], cnt = 0, w[N];
    ll st[N], ed[N], ans[N], f[L + 3][N];
    ll dep[N];

    void add(ll a, ll b) {
        e[++cnt] = (edge){head[a], b};
        head[a] = cnt;
    }

    void dfs(ll root, ll dad) {
        for (ll i = head[root]; i; i = e[i].nxt) {
            ll son = e[i].to;
            if (dad == son)
                continue;
            dep[son] = dep[root] + 1;
            f[0][son] = root;
            dfs(son, root);
        }
    }

    void finit() {
        for (ll i = 1; i <= L; i++)
            for (ll j = 1; j <= n; j++)
                f[i][j] = f[i - 1][f[i - 1][j]];
    }

    ll LCA(ll x, ll y) {
        if (dep[x] < dep[y])
            swap(x, y);
        for (ll i = L; i >= 0; i--) {
            if (dep[f[i][x]] < dep[y])
                continue;
            x = f[i][x];
        }
        if (x == y)
            return x;
        for (ll i = L; i >= 0; i--) {
            if (f[i][x] == f[i][y])
                continue;
            x = f[i][x], y = f[i][y];
        }
        return f[0][x];
    }

    void main() {
        ll ta, tb, R;
        scanf("%d%d%d", &n, &m, &R);
        for (ll i = 1; i <= n - 1; i++) {
            scanf("%d%d", &ta, &tb);
            add(ta, tb);
            add(tb, ta);
        }
        f[0][R] = R;
        dfs(R, R);
        finit();
        for (ll i = 1; i <= m; i++)
            scanf("%d%d", st + i, ed + i), printf("%d\n", LCA(st[i], ed[i]));
        return;
    }
}

int main() {
    name::main();
    return 0;
}

SG 函数

把一堆石子分成多堆石子：子游戏取异或和。

一堆石子被取走一些石子：前驱状态取 mex。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
//sg函数

int a[10] = {0, 1, 2, 3, 0, 1, 2, 3, 4, 5};

void solve() {
    int n;
    cin >> n;
    int ans = 0;
    while (n--) {
        int x;
        cin >> x;
        int sgx = a[x % 10]; //打表得出的结论
        ans ^= sgx;
    }
    if (ans == 0) {
        //先手输
        cout << "Vinit";
    } else {
        cout << "Ada";
    }
    return;
}

int f[200], sg[200];

int dfs(int x) {
    //暴力递归 / 记忆dp   dfs可行的方案
    map<int, int> m;
    for (int i = 1; x - f[i] >= 0; i++) {
        //可以取走斐波那契数列个石子
        int nx = x - f[i];
        //if(sg[nx]==-1)dfs(nx);
        m[sg[nx]]++;
    }
    //求mex
    int ans = 0;
    while (m[ans] > 0)
        ans++;
    //sg[x]=ans;
    return ans;
}

signed main() {
    //打表找规律，状态0一定是0（nim游戏）
    f[0] = 0, f[1] = 1; //斐波那契数列
    for (int i = 2; i <= 140; i++)
        f[i] = f[i - 1] + f[i - 2];
    cout << 0 << ' ';
    for (int i = 1; i <= 100; i++) {
        sg[i] = dfs(i);
        cout << sg[i] << ' ';
    }
    //得出sg循环节是0123012345
    int t;
    //    cin >> t;
    t = 1;
    while (t--) {
        solve();
        cout << endl;
    }
    return 0;
}

二进制相关

用数表示集合。数的二进制的第 \(i\) 位的 01 状态可表示一个元素是否在集合中。
\(\operatorname{lowbit}(x)\) 表示数 \(x\) 的最低的为 \(1\) 的一位。lowbit(x)=x&(-x)。
判断 \(x\) 是不是 \(y\) 的子集：x&y==x。
\(x\) 和 \(y\) 的交集 x&y，并集 x|y。
\(x\) 是 \(y\) 的子集时，\(y-x\)：x^y。
枚举 \(S\) 的子集：for(int i=S;i;i=i-1&S)。其中 \(i\) 是 \(S\) 的子集。
判断 \(s\) 从右边数第 \(i\) 位是否为 \(1\)：s&(1<<(i-1))。
把 \(s\) 从右边数第 \(i\) 位变成 \(1\)：s|(1<<(i-1))。

数位 DP

合法号码是不含前导零的 \(11\) 位的数字，要出现至少 \(3\) 个相邻的相同数字；号码中不能同时出现 \(8\) 和 \(4\)。

给定 \(l\) 和 \(r\)（不含前导零， \(11\) 位），求 \([l,r]\) 区间的合法号码数量。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l, r, num[20], dp[20][20][20][2][2][2][2];
//各维意义: 第几位 上一位数字 上两位数字 连过? <n? 4? 8?
ll dfs(int step, int pr1, int pr2, bool lkd, bool stn, bool ap4, bool ap8) {
    ll ans = 0, limit;
    if (ap4 && ap8)
        return 0; //不能同时出现 4 和 8
    if (step <= 0)
        return lkd; //搜索到头，返回这个数是否合法。本句相当于同时判断两个条件。实际上，只有这个和前面的那一句条件满足，答案才合法。
    if (dp[step][pr1][pr2][lkd][stn][ap4][ap8])
        return dp[step][pr1][pr2][lkd][stn][ap4][ap8]; //记忆化
    if (stn)
        limit = 9;
    else
        limit = num[step]; //保证枚举的数字<=n
    for (ll i = 0; i <= limit; i++) //枚举算符
        ans += dfs(step - 1, i, pr1,
                   lkd || (pr1 == pr2 && pr1 == i), 
                   stn || (i < num[step]),
                   ap4 || i == 4,
                   ap8 || i == 8);
    return dp[step][pr1][pr2][lkd][stn][ap4][ap8] = ans;
}

ll solve(ll x) {
    ll len = 0, ans = 0;
    if (x < 10000000000)
        return 0;
    memset(dp, 0, sizeof(dp));
    memset(num, 0, sizeof(num));
    while (x)
        num[++len] = x % 10, x /= 10;
    for (ll i = 1; i <= num[len]; i++) //从高位
        ans += dfs(10, i, 0, 0, i < num[len], i == 4, i == 8);
    return ans;
}

int main() {
    scanf("%lld%lld", &l, &r);
    printf("%lld", solve(r) - solve(l - 1));
    return 0;
}

费马平方和定理

费马平方和定理：奇素数 \(p\) 可以表示为两个正整数的平方和，当且仅当 \(p\) 是 \(4k+1\) 型的。并且在不考虑两个正整数顺序的情况下，这个表示方法唯一。

对抗搜索

一个 \(n\times n\)（\(n\ge 2\)）棋盘上有黑白棋子各一枚。游戏者 A 和 B 轮流移动棋子，A 先走。

A 的移动规则：只能移动白棋子。可以往上下左右四个方向之一移动一格。
B 的移动规则：只能移动黑棋子。可以往上下左右四个方向之一移动一格或者两格。

和通常的“吃子”规则一样，当某游戏者把自己的棋子移动到对方棋子所在的格子时，他就赢了。

两个游戏者都很聪明，当可以获胜时会尽快获胜，只能输掉的时候会尽量拖延时间。告诉你 \(n\) 和黑白棋子的坐标，你的任务是判断谁会赢，需要多少回合。

#include<bits/stdc++.h>
using namespace std;
const int inf = 1e8;
int dp[21][21][21][21][61][2]; //距离黑棋吃掉白棋还剩多少步
int a[8] = {-1, 0, 1, 0, -2, 0, 2, 0}; //模拟x轴移动
int b[8] = {0, 1, 0, -1, 0, 2, 0, -2}; //模拟y轴移动
int n, x, y, X, Y;
int dfs(int x1, int y1, int x2, int y2, int step, int op) //op=1轮到黑,op=0轮到白 
{
    if (step > 3 * n)
        return inf;
    if (x1 == x2 && y1 == y2)
        return op * inf;
    //当 op=1 时，说明上一轮白棋选择吃掉黑棋，是不合法的，op*inf刚好赋予正无穷
    //当 op=0 时，说明上一轮黑棋选择吃掉白棋，是目标完成，op*inf刚好为赋值0
    if (dp[x1][y1][x2][y2][step][op])
        return dp[x1][y1][x2][y2][step][op]; //记忆化
    dp[x1][y1][x2][y2][step][op] = op * inf; //同理
    for (int i = 0; i < (op ? 8 : 4); ++i) {
        int xx = x1 + a[i], yy = y1 + b[i];
        if (xx < 1 || xx > n || yy < 1 || yy > n)
            continue;
        if (!op)
            dp[x1][y1][x2][y2][step][op] = 
            max(dp[x1][y1][x2][y2][step][op], dfs(x2, y2, xx, yy, step + 1, 1));
            //如果此时轮到白棋，白棋将会选择最强抵抗
        else
            dp[x1][y1][x2][y2][step][op] =
            min(dp[x1][y1][x2][y2][step][op], dfs(x2, y2, xx, yy, step + 1, 0));
            //如果此时轮到黑棋，黑棋将会选择最快胜利
    }
    return ++dp[x1][y1][x2][y2][step][op]; //移动一次 步数+1
}

int main() {
    cin >> n >> x >> y >> X >> Y;
    if (abs(x - X) + abs(y - Y) == 1)
    {
        cout << "WHITE 1";
        return 0;
    }
    cout << "BLACK " << dfs(x, y, X, Y, 0, 0);
    return 0;
}