题目解析

题意分析

题目定义了一个字符串的$D$-对的概念，并引入了"令人惊讶的字符串"的判断标准：

1. $D$-对：对于字符串$s$，其$D$-对是指字符串中所有相距为$D$的有序字母对。例如，字符串$s = s_1s_2...s_n$，其$D$-对为$(s_1, s_{1+D}), (s_2, s_{2+D}), ..., (s_{n-D}, s_n)$。
2. $D$-唯一：如果一个字符串的所有$D$-对都互不相同，则称该字符串是$D$-唯一的。
3. 令人惊讶的字符串：如果一个字符串对于所有可能的距离$D$（$0 \leq D \leq n-2$，其中$n$是字符串长度）都是$D$-唯一的，则称该字符串是令人惊讶的。

解题思路

要判断一个字符串是否是令人惊讶的，需要检查该字符串对于所有可能的$D$是否满足$D$-唯一性。具体步骤如下：

1. 对于输入的字符串$s$，计算其长度$n$。
2. 遍历所有可能的距离$D$（从$0$到$n-2$）：
   • 对于每个$D$，生成所有$D$-对。
   • 检查这些$D$-对是否互不相同。如果有重复，则字符串不是令人惊讶的。
3. 如果所有$D$的$D$-对都互不相同，则字符串是令人惊讶的。

示例分析

示例1：

• 输入字符串：$ZGBG$
  • $D=0$：$(Z,G), (G,B), (B,G)$ → 全部唯一。
  • $D=1$：$(Z,B), (G,G)$ → 全部唯一。
  • $D=2$：$(Z,G)$ → 唯一。
  • 结论：$ZGBG$是令人惊讶的。

示例2：

• 输入字符串：$AABB$
  • $D=0$：$(A,A), (A,B), (B,B)$ → 全部唯一。
  • $D=1$：$(A,B), (A,B)$ → 重复，不唯一。
  • 结论：$AABB$不是令人惊讶的。

复杂度分析

• 对于每个字符串$s$，长度为$n$，需要检查$O(n)$个$D$值。
• 对于每个$D$，生成$O(n)$个$D$-对，并检查唯一性，可以用哈希表实现$O(1)$的插入和查询。
• 总复杂度为$O(n^2)$，对于$n \leq 79$，完全可接受。

代码实现思路

1. 读取输入字符串，直到遇到单独的$*$。
2. 对于每个字符串：
   • 遍历$D$从$0$到$n-2$。
   • 对于每个$D$，收集所有$D$-对，并检查是否有重复。
   • 如果任何$D$的$D$-对有重复，则字符串不是令人惊讶的。
3. 根据检查结果输出相应的结论。

/*ASCII标记*/
 
//Memory Time 
//212K   0MS 
 
#include<iostream>
#include<string>
#include<cstring>  // 仍然需要 strlen
using namespace std;
 
int main(void)
{
	char s[80];
	while(cin>>s && s[0]!='*')
	{
		int len=strlen(s);
		if(len<=2)  //长度小于等于2的串必定是surprising String
		{
			cout<<s<<" is surprising."<<endl;
			continue;
		}
		bool mark=true;  //标记s是否为Surprising String
		for(int d=0;d<=len-2;d++)  //d为当前所选取的两个字母之间的距离，d(max)=len-2
		{
			bool flag['Z'*100+'Z'+1];   //标记D-pairs字母对
			// 手动初始化 flag 数组
			for (int i = 0; i < 'Z'*100+'Z'+1; i++)
				flag[i] = false;
 
			bool sign=true;  //标记D-pairs字母对是不是D-unique
			for(int i=0;i<=len-d-2;i++)  //i为所选取的两个字母中第一个字母的下标
			{
				int pair=s[i]*100+s[i+d+1];  //D-pairs字母对的ASCII码所构成的四位数
 
				if(!flag[pair])
					flag[pair]=true;
				else
				{
					sign=false;  //存在相同的D-pairs,该字母对不是D-unique
					break;
				}
			}
			if(!sign)
			{
				mark=false;  //存在非D-unique，s不是Surprising String
				break;
			}
		}
		if(mark)
			cout<<s<<" is surprising."<<endl;
		else
			cout<<s<<" is NOT surprising."<<endl;
	}
	return 0;
}