wannafly 挑战赛8 E 小G的项链(manecher)
2024-10-07 06:08:20
链接:https://www.nowcoder.com/acm/contest/57/E
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld
题目描述
有一串有n颗珠子的项链,每颗珠子上有一个数字,从顺时针方向看依次是第1,2,…,n个珠子,第n个珠子之后是第1个珠子。但是小G觉得这串项链的造型不够美观,他决定用这串项链上的珠子造出一个新的项链,并且他希望这串新的项链是对称的。
一串项链是对称的,当且仅当存在至少一颗珠子满足:把它作为起始位置(即顺时针和逆时针方向数第0个珠子),对于任意的自然数i,顺时针数第i个珠子上的数字和逆时针数第i个珠子上的数字相同。特别的,一个仅有一颗珠子的项链也是对称的。
小G可以使用合成技术将任意正整数颗珠子合成为一个新的珠子,新珠子上的数字=原珠子上的数字的异或和。
用合成技术造出新项链的过程是这样的:最开始由小G确定一个能整除n的正整数k和一个原项链中的起始位置,之后从起始位置开始顺时针方向取连续的k个珠子,合成一个新的珠子作为新项链的第1个珠子,再取接下来连续的k个珠子,合成一个新的珠子作为新项链的第2个珠子,……,直到取完原项链的所有珠子为止。注意,合成的新珠子会直接放到新项链的位置,并不会插入原项链之中参与之后合成过程。新项链同样满足从顺时针方向看依次是第1,2,…,n个珠子,第n个珠子之后是第1个珠子。
小G希望新的项链上的珠子尽可能多,问新项链上的珠子最多有多少个。
输入描述:
第一行一个整数n。
第二行n个整数,第i个整数a
i
代表原项链上第i个珠子上的数字。
输出描述:
共一行一个整数,代表新项链的最大珠子数量。
输入例子:
5
9 3 9 1 1
输出例子:
5
-->
示例1
输入
5
9 3 9 1 1
输出
5
示例2
输入
9
7 8 6 5 4 3 1 2 15
输出
3
备注:
1 ≤ n ≤ 2e5,0<=ai<=1e9
////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
#define mst(a,b) memset((a),(b), sizeof a)
#define lowbit(a) ((a)&(-a))
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+;
const int maxn=4e5+;
int n;
int a[maxn],ps[maxn];
int s[maxn],ma[maxn<<],mp[maxn<<];
bool manacher(int ne){
int len=ne*;
for(int i=;i<ne;++i)s[ne+i]=s[i];
int l=;
ma[l++]=-;ma[l++]=-;
for(int i=;i<len;++i)ma[l++]=s[i],ma[l++]=-;
ma[l]=-;
int mx=,id=;
for(int i=;i<l;++i){
mp[i]=mx>i?min(mp[*id-i],mx-i):;
while(ma[i+mp[i]]==ma[i-mp[i]])++mp[i];
if(mp[i]->=ne)return true;
if(i+mp[i]>mx)mx=i+mp[i],id=i;
}
return false;
}
int get(int st,int en){
if(en>n)return ps[n]^ps[st]^ps[en-n]^ps[];
return ps[en]^ps[st];
}
int main(){
#ifdef local
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif
scanf("%d",&n);
for(int i=;i<=n;++i)scanf("%d",&a[i]),ps[i]=ps[i-]^a[i];
for(int k=;k<=n;++k){
if(n%k!=)continue;
int ans=n/k;
for(int i=;i<k;++i){
for(int j=;j<ans;++j)
s[j]=get(j*k+i,(j+)*k+i);
if(manacher(ans))return *printf("%d",ans);
}
}
return ;
}
最新文章
- 如何使用JS来检测游览器是什么类型,或android是什么版本号- 转载
- CSS3-html,样式与样式表的创建,选择器
- 如何在redhat下安装WineQQ
- bookhub -- 扁平化本地电子书管理与分享工具
- Android SQLite之乐学成语项目数据库存储
- 王立平-NGUI
- Android性能优化——之防止内存泄露
- 平面之后3D成主流?VR全景表示不服!——全景智慧城市常诚
- yii2之依赖注入与依赖注入容器
- vue中什么样的数据可以是在视图中显示
- 在nagios中使用nrpe自定义脚本
- 三、Dockerfile的说明和编写
- 配置percona mysql server 5.7基于gtid主主复制架构
- LinkedList源码分析和实例应用
- Jquery----对文档操作
- OpenSSH多路复用Multiplexing配置
- 使用NewLife网络库构建可靠的自动售货机Socket服务端(一)
- es6Promise及小程序Promise用法
- C &; C++ 宏与const
- Unsupported major.minor version 49.0的错误解决