Beta Round #9 (酱油杯noi考后欢乐赛)PLQ和他的小伙伴们

题目:http://www.contesthunter.org/contest/Beta%20Round%20%EF%BC%839%20%28%E9%85%B1%E6%B2%B9%E6%9D%AFnoi%E8%80%83%E5%90%8E%E6%AC%A2%E4%B9%90%E8%B5%9B%29/PLQ%E5%92%8C%E4%BB%96%E7%9A%84%E5%B0%8F%E4%BC%99%E4%BC%B4%E4%BB%AC

题解:先给题目点个赞!真是一道好题!

刚开始看见真是一点思路都没有,后来看见简要题解说KMP,不知道怎么用。。。

今天忽然有了思路,我们假设从1开始,然后可以得到一个惊呆序列,并且把每个人的惊呆指数记下来,得到一个数列a[i]。

那么这个数列是由从谁开始数1唯一确定的,比如从i开始i最后的惊讶指数就是a[1],i+1就是a[2],也就是我们保持了一个相对的位置关系。

那我们对由a对b做字符串匹配,(先把a在后面复制一遍),假设匹配成功点是i,那么i-n+1就是1是从起始点开始数的第几个人,我们就可以得出起始点是谁。

一道漂亮的题!

推起始点那里蛋疼了好久。。。

代码:

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 2000000+5

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }
int n,m,a[maxn],b[maxn],next[maxn],ans[maxn],tot; int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); n=read();m=read();int x=-;
for1(i,m)a[((x+=read())%=n)+]++;
for1(i,n)a[n+i]=a[i];
for1(i,n)b[i]=read();
int j=;
for2(i,,n)
{
while(j&&b[j+]!=b[i])j=next[j];
if(b[j+]==b[i])j++;
next[i]=j;
}
j=;
for1(i,*n-)
{
while(j&&b[j+]!=a[i])j=next[j];
if(b[j+]==a[i])j++;
if(j==n)ans[++tot]=(*n+-i)%n?(*n+-i)%n:n,j=next[j];
}
if(tot!=){printf("Cannot determine!\n");printf("%d\n",tot);}else printf("%d\n",ans[]); return ; }

改了其中的一些细节,好像更容易理解?

代码:

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 2000000+5

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }
int n,m,a[maxn],b[maxn],next[maxn],ans,tot; int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); n=read();m=read();int x=-;
for1(i,m)a[((x+=read())%=n)+]++;
for1(i,n)a[n+i]=a[i];
for1(i,n)b[i]=read();
int j=;
for2(i,,n)
{
while(j&&b[j+]!=b[i])j=next[j];
if(b[j+]==b[i])j++;
next[i]=j;
}
j=;
for1(i,*n-)
{
while(j&&b[j+]!=a[i])j=next[j];
if(b[j+]==a[i])j++;
if(j==n)tot++,ans=-i+n+n,j=next[j];
}
if(tot!=){printf("Cannot determine!\n");printf("%d\n",tot);}else printf("%d\n",(ans-)%n+); return ; }
上一篇:ps -aux


下一篇:文本选择问题: css & js