3级学业水平测试

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

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

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

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

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

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

输入复制

5 3 3

输出

11

输入复制

10 8 11

输出

12

3 <= n, a, b <= 100

  首先，我们可以设置三个变量，a1和b1，sum,分别代表着目前有几个盖子，几个空瓶子，目前喝了几瓶橙汁。然后进行取模，之后又将换来的橙汁喝掉，一直循环下去，循环到什么时候呢？就是a1

橙汁计划升级版代码：

#include
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

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

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

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

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

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

输入复制

8 3 3 2 1 2 1 3 2 3

输出

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 
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	int a[n],sum[100005]={0},t=-1;
	for(int i=0;i>a[i];
	for(int i=0;i 
  然后我们看看第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 
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< 
  虽说对了，但是
 
有四个样例超时了。
 
  于是我想到了递推，动手在纸上写了一回儿会，我有了一点思路，将参数m和n对应到二维数组里的行与列，可以就可以递推解答了！
 
递推代码：
 
#include 
using namespace std;
int main()
{
	int m,n,f[1000][1000]={0};
	scanf("%d %dn",&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 
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
 
  最后一道题“暑假作业” 
 
题目名称：暑假作业 
时间限制：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  
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级测试应该和普及组差不多难度了吧!明天继续开始搞，加油！
                
        
        

  
    
      
        
      
      
        
          暑期编程PK赛
          
        
        得CSDN机械键盘等精美礼品！