幸运数

小蓝认为如果一个数含有偶数个数位，并且前面一半的数位之和等于后面一半的数位之和，则这个数是他的幸运数字。例如 $2314$ 是一个幸运数字，因为它有 $4$ 个数位，并且 $2+3 = 1+4$ 。现在请你帮他计算从 $1$ 至 $100000000 $之间共有多少个不同的幸运数字。

无需多言，直接模拟非常传统的一道模拟题，直接循环模拟即可。答案 4430091

//
// Created by 田博 on 2023/4/8.
//
#include<bits/stdc++.h>

using namespace std;

void solve() {
    int ans = 0;
    for (int i = 1; i <= 100000000; i++) {
        vector<int> k;
        int tmp = i;
        while (tmp) k.push_back(tmp % 10), tmp /= 10;
        if (k.size() % 2 == 0) {
            int f = 0, s = 0;
            for (int j = 0; j < k.size() / 2; j++) {
                f += k[j];
                s += k[j + k.size() / 2];
            }
            if (f == s)ans++;

        }
    }
    cout << ans;
}

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

有奖问答

小蓝正在参与一个现场问答的节目。活动中一共有 30 道题目，每题只有答对和答错两种情况，每答对一题得 10 分，答错一题分数归零。
小蓝可以在任意时刻结束答题并获得目前分数对应的奖项，之后不能再答任何题目。最高奖项需要 100 分，所以到达 100 分时小蓝会直接停止答题。
已知小蓝最终实际获得了 70 分对应的奖项，请问小蓝所有可能的答题情况有多少种?

二进制枚举，注意跳出条件，很简单的题其实$O(k*2^k)$

重点关注可在任意时刻结束问答，因此所有为 70 的 step 均为有效答案，总共有 30 个题， 每个题的答题情况可记录为 $1-2^{30}$ 的二进制下的一个 bit，设 1 为答对，0 为答错。

//
// Created by 田博 on 2023/4/8.
//
#include<bits/stdc++.h>

using namespace std;

void solve() {
    int ans = 0;
    for (int i = 1; i < (1 << 30); i++) {
        int cnt = 0;
        for (int j = 0; j < 30; j++) {
            if (((i >> j) & 1) == 1) cnt += 10;
            else cnt = 0;
            if (cnt == 70) ans++;
            if (cnt >= 100) break;4n
        }
    }
    cout << ans;
}

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

平方差

给定 $L,R$，问 $L\leq x\leq R$ 中有多少个数$ x$ 满足存在整数 $y,z$ 使得$ x = y^2*z^2$ 。

看数据范围要么$log$要么$O(1)$，不妨打表看看什么情况下不满足

void solve() {
    set<int> st;
    for (int i = 1; i <= (int) 1e4; i++) {
        for (int j = 1; j * j <= i; j++) {
            if (i % j == 0) {
                int add = max(i / j, j);
                int sub = min(i / j, j);
                if ((add + sub) % 2 == 0 && (add - sub) % 2 == 0) {
                    st.insert(i);
                    break;
                }
            }
        }
    }
    for (int i = 1; i <= 1e4; i++) {
        if (!st.count(i)) cout << (i - 2) % 4 << endl;
    }
}

表的结果看出来$4n+2,n \in N $时不满足条件，因此直接去掉这部分就好了

//
// Created by 田博 on 2023/4/8.
//
#include<bits/stdc++.h>

using namespace std;

void solve() {
    int l, r;
    cin >> l >> r;
    int f = (l - 2) / 4;
    int s = (r - 2) / 4;
    cout << (r - l + 1) - (s - f + 1);
}

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

更小的数

小蓝有一个长度均为 $n$ 且仅由数字字符 $0 \to 9$ 组成的字符串，下标从 $0$ 到 $n-1$，你可以将其视作是一个具有 n 位的十进制数字 $num$,小蓝可以从$ num $中 选出一段连续的子串并将子串进行反转，最多反转一次。小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 $num{new}$ 满足条件 $num{new} < num$， 请你帮他计算下一共有多少种不同的子串选择方案，只要两个子串在 $num $中的 位置不完全相同我们就视作是不同的方案。
注意，我们允许前导零的存在，即数字的最高位可以是 0 ，这是合法的。

中心拓展法很合理，stringview可能可以蟒过去

//
// Created by 田博 on 2023/4/8.
//
#include<bits/stdc++.h>

using namespace std;

void solve() {
    string s;
    cin >> s;
    int l = s.size();
    int ans = 0;
    for (int i = 0; i < l; i++) {
        for (int j = 0; j + i <= l; j++) {
            string t = s.substr(i, j);
            string tt = t;
            reverse(tt.begin(), tt.end());
            if (tt < t) ans++;
        }
    }
    cout << ans;
}

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

颜色平衡树

给定一棵树，结点由 $1$至 $n$ 编号，其中结点 $1$ 是树根。树的每个点有一个 颜色 $C_i$。
如果一棵树中存在的每种颜色的结点个数都相同，则我们称它是一棵颜色平衡树。
求出这棵树中有多少个子树是颜色平衡树。

这个判断子树的东西很板吧，没啥可多叭叭的

//
// Created by 田博 on 2023/4/8.
//
#include<bits/stdc++.h>

using namespace std;
const int N = 200000 + 10;
vector<int> g[N];
int c[N];
int cnt[N];
map<int, int> mp;
int ans = 0;

bool judge() {
    set<int> S;
    for (int i = 0; i < N; i++) S.insert(cnt[i]);
    S.erase(0);
    return S.size() == 1;
}

void dfs(int u) {
    for (auto &v: g[u]) dfs(v);
    if (--mp[cnt[c[u]]] == 0) mp.erase(cnt[c[u]]);
    cnt[c[u]]++;
    mp[cnt[c[u]]]++;
    mp.erase(0);
    if (judge()) ans++, cout << u << endl;
}

