2020杭电多校集训-Distinct Sub-palindromes

题目：
S is a string of length n. S consists of lowercase English alphabets.

Your task is to count the number of different S with the minimum number of distinct sub-palindromes. Sub-palindrome is a palindromic substring.

Two sub-palindromes u and v are distinct if their lengths are different or for some i (0≤i≤length), ui≠vi. For example, string “aaaa” contains only 4 distinct sub-palindromes which are “a”, “aa”, “aaa” and “aaaa”.

传送门：problem 6754
题目大意：求用最少的不同子回文串构成不同的S的字符串的数量，其中，S由小写英文字母组成，子回文串是回文串的子串

思路：

1. n=1时，不难发现，S直接由26种英文字母构成即可
2. n=2时，最少的不同子回文串有2种， 因为S的类型只可能有XX,XY,YX，这三种，而XX有X,XX两种，XY有X,Y两种，YX同XY, 因此，由于可以重复，此时S的数目就是26*26=676，即每个位置都有26种选择；
3. n=3时，最少的不同子回文串有3种，因为S的类型只可能有XXX,XXY,XYX,XYZ等典型的4种， 对于XXX，有XXX,XX,X3种，对于XXY有XX,X,Y3种，对于XYX，有XYX，X,Y3种，对于XYZ,有X,Y,Z3种，因此，由于可以重复，此时S的数目就是262626=17576.
4. n=4时，典型的S有XXXX,XXYX,XXYY,XYZX等4种，对于XXXX,显然4种不同子回文串，对于XXYX,有X,Y,XX,XYX4种， 对于XXYY，显然4种，对于XYZX，只有3种，因此，由于至少得有三个不同的元素，此时S的数目就相当于从26个里面有顺序的选3个，即A(26，3)=15600；
5. n=5,6,……时，我们完全可以进行XYZXYZX等类似的扩展，这样子，不同的子回文串一定都是最少的3，因此，n>=4时，S的数目就都一样了，即15600种。

代码
直接switch相应输出即可

#include <iostream>
using namespace std;

int main()
{
    int t;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin>>t)
        while(t--)
        {
            int n;
            cin>>n;
            switch(n)
            {
                case 1:     cout<<26<<endl;break;
                case 2:     cout<<676<<endl;break;
                case 3 :    cout<<17576<<endl; break;
                default :   cout<<15600<<endl;
            }
        }
    return 0;
}

本文地址：https://blog.csdn.net/world_started/article/details/107504253