首页 > 代码库 > UVA 12378 Ball Blasting Game Manacher裸题
UVA 12378 Ball Blasting Game Manacher裸题
题目链接:点击打开链接
题意:
消除字符串游戏,选择一个字母,则会消除和该字母相同且连续的一段,然后左右两边合拢,若左右两边字母相同则再次消除掉。直到合拢时两边字母不相同。
问这样连续消除的最大次数。
思路:
先把连续相同的字母当成一个字母,然后求最长回文串,
则答案就是(最长长度+1)/;2
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <cstring> #include <iostream> using namespace std; const int MAXN = 110010; //字符串长度<MAXN char Ma[MAXN * 2]; int Mp[MAXN * 2]; int Manacher(char s[]) { int l = 0, len = strlen(s); Ma[l++] = '$'; Ma[l++] = '#'; for (int i = 0; i<len; i++) { Ma[l++] = s[i]; Ma[l++] = '#'; } Ma[l] = 0; int mx = 0, id = 0; for (int i = 0; i<l; i++) { Mp[i] = mx>i ? min(Mp[2 * id - i], mx - i) : 1; while (Ma[i + Mp[i]] == Ma[i - Mp[i]])Mp[i]++; if (i + Mp[i]>mx) { mx = i + Mp[i]; id = i; } } int ans = 0; for (int i = 0; i<2 * len + 2; i++) ans = max(ans, Mp[i] - 1); return ans; } char d[100100], s[100100]; int main(){ int T; cin>>T; while (T--) { scanf("%s", d); int top = 0; s[0] = d[0]; for(int i = 1; d[i]; i++) if(d[i]!=s[top]) s[++top] = d[i]; s[++top] = 0; printf("%d\n", (Manacher(s)+1)/2); } return 0; }
UVA 12378 Ball Blasting Game Manacher裸题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。