算法每日一题9

每日一题

每日一题系列旨在督促本人坚持算法练习，并期望将之养成一个习惯。

1、小蓝吃糖果

lanqiao-1624：小蓝吃糖果 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月6日

tags：鸽笼定理（抽屉定理）

$\textcolor{red}{分析：}$

1. 鸽巢原理，用“隔板法”求解。

2. 最多的一种糖果，把它的数量K看成K个隔板，隔成K个空间（把每个隔板的右边看成一个空间）；其它所有糖果的数量为S。

   （1）如果S < K-1，把S个糖果放到隔板之间，这K个隔板不够放，必然至少有2个隔板之间没有糖果，由于这2个隔板是同一种糖果，所以无解。

   （2）S ≥ K-1时，肯定有解。其中一个解是：把S个糖果排成一个长队，其中同种类的糖果是挨在一起的，然后每次取K个糖果，按顺序一个一个地放进K个空间。由于隔板数量比每一种糖果的数量都多，所以不可能有2个同样的糖果被放进一个空间里。把S个糖果放完，就是一个解，一些隔板里面可能放好几种糖果。

解决代码：

#include<bits/stdc++.h>
using namespace std;
int a[1005000];
int main(){
    long long sum=0;
    int Max=0;
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum += a[i];              //所有糖果数量
        if(a[i]>Max)  Max=a[i];   //最多的一种糖果
    }
    if(sum-Max+1>=Max) printf("Yes\n");
    else               printf("No\n");
return 0;
}

2、杨辉三角形

lanqiao-1457：杨辉三角形 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月7日

tags：二项式、组合数、杨辉三角

$\textcolor{red}{分析：}$

1. 通过观察不难发现，如果某一行的第二个数是n，那么第三个数就绝对是$C_n^2$=n(n-1)/2，因此，当n=44732的时候，第三个数绝对是44732x44731/2 = 1,000,453,546 > 10亿，你第三个数都已经大于10亿了，杨辉三角除了第二个数外其他都是递增的，所以最后需要加上n * (n + 1) / 2 +2计算出n必定会出现的位置，防止程序无输出的情况。

2. 自滚动数组计算杨辉三角，由于杨辉三角的对称性，我们只需要计算前半三角即可，a[0]表示的是第1列(第1列全为1)；

3. 如果i为奇数行并且j为奇数行的最中间一列，那么当前数就等于上一行前一个数的2倍，因为上一行的a[j-1]=a[j]；否则等于上两个数相加。

解决代码：

#include<bits/stdc++.h>
using namespace std;
//  杨辉三角形
// N的范围是1~10亿 
// 若某行的第二个数是n，当n=44732的时候，第三个数绝对是44732x44731/2 = 1,000,453,546 > 10亿
using ll = long long;
ll a[44732]; // 自滚动数组计算杨辉三角，由于杨辉三角的对称性，我们只需要计算前半三角即可，a[0]表示的是第1列(第1列全为1) 
ll n;

int main() {
	cin>>n;
	if(n==1){// 恒为1的话第一次出现就是第一个数 
		cout<<1;
		return 0;
	}
	a[0] = 1;// 第一列全为1 
	for(int i=3;i<44732;++i){// 从第3行开始 
		for(int j=i/2;j>0;--j){
			if(j==i/2&&i%2==1){// 如果i为奇数行并且j为奇数行的最中间一列，那么当前数就等于上一行前一个数的2倍，因为上一行的a[j-1]=a[j] 
				a[j] = 2*a[j-1];
			}else{// 否则等于上两个数相加 
				a[j] = a[j-1] + a[j];
			}
			if(a[j]==n){// 第一次找到 
				cout<<(i-1)*i/2+j+1;// 计算前i-1行的元素个数加上当前行的列号j，注意列号从0开始，所以需要再+1
				return 0; 
			}
		}
	}
	cout<<n*(n+1)/2+2;
	return 0;
}

3、

lanqiao-1457：杨辉三角形 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月7日

tags：二项式、组合数、杨辉三角

$\textcolor{red}{分析：}$

解决代码：

4、星期一

lanqiao-611：星期一 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月7日

tags：简单数学

$\textcolor{red}{分析：}$

1. 遍历从1901到2000年的每一年，判断是否是闰年，如果是闰年则总天数+366；否则总天数+365，最后除以7即可，结合1901 年 1 月 1 日是周几，得到最后有多少个周一。

2. 注意：1901年1月1日是星期二（可以通过Excel得到，或者根据当前日期推导2000年12月31日是星期几）。

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 星期一 
using ll = long long;
ll res = 0;
bool is_r(int n){
	if(n%4==0&&n%100!=0||n%400==0){
		return true;
	}
	return false;
}

int main() {
	for(int i=1901;i<=2000;++i){
		if(is_r(i))res += 366;
		else res += 365;
	}
	int ans = res / 7;
	cout<<ans<<endl;
	return 0;
}