第一题 最大乘积
题目描述
解题报告
这个是老老实实的枚举题了。
提前将1~9存放到一个数组中，前排列枚举所有情况，然后判断结果是否符合条件较好，可以dfs，也可以直接使用STL容器中next_permutation
参考代码(C++版本)
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long LL; int a[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; int st[10]; LL res; //补全判断是否合法的check函数 bool check(int n) { //每次调用这个函数的时候，要将准备用来判断的st数组清零 memset(st, 0, sizeof st); LL tmp = n; while(tmp) { st[tmp % 10] ++;//把这个取出来的数，放到st数组的，并且标记这个数，放置的次数 tmp /= 10; } //统计是否出现了多的，或是少的 for(int i = 1;i <= 9;i++) if(st[i] > 1 || st[i] ==0) return false; return true; } int main() { //全排列枚举，让a数组组合出所有情况，把这些情况处理为因数，再进行乘法 do{ for(int i = 1;i < 8;i++) { LL x1 = 0,x2 = 0; int j = 0,z = i; while(j < i) x1 = x1*10 + a[j++]; while(z < 9) x2 = x2*10 + a[z++]; //判断以及统计最大值 if(check(x1*x2)) res = max(res,x1*x2); } }while(next_permutation(a,a+9)); //输出最大值 cout << res << endl; return 0; }
第二题 阶乘约数
题目描述
解题报告
1、关于约数
这是小学知识了，约是约分的约。比如6,整数2可以和它进行约分 ，也就是能够整除，那么2就是6的约数。
2、定理运用
这个题按照官说法是要利用唯一分解定理进行求解，咱也不知道这个定理，咱就直接分解因数的…
假如不明白为什么我直接这么分解的，可以点击看看这篇文章
3、细节
可能有小可爱想先将100的阶乘算出来。再去慢慢分解因数的。
但是因为100的阶乘太大了，long long 都超过了，因为每个数的约数是彼此独立的，所以可以使用乘法定理，即：1的约数的个数 * 2的约数的个数 * 3的约数个数 …
参考代码(C++版本)
//唯一分解定理 //就是我总结的那个题 #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<cstring> using namespace std; int a[110]; int main() { memset(a,0,sizeof(a)); int n = 100; for(int i=2;i<=n;++i) { int j = i; for(int k=2;k*k<=j;++k) { while(j % k==0) { j /= k; a[k]++; } } if(j > 1) a[j]++; } long long ans = 1; for(int i=2;i<=n;++i) { if(a[i]) ans *= (a[i]+1); } cout<<ans<<endl; return 0; }
第三题 含2天数
题目描述
解题报告
这里就一个老老实实的枚举了，枚举每年，注意判断闰年平年就好。
参考代码(C++版本)
#include <iostream> #include <cstring> #include <algorithm> using namespace std; bool leap(int x) { return (x % 400 == 0 || x % 4 == 0 && x % 100 != 0); } bool check(int n) { while(n) { if(n % 10 == 2) return true; n /= 10; } return false; } int main() { int cnt = 0; //直接从1900枚举到9999年 for(int i = 1900; i <= 9999; i ++) { //特殊处理年份包含2的，因为一整天他都开心了，此时只是需要考虑平年闰年 if(check(i)) { if(leap(i)) cnt += 366; else cnt += 365; } else { //手动算每个中，包含2天数 + 整个2月 + 整个12月。一样是考虑平年闰年 if(leap(i)) cnt += 180; else cnt += 179; } } //输出 cout << cnt << endl; return 0; }
第四题 K倍区间
题目描述
解题报告
首先可以从题目的意思中get到，它是想让我们求一段区间中的数字的和，再判断这个总和是否是K的倍数。
想到求区间和，那么咱们常用的是前缀和。至于一维前缀是怎么证明的，我这里不详细阐述啦，我最近几天会更出关于前缀和使用的总结博客。这里只是用结论。
对于前缀和，首先要进行的是预处理，才能够在O ( 1 ) O(1)O(1)的时间查询到指定区间的和。
预处理的时候会出现两个数组：一个是a[]数组，其中存放的是题目中输入的数据；一个是sum数组，其中存放的是0到第i个位置的区间的总和。
因为这个题要咱们求K的倍数，那么提前可以将前缀和区间取模
sum[i]=(sum[i-1]+a[i])%k;
这里经过取模之后，sum数组中存放的数据应该有0（是k的倍数）也应该有其他的（比如题目样例中，求2的倍数，那么有可能是1）。
分析题目样例
1 2 3 4 5
经过前缀和公式处理之后
1 3 6 10 15
进过取模K KK（这里K KK = 2）之后
1 1 0 0 1
这里精心观察这些取模之后的结果，其实可以发现K KK个余数相同的区间，又可以组成一个K倍区间.
比如这里两个余数为1的区间，又可以形成一个K倍区间；
假如K是3了，那么可能出现的余数情况是0，1，2,同样的，K KK个1，或者K KK个2有可以出现K KK的倍数，我是这种理解的，不知道看这篇文章的小伙伴觉得妥不妥当。
经过这番分析，那么我们的任务只是需要找到，有多少个取模之后想等的前缀和区间。
唯一需要注意的是，要加上前缀和为0，也就是第一次取模就已经是K的倍数的的情况
参考代码(C++版本)
#include <iostream> #include <algorithm> using namespace std; const int N=100010; typedef long long ll; int sum[N],a[N],res[N]; int n,k; ll ans=0; int main(){ cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; sum[i]=(sum[i-1]+a[i])%k;//前缀和取模 ans+=res[sum[i]];//更新答案 res[sum[i]]++;//两个相等的前缀和就能组成一个k倍区间 } cout<<ans+res[0]<<endl; return 0; }
