博客广场/ 陈俊霖

比赛总结

8月Day6

A.Spelling Check 核心思路通过比较两个字符串的前缀和后缀，确定所有可能被删除的字符位置。因为第一个字符串比第二个多一个字符，删除一个字符后剩余部分必须与第二个字符串完全匹配。具体步骤从左向右扫描：比较 s 与 t，找到第一个 s[i] != t[i] 的位置 left。若全部匹配，则 left = m（即最后一个字符可删除）。从右向左

陈俊霖发布于 2026-8-8 20:13:10

综合/比赛总结综合/题解字符串

A.Spelling Check

核心思路

通过比较两个字符串的前缀和后缀，确定所有可能被删除的字符位置。因为第一个字符串比第二个多一个字符，删除一个字符后剩余部分必须与第二个字符串完全匹配。

具体步骤

从左向右扫描：比较 s 与 t，找到第一个 s[i] != t[i] 的位置 left。若全部匹配，则 left = m（即最后一个字符可删除）。
从右向左扫描：比较 s 与 t 的逆序，找到第一个 s[i] != t[j]（其中 j = i-1）的位置 right。若全部匹配，则 right = 0（即第一个字符可删除）。
判断可行性：若 left < right，则不存在可行删除位置，输出 0。
生成结果：否则，所有位置 p ∈ [right, left] 都是可行的删除位置（下标从 0 开始）。输出方案总数 (left - right + 1)，并按递增顺序输出每个 p+1（1-based 位置）。

题解

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

