20161023 NOIP 模拟赛 T2 解题报告

Task 2.回文串计数

(calc.pas/calc.c/calc.cpp)

【题目描述】

虽然是一名理科生，Mcx常常声称自己是一名真正的文科生。不知为何，他对于背诵总有一种莫名的热爱，这也促使他走向了以记忆量大而闻名的生物竞赛。然而，他很快发现这并不能满足他热爱背诵的心，但是作为一名强大的Boer，他找到了这么一条自虐的方式——背诵基因序列。不过这实在是太虐心了，就连Mcx也有些招架不住。不过他发现，如果他能事先知道这个序列里有多少对互不相交的回文串，他或许可以找到记忆的妙法。为了进一步验证这个方法，Mcx决定选取一个由小写字母构成的字符串SS来实验。不过由于互不相交的回文串实在过多，他很快就数晕了。不过他相信，在你的面前这个问题不过是小菜一碟。

【名词解释】

1.对于字符串SS,设其长度为Len,那么下文用Si表示SS中第i个字符(1<=i<=Len)

2.s[i,j]表示SS的一个字串，s[i,j] = “S_iS_i+1S_i+2…S_j-2S_j-1S_j”，比如当SS为”abcgfd”时,

s[2,5] = “bcgf” , s[1,5] = “abcgf”

3.当一个串被称为一个回文串当且仅当将这个串反写后与原串相同，如”abcba”

4.考虑一个四元组(l,r,L,R) , 当s[l,r]和s[L,R]均为回文串时，且满足1 <= l <=r< L <= R <= Len时，我们称s[l,r]和s[L,R]为一对互不相交的回文串。也即本题所求即为这种四元组的个数。两个四元组相同当且仅当对应的l,r,L,R都相同。

【题目输入】

仅一行，为字符串SS，保证全部由小写字母构成，由换行符标志结束。

【题目输出】

仅一行，为一个整数，表示互不相交的回文串的对数。

【样例输入】

aaa

【样例输出】

【样例解释】

SS = “aaa” , SS的任意一个字串均为回文串，其中总计有5对互不相交的回文串：

(1,1,2,2) , (1,1,2,3) , (1,1,3,3) , (1,2,3,3) , (2,2,3,3). (这里使用名词解释中的四元组进行表示)

【数据范围】

50%的数据满足SS的长度不超过200

100%的数据满足SS的长度不超过2000

————————————分割线————————————

划分型DP.

 1 #include "cstdio"
 2 #include "cstring"
 3 #include "algorithm"
 4 #include "fstream"
 5 #include "iostream"
 6 #include "sstream"
 7 #include "cstdlib"
 8 #include "cctype"
 9 
10 using namespace std ;
11 const int maxN = 2e3 + 1e2 ; 
12 typedef long long QAQ ;
13 
14 char s[ maxN ] ;
15 int Judge[ maxN ][ maxN ] ;
16 int f[ maxN ] ;
17 
18 inline void Init ( const int n ) {
19         for ( int i=0 ; i<n ; ++i ) Judge[ i ][ i ] = true ;
20         for(int i=0 ; i<n ; ++i ) {
21                 for(int L=-1 ; i-L>=0 && i+L<n ; ++L ) {
22                         if ( s [ i - L ] != s [ i + L ] ) break;
23                         else Judge[ i - L ][ i + L ] = true ; 
24                 }
25                 for(int L=-1 ; i-L>=0 && i+L+1<n ; ++L ) {
26                         if ( s [ i - L ] != s [ i + L + 1 ] ) break;
27                         else Judge[ i - L ][ i + L + 1 ] = true ;
28                 }
29         }
30 }
31 int main ( ) {
32         //freopen ( "calc.in" , "r" , stdin ) ; freopen ( "calc.out" , "w" , stdout ) ;
33         scanf ( "%s" , s ) ;int N = strlen ( s ) ;
34         Init ( N ) ; 
35         f[ 0 ] = 1 ;
36         for ( int i=1 ; i<=N-1 ; ++i ) {
37                 f[ i ] = f[ i - 1 ] ;
38                 for ( int j=0 ; j<=i ; ++j ) if ( Judge[ j ][ i ] ) ++ f[ i ] ; 
39         } 
40         unsigned long long Ans = 0 ; 
41         for ( int i=1 ; i<N ; ++i ) 
42                 for ( int j=i ; j<N ; ++j ) 
43                         if ( Judge[ i ][ j ] )Ans += f[ i - 1 ] ;
44         cout << Ans << endl ;
45         return 0 ; 
46 }

View Code

2016-10-25 15:49:15