USACO Section 5.1 Musical Themes - 题目转换以及KMP..

网友投稿 318 2022-11-14

USACO Section 5.1 Musical Themes - 题目转换以及KMP..

先写了一个N^3的裸搜试了试~~结果还过了12个点~~囧...然后就想起优化...主要思想是要利用前面已经搜索过的..尽量减少重复的判断搜索...根据这些特征自然而然的想到了KMP...但由于题目中是要求两列每位对应差相等而不是说两列完全相等...所以写了一晚上搞得十分蛋疼..还是搞不出来...

再看了下样例..发现题目可以转化!!! 其实差了一个自然数的两列..若写成相邻前后之差的形式就会变成完全相同的两列..如1 2 4 5 4 5 7 1 写成相邻前后之差的形式为 1 2 1 -1 1 2 1 -6 那么看出最长公共部分是有两个1 2 ...那么这串中符合题目要求最长的主旋律是3个音节( 因为这个1,2是1 2 4 又是 4 5 7 不难理解为啥实际结果比转化后的最长结果会大一.)...

经过这么转化..题目就变成了给出一个串...找出其中最长的两段不相邻的相同子串...我最先想到的KMP就可以完美实现了!!..N^2的算法..先枚举第一个段的起点..从1~N..将这个起点到N的段构造好Fail指针( 同最本质的KMP..指向离自己最近的相同前缀尾部部分 ) .. 构造好后..从第一段起点的后面一个点扫到N...就是用后面一段在先做好的长串里找最长公共子串...但要注意题目的要求..两段不能有公共部分...并且在通过转化后..这个条件又等同了两段间至少要有一个数..不能相邻...注意了这个条件的处理...这个KMP还是很好写的..

Program:

/* ID: zzyzzy12 LANG: C++ TASK: theme*/ #include #include #include #include #include #include#include#include #include #define oo 2000000005 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std; int a[5005],n,Fail[5005];int main() { freopen("theme.in","r",stdin); freopen("theme.out","w",stdout); int i,j,m,k,ans; bool f; scanf("%d",&n); for (i=1;i<=n;i++) scanf("%d",&a[i]); for (i=1;i=i && a[k+1]!=a[j]) k=Fail[k]; if (a[k+1]==a[j]) Fail[j]=k+1; else Fail[j]=k; } m=0; j=i+1; while (j<=n) { f=true; while (i+mans) ans=m+1; k=Fail[i+m-1]; while (k>=i && a[k+1]!=a[j]) k=Fail[k]; if (a[k+1]==a[j]) m=k-i+1; else m=0; } } if (ans<5) ans=0; printf("%d\n",ans); return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

上一篇:JMeter参数化4种实现方式(小结)
下一篇:USACO Section 4.2 The Perfect Stall - 网络流求最大二分图匹配..
相关文章

 发表评论

暂时没有评论，来抢沙发吧~