int main()
{
	string s, t;
	cin >> s >> t;
	int n = s.size(), m = t.size();
	int left = m;
	for (int i = 0; i < m; i ++) 
	{
		if (s[i] != t[i]) 
		{
			left = i;
			break;
		}
	}
	
	int right = 0;
	for (int i = n - 1, j = m - 1; j >= 0; i --, j --) 
	{
		if (s[i] != t[j]) 
		{
			right = i;
			break;
		}
	}
	
	if (left < right) 
	{
		cout << 0 << '\n';
	}
	else 
	{
		vector<int> ans;
		for (int p = right; p <= left; p ++) 
		{
			ans.push_back(p + 1);
		}
		cout << ans.size() << '\n';
		for (int i = 0; i < ans.size(); i ++) 
		{
			cout << ans[i] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

B.Prefix-Suffix Palindrome (Easy version)

核心思路

先贪心匹配尽可能长的相同前后缀，去掉它们后，在剩余中间部分寻找最长回文前缀或后缀，将其拼接到已匹配的前后缀之间，保证整体为回文且满足 a + b 的拼接形式。

具体步骤

匹配相同前后缀
用双指针从两端向中间扫描，只要 s[l] == s[r] 就同时向内移动，直到不相等或相遇。记录停止时的 left 和 right，此时已匹配的前后缀长度为 left。
判断是否已完成
若 left > right，说明整个字符串已是回文，直接返回原串。
处理中间部分
令 mid = s[left..right]，长度为 m。
找最长回文前缀
从长到短枚举长度 len，检查 mid[0..len-1] 是否为回文，找到第一个满足条件的长度 bestPre。
找最长回文后缀
从长到短枚举长度 len，检查 mid[m-len..m-1] 是否为回文，找到第一个满足条件的长度 bestSuf。
选择较长者并构造答案
- 若 bestPre >= bestSuf，答案 = s[0..left-1] + mid[0..bestPre-1] + s[right+1..]
- 否则，答案 = s[0..left-1] + mid[m-bestSuf..] + s[right+1..]
输出答案（每个测试用例输出一行）

题解

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

string solve(string& s) 
{
	int n = s.size(), l = 0;
	while (l < n - 1 - l && s[l] == s[n - 1 - l]) l++;
	int left = l, right = n - 1 - l;
	if (left > right) return s;
	string mid = s.substr(left, right - left + 1);
	int m = mid.size();
	int bestPre = 0;
	for (int len = m; len >= 1; len --) 
	{
		bool ok = true;
		for (int i = 0; i < len / 2; i ++) 
		{
			if (mid[i] != mid[len - 1 - i]) 
			{
				ok = false; 
				break; 
			}
		}
		if (ok) 
		{ 
			bestPre = len;
			break; 
		}
	}
	int bestSuf = 0;
	for (int len = m; len >= 1; len --) 
	{
		bool ok = true;
		for (int i = 0; i < len / 2; i ++) 
		{
			if (mid[m - len + i] != mid[m - 1 - i]) 
			{
				ok = false; 
				break; 
			}
		}
		if (ok) 
		{
			bestSuf = len; 
			break; 
		}
	}
	string res;
	if (bestPre >= bestSuf)
		res = s.substr(0, left) + mid.substr(0, bestPre) + s.substr(right + 1);
	else
		res = s.substr(0, left) + mid.substr(m - bestSuf) + s.substr(right + 1);
	return res;
}

int main() 
{
	int t;
	cin >> t;
	while (t--) 
	{
		string s;
		cin >> s;
		cout << solve(s) << '\n';
	}
	return 0;
}

C.Palindrome Pairs

核心思路

利用字符出现次数的奇偶性来判断两个字符串拼接后能否重排成回文串。每个字符串用一个 26 位二进制掩码表示其奇偶状态，两串合法当且仅当它们的掩码异或后二进制中 1 的个数 ≤ 1。遍历数组，用哈希表统计已出现掩码的数量，对每个字符串查询其可配对的掩码计数，累加答案。

具体步骤

计算掩码：对每个字符串，遍历字符，用异或操作 ^= 翻转对应位（26 个字母），得到掩码 mask。
查询配对：当前字符串 mask 能与之前所有字符串组成回文对的情况：
- 异或结果为 0（即相同掩码）：cnt[mask]
- 异或结果只有一位为 1（翻转任意一位）：cnt[mask ^ (1<<b)]（b 从 0 到 25）
累加答案：将上述计数总和加入答案。
记录当前掩码：将当前掩码在哈希表中的计数加 1。
输出答案：遍历结束后输出累加值。

题解

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

int main() 
{
	int n;
	cin >> n;
	
	unordered_map<int, long long> cnt;
	cnt.reserve(n * 2 + 5);
	
	long long ans = 0;
	
	for (int i = 0; i < n; i ++) 
	{
		string s;
		cin >> s;
		
		int mask = 0;
		for (char c : s) 
		{
			mask ^= (1 << (c - 'a'));
		}
		
		ans += cnt[mask];
		
		for (int b = 0; b < 26; b ++) 
		{
			ans += cnt[mask ^ (1 << b)];
		}
		
		cnt[mask]++;
	}	
	
	cout << ans;
	return 0;
}

D.Erase and Extend (Easy Version)

核心思路

任何操作序列得到的最终字符串，等价于原串某个前缀重复若干次后截取前 k 个字符。枚举所有可能的前缀长度，构造对应字符串并取字典序最小者。

具体步骤

读入 n, k 和字符串 s。
初始化答案 ans 为长度为 k 的全 'z' 字符串（最大字典序）。
枚举前缀长度 len 从 1 到 min(n, k)：
- 取前缀 cur = s.substr(0, len)。
- 不断执行 cur += cur，直到长度 ≥ k。
- 截取前 k 个字符作为候选。
- 若候选比 ans 字典序小，则更新 ans。
输出 ans。

题解

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	string ans(k, 'z');
	for (int len = 1; len <= min(n, k); len ++) 
	{
		string cur = s.substr(0, len);
		while ((int)cur.size() < k) 
		{
			cur += cur;
		}
		cur = cur.substr(0, k);
		if (cur < ans) ans = cur;
	}
	
	cout << ans << '\n';
	return 0;
}

E.Fixed Prefix Permutations

核心思路

将排列乘积的美丽值问题转化为最长公共前缀匹配问题：

对每个排列 aj，计算其逆排列 invj，其中 invj[x] 表示数字 x 在aj 中的位置。
对于任意两个排列 ai 和 aj，复合排列 (ai⋅aj)k=aj[ai[k]]。
若其前 k 位为 1,2,…,k，则对每个 pos≤k 有 aj[ai[pos]]=pos，即 invj[ai[pos]]=pos，也就是 ai[pos]=invj[pos]。
因此，复合排列的美丽值就等于 ai 与 invj 的最长公共前缀长度。
所以问题转化为：对每个 ai，在所有 invj 中找与之公共前缀最长的长度。

具体步骤

预处理所有逆排列的前缀
- 对每个排列 aj（j=1..n）构造逆排列 invj。
- 将每个 invj 的所有前缀（长度从 1 到 m）编码成一个整数（使用 11 进制，因为值域为 1~10），并全部插入哈希集合中。
查询每个原排列的最长匹配前缀
- 对每个 ai（i=1..n），依次取前缀长度 len=1,2,…,m，将 ai[1..len] 编码为整数。
- 若该编码存在于哈希集合中，则更新当前答案为 len；否则停止继续（因更长的前缀也不可能存在）。
输出结果
- 每个 ai 得到的最大 len 即为该排列在所有 j 上复合得到的最大美丽值。
- 按输入顺序输出这 n 个整数，用空格分隔，每组测试用例后换行。

题解

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

int main() 
{
	int t;
	cin >> t;
	
	while (t--) 
	{
		int n, m;
		cin >> n >> m;
		vector<vector<int>> a(n, vector<int>(m + 1));
		for (int i = 0; i < n; i ++) 
		{
			for (int j = 1; j <= m; j ++)
			{
				cin >> a[i][j];
			}
		}
		
		unordered_set<long long> preSet;
		preSet.reserve(n * m + 5);
		
		for (int j = 0; j < n; j ++) 
		{
			vector<int> inv(m + 1);
			for (int pos = 1; pos <= m; pos ++) 
			{
				inv[a[j][pos]] = pos;
			}
			long long code = 0;
			for (int pos = 1; pos <= m; pos ++) 
			{
				code = code * 11 + inv[pos];
				preSet.insert(code);
			}
		}
		
		for (int i = 0; i < n; i ++) 
		{
			long long code = 0;
			int len = 0;
			for (int pos = 1; pos <= m; pos ++) 
			{
				code = code * 11 + a[i][pos];
				if (preSet.count(code)) len = pos;
				else break;
			}
			cout << len << ' ';
		}
		cout << '\n';
	}	
	return 0;
}

F.Sasha and One More Name

核心思路

如果字符串中所有字符都相同，无论怎样切割重排，得到的字符串都相同，因此无解，输出 Impossible。
否则，答案只可能是 1 或 2（不可能超过 2）。
先尝试 一次切割（即把原串切成两段并交换顺序），检查是否能得到不同于原串的回文串。如果可以，答案为 1。
若一次切割不可行，则 两次切割 必定可行，输出 2。

具体步骤

读入字符串 s，长度为 n。
检查全相同
遍历 s，若所有字符都等于 s[0]，则输出 Impossible 并结束。
尝试一次切割
枚举所有切割位置 i（1 ≤ i < n）：
- 构造新串 t = s.substr(i) + s.substr(0, i)（即交换两段）。
- 若 t 是回文串且 t != s，则输出 1 并结束。
输出 2
如果上述循环未找到可行解，则输出 2。

题解

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

bool ispal(string s)
{
	int l = 0, r = s.size() - 1;
	while (l < r)
	{
		if (s[l] != s[r])
		{
			return false;
		}
		l ++, r --;
	}
	return true;
}

int main()
{
	string s;
	cin >> s;
	int n = s.size();
	bool same = true;
	for (int i = 0; i < n / 2; i ++)
	{
		if(s[i] != s[0]) same = false;
	}
	if (same)
	{
		cout << "Impossible";
		return 0;
	}
	for (int i = 1; i < n; i ++)
	{
		string t = s.substr(i) + s.substr(0, i);
		if (t != s && ispal(t))
		{
			cout << 1;
			return 0;
		}
	}
	cout << 2;
	return 0;
}

A.Spelling Check

核心思路

具体步骤

题解

B.Prefix-Suffix Palindrome (Easy version)

核心思路

具体步骤

题解

核心思路

具体步骤

题解

D.Erase and Extend (Easy Version)

核心思路

具体步骤

题解

E.Fixed Prefix Permutations

题解

F.Sasha and One More Name

核心思路

具体步骤

题解

评论

还没有账户？

登录