Codeforces Gym100502H：Clock Pictures（KMP算法）

http://codeforces.com/gym/100502/attachments

题意：有两个时钟上面有n个指针，给出的数字代表指针的角度。问能否在某一时刻使得两个时钟的指针重合。

思路：容易想到先对指针角度排序，然后相邻指针相减得到一个间距。如果这些间距能够相同的话，那么就代表可以在某个时刻重合。

最暴力地做法就是O（n^2）的复杂度。用第一个时钟的每一个间距去匹配第二个时钟的每一个间距，如果发现有能够匹配到的就说明可以。

明明都想到匹配了，但是我以为可以贪心地做，但是一直WA。比赛之后听到是KMP。瞬间爆炸。= =太弱了。

因为是环状的，所以要让第一个时钟的间距向后延伸n-1个。

然后让第一个时钟的间距当文本串，第二个时钟的间距当模式串，然后跑一下KMP就好了。

 #include <bits/stdc++.h>

 using namespace std;

 #define N 200010

 const int maxdeg = ;

 int nxt[N], a[N], b[N], c[N+N], d[N], n;

 void make_next() {

     for(int i = ; i <= n; i++) nxt[i] = ;

     int k = , j = ;

     nxt[] = ;

     while(j <= n) {

         if(k ==  || d[k] == d[j]) {

             k++; j++;

             nxt[j] = k;

         } else k = nxt[k];

     }

 }

 bool KMP() {

     int k = , j = ;

     make_next();

     while(j <  * n) {

         if(k ==  || d[k] == c[j]) {

             k++; j++;

             if(k == n) return true;

         } else k = nxt[k];

     }

     return false;

 }

 int main() {

     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-];

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

     }

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

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

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

         c[i] = c[i-n];

     if(KMP()) puts("possible");

     else puts("impossible");

     return ;

 }

巴特西

Codeforces Gym100502H：Clock Pictures（KMP算法）

最新文章

热门文章