void solve() {
    memset(cnt, 0, sizeof cnt);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int f;
        cin >> f >> c[i];
        g[f].push_back(i);
    }
    dfs(1);
    cout << ans;
}

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

买瓜

小蓝正在一个瓜摊上买瓜。瓜摊上共有 $n$ 个瓜，每个瓜的重量为 $A_i$ 。 小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。
小蓝希望买到的瓜的重量的和恰好为 $m $。 请问小蓝至少要劈多少个瓜才能买到重量恰好为 $m$ 的瓜。如果无论怎样小 蓝都无法得到总重恰好为 $m$ 的瓜，请输出 $-1$ 。

注意到n很小，但是状态很多，每个瓜可以不选，可以不切，可以切三种状态。

需要考虑状压dp，三进制枚举也可做，但不能过100%的testcases

//
// Created by 田博 on 2023/4/8.
//
#include<bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    double m;
    cin >> n >> m;
    vector<double> a(n);
    int ans = 0x3f3f3f3f;
    for (auto &x: a) cin >> x;
    int top = pow(3, n);
    for (int i = 1; i < top; i++) {
        double cnt = 0;
        int tmp = i;
        int cnttime = 0;
        for (int j = 0; j < n; j++) {
            int fu = tmp % 3;
            if (fu == 1) cnt += a[j];
            else if (fu == 2) cnt += a[j] / 2.0, cnttime++;
            tmp /= 3;
        }
        if (abs(cnt - m) <= 1e-5)ans = min(ans, cnttime);
    }
    if (ans >= 1e9) ans = -1;
    cout << ans;
}

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

网络稳定性

有一个局域网，由 $n$ 个设备和 $m$ 条物理连接组成，第 $i $条连接的稳定性为$w_i$ 。对于从设备 $A$ 到设备 $B$ 的一条经过了若干个物理连接的路径，我们记这条路径的稳定性为其经过所有连接中稳定性最低的那个。
我们记设备 $A$ 到设备 $B$ 之间通信的稳定性为 $A$ 至 $B$ 的所有可行路径的稳定性中最高的那一条。
给定局域网中的设备的物理连接情况，求出若干组设备$ x_i$ 和 $y_i$ 之间的通信 稳定性。如果两台设备之间不存在任何路径，请输出 $-1$ 。

kruskal 重构树 https://www.luogu.com.cn/problem/P2245 原题

//
// Created by 田博 on 2023/4/8.
//
#include<bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 10;
struct node {
    int v, nxt, w;
} e[maxn << 2], a[maxn << 2];
int n, m, k, num, Q;
int fa[maxn], top[maxn], f[maxn], deep[maxn], head[maxn];
int sum[maxn], son[maxn], key[maxn];

inline int read() {
    char c = getchar();
    int x = 0;
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - 48, c = getchar();
    return x;
}

inline int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

inline int add_edge(int x, int y) {
    e[++num].v = y;
    e[num].nxt = head[x];
    head[x] = num;
}

void dfs1(int r) {
    sum[r] = 1;
    int maxx = -1;
    for (int i = head[r]; i; i = e[i].nxt)
        if (!deep[e[i].v]) {
            deep[e[i].v] = deep[r] + 1;
            f[e[i].v] = r;
            dfs1(e[i].v);
            sum[r] += sum[e[i].v];
            if (sum[e[i].v] > maxx) maxx = sum[e[i].v], son[r] = e[i].v;
        }
}

void dfs2(int r, int topf) {
    top[r] = topf;
    if (!son[r]) return;
    dfs2(son[r], topf);
    for (int i = head[r]; i; i = e[i].nxt)
        if (deep[e[i].v] > deep[r] && son[r] != e[i].v) dfs2(e[i].v, e[i].v);
}

inline int LCA(int x, int y) {
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]]) swap(x, y);
        x = f[top[x]];
    }
    if (deep[x] < deep[y]) return x;
    return y;
}

inline int cmp(node aa, node bb) {
    return aa.w < bb.w;
}

void solve() {
    n = read();
    m = read();
    for (int i = 1; i <= m; i++) {
        a[i].w = read();
        a[i].v = read();
        a[i].nxt = read();
    }
    sort(a + 1, a + m + 1, cmp);
    for (int i = 1; i <= (n << 1); i++) fa[i] = i;
    k = n;
    for (int i = 1; i <= m; i++) {
        int xx = find(a[i].v);
        int yy = find(a[i].nxt);
        if (xx == yy) continue;
        fa[xx] = fa[yy] = ++k;
        add_edge(k, xx);
        add_edge(xx, k);
        add_edge(k, yy);
        add_edge(yy, k);
        key[k] = a[i].w;
    }
    for (int i = k; i; i--)
        if (!deep[i]) deep[i] = 1, dfs1(i), dfs2(i, i);
    Q = read();
    int x, y;
    while (Q--) {
        x = read();
        y = read();
        if (find(x) != find(y)) puts("-1");
        else printf("%d", key[LCA(x, y)]), putchar(10);
    }
}

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

异或和之和

给定一个数组 $A_i$，分别求其每个子段的异或和，并求出它们的和。或者说， 对于每组满足 $1\leq L\leq R\leq n$ 的 $L,R$ ，求出数组中第 $L $至第 $R$ 个元素的异或和。 然后输出每组 $L,R$ 得到的结果加起来的值。

//
// Created by 田博 on 2023/4/8.
//
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<int> m(n);
    for (auto &x: m) cin >> x;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int j = i; j < n; j++) {
            cnt ^= m[j];
            ans += cnt;
        }
    }
    cout << ans;
}

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