语法周赛 Round 20 题解

A. 编号第几小的思维场 T1

分析

• 难度：简单数学运算，难点主要在读题
• 子任务 1（30 分）：显然轮数为 $\lfloor \frac{n}{,}4\rfloor$。保证了是普通轮，直接输出 轮数+1 即可。
• 子任务 2（30 分）：保证了是思维场，思维场是 $6,8,10,12,14,16,18,20$，显然输出 轮数/2-2 即可。
• 子任务 3（40 分）：容易发现，简单场直接用 轮数/2-2 也能得到正确的结果。所以根据轮数，判断出来非普通轮就输出 轮数/2-2。

满分参考代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	int r = n / 4;	   // 所属轮数
	int t = n % 4 + 1; // 在那一场比赛中的题号（其实没用）
	if (r <= 5)
		cout << r + 1;
	else
		cout << r / 2 - 2;
	return 0;
}

B. 小猫向日葵

分析

• 难度：循环嵌套，主要难点在于耐心，当然如果用后期知识点就是简单题了。
• 子任务 1（30 分）：只买得起一个小猫向日葵或者一个樱桃辣椒，根据 $m$ 决定输出 $0$ 还是 $7$ 还是 $14$ 即可。
• 子任务 2（30 分）：考虑 $n$ 的阳光有多少种种植方案即可。
• 子任务 3（40 分）：可以枚举每个地皮是什么植物，七层嵌套循环完成。也可以枚举每种植物有几个，然后排列组合求出答案。

满分参考代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n, m;
	cin >> n >> m;
	int ans = 0;
	for(int a=0;a<=3;a++)
	for(int b=0;b<=3;b++)
	for(int c=0;c<=3;c++)
	for(int d=0;d<=3;d++)
	for(int e=0;e<=3;e++)
	for(int f=0;f<=3;f++)
	for(int g=0;g<=3;g++)
	{
		int sun = 0, power = 0;
		
		if(a==1) sun+=150,power+=300;
		if(b==1) sun+=150,power+=300;
		if(c==1) sun+=150,power+=300;
		if(d==1) sun+=150,power+=300;
		if(e==1) sun+=150,power+=300;
		if(f==1) sun+=150,power+=300;
		if(g==1) sun+=150,power+=300;

		if(a==2) sun+=888,power+=1600;
		if(b==2) sun+=888,power+=1600;
		if(c==2) sun+=888,power+=1600;
		if(d==2) sun+=888,power+=1600;
		if(e==2) sun+=888,power+=1600;
		if(f==2) sun+=888,power+=1600;
		if(g==2) sun+=888,power+=1600;
		
		if(a==3) sun+=275,power+=600;
		if(b==3) sun+=275,power+=600;
		if(c==3) sun+=275,power+=600;
		if(d==3) sun+=275,power+=600;
		if(e==3) sun+=275,power+=600;
		if(f==3) sun+=275,power+=600;
		if(g==3) sun+=275,power+=600;

		if(sun<=n && power>=m) ans++;
	}
	cout << ans;
	return 0;
}

C. 乒乓球

题解

我们把$k$颗球看做是一轮。

对于每一轮来说，如果在这一轮开始前，比分是a:b，那么这一轮结束后，比分是多少就是确定的。

很明显可以看出来的一点是，开始时候两个人的当前局得分如果都$>11$的话，同时把两个人的分数减去同样的分数，使得两个人的分数都$\le 11$，是不会影响这一轮结果的。

那么，我们开三个数组$t,sa,sb$，分别记录：

$t[a][b]$：最早什么时候，遇到这一轮开始前，比分是$a:b$。

$sa[a][b],sb[a][b]$：这个时候，小明/小红一共赢了多少局。

那么，当我下一次在$tim$时候（此时总比分是$A:B$）模拟遇到同样的$a,b$时，就可以视作，模拟的过程是每$tim-t[a][b]$一个周期，每个周期内，大局的得分都是$A-sa[a][b]:B-sb[a][b]$。

直接跳过这个超级大周期，然后模拟完剩余的时间即可。

由于开始的比分最多只有$12\times 12+1=145$种，因此模拟的总次数不会超过$145\times k$。

满分参考代码

#include <bits/stdc++.h>
#define maxn 1000005
#define ll long long
#define mod 998244353
using namespace std;
ll t[17][17];
ll sa[17][17],sb[17][17];
ll n,k;
string s;
ll a=0,b=0,A=0,B=0;
ll tim=0;
void moni()
{
	for (int i=0;i<k;i++)
	{
		tim++;
		if (s[i]=='A') a++; else b++;
		if (max(a,b)>=11 && abs(a-b)>=2)
		{
			if (a>b) A++; else B++;
			a=b=0;	
		}
		if (tim==n) {cout<<A<<":"<<B<<endl; exit(0);}
	}
}
int main()
{
	cin>>n>>k; 
	cin>>s;
	memset(t,-1,sizeof(t));
	t[0][0]=0;
	while (true)
	{
		moni();
		if (a==b && a>11) a=b=11;
		if (min(a,b)>=11 && a!=b) {if (a>b) a=12,b=11; else a=11,b=12;}
		if (t[a][b]!=-1) //曾经出现过 
		{
			ll da=A-sa[a][b],db=B-sb[a][b]; //deltaA,deltaB
			ll zhouqi=tim-t[a][b]; //周期大小
			ll quan=(n-tim)/zhouqi;
			A+=da*quan; B+=db*quan;
			tim+=quan*zhouqi;
			if (tim==n) {cout<<A<<":"<<B<<endl; return 0;}
			while (true) moni();
		}
		else
		{
			t[a][b]=tim; sa[a][b]=A; sb[a][b]=B;
		}
	}
	return 0;
}

D. 分糖果

题解

小朋友实际上只有三种，按$\mathrm{mod}3$分为$0,1,2$三类。

组成小组只有四种类型：$000,111,222,012$。

显然，$012$超过$3$是没有意义的，因为三个$012$可以拆分成$000,111,222$各一个。

因此，枚举$012$组成了几组即可。

满分参考代码

#include <bits/stdc++.h>
#define maxn 1000005
#define ll long long
#define mod 998244353
using namespace std;
int n;
vector<int> a[3];
int x,best,f;
int get(int x)
{
	for (int i=0;i<=2;i++) if (a[i].size()<x) return 0;
	int ret=x;
	for (int i=0;i<=2;i++) ret+=(a[i].size()-x)/3;
	return ret;
}
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) {cin>>x; a[x%3].push_back(i);}
	for (int i=0;i<=2;i++)
	{
		int tt=get(i);
		if (tt>best) {best=tt; f=i;}
	}
	cout<<best<<endl;
	for (int i=1;i<=f;i++)
	{
		for (int j=0;j<=2;j++) {cout<<a[j][a[j].size()-1]<<" "; a[j].pop_back();}
		cout<<endl;
	}
	for (int i=0;i<=2;i++)
	{
		while (a[i].size()>=3)
		{
			int siz=a[i].size();
			cout<<a[i][siz-1]<<" "<<a[i][siz-2]<<" "<<a[i][siz-3]<<endl;
			a[i].pop_back(); a[i].pop_back(); a[i].pop_back();
		}
	}
	return 0;
}