今天有一道题，我的题面没看明白，所以那一道题一分都没拿，有点可惜了，但是其他的题目还是有难度的，特别是第6题，证明我推了一页纸。

T1:Spelling Check

链接：Spelling Check - 题目详情 - QY code

这是道签到题，所以直接贴个代码吧：

#include <bits/stdc++.h>
using namespace std;
char s[1000010], t[1000010];
bool pref[1000010], suff[1000010];
vector <int> ans;
int main () {
    scanf ("%s%s", s, t);
    int n = strlen (s), m = strlen (t);
    pref[0] = true;
    for (int k = 1; k <= m; k++) pref[k] = pref[k - 1] && (s[k - 1] == t[k - 1]);
    suff[n] = true;
    for (int k = n - 1; k >= 0; k--) suff[k] = suff[k + 1] && (k >= m || s[k + 1] == t[k]);
    for (int k = 0; k < n; k++) {
        if (pref[k] && suff[k]) ans.push_back (k + 1);
    }
    printf ("%d\n", (int)ans.size ());
    for (int i = 0; i < (int)ans.size (); i++) printf ("%d ", ans[i]);
    return 0;
}

T2:Prefix-Suffix Palindrome (Easy version)

链接：Prefix-Suffix Palindrome (Easy version) - 题目详情 - QY code

一、题目理解

给定一个字符串 s，要求找出最长的字符串 t，满足：

1. t 的长度不超过 s 的长度

2. t 是回文串

3. t 可以拆分为 t = a + b（a、b 可以为空），其中 a 是 s 的前缀，b 是 s 的后缀

简单来说

从 s 的开头取一段、末尾取一段，拼在一起，要求拼出来的是回文，而且要尽量长。

举例

s = "abcdfdcecba"

答案 = "abcdfdcba"

因为 "abcdfdc" 是前缀，"ba" 是后缀，拼起来 "abcdfdcba" 是回文

---

二、初步分析

1. 回文的对称性

回文串从两端往中间看，左右对称。所以最长的 t 一定是：

• 从 s 的左边取尽量多的字符作为前缀 a

• 从 s 的右边取尽量多的字符作为后缀 b

• 中间补一段回文（可以是前缀的延续，也可以是后缀的延续）

2. 关键观察

t = a + b，其中 a 是 s 前缀，b 是 s 后缀。

由于 t 是回文，所以 a 的逆序应该等于 b（至少在外层是如此）。

也就是说：s 的前若干个字符 和 后若干个字符 应该互为反串。

---

三、算法设计

第一步：找回文边界

从 s 的两端向中间比较。

一直找到不相等的位置为止，记匹配了 k 对。

这 k 对字符构成了 t 的外层回文边界。

第二步：处理中间部分

去掉边界后，中间剩余部分为 mid = s[k..n-k-1]。

现在需要从 mid 中取出最长的回文，可以取：

• mid 的最长回文前缀（接在 a 后面）

• mid 的最长回文后缀（接在 b 前面）

两者取较长的那个。

第三步：拼接答案

答案 = s[0..k-1] + 最长回文(前缀 or 后缀) + s[n-k..n-1]

六、复杂度分析

| 操作 | 时间复杂度 |

|------|-----------|

| 找边界 | $O(n)$ |

| 找最长回文前缀 | $O(n²)$ |

| 找最长回文后缀 | $O(n²)$ |

| 总计 | $O(n²)$ |

Easy version 中所有字符串总长度 ≤ 5000，$O(n²)$ 完全可以通过。

七、总结

    1. 从两端往中间找匹配的字符 → 得到回文边界 k

    2. 中间剩余部分 → 找最长回文前缀或后缀

    3. 拼接：边界左 + 中间回文 + 边界右

核心思想：贪心地取最长的对称边界，再在中间部分找最长回文补全。

代码：

