LOJ2823 「BalticOI 2014 Day 1」三个朋友
2024-09-04 14:07:52
题意
给定一个字符串 S,先将字符串 S 复制一次(变成双倍快乐),得到字符串 T,然后在 T 中插入一个字符,得到字符串 U。
给出字符串 U,重新构造出字符串 S。
所有字符串只包含大写英文字母。
分析
参照jklover的题解。
此题使用hash十分简单,直接枚举每个前缀,与长度相等的后缀比较即可.
时间复杂度:线性。
代码
哈希的计算方法很妙。
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read()
{
rg T data=0;
rg int w=1;
rg char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
{
data=data*10+ch-'0';
ch=getchar();
}
return data*w;
}
template<class T>il T read(rg T&x)
{
return x=read<T>();
}
typedef unsigned long long ull;
co int N=2e6+1;
co ull Base=233;
ull Hash[N],Pow[N];
int n;
char s[N];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n);
scanf("%s",s+1);
if(n%2==0)
{
puts("NOT POSSIBLE");
return 0;
}
Pow[0]=1;
for(int i=1;i<=n;++i)
Pow[i]=Pow[i-1]*Base;
Hash[0]=0;
for(int i=1;i<=n;++i)
Hash[i]=Hash[i-1]*Base+s[i];
int cnt=0,cutpos;
ull res=0;
for(int i=1;i<=n;++i)
{
ull hashpre,hashsuf;
if(i<=n/2)
hashpre=Hash[n/2+1]+(Hash[i-1]-Hash[i])*Pow[n/2-i+1];
else
hashpre=Hash[n/2];
if(i<=n/2+1)
hashsuf=Hash[n]-Hash[n/2+1]*Pow[n/2];
else
hashsuf=(Hash[i-1]-Hash[n/2]*Pow[i-n/2-1])*Pow[n-i]+Hash[n]-Hash[i]*Pow[n-i];
if(hashpre==hashsuf)
{
++cnt;
if(res&&hashpre!=res)
{
puts("NOT UNIQUE");
return 0;
}
res=hashpre;
cutpos=i;
}
}
if(!cnt)
puts("NOT POSSIBLE");
else
{
if(cutpos>n/2)
for(int i=1;i<=n/2;++i)
putchar(s[i]);
else
for(int i=1;i<=n/2+1;++i)
if(i!=cutpos)
putchar(s[i]);
puts("");
}
return 0;
}
最新文章
- backup, file manipulation operations (such as ALTER DATABASE ADD FILE) and encryption changes on a database must be serialized.
- Sprint 3 回顾与总结 和团队贡献分 以及Sprint 1、2、3 总概
- Python 包的相对导入讲解
- c#配置log4net步骤
- 让wordpress分类和标签的描述支持HTML代码
- 转 layout_weight体验(实现按比例显示)
- VS生成时复制文件到指定目录
- 进入html+css世界的正确姿势
- 为你揭露2018微信公开课pro的12个重点
- vue框架入门和ES6介绍
- nginx反向代理+tomcat域名绑定
- Linux内核中常用的数据结构和算法(转)
- 自学Python4.4-装饰器的进阶
- jquery源码解析
- Mysql服务器处理客户端请求流程
- 使用jquery.validation+jquery.poshytip做表单验证--未完待续
- RxJava2.0学习笔记2 2018年7月3日 周二
- bash 定时任务
- [转载] iframe嵌入网页的用法
- unidac 6.0.1 与kbmmw 的一点小摩擦
热门文章
- Sybase数据库:两个特别注意的地方
- Linux中Nginx安装部署
- 0927-转载:SSM:spring+springmvc+mybatis框架中的XML配置文件功能详细解释
- [BZOJ1257]余数之和
- quartz(5)--作业管理和存储
- Android QRCodeReaderView 和Camera API冲突
- JavaWeb -- Struts 数据传输:OGNL和类型转换
- JSP导入包
- Java中异常的捕获顺序(多个catch)
- android开发环境:使用Android Studio搭建Android集成开发环境(图文教程)