2020.2.19GDUT寒假训练排位赛1-I 2020.2.19GDUT寒假训练排位赛1-I

I — Livestock Lineup 题目大意： 【2020.2.19GDUT寒假训练排位赛1-I】农夫约翰出去在路上散步，他想他可能迷路了!沿路有N个农场(1个≤N≤100个)不幸的是，农场没有门牌号，这使得农场主约翰很难确定他在路边的位置。然而，每个农场的路边都有一个彩色的邮筒，所以农民约翰希望，如果他看到离他最近的邮筒的颜色，他可以唯一地确定他在哪里。每个邮箱的颜色由大写字母A…Z指定。因此，这条路的N个邮箱的序列可以由一个长度为N的字符串表示，该字符串包含A…Z范围内的字母。某些邮箱可能与其他邮箱具有相同的颜色。农民John想知道如果他查看K个连续邮箱的任意序列，可以唯一地确定该序列在道路上的位置，这K的最小值是多少。例如，假设沿路的邮箱序列是’ABCDABC’。农民约翰不能设定K=3，因为如果他看到“ABC”，在这条路上有两个可能的位置可能是这一系列连续的颜色。K的最小值是K=4，因为如果他查看任何连续的4个邮箱，这个颜色序列唯一地决定了他在道路上的位置。
输入
第一行包含N
第二行包含一个N个字符的字符串，每个字符的范围是A…Z。
输出
打印K的最小值。

文章图片

题目分析：数据小，直接暴搜所有K的情况，即从1开始遍历字符串所有长度为K的子串是否有相同。
代码实现：

#include #include using namespace std; char s[105]; bool cmp(int a, int b, int x, int y)//比较从s[a]到s[b] 与从s[x]到s[y] 之间的字符串是否都相同，包括端点 { if(a==x && b==y) return false; int i, j; for(i=a,j=x; i<=b; i++,j++){ if(s[i]!=s[j]) return false; } return true; }int main() { int n,ans; scanf("%d",&n); scanf("%s",s); int i,j,m; for(i=0; i=n) break; for(m=0; m=n) break; if(cmp(j,j1,m,m1)==true){ cnt = true; break; } } if(cnt) break; }if(!cnt){//长度为K时，没有相同的子串 ans = i+1; break; } } cout << ans << endl; return 0; }

最后希望路过的dl给予改进建议！