非官方全题解|挑战赛#18（已完成）

userId_undefined

你是不是喜欢c++

荣耀黄金

2025-05-19 18:51:28

发布于：广东

132阅读
0回复
0点赞

挑战赛#18全题解来咯！！

前言

本蒟蒻第一次写挑战赛题解，希望各位大佬们多多指点。

@AC君给个周边吧，写这篇题解真的用了很长时间！！

好啦，废话不多说，进入正题！！

难度分布与知识点

本次挑战赛难度适中，在此感谢出题人@NoonMaple,让我这样的蒟蒻都可以AK挑战赛，成就感满满！，题目难度与考察知识点如下：

题目名称 题目难度 考察知识点
午枫爱画画 入门 模拟
午枫爱谦让 普及- 贪心，排序
午枫爱搬家 普及- 二分答案
午枫爱操作 普及/提高- 贪心，字符串
午枫爱迷宫 普及/提高- 广搜
午枫爱37 普及+/提高 动态规划

题目解析

T1：午枫爱画画

题目大意：给定两个数n、m表示输出井号与星号的次数，交替输出井号与星号直到其中一个输出次数用完，随后一直输出另一字符直到输出次数都用完。

分析与解：直接for循环模拟输出即可。

Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=min(n,m);i++) cout<<"#*";
	if(n>=m) 
	{
		for(int i=1;i<=n-min(n,m);i++) cout<<"#";
	} 
	else
	{
		for(int i=1;i<=m-min(n,m);i++) cout<<"*"; 
	}
	return 0;
}

T2：午枫爱谦让

题目大意：两人交替取出一个长度为偶数的数组中的数，每人每次都会取目前数组中最小的数。问两人最后分别取到的数的总和。

分析与解：将数组sort排序后遍历并累加即可。注意累加器要开long long。

Code

#include<bits/stdc++.h>
using namespace std;
int n,a[200005];
long long suma,sumb;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		if(i%2==1) suma+=a[i];
		else sumb+=a[i];
	}
	cout<<suma<<" "<<sumb<<endl;
	return 0;
}

T3：午枫爱搬家

题目大意：两人按顺序搬运n件物品，每件物品有自己的重量，找到一个每次搬运物品重量和的上限x，使得最多k次就能搬完这些物品，求x的最小值。

分析与解：看到题目中“最大货物重量和最小”这个关键句子，就能立马想到用二分解决这道题。每次求一个中间值mid，用solve函数判断这个中间值是否符合要求，若符合，继续找更小的数；若不符合，则往大一点的数找。

Code

#include<bits/stdc++.h>
using namespace std;
long long n,k,a[200005];
long long l=1,r=1e15,ans;
bool solve(long long x)
{
	long long sum=x,cnt=1;
	for(int i=1;i<=n;i++)
	{
		if(a[i]>x) return false;
		if(sum>=a[i])
		{
			sum-=a[i];
		}
		else 
		{
			cnt++;
			sum=x-a[i];
		}
	}
	if(cnt<=k) return true;
	else return false;
} 
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	while(l<=r)
	{
		long long mid=(l+r)/2;
		if(solve(mid))
		{
			ans=mid;
			r=mid-1;
		}
		else 
		{
			l=mid+1; 
		}
	}
	cout<<ans<<endl;
	return 0;
}

T4：午枫爱操作

讲解这道题之前，先插一句：这道题目读懂了题其实很简单。

题目大意：（这道题目有点难读懂，注意不要漏掉条件了。）
给定一个01字符串，可以对其执行任意次如下操作：

  • 选择一段从0开始，到1结束的区间。
  • 对于区间中的每个数（0或1），若为0，则变成1；若为1，则变成0。

最后，将这个字符串转化为二进制，让这个二进制数最大。求最大二进制数对应的字符串。

分析与解：请看下图。

看到这里，你懂了吗？

Code

