模板——杂项

KMP，LCA，SG 函数，二进制相关，数位 DP，费马平方和定理，对抗搜索，神秘康托展开，cout 输出流控制，三分（整数三分，实数三分），upper_bound 相关，树的一些性质，点分治。

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\) 的子集，复杂度是 \(O(2^k)\)。枚举（全集的）子集的子集的复杂度为 \(O(3^n)\)。
• 判断 \(s\) 从右边数第 \(i\) 位是否为 \(1\)：s&(1<<(i-1))。
• 把 \(s\) 从右边数第 \(i\) 位变成 \(1\)：s|(1<<(i-1))。
• 位运算运算律：
  • \((a \mid b) \mathbin{\&} c = (a \mathbin{\&} c) \mid (b \mathbin{\&} c)，(a \mathbin{\&} b) \mid c = (a \mid c) \mathbin{\&} (b \mid c)\)（与或互相分配）
  • \((a \oplus b) \mathbin{\&} c = (a \mathbin{\&} c) \oplus (b \mathbin{\&} c)\)
  • \(\sim(a \mathbin{\&} b) = (\sim a) \mid (\sim b)，\sim(a \mid b) = (\sim a) \mathbin{\&} (\sim b)\)（德摩根律）
  • \(a \mathbin{\&} (a \mid b) = a，a \mid (a \mathbin{\&} b) = a\)（吸收律）
  • \(a + b = a \oplus b + 2(a \mathbin{\&} b)\) 这本质上是把加法拆成“无进位和（XOR）”与“进位（AND 并左移）”两部分。

数位 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;
}

神秘康托展开

我们的目标是把全排列转化成一个变进制数，以方便我们进行加法。对于第 \(i\) 根手指，它有 \(n−i+1\) 种选择，根据位值原理，要想让每个数对应一个全排列，就要让这一位数是 \(n−i+1\) 进制的。

那么，整个过程分为三步：

1. 将火星数变成变进制数；
2. 将变进制数加上 \(m\)；
3. 将变进制数变成火星数。

我们来看一个实例： 将 \(1,4,5,2,3\) 变成变进制数：

• 首位 1 是 5 种选择 \(\{1,2,3,4,5\}\) 的第 1 种，故变为 0（从0开始）
• 次位 4 是 4 种选择 \(\{2,3,4,5\}\) 的第 3 种，故变为 2
• …
• 最后，排列 \(1,4,5,2,3\) 变成了 \((02200)\)

接下来给它加上 3 变成 \((02203)\)，并处理进位：

• 末位是 1 进制的，进 3 得 \((02230)\)。
• 次低位是 2 进制的，满 2 进一得 \((02310)\)。
• 中间位是 3 进制的，满 3 进一得 \((03010)\)。
• 次位是 4 进制的，\(3<4\)，不进位，得 \((03010)\)。

最后将 \((03010)\) 变回火星数。

• 首位 0 表示这位应选择 \(\{1,2,3,4,5\}\) 的第 1 种，即 1
• 次位 3 表示这位应选择 \(\{2,3,4,5\}\) 的第 4 种（1 被选过了），即 5
• …

所以本题答案为 14523 +3= 15243。

cout 输出流控制

int n = 141;
   // 1）分别以十六进制、十进制、八进制先后输出n
   cout << "1)" << hex << n << " " << dec << n << " " << oct << n << endl;
   double x = 1234567.89, y = 12.34567;
   // 2)保留5位有效数字
   cout << "2)" << setprecision(5) << x << " " << y << " " << endl;
   // 3)保留小数点后面5位
   cout << "3)" << fixed << setprecision(5) << x << " " << y << endl;
   // 4)科学计数法输出，且保留小数点后面5位
   cout << "4)" << scientific << setprecision(5) << x << " " << y << endl;
   // 5）非负数显示正号，输出宽度为12字符，宽度不足则用*填补
   cout << "5)" << showpos << fixed << setw(12) << setfill('*') << 12.1 << endl;
   // 6）非负数不显示正号，输出宽度为12字符，宽度不足则右边用填充字符填充
   cout << "6)" << noshowpos << setw(12) << left << 12.1 << endl;
   // 7）输出宽度为12字符，宽度不足则左边用填充字符填充
   cout << "7)" << setw(12) << right << 12.1 << endl;
   // 8）宽度不足时，负号和数值分列左右，中间用填充字符填充
   cout << "8)" << setw(12) << internal << -12.1 << endl;
   cout << "9)" << 12.1 << endl;

三分

三分用于单峰函数（例如二次函数）求最值等问题。

实数三分

求 calc 凹函数的最小值。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PII pair<ll, ll>
const ll mod = 1e9 + 7, N = 1e4 + 10, inf = 1e17;
const ld eps = 1e-9;

ll a[N], b[N], c[N], n;

ld calc(ld x) {
    ld ans = -inf;
    for (ll i = 1; i <= n; i++) {
        ans = max(ans, x * x * a[i] + x * b[i] + c[i]);
    }
    return ans;
}

void solve() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    ld l = 0, r = 1000;
    while (r - l > eps) {//或迭代固定次数
        ld m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
        if (calc(m1) < calc(m2)) {
            r = m2;
        } else {
            l = m1;
        }
    }
    cout << fixed << setprecision(4) << calc(l) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

整数三分

ll l, r;//凸函数极大值
while(l < r) {
    ll lmid = l + (r - l) / 3;
    ll rmid = r - (r - l) / 3;
    if(calc(lmid) <= calc(rmid))	l = lmid + 1;
    else r = rmid - 1;
}
printf("%lld\n", max(calc(l), calc(r)));

