Codeforces Round 943 (Div. 3)（A,B,C,D,E,F,G1,G2）

本文主要是介绍Codeforces Round 943 (Div. 3)（A,B,C,D,E,F,G1,G2），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

比赛链接

这场比较有意思，可惜最近太忙了没法仔细研究，只能看看别人的题解然后补掉了。这场还是比较难的。

C，E是构造，D是个模拟，F需要先推出一个结论，之后二分查找，G题是字符串的题，需要先用拓展kmp预处理一下，然后做法也很多，有根号分治，分治+剪枝，还有一个按顺序加数然后二分的做法。FG比较难，解题思路确实很妙。

---

A. Maximize?

题意：

给你一个整数 $x$ 。你的任务是找出任意一个整数 $y$ ，使得 $\gcd (x,y)+y$ 最大。 $(1\le y<x)$ 使得 $\gcd (x,y)+y$ 最大。

注意，如果有一个以上的 $y$ 满足该语句，那么你可以找出任何一个。

$\gcd (a,b)$ 是 $a$ 和 $b$ 的最大公约数。例如， $\gcd (6,4)=2$ 。

思路：

直接暴力枚举

code：

#include <iostream>
#include <cstdio>
using namespace std;int T,x;int gcd(int a,int b){while(b)b^=a^=b^=a%=b;return a;
}int main(){cin>>T;while(T--){cin>>x;int ans=0,maxx=0;for(int y=1,d;y<x;y++){d=gcd(x,y);if(d+y>maxx)ans=y,maxx=d+y;}cout<<ans<<endl;}return 0;
}

---

B. Prefiquence

题意：

给你两个二进制字符串 $a$ 和 $b$ 。二进制字符串是由字符 "0 "和 "1 "组成的字符串。

您的任务是确定最大可能的数字 $k$ ，使得长度为 $k$ 的字符串 $a$ 的前缀是字符串 $b$ 的子序列。

如果 $a$ 可以从 $b$ 中删除几个(可能是零个或全部)元素，那么序列 $a$ 就是序列 $b$ 的子序列。

思路：

按顺序枚举 $a$ 的每个字符，找到 $b$ 串中可以与它对应的字符，对应起来。模拟一遍这个过程即可知道 $a$ 最多能对应到长度为几的前缀了。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;int T,n,m;
string a,b;int main(){cin>>T;while(T--){cin>>n>>m>>a>>b;a=" "+a;b=" "+b;int i=0,j=0;while(i+1<=n && j+1<=m){while(j+1<=m && a[i+1]!=b[j+1])j++;if(i+1<=n && j+1<=m)i++,j++;}cout<<i<<endl;}return 0;
}

---

C. Assembly via Remainders

题意：

给你一个数组 $x_2,x_3,\dots ,x_n$ 。你的任务是找出任意一个数组 $a_1,\dots ,a_n$ , 其中：

• $1\le a_i\le 10^9$ 代表所有的 $1\le i\le n$ 。
• $x_i=a_i\mathrm{mod}{a}_{i-1}$ 代表所有 $2\le i\le n$ 。

这里的 $c\mathrm{mod}d$ 表示整数 $c$ 除以整数 $d$ 的余数。例如 $5\mathrm{mod}2=1$ , $72\mathrm{mod}3=0$ , $143\mathrm{mod}14=3$ 。

注意，如果有一个以上的 $a$ 满足该语句的要求，你可以找到任何一个。

思路：

对 $x_i=a_i\mathrm{mod}{a}_{i-1}$，如果 $a_{i-1}$ 是个很大的数的话，那么 $a_i$ 的取值就很比较少，为了让 $a_i$ 也保持一个很大的状态，方便后面的数来用，那么我们可以令 $a_i=a_{i-1}+x_i$，因为 $a_{i-1}$ 很大，比 $x_i$ 大得多，所以我们这样可以保证模出来就是 $x_i$。

