BZOJ2160 拉拉队排练(回文树)

2024-09-02 18:18

本文主要是介绍BZOJ2160 拉拉队排练(回文树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

HYSBZ - 2160

拉拉队排练
Time Limit: 10000MS Memory Limit: 265216KB 64bit IO Format: %lld & %llu

Submit Status

Description

艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点,好的拉拉队往往能帮助球队增加士气,赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道,帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束,在雨荨和校长的挑选下,n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起,和对手抗衡,为艾利斯顿篮球队加油助威。一个阳光明媚的早晨,雨荨带领拉拉队的队员们开始了排练。n个女生从左到右排成一行,每个人手中都举了一个写有26个小写字母中的某一个的牌子,在比赛的时候挥舞,为小伙子们呐喊、加油。雨荨发现,如果连续的一段女生,有奇数个,并且他们手中的牌子所写的字母,从左到右和从右到左读起来一样,那么这一段女生就被称作和谐小群体。现在雨荨想找出所有和谐小群体,并且按照女生的个数降序排序之后,前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大,雨荨只要你告诉她,答案除以19930726的余数是多少就行了。

Input

输入为标准输入。第一行为两个正整数n和K,代表的东西在题目描述中已经叙述。接下来一行为n个字符,代表从左到右女生拿的牌子上写的字母。

Output

输出为标准输出。输出一个整数,代表题目描述中所写的乘积除以19930726的余数,如果总的和谐小群体个数小于K,输出一个整数-1。

Sample Input

5 3
ababa

Sample Output

45
【样例说明】
和谐小群体女生所拿牌子上写的字母从左到右按照女生个数降序排序后为ababa, aba, aba, bab, a, a, a, b, b,前三个长度的乘积为。

Hint

总共20个测试点,数据范围满足: 

Source

Submit Status


统计不同回文出现的次数.排序之后快速幂.


#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
const int N = 26;
const int MAXN = 1e6 +20;
const int mod = 19930726;
typedef pair<int,int> Node;
struct Palindromic_Tree {int next[MAXN][N] ;int fail[MAXN],cnt[MAXN],len[MAXN],S[MAXN];int last,n,p;int newnode(int l){for(int i = 0; i < N; ++i) next[p][i] = 0;cnt[p] = 0;len[p] = l;return p++;}void init(){last = n = p = 0;S[0] = -1;newnode(0);newnode(-1);fail[0] = 1;fail[1] = 0;}int get_fail(int x){while(S[n-len[x]-1] != S[n]) x  = fail[x];return x;}void add(int c){c -= 'a';S[++n] = c;int cur = get_fail(last);if(!next[cur][c]) {int now = newnode(len[cur]+2);fail[now] = next[get_fail(fail[cur])][c];next[cur][c] = now;}++cnt[last = next[cur][c]];}void count(){for(int i = p-1; i >= 0; --i) cnt[fail[i]] += cnt[i];}
} ;
Palindromic_Tree T;
char s[MAXN];
ll quickExp(int a,int n)
{ll res = 1,b = a;while(n) {if(n&1) res = res*b % mod;b = b*b % mod;n >>=1;}return res;
}
Node a[MAXN];
void solve (ll n,ll k) {T.init () ;for(int i = 0; i < n; ++i) T.add ( s[i] ) ;T.count();int m = 0;for(int i = T.p-1; i > 1; --i) {if(T.len[i]&1)a[m++] = (Node){T.len[i],T.cnt[i]};}sort(a,a+m,greater<pair<int,int> >());ll ans = 1;for(int i = 0; k&&i < m; ++i) {int limt = min(k,a[i].se+0LL);k -= limt;ans = ans * quickExp(a[i].fi,limt) % mod;}if(k) ans = -1;printf("%lld\n",ans);
}
int main() 
{ll n,k;while(~scanf("%lld%lld%s",&n,&k,s)) solve(n,k);return 0;
}


这篇关于BZOJ2160 拉拉队排练(回文树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1130700

相关文章

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

NYOJ 37 回文字符串(记忆化搜索)

OJ题目 : 戳这里~~ 描述 所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的,比如"aba"。当然,我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你,给你一个字符串,可在任意位置添加字符,最少再添加几个字符,可以使这个字符串成为回文字符串。 输入 第一行给出整数N(0<N<100) 接下来的N行,每行一个字符串,每个字符串长度不超过1000.

leetcode: 5. 最长回文子串

5. 最长回文子串 题目链接https://leetcode.cn/problems/longest-palindromic-substring/ 题目描述 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2:

java常用算法之最长回文子串(Longest Palindromic Substring)

方法一:时间复杂度为O(n^3) public static String longestPalindrome1(String s) {int maxPalinLength = 0;String longestPalindrome = null;int length = s.length();// check all possible sub stringsfor (int i = 0; i

力扣-9. 回文数

文章目录 力扣题目代码工程方法1:方法2: 力扣题目 给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。 回文数 是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 例如,121 是回文,而 123 不是。 示例 1: 输入:x = 121 输出:true 示例 2: 输入:x = -121 输出:false 解释:从左

psd面试(最长回文子序列+动态规划);

点击打开链接 链接:https://www.nowcoder.com/acm/contest/90/D来源:牛客网 题目描述 掌握未来命运的女神 psd 师兄在拿了朝田诗乃的 buff 后决定去实习。 埃森哲公司注册成立于爱尔兰,是一家全球领先的专业服务公司,为客户提供战略、咨询、数字、技术和运营服务及解决方案。他们立足商业与技术的前沿,业务涵盖40多个行业,以及企业日常运营部门的各个

代码随想录刷题day23丨39. 组合总和,40.组合总和II, 131.分割回文串

代码随想录刷题day23丨39. 组合总和,40.组合总和II, 131.分割回文串 1.题目 1.1组合总和 题目链接:39. 组合总和 - 力扣(LeetCode) 视频讲解:带你学透回溯算法-组合总和(对应「leetcode」力扣题目:39.组合总和)| 回溯法精讲!_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0039.%E7%

后缀数组 - 求最长回文子串 + 模板题 --- ural 1297

1297. Palindrome Time Limit: 1.0 second Memory Limit: 16 MB The “U.S. Robots” HQ has just received a rather alarming anonymous letter. It states that the agent from the competing «Robots Unlim

[置顶]论如何优雅的处理回文串 - 回文自动机详解

写在前面 最近无意中看到了这个数据结构,顺便也就学习了一下。 而且发现网上关于这个算法的描述有很多地方是错的,在这里做了一些更正。 处理字符串的算法很多:     KMP,E-KMP,AC自动机,后缀三兄弟:后缀树、后缀数组、后缀自动机,Trie树、Trie图,符串hash... 但以上数据结构在处理回文串上还是稍有欠缺,用这些来处理回文显得太小题大做。 于是有了Manacher算