计协第一周算法赛大一组题解

A - A+B Problem

这道题，啊，洛谷经典题，你翻开那B题解啥解法都有

签到题嘛随便写 ~~(珍爱时间，拒绝int c=a+b;)~~

1
2
3
4
5
6
7
8
#include <iostream>
using namespace std;
int main() {
    int a,b;
    cin>>a>>b;
    cout<<a+b;
    return 0;
}

B - 成绩

这道题最精髓的点在于下面的Hint

1
2
3
4
数据说明
对于 30% 的数据，A=B=0。
对于另外 30% 的数据，A=B=100。
对于 100% 的数据，0≤A,B,C≤100 且 A,B,C都是 10 的整数倍。

如果不分类的话，那大可以

1
2
cin>>a>>b>>c;
cout<<a*0.2+b*0.3+c*0.5;

但是如果分类的话，代码是

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
cin>>a>>b>>c;
if (a==b){
	if (a==0){
		cout<<c*0.5;
	}else{
		cout<<50+c*0.5;
	}
}else{
	cout<<a*0.2+b*0.3+c*0.5;
}

那么说，

对于30%的数据，直接计算c的成绩，就可以省下两次乘法和两次加法

对于30%的数据，计算c的成绩+50，就可以省下两次乘法和一次加法

这不爽省一波时间？

C - 闰年判断

先判断是否100倍数，如果否再看能否被4整除，如果是就看能否被400整除

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
int main(){
	int a;
	cin>>a;
	if(a%100!=0){
		if(a%4==0){
			cout<<"1";
		}else{
			cout<<"0";
		}
	}else{
		if(a%400==0){
			cout<<"1";
		}else{
			cout<<"0";
		}
	}
	return 0;
}

D - 陶陶摘苹果

算法优化重点在于，是否先把身高和凳子高度相加

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
int main(){
	int a[10],num,count=0;
	for(int k=0;k<10;k++){
		cin>>a[k];
	}
	cin>>num;
	num+=30;
	for(int k=0;k<10;k++){
		if(a[k]<=num){
			count+=1;
		}
	}
	cout<<count;
	return 0;
}

如果没有预先加上凳子高度，只在第二个for中比较的时候使用if(a[k]<=num+30)的话，那么num+30会被多计算9次 ~~⑨次啊⑨次~~

E - 月落乌啼算钱（斐波那契数列）

** ~~遇事不决，打表万岁！~~ **

因为数据实在太小，为了时间索性打表

（实际比赛当中一定要结合题意和限制权衡算法，当然时间复杂度优先）

打表部分代码(用于生成表 ~~(也是生成斐波那契数列的)~~ )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include<iostream>
using namespace std;
int main(){
	long num[49]={0,1,1,2};
	for(int i=4;i<49;i++){
		num[i]=num[i-1]+num[i-2];
	}
	for(int i=0;i<48;i++){
		cout<<num[i]<<",";
	}
	cout<<num[48];
	return 0;
}

然后把表倒腾进去，写查表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#include<iostream>
using namespace std;
int main(){
	long a[49]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976};
	int k=0;
	cin>>k;
	printf("%.2f",double(a[k]));
    //或者cout<<a[k]<<".00";
	return 0;
}

F - 金币

没啥好说的，看注释吧

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;
int main(){
	long long n=0; //总得到金币数，和下面的a一样要初始化
	int k,a=0; //k储存天数，a储存已经给的天数，a必须初始化
	cin>>k;
	for(int i=1;;i++){
		if(k>=a+i){ //如果这一轮给完还有剩余或刚好给完
			for(int j=0;j<i;j++){
				n+=i;
				a++;
			}
		}else{ //这一轮中就给完
			for(int j=0;j<k-a;j++){ //上一轮刚好给完而进入这个else代码块的话，由于k-a=0，for跟没有一样
				n+=i;
			}
			break; //跳出
		}
	}
	cout<<n;
}

G - 杨辉三角

** ~~遇事不决，打表万岁！~~ **

这道题其实可以搞字符串打表，即这样：

1
2
3
4
string s1="1";
string s2="1 1";
string s3="1 2 1";
…………

嗯，打表是很好，但是我已经懒得写打表程序了

所以还是老老实实写程序吧

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
int main(){
	int n,a[21][21]={}; //老老实实初始化嗷
    cin>>n;
    a[1][1]=1; //预存一个
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            a[i][j]=a[i-1][j-1]+a[i-1][j]; //把上一行的数和上一行左边的数加在一起，两边因为边界的关系计算永远是0+1(所以初始化很重要，不然万一加到114514了呢(划掉) )
        }
    }
    for(int i=1;i<=n;i++){ //打表输出
        for(int j=1;j<=i;j++){
        	cout<<a[i][j]<<" ";
		}
        cout<<endl;
    }
    return 0;
}

H - 选数

** 递归是个好东西，~~地瓜也是~~ **

求是否是素数就一暴力取%，真想拿分还得线性筛(欧拉筛)

1
2
3
4
5
6
int get_num(int m){
	for(int i=2;i<m;i++){
		if(m%i==0) return 0; //如果被整除就返回0
	}
	return 1; //没有被整除过才会到这，返回1
}

然后就是核心递归部分，上注释！

（反正流程就跟十个人握手求多少组合那个9+8+7+balabala那玩意差不多，不过这变成k个人一起牵手手）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void chooe_num(int x,int y){ //x表示还要取多少个数字，y表示数组上一次取值的下标
	if(x==0){ //如果剩下没有可加的了，那就判断和是否为素数
		ans+=get_num(sum_add); //如果是素数，返回值为1，ans++；如果不是素数，返回值为0
	}
	else{
		y++; //下标右移一位，此时a[y]为可取数字的第一个
	    for(int i=y;i<=n;i++){ //循环取数
	    	sum_add+=a[i]; //将数字加入和
	    	x--; //已经选了一个所以剩余可选的数字-1；
	    	choose_num(x,i); //选下一个(如果没得选的话x=0，就是上面那种直接去判断了)
	    	sum_add-=a[i]; //判断完毕，减去当前数字，恢复没选这个值的时候的sum_add
	    	x++; //可选数字+1(上一个已经放回去了)
		}
	}
}

整体代码就是

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
int n,k,sum_add,ans,a[21];
int get_num(int m){
	for(int i=2;i<m;i++){
		if(m%i==0)
		return 0;
	}
	return 1;
}
void choose_num(int x,int y){
	if(x==0){
		ans+=get_num(sum_add);
	}
	else{
		y++;
	    for(int i=y;i<=n;i++){
	    	sum_add+=a[i];
	    	x--;
	    	choose_num(x,i);
	    	sum_add-=a[i];
	    	x++;
		}
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	choose_num(k,0);
	cout<<ans;
	return 0;
 } 

后记

我要看🐟总的B组题解！（超大声）