3级学业水平测试_题目名称:煎饼达人 时间限制:1000ms 内存限制:256mb 提交通过率:23% 题目描述 小

  今天，我找到了有道小图灵这个官方网站，里面有着非常多的比赛，于是，我决定尝试一番，第一级和第二季测试太简单了，连算法都没有考到，于是我重新考了一次3级学业水平测试，只花了一个小时四十分钟（总时间2小时），满分就到手了。

  今天，我来做一个总结，从第一题开始“橙汁计划升级版”。

题目名称：橙汁计划升级版

时间限制：1000ms内存限制：256MB提交通过率：37%

题目描述

小图灵家门口的便利店正在开展“橙汁计划”活动，每a个橙汁空瓶（不含瓶盖）可以兑换一瓶橙汁，每b个橙汁瓶盖也可以兑换一瓶橙汁。小图灵初始有n瓶未开封的橙汁，在不允许借瓶或借盖的情况下，他一共能喝到多少瓶橙汁？

输入描述

一行，三个整数n, a, b。

输出描述

一行，一个整数，表示小图灵总共能喝到的橙汁瓶数。

样例1

输入复制

5 3 3

输出

11

样例2

输入复制

10 8 11

输出

12

提示

3 <= n, a, b <= 100

  首先，我们可以设置三个变量，a1和b1，sum,分别代表着目前有几个盖子，几个空瓶子，目前喝了几瓶橙汁。然后进行取模，之后又将换来的橙汁喝掉，一直循环下去，循环到什么时候呢？就是a1<a&&b1<b的时候，这样子无论如何都不能换橙汁了，我们有三种循环方法for、while、do_while，目前三个方法复杂度都一样。

橙汁计划升级版代码：

#include<iostream>
using namespace std;
int main()
{
	int n,a,b,sum=0,a1=0,b1=0;
	cin>>n>>a>>b;
	sum=n;
	a1=n;	
	b1=n;
	for(int i=0;;i++)
	{
		if(b<=b1)
		{
			int t=b1/b;
	    	sum+=t;
		    b1%=b;
		    b1+=t;
		    a1+=t;			
		}
		else
		{
			int t=a1/a;
			sum+=t;
			a1%=a;
			a1+=t;
			b1+=t;
		}
		if(a1<a&&b1<b)
		  break;
	}
	cout<<sum<<endl;
	return 0;
} 

  然后来看看第二题“计数游戏”：

题目名称：计数游戏

时间限制：1000ms内存限制：256MB提交通过率：32%

题目描述

小图灵正在练习计数，他要从n个可能重复的数字a1...an中，找到第一个出现次数达到k的数字，来帮帮他吧。

输入描述

第一行两个整数n和k，第二行n个整数。

输出描述

一行，一个整数，表示答案。若答案不存在，输出-1。

样例1

输入复制

8 3 3 2 1 2 1 3 2 3

输出

2

样例2

输入复制

5 3 1 3 2 1 2

输出

-1

提示

对于40%的数据：n <= 10^3
对于100%的数据：1 <= k <= n <= 10^5，0 <= ai <= 10^5

  这种，我们可以用类似桶排序的方法，设置一个10^5的数组sum，将输入的数a[i]在sum[a[i]]加一，表示这个数组里a[i[有sum[a[i]]个，就这样，我们计算出输入的数中最大的数t，从sum[0]到sum[t]找刚好等于k的数，然后输出i。

计数游戏代码：

#include <iostream>
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	int a[n],sum[100005]={0},t=-1;
	for(int i=0;i<n;i++)
	  cin>>a[i];
	for(int i=0;i<n;i++)
	{
		sum[a[i]]++;	
	    if(sum[a[i]]==k)
	    {
	    	cout<<a[i]<<endl;	
	    	return 0;
		}
	}
	cout<<t<<endl;
	return 0;
}

  然后我们看看第3题“函数求值”:

题目名称：函数求解

时间限制：1000ms内存限制：256MB提交通过率：23%

题目描述

苦练数学的小图灵遇到了一个复杂的函数：

f(m, n)=

{

n + 1 & &  (m = 0) 

 m * 2 (n = 0 且 m > 0)

f(m - 1, n - 1) + f(m - 1, n) + f(m, n - 1)  //(m > 0 且 n > 0) 

}

由你来帮小图灵求出f(m, n)的值。

输入描述

一行，两个整数m和n。

输出描述

一行，一个整数，表示答案。由于答案可能很大，请将其对32767取模。

样例1

输入复制

2 3

输出

53

样例2

输入复制

10 10

输出

30238

提示

对于40%的数据：m * n <= 100
对于100%的数据：0 <= m, n <= 1000

  乍一看，还以为是关于分段函数的问题，仔细看了看后，就知道了，这道题需要用到递归或者递推，我们先从递归开始，先判断m是否等于0，等于0的话就直接返回n+1。然后在判断n是否等于0，m是否大于0，满足条件的话就返回m*2。最后一段是唯一一个需要用递归来解决的，只需要f(n-1,m-1)+f(m-1,n)+f(m,n-1)，怎样停下来呢，在达到前面两段后，自然会返回一个值，依次累加下去。

递归代码：

#include <iostream>
using namespace std;
int three(int a,int b)
{
	if(b==0&&a>0)
	  return a*2;
	else if(a==0)
	  return b+1;
	else if(a>0&&b>0)
	  return three(a-1,b-1)+three(a-1,b)+three(a,b-1);
}
int main()
{
	int n,m;
	cin>>m>>n;
	cout<<three(m,n);
}

  虽说对了，但是

有四个样例超时了。

  于是我想到了递推，动手在纸上写了一回儿会，我有了一点思路，将参数m和n对应到二维数组里的行与列，可以就可以递推解答了！

递推代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int m,n,f[1000][1000]={0};
	scanf("%d %d\n",&m,&n);
	for(int i=0;i<=m;i++)
	{
		for(int j=0;j<=n;j++)
		{
			if(i==0)
			  f[i][j]=j+1;
			else if(j==0)
			  f[i][j]=i*2;
			else
			  f[i][j]=(f[i-1][j-1]+f[i-1][j]+f[i][j-1])%32767;
		}
	}
	printf("%d",f[m][n]);
	return 0;
}