ll l, r;//凹函数极小值
while(l < r) {
    ll lmid = l + (r - l) / 3;
    ll rmid = r - (r - l) / 3;
    if(calc(rmid) >= calc(lmid))	r = rmid - 1;
    else l = lmid + 1;
}
printf("%lld\n", min(calc(l), calc(r)));

upper_bound 相关

对于元素单调上升的数列：

• lower_bound：返回第一个大于等于给定数的位置。
• upper_bound：返回第一个大于给定数的位置。

//从小到大排列，找第一个>=
lower_bound(begin(), end(), val, less<int>());
//从大到小排列，找第一个<=
lower_bound(begin(), end(), val, greater<int>());

// 第一个 >= x 的索引，没有返回 -1
int first_ge(const vector<int>& a, int x) {
    auto it = lower_bound(a.begin(), a.end(), x);
    return it == a.end() ? -1 : int(it - a.begin());
}

// 最后一个 <= x 的索引，没有返回 -1
int last_le(const vector<int>& a, int x) {
    auto it = upper_bound(a.begin(), a.end(), x);
    return it == a.begin() ? -1 : int(prev(it) - a.begin());
}

树的一些性质

直径

树上任意两节点之间最长的简单路径即为树的「直径」。

• 一棵树可以有多条直径，他们的长度相等。
• 可以用树形 DP 的方法在线性时间求出树的直径。

上面的性质在存在负权时依然成立。

• 可以用两次 DFS 的方法在线性时间求出树的直径。
• 树上所有直径都必定交于同一点（或同一条边），这个点（或边）被称为树的中心。
• 合并两棵树，新树直径端点一定属于原来两棵子树直径端点的集合。
• 对于树上任意一点 \(x\)，离它最远的点一定是直径的某个端点。

中心

在树中，如果节点 \(x\) 作为根节点时，从 \(x\) 出发的最长链最短，那么称 \(x\) 为这棵树的中心。

• 树的中心不一定唯一，但最多有 2 个，且这两个中心是相邻的。树的中心一定位于树的直径上。
• 树上所有点到其最远点的路径一定交会于树的中心。
• 当通过在两棵树间连一条边以合并为一棵树时，连接两棵树的中心可以使新树的直径最小。

重心

三个等价定义：

1. 在树中删去结点 \(v\) 后，得到的图中每个连通分量的大小均不超过原树结点数的一半。
2. 在所有删去某个结点后得到的最大连通分量大小中，删去结点 \(v\) 时所得到的值最小。
3. 树中所有结点到某个结点的距离和中，到结点 \(v\) 的距离和最小。

性质：

• 树的重心如果不唯一，则恰有两个。这两个重心相邻。而且，删去它们的连边后，树将变为两个大小相同的连通分量。
• 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
• 把两棵树通过一条边相连得到一棵新的树，那么新树的重心在连接原来两棵树的重心的路径上。
• 一棵有根树的重心一定在根结点所在的重链上。
• 一棵树的重心一定是：根结点的 重子结点对应子树的 重心的 祖先。

点分治

只要路径信息能由“端点到分治中心”的摘要合并得到，并且能在每层快速查询/插入这些摘要，那么点分治就能处理整棵树所有简单路径的信息。算法框架如下：

solve(当前连通块):
    1. 找到重心 c
    2. 统计所有经过 c 的路径
    3. 删除 c
    4. 对 c 的每个子树递归 solve

注意在重新选择根节点之后一定要重新计算子树的大小。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 1e4 + 10, M = 1e7 + 10;

ll n, m, siz[N], vis[N], ans[N], que[N];
vector<PII> e[N];
bitset<M> b;

void getSiz(ll root, ll dad) {
    siz[root] = 1;
    for (auto [son, w] : e[root]) {
        if (son == dad || vis[son]) {
            continue;
        }
        getSiz(son, root);
        siz[root] += siz[son];
    }
}

ll getCent(ll root, ll dad, ll tal) {
    for (auto [son, w] : e[root]) {
        if (son == dad || vis[son]) {
            continue;
        }
        if (siz[son] > tal / 2) {
            return getCent(son, root, tal);
        }
    }
    return root;
}

void getInfo(ll root, ll dad, ll dis, vector<ll> &ret) {
    if (dis > M - 10) {
        return;
    }
    ret.push_back(dis);
    for (auto [son, w] : e[root]) {
        if (son == dad || vis[son]) {
            continue;
        }
        getInfo(son, root, dis + w, ret);
    }
}

void calcAns(ll root) {
    getSiz(root, root);
    ll cent = getCent(root, root, siz[root]);
    vector<ll> pre;
    pre.push_back(0);
    b[0] = 1;
    for (auto [son, w] : e[cent]) {
        if (vis[son]) {
            continue;
        }
        vector<ll> cur;
        getInfo(son, cent, w, cur);
        for (auto dis : cur) {
            for (ll i = 1; i <= m; i++) {
                if (que[i] >= dis && b[que[i] - dis]) {
                    ans[i] = 1;
                }
            }
        }
        for (auto dis : cur) {
            if (!b[dis]) {
                pre.push_back(dis);
                b[dis] = 1;
            }
        }
    }
    for (auto dis : pre) {
        b[dis] = 0;
    }
    pre.clear();
    vis[cent] = 1;
    for (auto [son, w] : e[cent]) {
        if (vis[son]) {
            continue;
        }
        calcAns(son);
    }
}

void solve() {
    cin >> n >> m;
    for (ll i = 1, u, v, w; i <= n - 1; i++) {
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    for (ll i = 1; i <= m; i++) {
        cin >> que[i];
    }
    calcAns(1);
    for (ll i = 1; i <= m; i++) {
        if (ans[i]) {
            cout << "AYE" << endl;
        } else {
            cout << "NAY" << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T = 1;
    while (T--) {
        solve();
    }
    return 0;
}