电信做网站吗,如何制作课程网站模板下载,全网站开发是什么,中国建设网官方网站平台题意#xff1a;给一个序列#xff0c;找出1个连续子序列#xff0c;将其平分成前#xff0c;中#xff0c;后等长的3段子序列#xff0c;要求【前】和【中】是回文#xff0c;【中】和【后】是回文。求3段最长为多少#xff1f;由于平分的关系#xff0c;所以答案应该… 题意给一个序列找出1个连续子序列将其平分成前中后等长的3段子序列要求【前】和【中】是回文【中】和【后】是回文。求3段最长为多少由于平分的关系所以答案应该是3的倍数。 思路先Manacher求最长子串利用期间所记录的P 数组穷举一下所有可能的前两串再用O(1)时间判断第3串是否符合要求。 具体做法 1P[i]记录的是以i为中心从i-P[i]1到iP[i]-1这段都是回文。由于前两段之和必为偶数所以必须选取str[i]为#的。 2扫一遍每个#以其最长的回文开始穷举仅需将P[i]--即可然后找到右边对应的#判断P[i]是不是大于所穷举的长度直到3段都满足要求了跳出此‘#’换下一个。 1 #include iostream2 #include cstring3 #include vector4 #include stdio.h5 using namespace std;6 const int N100010;7 int n;8 int s[N*2];9 int P[N*2];
10
11
12 int cal(int len)
13 {
14 if(n3) return 0;
15 memset(P,0,sizeof(P));
16 int id1, mx1;
17 P[0]1;
18 P[1]1;
19 for(int i2; ilen; i)
20 {
21 P[i] imx? 1: min( P[2*id-i], mx-i);
22 while(s[iP[i]]s[i-P[i]]) P[i];
23 if(iP[i]mx)
24 {
25 idi;
26 mxiP[i];
27 }
28 }
29 int ans0;
30 for(int i3; i4len; i2)
31 {
32 int tagP[i]-1;
33 if( tag1 tagans )
34 {
35 while( P[itag]tag tagans ) tag--;
36 if(tagans) anstag;
37 }
38 }
39
40 return ans/2*3;
41 }
42
43 int main()
44 {
45 //freopen(input.txt, r, stdin);
46 int t, tmp, j0;
47 cint;
48
49 while(t--)
50 {
51 scanf(%d, n);
52 s[0]-1;
53 s[1]-2;
54 for(int i0,j2; in; i)
55 {
56 scanf(%d,tmp);
57 s[j]tmp;
58 s[j]-2;
59 }
60 s[n*22]-30;
61
62 printf(Case #%d: %d\n, j, cal( n*22 ));
63 }
64 return 0;
65 } AC代码 转载于:https://www.cnblogs.com/xcw0754/p/4722537.html
