题目颜色大致对标洛谷难度

$\color{#F39C11}{A}$

思路

容易发现这是一道双端队列的模板题，所以直接模拟就好。

我使用的是手工队列（忘了 STL 的双端队列怎么写了，而且估计手写比STL快很多）。

AC code

#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{#F39C11}{B}$

思路

定义一个数组能分为若干份，每一份都是 $4,8,15,16,23,42$ 的前缀的数组是 半优秀 的。

容易发现只有满足以下性质的数组才是 半优秀：

对于每一个 $i(1\leq i\leq n)$，统计 $6$ 个数字的数量，较大的数字的数量一定少于等于较小的数字的数量。

那么，如果一个数的出现，使目前的数组不是 半优秀 的，那么它一定会使整个数组不是优秀的，所以需要删去。

那么，最后剩下的数的数量就是 $6\times 42 \text{的数量}$。

只需要用 $n$ 减去剩下的数的数量，就可以得出答案。

AC code

#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{#F39C11}{C}$

思路

只需要求得某个数的第几次出现的位置，想到先统计这个数的所有出现位置。

使用 vector 储存。

AC code

#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{#FFC116}{D}$

思路1.暴力

直接暴力枚举重复子串长度，剔除明显不符合的子串长度，判断是否符合条件。（原本能过，结果加强数据被卡了）。

TLE code

#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

#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 的同学看这里。

如果理解了 kmp 中 next 数组的作用，这道题就很简单了。

字符串可以从最后一位开始被分为长度为 $n-next_n$ 相同的若干段。

如果 $n% (n-next_n)==0$，则代表可以被分为 $\frac{n}{n-next_n}$ 段，即为答案。

否则，答案为 $1$，即不存在这样的子串。

AC code

#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{#FFC116}{E}$

思路

我们已经得知每盏灯的初始状态和哪两个开关控制它。

首先分类讨论：

如果最开始这盏灯是开着的，那么这两个开关应该做出同样的操作，即要么全按，要么全不按。

如果最开始这盏灯是关着的，那么这两个开关应该做出不同的操作，即一个按一个不按。

总结一下，就是有 $m$ 个数，其中有 $n$ 个关系，有些关系是两个数要一样，有些关系是两个数要不一样，问是否合理。

自然而然地，我们想到了并查集。

先处理一样的，再处理不一样的。

一样的很好处理，这里不废话了。

重点是如何处理不一样的。

我们可以用一个数组 $f$ 来存 $i$ 上一次的关系中，应该与那个数不一样。

那么，假设这一次的关系中，是 $i,j$ 要保持不一样，那么，我们可以肯定的是 $i$ 应该与 $f_j$ 一样，$j$ 应该与 $f_i$ 一样，所以合并就好了，再更新 $f_i.f_j$ 即可。

AC code

#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;
}