BNUOJ新生赛题解

首页 > 代码库 > BNUOJ新生赛题解

2024-10-19 11:58:01 211人阅读

首先给个链接给大家，让大家慢慢看题http://acm.bnu.edu.cn/v3/problem.php#page=1726

题目1：无聊的游戏

比赛的时候不敢对数学题下手是个巨大的问题。题目很明显给那么大的n，k（最大10^9）。除了数学规律没有其他方法。首先就是对n分类，分奇偶。多算几个就边弄边猜

下面讨论：n为奇数时，当k%4=1或者2时，B获胜，否则A获胜

n为偶数时，当k为奇数，为平局输出F；当k%4=2时，输出B，否则输出A

其实吧，这种题在比赛的时候，派个队友数学好的，把n，k=1，2，3，4，5，6的各种情况列举一下，细心点，总结规律。很好做的

不多说，代码如下：

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		if (n%2)
		{
			if (k%4==1||k%4==2) puts("B");
			else puts("A");
		}
		else
		{
			if (k%2==1) puts("F");
			else if (k%4==2) puts("B");
			else puts("A");
		}
	}
	return 0;
}

题目2：萌萌哒BY哥哥

这个没啥好说的，大家去翻组合数学的书吧，错排公式：Xn=（n-1）(X(n-1)-X(n-2))。唯一的坑点是不能用int要用long long

题目3：Monty Hall Problem

数学好的队友做的，思路如下：

原来一共n扇门，其中有n-1扇门后面是山羊，只有1扇门后面是汽车。因此，初始情况选择山羊的概率是（n-1）/n，汽车的概率是1/n

第一次选择之后，已经揭晓了n-2个山羊，由题意知，必须改选门，则：初始选择山羊的话，就改成了选择汽车，因此答案就是（n-1）/n

题目4：计算题

坑点1：可以为空，即长度为0时输出0。因此必须用gets读入

坑点2：每次累加时要给ans%p，不然可能越界

题目5：冠名争夺战

很好的博弈题：答案出人意料的简单：永远都是Bill will lose HAHA

解释：反证法：（注意到决策次数不是把所有的石子都选择完，而是只选择几个）（证明思想非常类似于取石子的博弈）

假设后手有必胜策略，即取到Ai颗石子使得在剩余的所有石子中，先手找不到一个石子可以打败Ai。那么在先手的第一次任意选择时，先手就可以选择Ai颗石子使自己获胜。因此，无论游戏怎样设计，必然都是先手获胜

题目6：柯南的精灵

数学题：至今没找到规律，希望有大神能够教教我

题目7：疯狂睡眠

标准贪心：以各睡眠时间的结束点由低到高进行排序，若相同，则按照起始点的由低到高排序

排序后，依次按顺序逐渐选择即可。代码如下

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Sca_d(x) scanf("%d",&x)
#define Sca_s(x) scanf("%s",x)
#define Sca_c(x) scanf("%c",&x)
#define Sca_f(x) scanf("%f",&x)
#define Sca_lf(x) scanf("%lf",&x)
#define Sca_lu(x) scanf("%I64d",&u)
#define Sca_ld(x) scanf("%I64d",&x)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 0x3f3f3f3f

struct node
{
	int x,y;
}que[10005];

int cmp(const void *a,const void *b)
{
	struct node *c=(node *)a;
	struct node *d=(node *)b;
	if (c->x!=d->x) return c->y - d->y;
	return c->x - d->x;
}

