三. 完善程序

1.

题目描述:

你可以操控充气城堡里的充气大炮向前方的水池里发射一些小炮弹。在任何时候，相同体积的两个炮弹不能在水池中共存，它们会立即合成出一个更大的炮弹，其体积等于这两个小炮弹的体积之和。

例如：发射三个体积分别为2、2、4的炮弹，那么两个体积为2的炮弹会合成出一个体积为4的炮弹，此时两个体积为4的炮弹又会合成出一个体积为8的炮弹。

---

现在你总共向水池中发射了 $n$ 枚炮弹，求：

（1）全部发射完毕后水池中炮弹的数量；

（2）水池中最大的炮弹的体积；

（3）水池中最小的炮弹的体积。

输入:

第一行：一个整数 $n$，表示发射的炮弹数量；

第二行：$n$ 个整数，分别表示已经发射的每个炮弹的体积。

输出:

三个整数，分别为题目描述中第（1）、（2）、（3）小题的答案，以空格分隔。

数据限制:

$1≤n,v≤10^6$。

备注:

$log_210^6≈16.6$。

#include<bits/stdc++.h>
using namespace std;
___1___;
int a[maxn];
int main() {	
	int n,tmp;
	cin>>n;
	int maxv=0,minv=0,cnt=0;
	for(int i=1; i<=n; i++){
		cin>>tmp;
		___2___;
	}
	for(int i=1; i<=maxn; i++){
		while(a[i]>1){
			___3___;
			a[i*2]++;
		}
		if(___4___){
			cnt++;
			if(i>maxv) maxv=i;
            if(___5___) minv=i;
		}
	}
	printf("%d %d %d",cnt,maxv,minv);
	return 0;
}

41.空白1处应该填写的代码为（）{{ select(41) }}

• const int maxn=1e6+10
• const int maxn=2e6+10
• const int maxn=1e7
• const int maxn=2e7

42.空白2处应该填写的代码为（）{{ select(42) }}

• a[i]=tmp
• a[i]=1
• a[tmp]=1
• a[tmp]++

43.空白3处应该填写的代码为（）{{ select(43) }}

• a[i]=a[i]-1
• a[i]=a[i]-2
• a[i]=a[i]/2
• a[i]=0

44.空白4处应该填写的代码为（）{{ select(44) }}

• a[i]==1
• a[i]>1
• a[i*2]>1
• a[i*2]>0

45.空白5处应该填写的代码为（）{{ select(45) }}

• i<minv
• i<minv && a[i]>0
• i<maxn
• minv==0

2.

题目描述:

现有 $n$ 根长度不一定相等的火柴棒，每根火柴棒都有唯一的一个编号。（这意味着即便有一些火柴棒长度相等，它们也被看作是不一样的火柴棒。）从中拿三根组成一个等腰三角形，有几种拿法？

输入:

第一行：一个整数 $n$，表示火柴棒的数量；

第二行：$n$ 个整数，分别表示每根火柴棒的长度。

输出:

一个整数，表示可行的方案数。

数据限制:

$3≤n≤1000$；每根火柴棒的长度不超过$500$。

备注:

本题算法为：先挑选2根等长的火柴棒作为等腰三角形的腰，再挑选长度合适的第三根火柴棒作为底边。显然，第三条边的长度可以分三类讨论：比腰短、与腰等长、比腰长。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int a[maxn];

/*
C(x,y)函数表示从y个数中挑选x个数的方案数。
其数学公式经过化简后可以表示为：C(x,y)=y(y-1)(y-2)...(y-x+1)/x!。
例如：从8根火柴棒中挑选3根，可供选择的方案数为：C(3,8)=8*7*6/(1*2*3)=56种。
*/

int C(int x, int y){
	int sum=1;
	for(int i=1; i<=x; i++){
		sum*=y;
		___1___;
		y--;
	}
	return sum;
}

int main() {	                   
	int n;
	cin>>n;
	int t;
	for(int i=1; i<=n; i++){
		cin>>t;
		a[t]++;
	}
	int cnt_left=0;
	int sum=0;
	for(int i=1; i<maxn; i++){
		if(a[i]>=2){
        //从比腰短的火柴棒中挑选
    		___2___;
      //从与腰等长的火柴棒中挑选
			if(a[i]>=3){
        		___3___;
			}
      //从比腰长的火柴棒中挑选
			for(___4___){
				sum+=C(2,a[i])*a[j];
			}
		}
		___5___;
	}
	cout<<sum;
	return 0;
}

46.空白1处应该填写的代码为（）{{ select(41) }}

• sum/=x
• sum/=i
• sum/=(y-x)
• sum/=(x f-i)

47.空白2处应该填写的代码为（）{{ select(42) }}

• sum+=C(2,a[i])*cnt_left
• sum+=a[i]*cnt_left
• sum+=(a[i]-2)*cnt_left
• sum+=cnt_left

48.空白3处应该填写的代码为（）{{ select(43) }}

• sum+=a[i]
• sum+=C(3,a[i])
• sum+=1
• sum+=a[i]-2

49.空白4处应该填写的代码为（）{{ select(44) }}

• int j=i; j<maxn; j++
• int j=a[i]; j<maxn; j++
• int j=i+1; j<2*i; j++
• int j=i; j<=2*i; j++

50.空白5处应该填写的代码为（）{{ select(50) }}

• cnt_left++
• cnt_left=a[i]
• cnt_left+=i
• cnt_left+=a[i]