每个位置都是这样，就可以从第一个数直接算出后面 $n$ 个数是什么了，不过因为规定 $a_i\le 10^9$，所以我们不好确定第一个数填什么，我们可以反过来想，直接规定 $a_n=10^9$，然后往前推就行了。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=505;int T,n;
int a[maxn],x[maxn];int main(){cin>>T;while(T--){cin>>n;for(int i=2;i<=n;i++)cin>>x[i];a[n]=1e9;for(int i=n-1;i>=1;i--){a[i]=a[i+1]-x[i+1];}for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];}return 0;
}

---

D. Permutation Game

题意：

Bodya 和 Sasha 发现了一个排列 $p_1,\dots ,p_n$ 和一个数组 $a_1,\dots ,a_n$ 。他们决定玩一个著名的 “排列游戏”。

长度为 $n$ 的排列是由 $n$ 个不同的整数组成的数组，这些整数从 $1$ 到 $n$ 按任意顺序排列。例如， $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列( $2$ 在数组中出现了两次)， $[1,3,4]$ 也不是一个排列( $n=3$ ，但数组中有 $4$ )。

它们都在排列中选择了一个起始位置。

对局持续了 $k$ 个回合。棋手同时下棋。在每个回合中，每个棋手都会发生两件事：

• 如果棋手当前的位置是 $x$ ，他的得分就会增加 $a_x$ 。
• 然后棋手要么停留在当前位置 $x$ ，要么从 $x$ 移动到 $p_x$ 。

在整整 $k$ 个回合后，得分较高的一方即为获胜者。

已知博迪娅的起始位置 $P_B$ 和萨沙的起始位置 $P_S$ ，如果双方都想获胜，请判断谁会赢得对局。

思路：

如果我们在 $i$，选择移动的话，就会移动到 $a_i$ 位置，我们可以看作是一条 $i\to a_i$ 的单向边，我们停留在第 $i$ 个位置，就相当于停留在编号为 $i$ 的点上。如果 $a$ 数组是一个排列的话，这个图就会呈现出一些非常美妙的性质。

因为每个点都会作为出发点一次，所以每个点的出度为 $1$，因为 $a$ 数组是一个排列，因此每个点的入度也为 $1$，因此这个图只存在环（自环也看作是一个环），$n$ 个点就组成了若干的互不干扰的若干个环，每个点 在且仅在 一个环上。

在这个题里，我们想要分数尽可能大，那么我们可以选择向着环上的下一个位置进发，也可以停留在这个位置，下一回合继续拿这里的分。显然我们想要停在分数尽可能大的点上，不过一路走过去也可能还不如一直在原点呆着吃分。

但是我们如果决定了留在某个点上，分数的计算是相当简单的，我们只需要用一路上的分数加上剩余回合数乘上这个点的分数即可。因此我们可以一路走完这个环上的所有点，算出停留在环上任意一点的分数，保留最大值即可。（不过不知道的话也不影响做出来这题，无非是改成向下走 $n$ 次而已）

两个人都这样算一下，然后比较即可。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2e5+5;
typedef long long ll;int T,n,k,p1,p2;
int p[maxn],a[maxn];int main(){cin>>T;while(T--){cin>>n>>k>>p1>>p2;for(int i=1;i<=n;i++)cin>>p[i];for(int i=1;i<=n;i++)cin>>a[i];ll m1=1ll*a[p1]*k,m2=1ll*a[p2]*k;ll tmp=a[p1],tk=k-1;for(int id=p[p1];id!=p1 && tk;id=p[id]){m1=max(m1,1ll*a[id]*tk+tmp);tmp+=a[id];tk--;}tmp=a[p2];tk=k-1;for(int id=p[p2];id!=p2 && tk;id=p[id]){m2=max(m2,1ll*a[id]*tk+tmp);tmp+=a[id];tk--;}puts((m1==m2)?"Draw":((m1>m2)?"Bodya":"Sasha"));}return 0;
}

---

E. Cells Arrangement

题意：

给你一个整数 $n$ 。您在网格 $n\times n$ 中选择了 $n$ 单元格 $(x_1,y_1),(x_2,y_2),\dots ,(x_n,y_n)$ ，其中 $1\le x_i\le n$ 和 $1\le y_i\le n$ 。

让 $\mathcal{H}$ 成为任意一对单元格之间不同的曼哈顿距离集合。你的任务是最大化 $\mathcal{H}$ 的大小。注释中给出了集合及其构造的例子。

