题目详细题解

题目理解

题目要求判断一个字符串 $s$ 是否能够被分割成至少 $2$ 个非空子串 $t_1, t_2, \dots, t_k$，使得对于任意 $1 \le i < j \le k$，都满足 $t_i$ 的第一个字符不等于 $t_j$ 的最后一个字符。

关键观察

设字符串 $s$ 的第一个字符为 $first = s[0]$，最后一个字符为 $last = s[n-1]$。

核心结论：字符串 $s$ 是“好字符串”当且仅当 $s[0] \ne s[n-1]$。

充分性证明

若 $s[0] \ne s[n-1]$，则 $s$ 是好字符串。

构造方法：

• 令 $k = 2$
• $t_1 = s[0]$ （只取第一个字符）
• $t_2 = s[1..n-1]$ （从第二个字符到末尾）

验证条件：

• 对于 $i=1, j=2$：$t_1$ 的第一个字符是 $s[0]$，$t_2$ 的最后一个字符是 $s[n-1]$
• 因为 $s[0] \ne s[n-1]$，所以条件成立
• $k \ge 2$，满足要求

因此这种情况下答案是 "YES"。

必要性证明

若 $s[0] = s[n-1]$，则 $s$ 不是好字符串。

假设存在一种分割方式 $s = t_1 + t_2 + \dots + t_k$（$k \ge 2$）满足条件。

考虑 $t_1$ 的第一个字符：

• 它一定等于 $s[0]$

考虑 $t_k$ 的最后一个字符：

• 它一定等于 $s[n-1]$

根据条件，对于 $i=1, j=k$，必须有：

• $t_1$ 的第一个字符 $\ne$ $t_k$ 的最后一个字符

即：

这与假设 $s[0] = s[n-1]$ 矛盾。

因此不存在这样的分割，答案为 "NO"。

特殊情况讨论

需要注意的是，即使 $s[0] = s[n-1]$，也有可能让 $k > 2$ 来规避 $i=1, j=k$ 的条件吗？

不能。因为条件要求对所有 $1 \le i < j \le k$ 成立，其中必然包含 $i=1, j=k$ 这一对。这一对的要求是：

而：

只要 $s[0] = s[n-1]$，这一对就一定违反条件。

$k$ 的值不能改变这个事实，因为 $t_1$ 总是包含 $s[0]$ 作为其第一个字符，$t_k$ 总是包含 $s[n-1]$ 作为其最后一个字符。

算法步骤

1. 读入测试用例数 $t$
2. 对于每个测试用例：
   • 读入 $n$ 和字符串 $s$
   • 如果 $s[0] \ne s[n-1]$，输出 "YES"
   • 否则输出 "NO"