就这样，

 

  然后是第四题“购机攻略” 

题目名称：购机攻略

时间限制：1000ms内存限制：256MB提交通过率：12%

题目描述

小图灵准备购买一部新手机，他要根据参数评分、价格和颜值三个方面制定一套严格的购机攻略。具体是这样的：
第一步，性价比排序。小图灵会用参数评分除以价格，算出每部手机的性价比，性价比越高，排名越靠前。
第二步，颜值PK。小图灵会在性价比前k高的手机中选择颜值最高的，如果有多部手机的颜值并列最高，则选择编号最小的。它就将成为小图灵的新手机！
当然，可能有多部手机性价比相同，因此参与颜值PK的手机可能多于k部，小图灵将以性价比排名第k位的手机作为门槛，达到此门槛的手机都能参与颜值PK。
请问，究竟哪部手机能成为小图灵的新手机呢？

输入描述

第一行两个整数n和k，表示有n部手机可供选择，性价比前k位将进入颜值PK。
接下来n行，每行三个整数，第i行表示第i号手机的参数评分、价格和颜值。

输出描述

一行，一个整数，表示小图灵将会购买的手机编号。

样例1

输入复制

5 2 50 3000 85 99 6000 90 98 5000 70 36 2000 80 45 2500 95

输出

5

提示

对于30%的数据：n <= 10^3
对于60%的数据：所有手机的性价比都不相同
对于100%的数据：1 <= k <= n <= 10^5，1 <= 参数评分、价格、颜值 <= 10^5

样例解释
3号手机性价比最高，4号和5号并列第2，因此都能进入颜值PK。这三部手机中5号颜值最高，因此小图灵会购买5号手机。

  看完了题目，我第一时间就想到了贪心算法，然后是结构体，高效排序。在输入时记录编号并算出性价比，根据性价比排序，检查第k位是否与后面的元素性价比相同，尝试更新k。在前k个元素中挑选颜值最高的，颜值并列最高时挑选编号小的，就可以得到答案了。

购机攻略代码;

#include <bits/stdc++.h>
using namespace std;
struct phone 
{
    int cs,jg,yz,id;
    double xjb;
}a[100005];
bool cmp(phone x, phone y) 
{
    return x.xjb > y.xjb; 
}
int main() 
{ 
    int n,k,maxi=0; 
	scanf("%d%d",&n,&k); 
	for(int i=1;i<=n;i++) 
	{ 
	    scanf("%d%d%d",&a[i].cs,&a[i].jg,&a[i].yz);
	    a[i].id=i; 
		a[i].xjb=(double)a[i].cs/a[i].jg; 
	}
	sort(a+1,a+n+1,cmp); 
	while(a[k].xjb==a[k+1].xjb) 
	  k++; 
    for(int i=1;i<=k;i++)
      if(a[i].yz>a[maxi].yz||a[i].yz==a[maxi].yz&&a[i].id<a[maxi].id) 
	    maxi=i;
    printf("%d",a[maxi].id); 
	return 0; 
}

  最后一道题“暑假作业” 

题目名称：暑假作业

时间限制：1000ms内存限制：256MB提交通过率：23%

题目描述

今天是学期的最后一天，小图灵抱着一摞暑假作业愉快地回家了。到家一看，他需要在m天假期内完成n项作业，这可得好好规划一下。小图灵预计第i项作业需要ai分钟完成，但他每天只愿意写k分钟作业，而且一天内只会写一项作业的一部分或全部，即使时间富裕，他也不会在同一天开始写下一项作业。小图灵想知道，在确保完成所有作业的情况下，k的最小值需要是多少。

输入描述

共两行，第一行包含两个整数n和m，第二行n个整数表示ai。

输出描述

一行，一个整数，表示k的最小值。（k可能超过地球上一天的总分钟数。）

样例1

输入复制

5 8 30 50 20 40 70

输出

35

提示

对于60%的数据：n * m <= 10^8
对于100%的数据：1 <= n <= m <= 10^5，1 <= ai <= 10^5

  看了一眼10^5，心中叹了一口气，暴力枚举是肯定要超时的，那么比暴力枚举更快速的算法是什么呢？我眼睛一亮，想到了二分算法，答案至少是1，不可能为0，至多是最大的元素，得到初始区间。每次取中间值，遍历数组统计需要的分钟数，大于规定时间则尝试每天多做些题，否则尝试每天少做些题，直到查找区间不存在就停止while循环。

二分代码：

#include <bits/stdc++.h> 
using namespace std; 
int main() 
{
	int n,m,a[100005],l=1,r=0; 
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) 
	{ 
	    scanf("%d",&a[i]); 
		r=max(r,a[i]);
	} 
	while(l<=r) 
	{ 
	    int mid=(l+r)/2,cnt=0;
	    for(int i=1;i<=n;i++) 
		  cnt+=ceil((double)a[i]/mid); 
		if(cnt>m) 
		  l=mid+1; 
		else 
		  r=mid-1;
	}
    printf("%d",l); 
	return 0; 
}

    这个3级学业水平测试还是有点难度的，比普及组的题只差了一两筹，4级测试应该和普及组差不多难度了吧!明天继续开始搞，加油！