A 回文(version 1）

知识点：字符串，回文，读题

则称 $x^2$ 为一个双回文数。

先判断是不是平方数：用整型存储 $t=\sqrt{x}$ ，检查 $t\times t = x$ 是否成立。

然后检查 $t$ 是否等于 $\text{reverse}(t)$ ，$x$ 是否等于 $\text{reverse}(x)$ 即可，这步可以用 $\text{to\_string}$ 函数简单地实现。

时间复杂度 $\mathcal{O}(log_{10}n)$ ，即数字位数。

void solve() {
    int x;
    cin >> x;
    int t = sqrt(x);
    auto check = [&](int x) {
        string s1 = to_string(x), s2 = s1;
        reverse(all(s2));
        return s1 == s2;
    };
    if (t * t == x && check(t) && check(x))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

B 未知(version 1)

知识点：异或，构造

发现在 $x\neq y$ 时，有当 $n=y$ 时，$x\oplus y > 0$ ，$y\oplus y = 0$ 。

时间复杂度 $\mathcal{O}(1)$

void solve() {
    int x, y;
    cin >> x >> y;
    cout << y << endl;
}

C 回文(version 2)

知识点：贪心

不妨把 $n$ 看成 $1$ ，把 $m$ 看成 $2$ ，那么最终的串，本质上就是把原来对应的权值串分隔成若干段，每段都是 $1$ 或 $2$ ，所以我们直接贪心匹配，能配 $2$ 就配 $2$ ，配不了就配 $1$ ，否则就失败。

关于贪心的证明：

如果当前两端都能组成 $m$ ，那说明这两端至少都“有余量”可以往里多吃一个字符。这时如果存在某个可行方案是先配 $n-n$ ，那么把两端各多吃掉一个 $n$ ，改成先配 $m-m$ ，中间剩下的子问题仍然是同构的。

时间复杂度 $\mathcal{O}(n)$

void solve() {
    string s;
    cin >> s;
    int l = 0, r = s.size() - 1;
    while (l <= r) {
        bool f1 = s[l] == 'm' || l + 1 <= r && s[l] == 'n' && s[l + 1] == 'n', f2 = s[r] == 'm' || l <= r - 1 && s[r] == 'n' && s[r - 1] == 'n';
        if (f1 && f2)
            l += (s[l] == 'm' ? 1 : 2), r -= (s[r] == 'm' ? 1 : 2);
        else if (s[l] == 'n' && s[r] == 'n')
            ++l, --r;
        else {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
}

D 未知(version 2)

知识点：枚举，压缩解集

如果数组中存在两个 $1$ ，我们令 $i=j=pos_{1}$ ，$z=pos_{2}$ 即可。

如果数组中存在数字出现过两次，且数组中存在 $1$ ，我们令 $i=pos_{x_1}$ ，$j=pos_{x_2}$ ，$z=pos_1$ 即可。

否则我们检查数组中所有小于 $\sqrt{10^9}\approx 31622$ 的数字 $x$ ，查看所有指数 $x^i(i\geq 2)$ ，是否 $i$ 和 $x^i$ 均存在。

时间复杂度 $\mathcal{O}(nlog|a_i|)$

void solve() {
    int n;
    cin >> n;
    vector<int> a;
    unordered_map<int, int> mp;
    for (int i = 0, x; i < n; ++i) {
        cin >> x, mp[x]++;
        if (x <= 31622 && x != 1) a.pb(x);
    }
    if (mp[1] >= 2) {
        cout << "YES" << endl;
        return;
    }
    for (auto [u, v] : mp) {
        if (v >= 2 && mp[1]) {
            cout << "YES" << endl;
            return;
        }
    }
    for (auto v : a) {
        int x = v * v;
        for (int i = 2; x <= 1e9; ++i, x *= v) {
            if (mp[i] && mp[x]) {
                _(i, x);
                cout << "YES" << endl;
                return;
            }
        }
    }
    cout << "NO" << endl;
}

E 未知(version 3)

知识点：树，构造，贪心

每个深度都要一个叶子和一个往下的内部点，最少的节点数是 $2m$ ，最多的则是将每个深度的叶子都拆成互不共享路径，最多需要 $1+\frac{m(m+1)}{2}$ 个点。

我们构造每一层的节点数 $cnt[1..m]$ ：

$cnt[m] = 1$
对 $d = m-1… 1$ ，设当前还要给 $1..d$ 层分配 $rest$ 个节点；
第 $d$ 层最多不能超过 $cnt[d+1] + 1$ ，否则下一层接不上；
同时还要给更浅的 $d-1$ 层至少留下 $2*(d-1)$ 个点。

所以可以取：
$$cnt[d] = \min(cnt[d+1]+1,\; rest – 2(d-1))$$
这样就能把总节点数正好分完。

最后连一下边，上下层的点一一对应，多余的点全部连到上一层的第一个节点即可。

时间复杂度 $\mathcal{O}(n)$

void solve() {
    int n, m;
    cin >> n >> m;

    if (!(2 * m <= n && n <= 1 + m * (m + 1) / 2)) {
        cout << "NO" << endl;
        return;
    }

    vector<int> cnt(m + 1);
    cnt[m] = 1;

    int rest = n - 2;
    for (int d = m - 1; d >= 1; --d) {
        int x = min(cnt[d + 1] + 1, rest - 2LL * (d - 1));
        cnt[d] = x;
        rest -= x;
    }

    vector<PII> edges;

    int id = 2;
    vector<int> pa = {1};

    for (int d = 1; d <= m; ++d) {
        vector<int> cur(cnt[d]);
        for (int i = 0; i < cnt[d]; ++i) cur[i] = id++;

        int p = (int)pa.size();

        for (int i = 0; i < p; ++i) edges.pb({pa[i], cur[i]});

        for (int i = p; i < cnt[d]; ++i) edges.pb({pa[0], cur[i]});

        if (d < m) pa.assign(cur.begin(), cur.end() - 1);
    }

    cout << "YES" << endl;
    for (auto [u, v] : edges) cout << u << " " << v << endl;
}

F 回文(version 3)

知识点：计数，子序列，特殊构造

注意到 $1\leq x\leq 3$ ，合法的回文子序列一定为以下形式：

$x=1$ ：单一字符，个数为 $r-l+1$ 。
$x=2$ ：两个相同字符，区间内任选两个即可，个数为 $\frac{k(k-1)}{2}$ 。
$x=3$ ：形如 $c_c$ 。假设我们在询问区间 $[l,r]$ 内固定了外侧字母是 $c$ 。对于区间内的任意一个位置 $i$ 作为中间字母，它能组成的数量为 $(左边 c 的数量)\times(右边c的数量)$ 。记前 $i$ 个字符中 $c$ 出现了 $cnt[i]$ 次，令 $A=cnt[l-1], B = cnt[r]$ ，得到：

$$\sum\limits_{i=l}^{r}(cnt[i-1]-A)\times(B-cnt[i])$$

展开得
$$\sum\limits_{i=l}^{r}(B\cdot cnt[i-1]-cnt[i-1]\cdot cnt[i]-A\cdot B+A\cdot cnt[i])$$
所以我们维护 $cnt$ 的前缀和 $cnt[i]*cnt[i-1]$ 的前缀和即可。

时间复杂度 $\mathcal{O}(\alpha(n+q))$

void solve() {
    int n, q;
    string s;
    cin >> n >> q >> s;

    vector<array<int, 26>> cnt(n + 1, array<int, 26>{}), sum(n + 1, array<int, 26>{}), pref(n + 1, array<int, 26>{});

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 26; ++j) {
            cnt[i][j] = cnt[i - 1][j] + (s[i - 1] - 'a' == j);
            sum[i][j] = sum[i - 1][j] + cnt[i][j];
            pref[i][j] = pref[i - 1][j] + 1LL * cnt[i - 1][j] * cnt[i][j];
        }
    }

    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;

        if (x == 1) {
            cout << r - l + 1 << endl;
        } else if (x == 2) {
            int ans = 0;
            for (int c = 0; c < 26; ++c) {
                int k = cnt[r][c] - cnt[l - 1][c];
                ans += k * (k - 1) / 2;
            }
            cout << ans << endl;
        } else if (x == 3) {
            int ans = 0;
            for (int c = 0; c < 26; ++c) {
                int A = cnt[l - 1][c], B = cnt[r][c], len = r - l + 1;
                ans += B * (sum[r - 1][c] - ((l >= 2) ? sum[l - 2][c] : 0)) - (pref[r][c] - pref[l - 1][c]) - A * B * len + A * (sum[r][c] - sum[l - 1][c]);
            }
            cout << ans << endl;
        }
    }
}