#include <bits/stdc++.h>
using namespace std;
bool check (string s) {
    int n = s.size ();
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - i - 1]) return false;
    } 
    return true;
}
string ppre (string s) {
    for (int len = s.size (); len >= 1; len--) {
        if (check (s.substr (0, len))) return s.substr (0, len);
    }
    return "";
}
string ssuf (string s) {
    for (int len = s.size (); len >= 1; len--) {
        if (check (s.substr (s.size () - len, len))) return s.substr (s.size () - len, len);
    }
    return "";
}
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        string s;
        cin >> s;
        int n = s.size ();
        int k = 0;
        while (k < n / 2 && s[k] == s[n - k - 1]) k ++;
        string mid = s.substr (k, n - 2 * k);
        string pre = ppre (mid);
        string suf = ssuf (mid);
        string ans = s.substr (0, k);
        if (pre.size () >= suf.size ()) ans += pre;
        else ans += suf;
        ans += s.substr (n - k, k);
        cout << ans << endl;
    }
    return 0;
}

T3:Palindrome Pairs

链接：Palindrome Pairs - 题目详情 - QY code

题意:

给定 N 个字符串（仅含小写字母），求有多少对 (i, j)（i < j）满足：将两个字符串拼接后，存在某种排列是回文串。

换句话说，两个字符串 s[i] 和 s[j] 拼接后，如果其字符的某种排列可以构成回文串，则这对就是一个有效对。

思路分析

1. 回文排列的判定条件

一个字符串能通过排列变成回文串，当且仅当：

• 至多 1 个字符出现奇数次

例如：

• aabbc → a:2, b:2, c:1 → 只有 c 是奇数 → 可以排列为回文 abcba

• aabbcd → a:2, b:2, c:1, d:1 → 两个奇数 → 不能排列为回文

2. 转化为位运算

对于每个字符串，用一个 26 位的掩码（mask）表示各字符出现次数的奇偶性：

• 第 k 位为 1：字符 k 出现奇数次

• 第 k 位为 0：字符 k 出现偶数次

两个字符串 s[i] 和 s[j] 拼接后能排列成回文 ⟺ 两个掩码的异或结果中，1 的位数 ≤ 1

即：popcount(mask[i] ^ mask[j]) <= 1

3. 满足条件的两种情况

• 0 位不同：mask[i] == mask[j]，即异或为 0

• 1 位不同：mask[i] ^ mask[j] 恰好有 1 位为 1，即 mask[j] == mask[i] ^ (1 << k)（k = 0..25）

4. 算法流程

1. 用哈希表 cnt 记录每个掩码出现的次数

2. 遍历每个字符串：

   - 计算其掩码 mask

   - 答案加上 cnt[mask]（相同掩码的配对）

   - 对每个 k ∈ [0, 25]，答案加上 cnt[mask ^ (1 << k)]（差 1 位的配对）

   - 将 mask 加入哈希表

3. 输出答案

5. 复杂度

• 时间：$O(N × 26) = O(26N)$

• 空间：$O(N)$（哈希表）

代码：

#include <bits/stdc++.h>
using namespace std;
char s[1000010];
int n;
int main () {
    scanf ("%d", &n);
    unordered_map <int, long long> cnt;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        scanf ("%s", s);
        int mask = 0;
        for (int j = 0;    s[j]; j++) mask ^= (1 << (s[j] - 'a'));
        ans += cnt[mask];
        for (int k = 0; k < 26; k++) ans += cnt[mask ^ (1 << k)];
        cnt[mask] ++;
    }
    printf ("%lld\n", ans);
    return 0;
}

T4:Erase and Extend (Easy Version)

链接：Erase and Extend (Easy Version) - 题目详情 - QY code

题意

给定一个长度为 $n$ 的字符串 $s$，你可以对它进行两种操作：

1. 删除：删掉字符串的最后一个字符

2. 复制：将字符串翻倍，$s := s + s$

每种操作可以进行任意次（包括 0 次）。

目标是：通过这些操作，得到一个长度恰好为 $k$ 的字符串，且该字符串的字典序最小。

思路

核心观察

所有操作可以归结为：选一个前缀 $s[0..i]$，将它重复到长度 $k$。

原因：

• 删除只能从末尾删，所以第一步必然是选某个前缀 $p = s[0..i]$

• 复制后得到 $pp$，再删除只是取 $pp$ 的前缀

• 关键性质：任何"复制→删除→复制→..."的交错操作，都不会比直接选一个更短的前缀重复更好