如果存在不止一个解，你可以输出任意一个。

单元格 $(x_1,y_1)$ 和 $(x_2,y_2)$ 之间的曼哈顿距离等于 $|x_1-x_2|+|y_1-y_2|$ 。

思路：

直接说构造方法，第一个点放在 $(1,1)$，第二个点放在 $(2,1)$，之后第 $i$ 个点放在 $(i,i)$。

为什么这样凑得到的不同数的个数就是最大的？因为最多有 $0\sim 2n-2$ 共 $2n-1$ 个不同的数（两个点最大的曼哈顿距离就是一个角到另一个角），因此只要包括了所有的 $2n-1$ 个数就是最大的，上面这个构造方法就可以。

前两个点可以保证凑出 $0,1$，然后后面 $n-2$ 个点相邻点之间曼哈顿距离差 $2$，所以相邻的点可以得到 $2$，中间隔一个点就能得到 $4$，类推可以得到 $6,8,\dots ,2n-6$，点 $(1,1)$ 和 $(n-1,n-1),(n,n)$ 可以得到 $2n-4,2n-2$，这样就凑出了所有的偶数。$(2,1)$ 和 $(3,3)$ 曼哈顿距离差 $3$，之后每隔一个点距离加 $2$，就可以得到 $3,5,7,\dots ,2n-3$，这样就凑出了所有奇数。因此这种凑法可以凑出 $0\sim 2n-2$ 中的所有数。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
#define pii pair<int,int>
using namespace std;
const int maxn=1e3+5;int T,n;
pii pos[maxn]={{0,0},{1,1},{1,2},{3,3}};int main(){for(int i=4;i<=1e3;i++)pos[i]=pii(i,i);cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++){auto [x,y]=pos[i];cout<<x<<" "<<y<<endl;}cout<<endl;}return 0;
}

---

F. Equal XOR Segments

题意：

如果可以将数组分成 $k>1$ 部分，使得每部分的值的 bitwise XOR 都相等，那么我们就可以称这个数组为 $x_1,\dots ,x_m$ 有意思的数组。

更具体地说，你必须将数组 $x$ 分成 $k$ 个连续的部分， $x$ 中的每个元素都必须准确地属于 $1$ 个部分。设 $y_1,\dots ,y_k$ 分别是各部分元素的 XOR。那么 $y_1=y_2=\cdots =y_k$ 必须满足。

例如，如果是 $x=[1,1,2,3,0]$ ，可以将其拆分如下： $[1],[1],[2,3,0]$ .事实上是 $1=1=2\oplus 3\oplus 0$ 。

给你一个数组 $a_1,\dots ,a_n$ 。你的任务是回答 $q$ 个查询：

• 对于固定的 $l$ , $r$ , 判断子数组 $a_l,a_{l+1},\dots ,a_r$ 是否有趣。

思路：

因为我们要算区间异或和，所以我们先预处理出 $a$ 数组的前缀异或和 $s$ 数组，这样 $a_l\oplus a_{l+1}\oplus \cdots \oplus a_r=s_r\oplus s_{l-1}$。

上面 $y_1=y_2=\cdots =y_k$ 的话，就说明 $y_1\oplus y_2=0$ 同理后面两个两个抵消，如果 $k$ 是奇数的话，那么 $y_1=y_2=\cdots =y_k=y_1\oplus y_2\oplus \cdots \oplus y_k=s_n$ 也就是说所有的 $y$ 值都等于 $a$ 数组所有数的异或和。同理 $k$ 是偶数的时候可以推出来 $y_1\oplus y_2\oplus \cdots \oplus y_k=s_n=0$。

因为划分分区是我们决定的，因此我们可以尽可能少的划分分区。可以发现，如果存在可行的划分方案，我们一定可以划分出两个或三个分区。因为 $y$ 是相同的，所以如果存在一个划分方案，我们可以两个相邻分区合并一下，也就是异或一下区间异或和变成 $0$，然后合并到相邻分区即可，最后一定会剩下两个或三个分区。

• 当 $s_n=0$ 时，我们随便划分就行了，两个分区即可。划出一个分区，另一半的异或值一定等于它（因为总异或值为 $0$）。