#include<bits/stdc++.h>
using namespace std;
int n,num=-1;
string s;
int main()
{
	cin>>n>>s;
	for(int i=n-1;i>=0;i--)
	{
		if(s[i]=='1') 
		{
			num=i;
			break;
		}
	}
	if(num==-1) 
    {
    	cout<<s<<endl;
    	return 0;
	}
	for(int i=0;i<num;i++)
	{
		if(s[i]=='0')
		{
			for(int j=i;j<=num;j++)
			{
				if(s[j]=='0') s[j]='1';
				else
				{
					s[j]='0';
					i=j-1;
					break;
				}
			}
		}
	}
	cout<<s<<endl;
	return 0;
}

T5：午枫爱迷宫

题目大意：本题题目信息量较大，请自行查看题目。（点击上方题目）

分析与解：广搜。将题目分为四个阶段：

1. 小午（N）到钥匙（！）

2.钥匙（！）到小枫（M）

3.小枫（M）到出口（@）

4.小午（N）到出口（@）-->小午独自逃出迷宫

随后对与每个阶段都进行一遍广搜即可。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,nx,ny,mx,my,kx,ky,cx,cy;//记录位置
char a[1005][1005];
bool vis[1005][1005];
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};//方向
struct node{
	int x,y;
};
bool bfs(int sx,int sy,int fx,int fy,bool key)//key表示此时是否已经救出小枫
{
	memset(vis,0,sizeof(vis));//清空标记数组
	queue<node>q;
	q.push({sx,sy});
	vis[sx][sy]=1;
	while(!q.empty())
	{
		node t=q.front();
		q.pop();
		if(t.x==fx&&t.y==fy) return 1;
		for(int i=0;i<4;i++)
		{
			int x1=t.x+dx[i],y1=t.y+dy[i];
			if(x1>=1&&x1<=n&&y1>=1&&y1<=m&&!vis[x1][y1])
			{
				char c=a[x1][y1];
				if(c=='#'||(!key&&c=='$')) continue;//第二个条件是没救出小枫时
				vis[x1][y1]=1;
				q.push({x1,y1});
			}
		}
	}
	return 0;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='N') nx=i,ny=j;
			else if(a[i][j]=='M') mx=i,my=j;
			else if(a[i][j]=='!') kx=i,ky=j;
			else if(a[i][j]=='@') cx=i,cy=j;//标记位置
		} 
	}
	bool ans1=bfs(nx,ny,kx,ky,0);
	bool ans2=bfs(kx,ky,mx,my,0);
	bool ans3=bfs(mx,my,cx,cy,1);
	bool ans4=bfs(nx,ny,cx,cy,0);//四遍广搜分别对应四个阶段
	if(ans1&&ans2&&ans3) cout<<"we were here together"<<endl;//两人一起逃出
	else if(ans4) cout<<"sorry"<<endl;//小午逃出
	else cout<<"NO"<<endl;//无法逃出
	return 0;
}

T6：午枫爱37

题目大意：从n张卡片中选任意个数，求能使得这些数的和为21的倍数的取法有多少种。（答案对 998244353 取模）

分析与解：动态规划。既是3的倍数又是7的倍数，即为21的倍数。dp[i]表示总和模21余i的方案数，动态转移方程也很好推出了（请看代码）

注意：本题中只考虑卡片上的数模21的余数，dp[0]开始时要赋值为1。我这里使用滚动数组优化空间。

Code

#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int dp[30],n;
int main()
{
	cin>>n;
	dp[0]=1;//不取有一种方案余数为0
	for(int i=1;i<=n;i++)
	{
		int num,t[30]={0};
		cin>>num;
		int m=num%21;//只考虑余数
		for(int j=0;j<21;j++)
		{
			t[j]=(dp[j]+dp[(j-m+21)%21])%MOD;//转移
		}
		for(int j=0;j<21;j++)
		{
			dp[j]=t[j];
		}
	}
	cout<<dp[0]<<endl;//余数为0的方案数
	return 0;
}

啊！终于写完了！@AC君给个周边吧！！！

userId_undefined
去预览
0/2000

全部评论 7

热门讨论