E - Slot Machines Gym - 101667I —— kmp

本文主要是介绍E - Slot Machines Gym - 101667I —— kmp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原文链接：
https://odzkskevi.qnssl.com/6fd8c99567698f4bad5a228cc982bad7?v=1534480987

这么长的题目我都看不懂，还是别人和我讲的题意，就是给你一串数字，前面可能是没有规律的，后面是有规律的，让你找出需要删掉k个数，然后循环内数的个数是p，k+p最小。
网上kmp算法很多，这个我是看别人的，它可以找到上一个循环的节点。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn],nex[maxn];
int n;
void getnext()
{int i=1,j=0;nex[1]=0;while(i<=n){if(j==0||a[i]==a[j]){i++,j++;nex[i]=j;}elsej=nex[j];}
}
int main()
{scanf("%d",&n);for(int i=n;i>=1;i--)scanf("%d",&a[i]);getnext();int k=1e9,p=1e9;for(int i=1;i<=n;i++){int np=i-nex[i+1]+1,nk=n-i;if(np+nk<p+k)p=np,k=nk;}printf("%d %d\n",k,p);return 0;
}

这篇关于E - Slot Machines Gym - 101667I —— kmp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---