• 当 $s_n\ne 0$ 时，我们就需要划出三个分区，因为每个分区异或和相同，且等于总的异或值 $s_n$，因此第一个分区的异或和为 $s_n$，前两个分区异或和就是 $0$。

第一种情况很简单，第二种情况，我们假设左右端点是 $l,r$，三个分区分界点分别是 $x,y$（$l\sim x$ 是第一个分区，$x+1\sim y$ 是第二个，$y+1\sim r$ 是第三个），满足情况的 $x,y$ 就需要 $s_x\oplus s_{l-1}=s_n,s_y\oplus s_{l-1}=0$，即 $s_x=s_n\oplus s_{l-1},s_y=s_{l-1}$ 且 $l<x<y<r$。

如何查找 $l\sim r$ 中有没有等于上面值的位置呢？我们可以对每个数开一个桶，按顺序存储所有等于这个数的位置，然后要找的时候直接去对应桶里二分查找即可，因为值域很大，桶我们用 $map$。

code：

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std; 
const int maxn=2e5+5;int T,n,q;
int a[maxn];
map<int,vector<int> > val;int main(){cin>>T;while(T--){cin>>n>>q;val.clear();val[0].push_back(0);for(int i=1;i<=n;i++){cin>>a[i];a[i]^=a[i-1];val[a[i]].push_back(i);}for(int i=1,l,r;i<=q;i++){cin>>l>>r;l--;if(a[r]==a[l])puts("YES");else {auto it1=lower_bound(val[a[r]].begin(),val[a[r]].end(),l+1),it2=upper_bound(val[a[l]].begin(),val[a[l]].end(),r-1);if(it1==val[a[r]].end() || it2==val[a[l]].begin()){puts("NO");continue;}else it2--;int x=*it1,y=*it2;if(l<x && x<y && y<r)puts("YES");else puts("NO");}}}return 0;
}

---

G1. Division + LCP (easy version)

题意：

这是问题的简单版本。在此版本中 $l=r$

给你一个字符串 $s$ 。对于固定的 $k$ ，考虑将 $s$ 恰好分成 $k$ 个连续的子串 $w_1,\dots ,w_k$ 。假设 $f_k$ 是所有分割中最大的 $LCP(w_1,\dots ,w_k)$ 。

$LCP(w_1,\dots ,w_m)$ 是字符串 $w_1,\dots ,w_m$ 的最长公共前缀的长度。

例如，如果 $s=abababcab$ 和 $k=4$ ，可能的除法是 $abababcab$ 。由于 $ab$ 是这四个字符串的最长公共前缀，因此 $LCP(ab,ab,abc,ab)$ 就是 $2$ 。请注意，每个子串都由一段连续的字符组成，每个字符都属于个子串。

您的任务是找出 $f_l,f_{l+1},\dots ,f_r$ 。在本版本中为 $l=r$。

思路：

思路看的这个大佬的

首先 $w_1$ 一定是这个串 $s$ 的前缀，我们要 $LCP$ 有 $x$ 长度的公共前缀，首先每个 $w$ 串都要与串 $s$ 至少有 $x$ 长度的公共前缀。因此我们要算出从每个位置 $i$ 开始的子串与这个串的最长公共前缀。这个东西就是拓展kmp，也叫Z算法（讲解可以看这个，从1小时3分开始讲），我们 $O(n)$ 跑一遍拓展kmp，就得到了从每个位置 $i$ 开始的子串与这个串的最长公共前缀长度 $z[i]$。

直接算 $LCP$ 不好算，但是我们验证 $LCP$ 是好验证的。上面说了我们要 $LCP$ 有 $x$ 长度的公共前缀，每个 $w$ 串都要与串 $s$ 有 $x$ 长度的公共前缀，因此选做起点的那个位置 $i$ 的 $z[i]$ 值需要大于等于 $x$ 即可，然后我们把以这个后面 $i\sim i+x-1$ 个位置的字符就划给了一个 $w$ 串，一个 $w$ 串就凑出来了。之后我们从 $i+x$ 继续向后找，假如说下一个 $w$ 串从 $j$ 开始，中间 $i+x\sim j-1$ 的字符我们就可以直接划给前面的 $w$ 串。我们这样找一遍就能找到最多的 $w$ 串。

