[题解]Codeforces Round #519 - D. Mysterious Crime

【题目】

【描述】

有m个n排列，求一共有多少个公共子段。

数据范围：1<=n<=100000，1<=m<=10

【思路】

对于第一个排列来说，如果第k个位置开始往后L长的子段是一个公共的子段，那么从k开始往后数1,2,...,L-1长的子段都是公共的子段；如果第k个位置开始往后L长的子段是一个公共的子段，但第k个位置开始往后L+1长的子段不是一个公共的子段，那么位置k到位置k+L中任一位置j开始往后直到位置k+L的子段都不是公共的子段。这就意味着公共的子段被划分成了若干个部分，每个部分一定有最长的一个公共子段。对于一个最长的公共子段，不妨设其长度为L，则与它划分在同一组内的公共子段也就是它的子段，长度为1的有L个，长度为2的有L-1个…… 于是这一组一共有1+2+...+L=(L+1)*L/2个公共子段。

用一个数组pos[x][i]=j表示数字x在第i个排列中是第j个。要判断第k个位置的数是否还跟前面是在同一组，就需要判断前面那一组的开始（设为第p个位置）处的数和第k个位置处的数在m个排列中的相对位置是否都一样，即是不是都相差k-p，做一次检查需要O(m)。而由于公共子段的划分是不重合的（即没有一个公共子段属于一个以上的组），于是只需要从前往后扫一遍：从i开始向后扩展公共子段，当新的位置不再属于前一个组时，起始位置i跳到这个新的位置继续重复之前的操作。于是总的复杂度为O(n*m)。

（智障的zyy在比赛的时候把上一段加粗处的地方写错了，直接把位置当做这个位置上的数那来算，竟然还过了6组数据orz…… 因为这个智障的问题，再一次跟跑回expert失之交臂…… （年轻时候的zyy真厉害啊…… （说不定这道题做对了也回不了expert呢orz…… （闭嘴吧……

【我的实现】

复杂度：O(n*m)

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <algorithm>

 4 #include <cstring>

 5

 6 using namespace std;

 7 #define MaxN 100020

 8 #define MaxM 20

 9

10 long long pos[MaxN][MaxM];

11 long long a[MaxN];

12 long long Len[MaxN];

13 int n, m;

14 bool Check(int x, int y) //true: same

15 {

16     int delta = pos[x][1] - pos[y][1];

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

18         if(pos[x][i] - pos[y][i] != delta)

19             return false;

20     return true;

21 }

22

23 int main()

24 {

25     int i, j;

26     int x;

27     long long Ans;

28     scanf("%d%d", &n, &m);

29     for(i = 1; i <= m; i++)

30     {

31         for(j = 1; j <= n; j++)

32         {

33             scanf("%d", &x);

34             pos[x][i] = j; //x zai i hang j lie

35             if(i == 1)

36                 a[j] = x;

37         }

38     }

39     memset(Len, 0, sizeof(Len));

40     for(i = 1; i <= n; )

41     {

42         Len[i]++;

43         for(j = i+1; j <= n; j++)

44         {

45             if(Check(a[i], a[j]))

46                 Len[i]++;

47             else

48             {

49                 //i = j;

50                 break;

51             }

52         }

53         i = j;

54     }

55     Ans = 0;

56     for(i = 1; i <= n; i++)

57         if(Len[i])

58             Ans += Len[i] * (Len[i] + 1) / 2;

59     cout << Ans << endl;

60     return 0;

61 }

【评测结果】

巴特西

[题解]Codeforces Round #519 - D. Mysterious Crime

最新文章

热门文章