YC2023:英才专题测试-数据结构1 题解
<script type="text/javascript" src="http://c328740.r40.cf1.rackcdn.com/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>### 题目颜色为洛谷难度
# [$\color{#F39C11}{A}$](https://vjudge.csgrandeur.cn/contest/576896#problem/A)
[洛谷上](https://www.luogu.com.cn/problem/P2952)
## 思路
容易发现这是一道双端队列的模板题，所以直接模拟就好。
我使用的是手工队列（忘了 STL 的双端队列怎么写了，而且估计手写比STL快很多）。
## AC code
```cpp
#include<bits/stdc++.h>
using namespace std;
char ch[20],ch1[20];
int n,q[200005],he=100000,ta=100000,a,cnt;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%s%s",ch,ch1);
if(ch[0]=='A')
{
if(ch1[0]=='L') q[he--]=++cnt;
else q[++ta]=++cnt;
}
else
{
scanf("%d",&a);
if(ch1[0]=='L') he+=a;
else ta-=a;
}
}
for(int i=he+1;i<=ta;++i) printf("%d\n",q[i]);
return 0;
}
```
# [$\color{#3498DB}{B}$](https://vjudge.csgrandeur.cn/contest/576896#problem/B)
[洛谷上](https://www.luogu.com.cn/problem/CF1176C)
## 思路
定义一个数组能分为若干份，每一份都是 $4,8,15,16,23,42$ 的前缀的数组是 **半优秀** 的。
容易发现只有满足以下性质的数组才是 **半优秀**：
对于每一个 $i(1\leq i\leq n)$，统计 $6$ 个数字的数量，较大的数字的数量一定少于等于较小的数字的数量。
那么，如果一个数的出现，使目前的数组不是 **半优秀** 的，那么它一定会使整个数组不是 **优秀** 的，所以需要删去。
那么，最后剩下的数的数量就是 $6\times 42 \text{的数量}$。
只需要用 $n$ 减去剩下的数的数量，就可以得出答案。
## AC code
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[500005],num[7];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
{
int k=(a[i]==4)?1:(a[i]==8)?2:(a[i]==15)?3:(a[i]==16)?4:(a[i]==23)?5:6;
if(k==1){++num[k];continue;}
if(num[k]+1>num[k-1]) continue;
else ++num[k];
}
printf("%d",n-num[6]*6);
return 0;
}
```
# [$\color{#FFC116}{C}$](https://vjudge.csgrandeur.cn/contest/576896#problem/C)
[洛谷上](https://www.luogu.com.cn/problem/UVA11991)
## 思路
只需要求得某个数的第几次出现的位置，想到先统计这个数的所有出现位置。
使用 vector 储存。
## AC code
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,a,k,u,maxn;
vector<int>v[1000005];
int main()
{
while(~scanf("%d%d",&n,&m))
{
maxn=0;
for(int i=1;i<=n;++i) scanf("%d",&a),v[a].push_back(i),maxn=max(maxn,a);
while(m--) scanf("%d%d",&k,&u),printf("%d\n",(k>v[u].size())?0:v[u][k-1]);
for(int i=1;i<=maxn;++i) v[i].clear();
}
return 0;
}
```
# [$\color{#52C41A}{D}$](https://vjudge.csgrandeur.cn/contest/576896#problem/D)
[洛谷上](https://www.luogu.com.cn/problem/UVA10298)
## 思路1.暴力
直接暴力枚举重复子串长度，剔除明显不符合的子串长度，判断是否符合条件。（原本能过，结果加强数据被卡了）。
## TLE code
```cpp
#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
while(1)
{
cin>>s;
int n=s.size();
if(s==".") break;
for(int i=1;i<=n;++i)
{
if(n%i) continue;
int flag=0;
for(int j=i;j<n;j+=i)
{
if(flag) break;
for(int k=0;k<i;++k)
if(s[k]!=s[j+k]){flag=1;break;}
}
if(!flag){printf("%d\n",n/i);break;}
}
}
return 0;
}
```
## 思路2.优化暴力
只枚举第二段的开头与字符串的开头相同的情况，虽然不是正确的做法（时间复杂度也不正确），但是本题可以卡过去。
## AC code
```cpp
#include<bits/stdc++.h>
using namespace std;
string s;
vector<int>v;
int main()
{
while(1)
{
cin>>s;
int n=s.size();v.clear();
if(s==".") break;
for(int i=1;i<n;++i) if(s[i]==s[0]) v.push_back(i);
v.push_back(n);
for(int kk=0;kk<v.size();++kk)
{
int i=v[kk];
if(n%i) continue;
int flag=0;
for(int j=i;j<n;j+=i)
{
if(flag) break;
for(int k=0;k<i;++k)
if(s[k]!=s[j+k]){flag=1;break;}
}
if(!flag){printf("%d\n",n/i);break;}
}
}
return 0;
}
```
## 思路3.kmp
直接使用 kmp 算出 next 数组。还不会 kmp 的同学看[这里](https://www.luogu.com.cn/problem/solution/P3375)。
如果理解了 kmp 中 next 数组的作用，这道题就很简单了。
字符串可以从最后一位开始被分为长度为 $n-next_n$ 相同的若干段。
如果 $n\% (n-next_n)==0$，则代表可以被分为 $\frac{n}{n-next_n}$ 段，即为答案。
否则，答案为 $1$，即不存在这样的子串。
## AC code
```cpp
#include<bits/stdc++.h>
using namespace std;
int p[2000005],n,j;
char s[2000005];
int main()
{
while(1)
{
scanf("%s",s+1);
n=strlen(s+1);
if(s[1]=='.') break;
for(int i=2;i<=n;i++)
{
while(j>0&&a[j+1]!=a[i]) j=p[j];
if(a[j+1]==a[i]) j++;
p[i]=j;
}
if(n%(n-p[n])==0) printf("%d\n",n/(n-p[n]));
else printf("1\n");
}
}
```
# [$\color{#3498DB}{E}$](https://vjudge.csgrandeur.cn/contest/576896#problem/E)
[洛谷上](https://www.luogu.com.cn/problem/CF776D)
## 思路
我们已经得知每盏灯的初始状态和哪两个开关控制它。
首先分类讨论：
如果最开始这盏灯是开着的，那么这两个开关应该做出同样的操作，即要么全按，要么全不按。
如果最开始这盏灯是关着的，那么这两个开关应该做出不同的操作，即一个按一个不按。
总结一下，就是有 $m$ 个数，其中有 $n$ 个关系，有些关系是两个数要一样，有些关系是两个数要不一样，问是否合理。
自然而然地，我们想到了并查集。
先处理一样的，再处理不一样的。
一样的很好处理，这里不废话了。
重点是如何处理不一样的。
我们可以用一个数组 $f$ 来存 $i$ 上一次的关系中，应该与那个数不一样。
那么，假设这一次的关系中，是 $i,j$ 要保持不一样，那么，我们可以肯定的是 $i$ 应该与 $f_j$ 一样，$j$ 应该与 $f_i$ 一样，所以合并就好了，再更新 $f_i.f_j$ 即可。
## AC code
```cpp
#include<bits/stdc++.h>
using namespace std;
struct node{int k,l,r;}t[100005];
inline bool cmp(node a,node b){return a.k>b.k;}
int n,m,a,b,fa[100005];
int s[100005];
int find(int x){return (fa[x]==x)?x:fa[x]=find(fa[x]);}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) fa[i]=i;
for(int i=1;i<=n;++i) scanf("%d",&t[i].k);
for(int i=1;i<=m;++i)
{
scanf("%d",&a);
while(a--)
{
scanf("%d",&b);
if(t[b].l) t[b].r=i;
else t[b].l=i;
}
}
sort(t+1,t+n+1,cmp);
for(int i=1;i<=n;++i)
{
if(t[i].k){if(find(t[i].l)!=find(t[i].r)) fa[find(t[i].l)]=find(t[i].r);}
else
{
int fl=find(t[i].l),fr=find(t[i].r);
if(fl==fr) printf("NO"),exit(0);
else
{
if(s[fr]) fa[s[fr]]=fl;s[fr]=fl;
if(s[fl]) fa[s[fl]]=fr;s[fl]=fr;
}
}
}
printf("YES");
return 0;
}
```
## 总结
感觉洛谷难度评的整体较高，个人认为难度：$\color{#F39C11}{A}$,$\color{#F39C11}{B}$,$\color{#F39C11}{C}$,$\color{#FFC116}{D}$,$\color{#FFC116}{E}$。
除了 $B$ 和 $E$ 题，其他几乎全是模板，只有少许应用。
需要的知识点：[双端队列](https://oi-wiki.org/ds/queue/#%E5%8F%8C%E7%AB%AF%E9%98%9F%E5%88%97)、[桶](https://oi-wiki.org/basic/bucket-sort/)、[vector](https://oi-wiki.org/lang/csl/sequence-container/)、[kmp](https://oi-wiki.org/string/kmp/)、[并查集](https://oi-wiki.org/ds/dsu/)。
## 练后思考
### 1.基础篇
如果 E 题需要输出按开关的方案，该如何做？
### 2.进阶篇
如果 E 题中，一个灯的开关不止两个，该如何做？