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

BNUOJ新生赛题解

首先给个链接给大家,让大家慢慢看题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新生赛题解