杭电多校第一场 1004 Distinct Sub-palindromes 题解

题目大意

长度为n的字符串,这个字符串由小写字母构成,求所有长度为n的字符串中,子回文串数量最小的串的数量为多少。

解题思路

一开始还以为是$26^n$,结果我们一个队交快速幂wa了三次。。

(我就wa了一次。。

首先,当长度为一的时候,很显然答案是26,因为无论你用哪个字母,子回文串的数量都是1。

当长度为二的时候,可以理解为在长度为一的串中,在空隙中插入其他字母,发现,无论你插入哪个字母,串的子回文串的数量都会加一,所以答案为$26^2$。当长度为三的时候,可以得出同样的结果,答案为$26^3$。

当长度大于三的时候,可以发现,当原长度为三的串中各个元素都不相同的时候,在其空隙中插入与左右两边都不相同的第三个字母,这个时候,串的回文子串的数量是不会增加的,所以答案为$262524$。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main(){
int n;
scanf("%d", &n);
while(n--){
int t;
cin >> t;
if(t==1)
cout << 26 << endl;
else if(t == 2)
cout << 676 << endl;
else if(t==3)
cout << 17576 << endl;
else cout << 15600 << endl;
}
return 0;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信