ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[CCPC2022湖北省赛]J. Palindrome Reversion(字符串hash)

2022年5月22日 989点热度 1人点赞 0条评论

题目链接:https://codeforces.com/gym/103729/problem/J

赛场上没做出这题,可惜了。其实一开始就想到了字符串hash,甚至思路都和题解一样,但是由于忘记了字符串hash的板子,然后一时着急就没做出来。其实不难。

题意

给定一个字符串S,问能否通过将一个连续区间[l ,r](l <= r)翻转一次使得字符串S变为一个回文串。

输出任意一种可行方案即可。

如果不存在就输出-1 -1。

思路

第一步,如果这个字符串本身就是回文就不需要修改,直接输出1 1就行。

第二步,将字符串左右两边的回文部分删除,记录下删除了多少(记录为dl),输出答案的时候需要补上。

第三步,将当前字符串S初始化成hash串,要做两个hash,一个正向一个反向,同时把进制数base求一下连续的幂(后面求子串的hash会用到)。

第四步,以1作起点,向右枚举终点,如果找到了一个区间翻转可以使得字符串变为回文,那么就直接输出。如果没有,再从N为终点,向左枚举起点,如果有答案也直接输出。记得加上dl。

为什么从1和N开始枚举呢,因为可以翻转变为回文的一定是以下三种情况。

如果没答案就输出-1 -1。

真实惨痛的经历,下次一定要带全板子!

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef unsigned long long ULL;
const ULL maxn = 1e5 + 9, base = 131;

ULL h1[maxn], h2[maxn], b[maxn];
char s[maxn];
int N = 0;

void initHash(char s[], int N)
{
	b[0] = 1;
	for(int i = 1;i <= N; ++ i)b[i] = b[i - 1] * base;
	for(int i = 1;i <= N; ++ i)h1[i] = h1[i - 1] * base + s[i];
	for(int i = N;i >= 1; -- i)h2[i] = h2[i + 1] * base + s[i];
}

ULL getHash1(int l,int r){return h1[r] - h1[l - 1] * b[r - l + 1];}
ULL getHash2(int l,int r){return h2[l] - h2[r + 1] * b[r - l + 1];}

bool isRe(int l,int r)//将[l, r]翻转是否回文 
{
	ULL res1 = getHash1(1, l - 1) * b[N - l + 1] + getHash2(l, r) * b[N - r] + getHash1(r + 1, N);
	ULL res2 = getHash2(r + 1, N) * b[r] + getHash1(l, r) * b[l - 1] + getHash2(1, l - 1);
	return res1 == res2;
}

signed main()
{
	cin >> s + 1;
	int l = 1, r = strlen(s + 1);
	while(l <= r && s[l] == s[r])l ++, r --;
	int dl = l - 1;
	if(l > r)return printf("1 1\n"), 0;
	
	for(int i = l;i <= r; ++ i)s[++ N] = s[i];
	s[N + 1] = '\0';
	initHash(s, N);
	for(int i = 1;i <= N; ++ i)if(isRe(1, i))return printf("%lld %lld\n", 1 + dl, i + dl), 0;
	for(int i = N;i >= 1; -- i)if(isRe(i, N))return printf("%lld %lld\n", i + dl, N + dl), 0;
	printf("-1 -1\n");
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ ccpc 哈希 回文 字符串 字符串hash
最后更新:2022年7月9日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 题意
  • 思路
  • 代码

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号