CSU - 1581 Clock Pictures （KMP的变形题，难想到）

题目链接：

http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1581

题目意思：告诉你现在有两个钟，现在两个钟上面都有n个指针，告诉你指针的位置，问你将钟表旋转的话能不能使得两个钟表重合

ps：将钟面的圆分成360000份，告诉你的指针的位置代表正北方向到指针的夹角（顺时针）

分析：

对每个钟的指针，按照与正北方向的夹角（顺时针）（因为题目给的就是顺时针）从小到大排序

然后得到相邻指针间的间距，然后根据KMP跑这些间距，如果能够匹配成功的话

那么肯定可以旋转到重合啊

有几个需要注意的地方：

1.最后一个指针的角度减去第一个指针的角度然后要加上360000才是两个指针间的间距

2.因为钟表是环，所以我们一个钟表的数组要变成两倍长度的该数组，因为我们要模拟环的匹配

这个是需要仔细思考的地方！

code：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<memory>

#include<algorithm>

using namespace std;

#define mod 360000

int a[],b[];

int c[],d[*];

int next1[];

int sum;

void getnext(int s[],int next1[],int m)

{

    next1[]=;

    next1[]=;

    for(int i=;i<m;i++)

    {

        int j=next1[i];

        while(j&&s[i]!=s[j])

            j=next1[j];

        if(s[i]==s[j])

            next1[i+]=j+;

        else

            next1[i+]=;

    }

}

int kmp(int ss[],int s[],int next1[],int n,int m)

{

    getnext(s,next1,m);

    int j=;

    for(int i=;i<n;i++)

    {

        while(j&&s[j]!=ss[i])

            j=next1[j];

        if(s[j]==ss[i])

            j++;

        if(j==m)

        {

           return ;

        }

    }

    return ;

}

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=;i<n;i++)

        scanf("%d",&a[i]);

    for(int i=;i<n;i++)

        scanf("%d",&b[i]);

    sort(a,a+n);

    sort(b,b+n);

    for(int i=;i<n-;i++)

        c[i]=a[i+]-a[i];

    c[n-]=a[]-a[n-]+mod;

    for(int i=;i<n-;i++)

        d[i]=b[i+]-b[i];

    d[n-]=b[]-b[n-]+mod;

    for(int i=n;i<*n;i++)

        d[i]=d[i-n];

    if(kmp(d,c,next1,*n,n))

        printf("possible\n");

    else

        printf("impossible\n");

    return ;

}

巴特西

CSU - 1581 Clock Pictures （KMP的变形题，难想到）

最新文章

热门文章