举个例子，题目上 $s=abababcab$ 和 $LCP=2$，我们可以算出 $z$ 数组如下：

s: a b a b a b c a b
z: 9 0 4 0 2 0 0 2 0

首先从第 $0$ 个位置开始找，$z[0]=9\ge 2$，因此前 $LCP=2$ 个字符划给 $w_1$。再从第 $0+LCP=2$ 个位置开始找，$z[2]=4\ge 2$，因此接下来的 $2$ 个字符划给 $w_2$。再从第 $4$ 个位置开始找， $z[4]=2\ge 2$，因此接下来的 $2$ 个字符划给 $w_3$。再从第 $6$ 个位置开始找， $z[6]=0<2,z[7]=2\ge 2$，因此第六个字符划给前面的 $w_3$，接下来第 $7,8$ 个字符划给 $w_4$。

因为 $LCP$ 越小，满足条件产生的 $w$ 串的个数 $k$ 就越多，也就是说 $LCP$ 是单调的，因此我们可以二分来找这个 $LCP$，时间复杂度就是 $O(n\log n)$ 了。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=2e5+5;int T,n,L,R;
int z[maxn];
string s;void init(){z[0]=n;for(int i=1,id=0,r=0,len;i<n;i++){len=(i<r)?min(z[i-id],r-i):0;while(i+len<n && s[i+len]==s[len])len++;if(i+len>r){r=i+len;id=i;}z[i]=len;}
}int main(){cin>>T;while(T--){cin>>n>>L>>R>>s;init();
//		for(int i=0;i<n;i++)cout<<z[i]<<" \n"[i==n-1];int l=0,r=n,mid;while(l<r){mid=(l+r+1)>>1;int k=0;for(int i=0;i<n;){if(z[i]>=mid)k++,i+=mid;else i++;}if(k>=L)l=mid;else r=mid-1;}cout<<l<<endl;}return 0;
}

---

G2. Division + LCP (hard version)

题意：

这是问题的困难版本。在此版本中 $l\le r$

给你一个字符串 $s$ 。对于固定的 $k$ ，考虑将 $s$ 恰好分成 $k$ 个连续的子串 $w_1,\dots ,w_k$ 。假设 $f_k$ 是所有分割中最大的 $LCP(w_1,\dots ,w_k)$ 。

$LCP(w_1,\dots ,w_m)$ 是字符串 $w_1,\dots ,w_m$ 的最长公共前缀的长度。

例如，如果 $s=abababcab$ 和 $k=4$ ，可能的除法是 $abababcab$ 。由于 $ab$ 是这四个字符串的最长公共前缀，因此 $LCP(ab,ab,abc,ab)$ 就是 $2$ 。请注意，每个子串都由一段连续的字符组成，每个字符都属于个子串。

您的任务是找出 $f_l,f_{l+1},\dots ,f_r$ 。

思路1（根号分治）：

最坏情况下就是 $l=1,r=n$，我们需要算出所有 $f$ 值。上面方法算一个 $f$ 值就要花 $n\log n$ 的时间，不可能大量来用。发现当 $i$ 比较大的时候，后面不同的 $f$ 值就会变的非常稀疏。仔细一想其实也比较好证明为什么，因为划分了 $i$ 个串，每个串最多分到 $n/i$ 个字符，更别说相同的前缀长度了。

如果 $i\le \sqrt{n}$，那么 $i$ 的取值 $\sqrt{n}$ 个，不同的 $f$ 取值也最多只有 $\sqrt{n}$ 个。如果 $i>\sqrt{n}$，那么每个串最多分到 $\sqrt{n}$ 个字符，前缀长度也一定少于 $\sqrt{n}$，因此取值最多只有 $\sqrt{n}$ 个，也就是 $f$ 的取值只有 $\sqrt{n}$ 个。综上，$f$ 的取值最多只有 $2\sqrt{n}$ 个。

感觉很可以根号分治，前面 $\sqrt{n}$ 个 $f$ 我们直接暴力来算也无所谓，时间复杂度 $O(n\sqrt{n}\log n)$，主要是后面的 $f$ 如何算。

---

发现验证一个 $LCP$ 的时候，可以算出它最多可以划分出几个 $w$ 串，又因为 $LCP$ 是单调的，所以如果一个 $LCP$ 如果可以划分出若干个 $w$ 串，那么更小的 $LCP$ 一定至少也可以划分出这些 $w$ 串，划分更少 $w$ 串时，前缀长度一定大于等于这个值。

$f_i$ 其实就是划分 $i$ 个串时的 $LCP$，如果我们验证一个 $LCP=x$ 得到最多可以划分出 $k$ 个 $w$ 串，那么相当于 $f_k=x$。$w$ 串个数越少，能得到的前缀长度就越大，也就是 $f_{1\sim k-1}\ge x$，若 $f_{k^{\prime }}=x+1$，那么中间的 $f$ 就能知道了，是 $f_{k^{\prime }+1\sim k}=x$。

对块数 $i$ 大于等于 $\sqrt{n}$ 的划分，它们的最大前缀长度是 $\le \sqrt{n}$ 的，所以我们对每个 $\le \sqrt{n}$ 的前缀长度算一下最多可以划分多少个串，然后放进 $f$ 数组中。最后跑一下后缀最大值，这样 $i\ge \sqrt{n}$ 直接查 $f$ 数组即可，时间复杂度 $O(n)$。

code1：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=2e5+5;int T,n,L,R;
string s;int z[maxn];
void init(){z[0]=n;for(int i=1,len,id,r=0;i<n;i++){len=(r>i)?min(z[i-id],r-i):0;while(i+len<n && s[i+len]==s[len])len++;if(i+len>r){r=i+len;id=i;}z[i]=len;}
}
int div(int x){//前缀长度为x时能分出的最多块数 int cnt=0;for(int i=0;i<n;i++){if(z[i]>=x){i=i+x-1;cnt++;}}return cnt;
}
int calc(int k){//二分计算分成k块的最大前缀长度 int l=0,r=n,mid;while(l<r){mid=(l+r+1)>>1;if(div(mid)>=k)l=mid;else r=mid-1;}return l;
}int main(){
//	cin.tie(0)->sync_with_stdio(false);cin>>T;while(T--){cin>>n>>L>>R>>s;vector<int> f(n+2,0);
//		s=" "+s;init();
//		for(int i=0;i<n;i++)cout<<z[i]<<" \n"[i==n-1];int t=min(450,n);//分块阈值//分的块数超出k，预处理 //分的块数小于k，直接算for(int i=1;i<=n/t;i++)//枚举前缀长度 分t块 前缀长度最多n/t f[div(i)]=i; for(int i=n;i>=1;i--)f[i]=max(f[i+1],f[i]);for(int i=L;i<=R;i++){if(i>=t)cout<<f[i];else cout<<calc(i);cout<<" \n"[i==R];}}return 0;
}

---

思路2（分治，剪枝）：

还是上面的结论，$f$ 的取值最多只有 $2\sqrt{n}$ 个，而且 $f$ 的值还是单调（递减）的。所以如果我们算出来某个 $f_l=x$，$f_r=x$，那么我们直接就可以确定 $f_{l\sim r}=x$。

因此我们直接对这个区间进行分治，比如对 $1\sim n$ 的区间，它的取值范围就是 $f_n\sim f_1$，我们把它拆成两段 $1\sim mid,mid+1\sim n$，取值范围分别变成了 $f_{mid}\sim f_1,f_n\sim f_{mid+1}$，我们一直拆下去，遇到取值只能是一个数的区间就可以直接返回了。

剪枝前就是 $n^2\log n$，剪枝后时间复杂度比较玄学，说一下我的见解。对一个取值，我们能找到它的边界最多需要 $\log n$ 次计算，因为最多有 $2\sqrt{n}$ 个取值，因此需要 $2\sqrt{n}\log n$ 次计算，总的计算次数为 $2n\sqrt{n}{\log }^{2}n$，虽然看起来很会 $T$ 的样子，但是实际上跑的还是蛮快的，而且写法简单。（希望只是我复杂度算假了，如果有会算的可以评论一下，感谢）

code2：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=2e5+5;int T,n,L,R;
string s;int z[maxn];
void init(){z[0]=n;for(int i=1,len,id,r=0;i<n;i++){len=(r>i)?min(z[i-id],r-i):0;while(i+len<n && s[i+len]==s[len])len++;if(i+len>r){r=i+len;id=i;}z[i]=len;}
}
int div(int x){//前缀长度为x时能分出的最多块数 int cnt=0;for(int i=0;i<n;i++){if(z[i]>=x){i=i+x-1;cnt++;}}return cnt;
}
int calc(int k){//二分计算分成k块的最大前缀长度 int l=0,r=n,mid;while(l<r){mid=(l+r+1)>>1;if(div(mid)>=k)l=mid;else r=mid-1;}return l;
}
int ans[maxn];
void segement(int l,int r,int x,int y){if(x==y){for(int i=l;i<=r;i++)ans[i]=x;return;}int mid=(l+r)>>1;segement(l,mid,x,calc(mid));segement(mid+1,r,calc(mid+1),y);return;
}int main(){
//	cin.tie(0)->sync_with_stdio(false);cin>>T;while(T--){cin>>n>>L>>R>>s;init();segement(L,R,calc(L),calc(R));for(int i=L;i<=R;i++)cout<<ans[i]<<" \n"[i==R];}return 0;
}

---

思路3：

我们仔细看一下对一个 $LCP=x$ 算分的块数的过程。就是先找到最近的 $\ge x$ 的 $z$ 值，然后再从这个位置向后 $x$ 位，再找下一个满足的 $z$ 值。我们一位一位向后找很没效率，那么我们处理出所有 $\ge x$ 的 $z$ 值的下标，在里面二分地依次找不就行了。

这样我们原本 $O(n)$ 找一遍就变成了 $O({\log }^{2}n)$ 找一遍，找到后还是和思路1的预处理的方法一样。如果结果是 $k$，就得到了 $f_k=x$。$LCP$ 从 $n$ 到 $1$ 枚举一遍，算出结果并记录到 $f$ 数组上，最后再跑个后缀最大值即可。

不过我们不可能开 $n$ 个桶，用桶装所有 $\ge x$ 的 $z$ 值的下标，最坏是 $n^2$ 的。我们用桶装 $=x$ 的 $z$ 值的下标，然后从 $n$ 到 $1$ 按顺序访问，用一个 $set$ 存储访问过的下标，这样我们依次访问，在访问到第 $x$ 个桶的时候，$set$ 中正好就存储了所有 $\ge x$ 的 $z$ 值的下标，一遍访问一边算即可。

code3：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
const int maxn=2e5+5;int T,n,L,R;
string s;int z[maxn];
vector<int> a[maxn];
void init(){z[0]=n;a[z[0]].push_back(0);for(int i=1,len,id,r=0;i<n;i++){len=(r>i)?min(z[i-id],r-i):0;while(i+len<n && s[i+len]==s[len])len++;if(i+len>r){r=i+len;id=i;}z[i]=len;a[z[i]].push_back(i);}
}
int div(int x){//前缀长度为x时能分出的最多块数 int cnt=0;for(int i=0;i<n;i++){if(z[i]>=x){i=i+x-1;cnt++;}}return cnt;
}
int ans[maxn];int main(){
//	cin.tie(0)->sync_with_stdio(false);cin>>T;while(T--){cin>>n>>L>>R>>s;for(int i=1;i<=n;i++)a[i].clear(),ans[i]=0;init();set<int> S;for(int i=n;i>=1;i--){for(auto idx:a[i])S.insert(idx);int cnt=0;for(int j=0,nxt;j<n;){auto it=S.lower_bound(j);if(it==S.end())break;j=*it+i;cnt++;}ans[cnt]=max(ans[cnt],i);}for(int i=n-1;i>=1;i--)ans[i]=max(ans[i+1],ans[i]);for(int i=L;i<=R;i++)cout<<ans[i]<<" \n"[i==R];}return 0;
}

这篇关于Codeforces Round 943 (Div. 3)（A,B,C,D,E,F,G1,G2）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---