当前位置： 移动技术网 > 移动技术>移动开发>IOS > Distinct Sub-palindromes（思维题）

Distinct Sub-palindromes（思维题）

2020年07月23日  | 移动技术网移动技术  | 我要评论


题目：设一个字符串的值为其所含回问子串的个数，给你一个数字n，全由小写字母构成的长度为n的值最小的字符串由多少个。

思路：分两种情况，当n小于3的时候任意字符串的值都相等，稍微想想就知道如果字符串中每个字符不同那么值就为长度，当有字符是同一字符时，虽然长度为1的回文子串少了但长度大于1的回文子串必然增加所以值还是等于n.但当n大于3时情况发生了改变，含有相同字符时子串可能不会增加如：abca,原因是因为中间含有两个不同的字符导致不回文，所以我们构造字符串时相同字符之间至少要隔两个字符，又为了使回文串最少所以只能隔两个。又因为单个不同的字符也算一个回文串。为了使值最少所以后面使用的字符要尽可能是前面已经出现过的字符。所以根据上述条件可以得出一个简单但深刻的结论：该字符串是以前三个不同字符为循环节的字符串时值最小。
ac代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define int long long
const int mod = 998244353;
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) {
        int a; cin >> a;
        if (a == 1) cout << 26 << endl;
        if (a == 2) cout << 676 << endl;
        if (a == 3) cout << 17576 << endl;
        if (a > 3) {
            cout << 26 * 25 * 24 << endl;
        }
    }
    return 0;
}

本文地址：https://blog.csdn.net/chineseherofeng/article/details/107498540

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网