一、最大乘积
题目链接：最大乘积 - 蓝桥云课 (lanqiao.cn)
题目要求：
把 1 ~ 9 这 9 个数字分成两组，中间插入乘号，有的时候，它们的乘积也只包含 1 ~ 9 这 9 个数字，而且每个数字只出现 1 次。
比如：
984672 * 351 = 345619872 98751 * 3462 = 341875962 9 * 87146325 = 784316925 ...
符合这种规律的算式还有很多，请你计算在所有这些算式中，乘积最大是多少？
注意，需要输出的是一个整数，表示那个最大的积，只输出乘积，不要输出整个算式。
解题思路：
暴力全排列，将全排列数字分离成两个数字，判断有没有重复即可
#include<bits/stdc++.h> using namespace std; int a[11],b[11],s[11],ans; bool pd(int n)//判重 { while(n) { s[n%10]++; n/=10; } for(int i=1;i<10;i++) { if(s[i]!=1) { return false; } } return true; } int jia(int x, int y)//分解 { int t=0; for(int i=x;i<=y;i++) { t = t * 10 + a[i]; } return t; } void dfs(int x) { if(x==10) { for(int i=1;i<=8;i++) { int x = jia(1,i); int y = jia(i+1,9); } for(int i=1;i<=8;i++) { int x = jia(1,i); int y = jia(i+1,9); if(pd(x*y)) { ans = max(ans,x*y); } memset(s,0,sizeof(s)); } return; } for(int i=1;i<=9;i++) { if(!b[i]) { a[x] = i; b[i] = 1; dfs(x+1); b[i] = 0; } } } int main() { dfs(1); cout<<ans; return 0; }
二、阶乘约数
题目链接：阶乘约数 - 蓝桥云课 (lanqiao.cn)
题目要求：
定义阶乘 n! = 1 × 2 × 3 × · · · × n。
请问 100!（100 的阶乘）有多少个正约数。
解题思路：
用一个数学公式：
任意一个正整数 X 都可以表示成若干个质数乘积的形式，即 X = p1α1 ∗ p2α2 …… ∗ pnαn
约数个数 = (a1 + 1)(a2 + 1)……(an + 1)
100! 是个158位的数，我们先将1~100分别做因数分解，这些因数累乘起来，得到100!的因数分解。
#include<bits/stdc++.h> using namespace std; int a[100]; int main() { for(int i=2;i<=100;i++) { int n = i; for(int j=2;j<=n/j;j++) { while(n%j==0) { a[j]++; n /= j; } } if(n>1) { a[n]++; } } long long ans = 1; for(int i=2;i<=100;i++) { if(a[i]) { ans *= (a[i]+1); } } cout<<ans; return 0; }
三、含2天数
题目链接：含 2 天数 - 蓝桥云课 (lanqiao.cn)
题目要求：
小蓝特别喜欢 2，今年是公元 2020 年，他特别高兴，因为每天日历上都可以看到 2。
如果日历中只显示年月日，请问从公元 1900 年 1 月 1 日到公元 9999 年 12 月 31 日，一共有多少天日历上包含 2。即有多少天中年月日的数位中包含数字 2。
解题思路：
判断闰年，判断这个年份的位数是否带2，重点是这两个，如果年份没2，134567891011月份的带2日期是10*12，直接相加即可。
#include<bits/stdc++.h> using namespace std; bool pd(int y)//年份是否有2 { while(y) { if(y%10==2) { return true; } y /= 10; } return false; } bool run(int y)//闰年 { if(y%400==0||y%100!=0&&y%4==0) { return true; } return false; } int main() { int n = 0; int t = 0; for(int i=1900;i<=9999;i++) { if(pd(i)) { if(run(i)) { n = 366; } else { n = 365; } } else { if(run(i)) { n = 31 + 120 + 29; } else { n = 31 + 120 + 28; } } t += n; } cout<<t; return 0; }
四、k倍区间
题目链接：“蓝桥杯”练习系统
题目要求：
解题思路：
区间序列之和是k的倍数，两个区间之间的差值如果是k的倍数，则中间的数满足k倍区间；用前缀和记录一下，再遍历用乘法原理
#include<bits/stdc++.h> using namespace std; long long sum,ans,a[100010]; int main() { int n,k,x; cin>>n>>k; for(int i=1;i<=n;i++) { cin>>x; sum += x; a[sum%k]++; } for(int i=0;i { ans += a[i] * (a[i]-1)/2; } ans += a[0]; cout<<ans; }
今天的题千万要多多理解，尤其第二题第四题，大家加油。
