2023年莆田市C++专项第三期学员友谊赛题解
本次比赛共有 $80$ 人提交代码，最高分 $375$，$200$ 分及以上 $15$ 人。
恭喜俞伯洋同学获得本次比赛第一名！
| | 提交数 | 通过数 | 通过率 | 与出题组预期相比 |
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |
| A | $140$ | $16$ | $11.43\%$ | 略低于预期 |
| B | $131$ | $4$ | $3.05\%$ | 符合预期 |
| C | $109$ | $0$ | $0\%$ | 远低于预期 |
| D | $139$ | $4$ | $2.88\%$ | 符合预期 |
# 比赛出锅：
- C 数据强度不够，导致有人通过奇葩骗分算法得到 $40$ 分。
- D 题样例 #3 有误。
在这里出题组向大家道歉。
下面是本次比赛的题解。
# A
出题&题解：by tyx。
判断单曲循环很简单，难点在于后面两种模式。
要想知道这个歌单是什么播放模式，就必须先找出 $k$。我们可以依次枚举 $k$ 的值，但很显然这种算法的时间复杂度是平方级别，只能得到 50pts。
想要 AC，就必须使用 $O(n)$ 做法。经过推理，我们可以证明，如果该歌单是列表循环模式，$k$ 的值是唯一的。证明如下：
- 假设存在一个 $k$ 满足列表循环的条件。
- 对于每一个小于 $k$ 的正整数 $k'$，由于 $a_1=a_{k+1}$ 且 $a_1$ 到 $a_k$ 的所有数均不相同，所以 $a_1$ 和 $a_{k'+1}$ 一定不等（因为 $k'<k$，所以 $k'+1 \le k$）。因此 $k'$ 不满足条件。
- 对于每一个大于 $k$ 的正整数 $k''$，由于 $a_1=a_{k+1}$ 且 $a_1$ 到 $a_k$ 的所有数均不相同，所以 $a_1$ 至 $a_{k''+1}$ 中一定至少有两个数相等（因为 $k''>k$，所以 $k+1 \le k''$）。因此 $k''$ 不满足条件。
- 所以，$k$ 的值唯一。
因此我们在枚举时，只要找到第一个满足 $a_1$ 到 $a_i$ 全部不等且 $a_1=a_{i+1}$ 的数，就可以终止枚举了。此时我们再判断 $i$ 是否满足题目条件即可，时间复杂度 $O(n)$。
最后还有一个要注意的点，就是 $a_1$ 到 $a_n$ 全部不等时，我们可以选择 $k=n$，因此这个列表的播放方式是列表循环。
## AC code：
```cpp
#include<bits/stdc++.h>
using namespace std;
int T,n,t[200005],k;
bool book[200005];
int main()
{
cin>>T;
while(T--)
{
k=0;
cin>>n;
for(int i=1;i<=n;i++)
cin>>t[i];
for(int i=1;i<=n&&book[t[i]]==0;i++)
{
book[t[i]]=1;
k++;
}
for(int i=1;i<=k;i++)
{
for(int j=1;i+j*k<=n;j++)
{
if(t[i]!=t[i+j*k])
{
cout<<"3\n";
goto end;
}
}
}
if(k==1)
cout<<"1\n";
else
cout<<"2\n";
end:1;
for(int i=1;i<=n;i++)
book[i]=0;
}
return 0;
}
```
# B
出题&题解：by hzf。
先分析一下这道题。
先想一想朴素算法，从大到小枚举 $b$，$O(n)$ 判断，总复杂度为 $O(nm)$，预计 50pts。
接下来思考正解。
假设 $b$ 与 $a$ 中的每个数都互质，那么对于每个 $a_i=c_{i_1}^{d_{i_1}}c_{i_2}^{d_{i_2}}...c_{i_k}^{d_{i_k}}$（其中 $c_{i_j}$ 为 $a_i$ 的质因数），都有 $b$ 不为 $c_{i_j}$ 的倍数，那么只需要标记所有 $c_{i_j}$ 的倍数即可。
在标记完后，我们从 $m$ 到 $1$ 枚举 $b$ 的值，如果未被标记便输出 $b$（这一部分的时间复杂度为 $O(m)$）。
然后就是求出所有 $c_{i_j}$。
### 算法 1：
将每个 $a_i$ 分解质因数，然后依次标记，这样的最劣复杂度大约是 $O(nm\sqrt{m})$。
### 算法 2:
在**算法 1** 的基础上优化一下，存储所有的 $c_{i_j}$，那么时间复杂度就是 $O(n\sqrt m)$。
### 算法 3:
我们能否枚举 $c_{i_j}$ 呢？
答案是可以的，在跑质数筛的同时，若 $i$ 为质数，则判断 $ij$ 是否为 $a$ 中任意一个数（其中 $j$ 为正整数且 $i×j \le m$），如果是则标记 $i$ 的所有倍数。该算法的时间复杂度为 $O(m)$。
因此，我们便解决了这道题。
## AC code：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
bool book[5000005],vis[5000005],pd[5000005];
main(){
cin>>n>>m;
while(n--){int a;cin>>a,vis[a]=true;}
for(int i=2;i<=m;++i)if(book[i]==false){
book[i]=true;
for(int j=1;i*j<=m;++j)if(vis[i*j]==true){
for(int v=1;i*v<=m;++v)pd[i*v]=true;
break;
}
for(int j=1;i*j<=m;++j)book[i*j]=true;
}
for(int i=m;i>=1;--i)if(pd[i]==false){cout<<i;return 0;}
return 0;
}
```
# C
出题：by tyx&hzf。
题解：by hzf。
先简要分析：
这题显然是一道 $dp$ 题，我们可以用 $f_{i,j,k}$ 来存储三种操作的数量，即使用 $i$ 次与，$j$ 次或，$k$ 次异或。
注意，此处有一错误做法，就是用 $f_{i,j,k}$ 来存储最优状态，以 $(7 \oplus 8) > (8 \oplus 8)$ 为例解释。
那么如何存储呢？
注意，$a_i \le 2^8-1$，所以所有数操作后的结果必然小于 $64$，由于 $x,y,z \le 100$，因此可以定义一个四维 `bool` 数组 $f$，$f_{a,i,j,k}=1$，表示使用 $i$ 次与，$j$ 次或，$k$ 次异或后可以得到 $a$ 。
那么该如何转移呢？
当 $f_{a,i,j,k}=1$ 时：
- $f_{a \land A_{i+j+k+1},i+1,j,k}=1$
- $f_{a \lor A_{i+j+k+1},i,j+1,k}=1$
- $f_{a \oplus A_{i+j+k+1},i,j,k+1}=1$
其中 $f_{0,0,0,0}=1$ 为动态规划边界。
最后，找到最大的满足 $f_{a,x,y,z}=1$ 的 $a$ 并输出即可。
## AC code:
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,x,y,z,a;
bool f[64][105][105][105];
int main(){
cin>>n>>x>>y>>z>>a,f[a][0][0][0]=true;
for(int i=2;i<=n;++i){
cin>>a;
for(int j=0;j<i;++j)for(int v=0;j+v<i;++v){
int k=i-1-j-v;
if(k<=z&&j<=x&&v<=y)for(int b=0;b<=63;++b){
if(j>0&&f[b][j-1][v][k])f[b&a][j][v][k]=true;
if(v>0&&f[b][j][v-1][k])f[b|a][j][v][k]=true;
if(k>0&&f[b][j][v][k-1])f[b^a][j][v][k]=true;
}
}
}
for(int i=63;i>=0;--i)if(f[i][x][y][z]){cout<<i;return 0;}
return 0;
}
```
# D
出题：by hzf。
题解：by tyx。
此题初看似乎有些难以入手，但其实核心思路并不难。
首先这个 D 类串中每个字符的选取都是有范围的，比如在 `abcde` 这个字符串中找到一个长度为 $2$ 的 D 类串，那么这个 D 类串的第一位肯定不会是 `e`，第二位肯定不会是 `a`。可以证明，对于 D 类串的第 $i$ 个字符，其选取范围是 $s_{i-1}$ 至 $s_{n-k+i-1}$，这里 $s$ 的下标从 $0$ 开始。
由于我们要选择的 D 类串要满足字典序最大，所以根据贪心策略，D 类串的第 $1$ 个字符肯定为 $s_0$ 到 $s_{n-k}$ 中最大值，如果有最大值肯定选择下标最小的一个，正确性请读者自己证明。
找到 D 类串的第 $1$ 个字符后，由于第 $2$ 个字符在第 $1$ 个字符之后，所以我们从 D 类串第 $1$ 个字符在 $s$ 中的下标开始枚举。接下来一直枚举到 第 $k$ 个字符。
此方法最劣时间复杂度 $O(kn)$，可以得到 70pts。如果加上特判和卡常可以得到 80pts。
## 70pts code：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,k,sum,maxn;
string s;
int main()
{
cin>>n>>k>>s;
if(k==0)
return 0;
for(int i=1;i<=k;i++)
{
maxn=sum;
sum++;
for(int j=sum-1;j<n-k+i;j++)
{
if(s[j]>s[maxn])
{
maxn=j;
sum=j+1;
}
}
cout<<s[maxn];
}
return 0;
}
```
思考正解。
上面的代码为什么会 TLE？例如在 `yxwvwhfreuowregohrwoieigithigrigu` 这个字符串中找出一个长度为 $2$ 的 D 类串，其实我们在 $s_0$ 就已经找到 D 类串的第一个字符了，但是我们要枚举到倒数第二位的 `g`，而且在找 D 类串的第二个字符时重新从 $s_1$ 开始枚举，这样浪费了很多时间。
那应该怎么办呢？
假如我们给定了一个字符串 `ppppppphzfakioi`，在其中找出一个长度为 $7$ 的 D 类串。此时我们可以发现：由于 `h` 的后面有一个 `z`，所以我们在所有选取范围包含 `z` 的 D 类串中的字符时，肯定不会选到 `h`（因为 `h` 比 `z` 小且比 `z` 先失效）。因此当 `z` 进入选取范围时，我们就不用再考虑是否要选择 `h` 了，这和单调队列的性质很相似。因此此题可以使用单调队列解题，当一个字符入队时弹出所有小于它的字符。
## AC code：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,k;
string s;
deque<int>q;
int main()
{
cin>>n>>k>>s;
for(int i=0;i<n;i++)
{
while(!q.empty()&&s[q.back()]<s[i])
q.pop_back();
q.emplace_back(i);
if(i>n-k-1)
{
cout<<s[q.front()];
q.pop_front();
}
}
return 0;
}
```
此题也可以使用 ST 表解决，代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,k,Max[200005][25];
string s;
inline int fin(int l,int r){
int lg=std::log2(r-l+1);
if(s[Max[l][lg]]>=s[Max[r-(1<<lg)+1][lg]])return Max[l][lg];
return Max[r-(1<<lg)+1][lg];
}
int main(){
cin>>n>>k>>s,s=' '+s;
for(int i=1;i<=n;++i)Max[i][0]=i;
for(int i=1;i<=20;++i)for(int j=1;j+(1<<i)-1<=n;++j){
if(s[Max[j][i-1]]>=s[Max[j+(1<<(i-1))][i-1]])Max[j][i]=Max[j][i-1];
else Max[j][i]=Max[j+(1<<(i-1))][i-1];
}
int now=1;
for(int i=1;i<=k;++i)now=fin(now,n-k+i),cout<<s[now++];
return 0;
}
```
当然也可以使用线段树等数据结构，这里不放代码，留给读者自行思考。
