网站建设 图标,网站的制作视频,企业管理培训课程排行榜,外贸企业网站源码我看网上也没有写这个题的#xff0c;顺便写一下#xff08;可能是大佬都觉得太简单了 #xff09; 链接#xff1a;牛客网 时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K 64bit IO Format: %lld 题目描述…我看网上也没有写这个题的顺便写一下可能是大佬都觉得太简单了 链接牛客网 时间限制C/C 1秒其他语言2秒 空间限制C/C 32768K其他语言65536K 64bit IO Format: %lld 题目描述 有一串有n颗珠子的项链每颗珠子上有一个数字从顺时针方向看依次是第12…n个珠子第n个珠子之后是第1个珠子。但是小G觉得这串项链的造型不够美观他决定用这串项链上的珠子造出一个新的项链并且他希望这串新的项链是对称的。 一串项链是对称的当且仅当存在至少一颗珠子满足把它作为起始位置即顺时针和逆时针方向数第0个珠子对于任意的自然数i顺时针数第i个珠子上的数字和逆时针数第i个珠子上的数字相同。特别的一个仅有一颗珠子的项链也是对称的。 小G可以使用合成技术将任意正整数颗珠子合成为一个新的珠子新珠子上的数字原珠子上的数字的异或和。 用合成技术造出新项链的过程是这样的最开始由小G确定一个能整除n的正整数k和一个原项链中的起始位置之后从起始位置开始顺时针方向取连续的k个珠子合成一个新的珠子作为新项链的第1个珠子再取接下来连续的k个珠子合成一个新的珠子作为新项链的第2个珠子……直到取完原项链的所有珠子为止。注意合成的新珠子会直接放到新项链的位置并不会插入原项链之中参与之后合成过程。新项链同样满足从顺时针方向看依次是第12…n个珠子第n个珠子之后是第1个珠子。 小G希望新的项链上的珠子尽可能多问新项链上的珠子最多有多少个。 输入描述:
第一行一个整数n。 第二行n个整数第i个整数ai代表原项链上第i个珠子上的数字。
输出描述: 共一行一个整数代表新项链的最大珠子数量。 示例1 输入
5
9 3 9 1 1输出
5示例2 输入
9
7 8 6 5 4 3 1 2 15输出
3备注: 1 ≤ n ≤ 2 x 105,0 ≤ ai ≤ 109 题意 给你n个数组成环分成k个等长的区间每个区间的值就是区间内部数的异或和用区间的相对位置摆成环且使这个环组成回文串问你回文串最长是多少 题解 因为n个数组成环所以我们先把环破开就是环翻倍nn让尾连头。然后求出所有前缀异或和pre 因为要把n分成长度为len的num个区间。 我们要尝试len的每一种情况让每个区间内的len个数异或和然后看组成的是不是回文串找到最大的len情况。 因为我们一开始将2*n个数都存了前缀异或和根据异或的性质a^a0,所以我就可以通过前缀异或和轻松算出每个区间的异或值比如pre[3] ^ pre[6]算出来就是区间[4,6]的异或和因为3之前的重复就消除了 求出每区间的异或和放在一个数组b中再求b是否为回文串。但注意b是一个环直接判断可能不对比如abb不是回文串但是abb是一个环如果你用正确的打开方式它也可以是bab那就是回文串了那该怎么办对既然是环我们就给它拆成链我们把项链倍长如果倍长后的字符串中存在一个子串是回文串且长度超过了倍长前字符串的长度显然是存在对称轴的。 还是abb拆之后就是abbabb,看这个最长回文串的长度5是否大于本身3 至此基本上就大功告成了 什么你说用什么求回文串那肯定暴力 当然用Manacher b站讲解Manacher 附码
#include bits/stdc.h
using namespace std;
const int maxn 1e6 5;int n;
int p[maxn*2];
int str[maxn*2];//数组范围要乘2因为环要拆成链
int a[maxn*2];
int b[maxn*2];
int pre[maxn*2];int init(int *s,int len)
{str[0];int ant1;str[1]#;for(int i1;ilen;i){str[ant]s[i];str[ant]#;}str[ant]\0;return ant;
}
int manacher(int *s,int num)
{int ans-1;int leninit(b,num);int mx0;int id0;for(int i1;ilen;i){if(imx)p[i]min(p[id*2-i],mx-i);else p[i]1;while(str[ip[i]]str[i-p[i]])p[i];if(p[i]imx)mxp[i]i,idi;ansmax(ans,p[i]-1);}return ans;
}
bool check(int len) {int num n / len;for(int i 0; i len; i) {for(int j 0; j num; j) {b[j] pre[(j 1) * len i] ^ pre[j * len i];}for(int i 0; i num; i) {b[i num] b[i];}if(manacher(b, num * 2)num) return true;}return false;
}
int main() {cinn;for(int i 1; i n; i) {cina[i];pre[i] pre[i-1] ^ a[i];}for(int i n 1; i n n; i) {pre[i] pre[i - 1] ^ a[i - n];}int ans 1;for(int i 1; i sqrt(n); i) {if(n % i) continue;if(check(n / i)) ans max(ans, i);if(check(i)) ans max(ans, n / i);}printf(%d\n, ans);return 0;
}
