[PHP知识库]小A的游戏（思维）

题目链接：http://icpc.upc.edu.cn/problem.php?cid=2869&pid=8

题目描述
小A在和小B玩一个游戏，小A有一个字符串S，现在小A删除了其中K个字符，给出删除前的字符串S，和删除后的字符串S’，现在小A想知道，是否无论怎样删除，小B都能猜中他删除了哪些位置上的字母。
若一定，输出 $Certain$ ，否则输出 $Uncertain$。
输入
第一行一个正整数$t$，表示数据组数。
第二行一个字符串表示 s 。
第三行一个正整数表示 K 。$1\le K\le |s|\le 100$ ，s 仅包含小写字母。
输出
对于每组数据，输出一行一个字符串。
若一定，输出 $Certain$ ，否则输出 $Uncertain$ 。

样例输入

1 
snuke 
2 

样例输出

Certain

提示
例如如果小a删去s,e，则她告诉你"nuk"，那么小b可以确定删去的是原串的第1个字符和第5个字符。
无论小a删去哪两个字符，小b都一定可以确定其在原串的位置。

对于50%的数据，t<=10,k<=n<=10
对于70%的数据，t<=10,k<=n<=20
对于100%的数据,t<=10,k<=n<=100

思考：

要想出什么的模型，删除一些位置后，从剩下的一段看不出来删除的哪些位置。
如果S串中存在这样的模型，那就是$Unsertain$.

结论：
如果两个字符相同，那删除一个字符和中间的所有字符，是判断不出来删除的是前一个字符还是后一个字符的。

实现：

从前往后二重循环，如果两个字符相等，并且其距离不超过k，就找到了这个模型。
要注意特判下删除的个数等于串长的情况，删完了肯定知道删了哪些位置。

Code：

#include<iostream>
using namespace std;

const int N=200010;
int n,m,a[N];
string s;

int main(){
	int T;cin>>T;
	while(T--)
	{
		int k;
		cin>>s>>k;
		s=' '+s;
		n=s.size()-1;
		
		if(k==n){ //特判删完的情况 
			cout<<"Certain"<<endl;
			continue;
		}
		
		int flag=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)
			{
				if(s[i]==s[j]){
					if(j-i<=k) flag=1;
					break;
				}
			}
			if(flag) break;
		}
		if(flag) cout<<"Uncertain"<<endl;
		else cout<<"Certain"<<endl;
	}
	
	return 0;
}

确实，这个模型要想一段时间。