证明：假设选了前缀 $p = s[0..i]$，复制得到 $pp$，删除到 $p + s[0..j]$（$j < i$）。比较 $(p + s[0..j])^\infty$ 和 $(s[0..j])^\infty$：它们前 $j+1$ 个字符相同（都是 $s[0..j]$），但在位置 $j+1$，前者是 $s[j+1]$（来自 $p$ 的部分），后者是 $s[0]$。如果 $s[0] < s[j+1]$，那么 $s[0..j]$ 直接重复更优；如果 $s[0] > s[j+1]$，交错操作反而更差。所以交错操作永远不优于直接选更短的前缀。

算法

枚举所有前缀 $s[0..i]$（$i = 0, 1, \ldots, n-1$），对每个前缀计算它重复到长度 $k$ 的字符串，取字典序最小的一个。

优化：不需要每次都构造完整字符串，只需逐字符比较当前前缀的无限重复与当前最优前缀的无限重复，遇到第一个不同字符即可判定。

复杂度

$O(n \times k)$，对于 $n, k \le 5000$ 最多 $2.5 \times 10^7$ 次比较，可以通过。

代码：

#include <bits/stdc++.h>
using namespace std;
char s[5010];
int main () {
    int n, k;
    scanf ("%d %d", &n, &k);
    scanf ("%s", s);
    int best = 0;
    for (int i = 1; i < n; i++) {
        int len1 = i + 1, len2 = best + 1;
        bool better = false;
        for (int j = 0; j < k; j++) {
            char c1 = s[j % len1];
            char c2 = s[j % len2];
            if (c1 != c2) {
                if (c1 < c2) better = true;
                break;
            }
        }
        if (better) best = i;
    }
    int len = best + 1;
    for (int j = 0; j < k; j++) putchar (s[j % len]);
    return 0;
}

T5:Fixed Prefix Permutations

链接：Fixed Prefix Permutations - 题目详情 - QY code

题意

给定 n 个长度为 m 的排列 $a_1,a_2,..,a_n$​ 。

• 一个排列的美丽值：最大的 k ，使得前 k 个位置满足$p_1​=1,p_2​=2,…,p_k​=k$。如果 $p_1 \neq 1$ ，美丽值为 0 。

• 两个排列 p,q 的乘积 p⋅q 定义为排列 r ，其中 $r_j=q_{p_j}$

• 对每个 i ，求所有 j 中， $a_i*a_j$​ 的美丽值最大值。

简单来说

对于每一个排列$a_i$，我们要找一个$a_j$，使得乘积排列$a_i*a_j$的开头尽可能多的变成：$1,2,3,...,k$

也就是让乘积排列的前缀尽量匹配$1,2,3,...$

举例

如果乘积排列是：$1,2,4,3$，那么它的美丽值2，因为前两个值是$1,2$，但第三个值不是$3$

初步分析

对于$a_i,a_j$，第$pos$位的值是：$a_j[a_i[pos]]$

也就是说

• 先取 $a_i[pos]$
• 再把它当作下标，去 $a_j$​ 中取值

我们希望乘积前k位排列满足：$a_j[a_i[pos]]=pos$

所以：$a_j[a_i[pos]]=pos$

观察

如果$a_i[pos]=x$，那么我们希望：$a_j[x]=pos$

也就是说，在排列$a_j$中，$x$出现的位置应该是pos

因此，对于每个排列$a_j$，我们可以先求出每个数字出现的位置

所以问题就变成了：对每个 $a_i$ ，在所有 $a_j$​ 的位置序列中，求最长前缀匹配长度。

那么代码就很简单了。

代码

#include <bits/stdc++.h>
using namespace std;
int main () {
    int t;
    scanf ("%d", &t);
    while (t--) {
        int n, m;
        scanf ("%d%d", &n, &m);
        vector <vector <int> > a (n + 1, vector <int> (m + 1));
        for (int i = 0; i < n; i++){
			for (int j = 0; j < m; j++) scanf ("%d", &a[i][j]);
		}
        set<long long> pre;
        for (int i = 0; i < n; i++) {
            vector<int> inv (m + 1);
            for (int j = 0; j < m; j++) inv[a[i][j]] = j + 1;
            long long h = 0;
            for (int l = 1; l <= m; l++) {
                h = h * 11 + inv[l];
                pre.insert (h);
            }
        }
        for (int i = 0; i < n; i++) {
            int ans = 0;
            long long h = 0;
            for (int k = 1; k <= m; k++) {
                h = h * 11 + a[i][k - 1];
                if (pre.count (h)) ans = k;
            }
            printf ("%d ", ans);
        }
        printf ("\n");
    }
    return 0;
}