int main()
{
	//input;
	int t,n,i,j,k,ans,cur;
	cin>>t;
	while(t--)
	{
		Fill(que,0);
		cin>>n;
		For2(i,1,n)
			Sca_d(que[i].x),Sca_d(que[i].y);
		qsort(que+1,n,sizeof(que[0]),cmp);
		cur=i=ans=0;
		while(i<n)
		{
			i++;
			if (cur<que[i].x)
			{
				cur=que[i].y;
				ans++;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

题目8：First Contact

简单0-1背包模型：却浪费了1个小时，还需对经典问题多加总结与训练

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Sca_d(x) scanf("%d",&x)
#define Sca_s(x) scanf("%s",x)
#define Sca_c(x) scanf("%c",&x)
#define Sca_f(x) scanf("%f",&x)
#define Sca_lf(x) scanf("%lf",&x)
#define Sca_lu(x) scanf("%I64d",&u)
#define Sca_ld(x) scanf("%I64d",&x)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 0x3f3f3f3f

int dp[1005];
int book[1005];
int aa[1005];
int bb[1005];

int main()
{
	//input;
	int a,b,n,x,y,i,j,t;
	cin>>t;
	for(int Case=1;Case<=t;Case++)
	{
		Fill(dp,0);Fill(aa,0);Fill(bb,0);Fill(book,0);
		cin>>a>>b>>n;
		For2(i,1,n) cin>>aa[i];
		For2(i,1,n) cin>>bb[i];
		/*For2(i,1,n)
			For2(j,1,i)
				if (aa[i]>aa[j]||(aa[i]==aa[j]&&bb[i]<bb[j]))
				{
					int temp;
					temp=aa[i];aa[i]=aa[j];aa[j]=temp;
					temp=bb[i];bb[i]=bb[j];bb[j]=temp;
				}
		*/
		for(i=1;i<=n;i++)
			for(j=a;j>=aa[i];j--)
				dp[j]=max(dp[j],dp[j-aa[i]]+bb[i]);
		printf("Case #%d: %s\n",Case,dp[a]>=b?"YES":"NO");
		//printf("%d\n",dp[a]);
	}
	return 0;
}

题目9：平面切割者

本来比赛的时候可以自豪一番，第一次就把公式推理出来了，坑爹的n=0！

首先可以画图计算：n=0时ans=2，n=1时ans=4，n=2时ans=8，n=3时ans=13，n=4时ans=19（这个画图比较费劲。。圆要画得很大）

接下来是推理：把大圆和小圆中间的圆环看作一个部分，每次增加一根线，多增加两个区域

把小圆看作另外一个部分，每次增加一根线，多增加i个区域，其中i是当前添加的是第i根线

因此，在O（n）时间推得，ans[i]=ans[i-1]+i+2。初始值ans[0]=0，ans[1]=4，递推式从i=1开始计算

题目10：拯救辣条

这么小的数据，简单粗暴的DFS即可！注意：题中求与Bi不同的组数，因此输出ans-1

代码如下：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Sca_d(x) scanf("%d",&x)
#define Sca_s(x) scanf("%s",x)
#define Sca_c(x) scanf("%c",&x)
#define Sca_f(x) scanf("%f",&x)
#define Sca_lf(x) scanf("%lf",&x)
#define Sca_lu(x) scanf("%I64d",&u)
#define Sca_ld(x) scanf("%I64d",&x)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 0x3f3f3f3f

const int maxn=10;
int ans;
int t,n,a[maxn],b[maxn],c[maxn];

void dfs(int cur)
{
	int i,j,k;
	if (cur==n+1)
	{
		ans++;
		//For2(j,1,n)
		//	printf("%d%c",c[j],j==n?'\n':' ');
		return;
	}
	For2(i,0,a[cur])
	{
		c[cur]=i;
		if (cur==1) dfs(cur+1);
		else if ((b[cur]>b[cur-1]&&c[cur]>c[cur-1])||(b[cur]==b[cur-1]&&c[cur]==c[cur-1])||(b[cur]<b[cur-1]&&c[cur]<c[cur-1]))
			dfs(cur+1);
	}
	return;
}

int main()
{
	//input;
	int i,j,k;
	cin>>t;
	while(t--)
	{
		cin>>n;
		For2(i,1,n) cin>>a[i];
		For2(i,1,n) cin>>b[i];
		ans=0;
		dfs(1);
		cout<<ans-1<<endl;
	}
	return 0;
}

题目11：顽皮的字母

字母顽皮的我都想打人了。但学到了一个很好的像是DP的思想，我当前的判断值只跟前面已经做过的判断比较

代码如下：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Sca_d(x) scanf("%d",&x)
#define Sca_s(x) scanf("%s",x)
#define Sca_c(x) scanf("%c",&x)
#define Sca_f(x) scanf("%f",&x)
#define Sca_lf(x) scanf("%lf",&x)
#define Sca_lu(x) scanf("%I64d",&u)
#define Sca_ld(x) scanf("%I64d",&x)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 0x3f3f3f3f

char s[1000000],ans[1000000];
int main()
{
	//input;
	int i,j,k,l,t,flag,start,cur;
	cin>>t;
	while(t--)
	{
		 cin>>s;
		 l=strlen(s);
		 cur=1;
		 ans[0]=s[0];
		 for(i=1;i<l;i++)
		 {
		 	if (s[i]%2)//当前字母为 a,c,e,g…… 
		 	{
		 		if (s[i]+1==ans[cur-1]) cur--;//满足ab，cd……把ans的已存的字母删除 
		 		else ans[cur++]=s[i];//添加当前字母 
		 	}
		 	else//当前字母为b,d,f,h…… 
		 	{
		 		if (s[i]-1==ans[cur-1]) cur--;
		 		else ans[cur++]=s[i];
		 	}
		 }
		 ans[cur]='\0';
		 if (!cur) puts("sad!");//所有的字母已经消除 
		 else printf("%s\n",ans);
	}
	return 0;
}

BNUOJ新生赛题解

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > BNUOJ新生赛题解

BNUOJ新生赛题解

看完仍有疑问？有类似问题直接问程序猿