这道题目没做出来的原因是因为没看懂题目，说明我的分析能力还有所欠缺

T6:Sasha and One More Name

链接：Sasha and One More Name - 题目详情 - QY code

题意

给定一个回文串 s，需要将其切割 k 次（得到 k+1 段），重新排列拼接后得到一个与原串不同的回文串。段不能翻转，只能改变顺序。求最小的 k，若无解输出 Impossible。

思路

核心结论

答案只可能是 Impossible、1 或 2，不存在 ≥ 3 的情况。

三步判断

第 1 步：所有字符相同 → Impossible

如果所有字符都一样（如 qqqq），无论怎么切割重排，结果都是原串。

第 2 步：尝试 k=1（切一刀，两段交换）

枚举所有切割位置 i（1 ≤ i < n），将 s 切成 s[1..i] 和 s[i+1..n] 两段，交换得到旋转串 t = s[i+1..n] + s[1..i]。

检查 t 是否为回文串且与原串不同。若存在这样的 i，答案为 1。

例子：otto 切成 ot|to，交换得 toot，是回文且不同 → 答案 1。

第 3 步：检查 k=2 是否可行

如果 k=1 失败，检查前半部分是否全为相同字符（即 s[1] = s[2] = ... = s[⌊n/2⌋]）：

• 全相同 → Impossible：前半全同意味着整个串形如 aaa...aXaaa...a（X 为中间字符），唯一能组成的回文串就是原串。

• 不全相同 → 答案为 2：前半部分存在不同字符，意味着存在某个前缀不是回文串，利用它可以构造出 k=2 的合法方案。

例子：nolon 前半部分为 no，不全相同 → 答案 2。

切成 no|l|on，重排为 on|l|no = onlno，是回文且不同。

为什么 k=2 一定可行（当前半不全相同时）？

设前半部分存在 s[i] ≠ s[1]（i ≤ n/2），则前缀 s[1..i] 不是回文串。

切割位置选 i 和 n-i，得到三段：A = s[1..i]、B = s[i+1..n-i]、C = s[n-i+1..n]。

由于 s 是回文串，C = reverse(A)。重排为 C + A + B = reverse(A) + A + B。

因为 A 不是回文串，所以 reverse(A) ≠ A，因此 reverse(A) + A + B ≠ A + B + reverse(A) = s（与原串不同）。

同时可以证明这种构造能产生回文串，因此 k=2 可行。

为什么 k≥3 不会突然有用

k=2 的失败意味着： 前半部分全相同 ，即整个串最多只有一个"特殊字符"（在正中间）。

更多的切割只是把全是 'a' 的部分切成更多段，但：

• 切出来的段要么全是 'a'，要么包含中间的 X
• 重排后 X 仍必须在正中间
• 其余位置仍全是 'a'
• 结果仍等于原串切割次数再多也改变不了这个事实。

代码：

#include <bits/stdc++.h>
using namespace std;
char s[5010];
int main () {
    scanf ("%s", s + 1);
    int n = strlen (s + 1);
    bool allsame = true;
    for (int i = 2; i <= n; i++) {
        if (s[i] != s[1]) {
            allsame = false;
            break;
        }
    }
    if (allsame) {
        puts ("Impossible");
        return 0;
    }
    for (int i = 1; i < n; i++) {
        bool flag = true;
        for (int j = 1; j <= n / 2; j++) {
            int p1 = ((i + j - 1) % n) + 1;
            int p2 = ((i + n - j) % n) + 1;
            if (s[p1] != s[p2]) {
                flag = false;
                break;
            }
        }
        if (!flag) continue;
        bool diff = false;
        for (int j = 1; j <= n; j++) {
            int p = ((i + j - 1) % n) + 1;
            if (s[p] != s[j]) {
                diff = true;
                break;
            }
        }
        if (diff) {
            puts ("1");
            return 0;
        }
    } 
    bool same = true;
    for (int i = 2; i <= n / 2; i++) {
        if (s[i] != s[1]) {
            same = false;
            break;
        }
    }     
    if (same) puts ("Impossible");
    else puts ("2");
    return 0;
}