锐客网

  1. 首页 > it技术 > >

蓝桥杯|蓝桥杯31天冲刺打卡（Day9）

蓝桥杯c++

Hallo，小伙伴们！没错！又是我——永遇乐，不知不觉就已经第九天了，今天我继续带领你们解答蓝桥杯的题目。俗话说得好：冰冻三尺非一日之寒，所以我们做题也要持之以恒呀！各位小伙伴，你们准备好与我共同继续前行了吗？
今天有四道题目，也不算太难，没涉及什么算法，主要是模拟和数学。让我们遨游于题海中吧！

A 最大乘积 蓝桥杯|蓝桥杯31天冲刺打卡（Day9）
文章图片


回顾老题： 博主看到的时候就心想：这怎么和昨天的神奇算式这么像！！！
神奇算式原题及题解传送门
蓝桥杯|蓝桥杯31天冲刺打卡（Day9）
文章图片


解析：
打眼儿一看，这是一道模拟题，这道题目要求我们式子左边的两个数共包含1~9，9位数字，式子右边要求我们也是9位数（1~9不同的数字），所以我们需要用数组判定两边的数位中是否出现相同的数，而且我们看到例子中的9*87146325 = 784316925，看到这个乱序的数，我们想到了什么？没错！就是C++中的全排列函数，到这里我们成功了一大半了。题目问的是乘积最大是多少，我们当然会不自主地想到max函数。到这里，本题就已经分析完毕，接下来让我们看看具体如何实现吧！

代码：
#include #define INF 0x3f3f3f3f using namespace std; typedef long long LL; LL maxn; int a[10]= {0,1,2,3,4,5,6,7,8,9},b[10]; //a用于全排列，b用于判断数位上的数是否有重复 bool check() { for(int i=1; i<=9; i++) if(b[i]==0) return false; return true; }int main() { do { for(int i=1; i<9; i++) { LL s1=0,s2=0; memset(b,0,sizeof(b)); //清零for(int j=1; j<=i; j++) s1=s1*10+a[j]; //从9位数中的8处地方的某一处划分成两个数for(int j=9; j>i; j--) s2=s2*10+a[j]; //cout<



B 阶乘约数 蓝桥杯|蓝桥杯31天冲刺打卡（Day9）
文章图片


解析：
小伙伴们，看到100！的瞬间傻眼了吧？博主当时也傻了，这100！多大不说，还要我求有几个正约数，这该咋求啊？算出来再一个一个去求？那根本不可行呀！long long也只能存到20！，所以我们肯定不用这个方法，所以我在网上查了一下，发现两个定理：唯一分解定理和约数和定理。
唯一分解定理：蓝桥杯|蓝桥杯31天冲刺打卡（Day9）
文章图片

【蓝桥杯|蓝桥杯31天冲刺打卡（Day9）】 大概意思就是任意大于1的数都能通过素数相乘而得到。
约数和定理：对于一个大于1正整数n可以分解质因数：n=p1^a1*p2^a2*p3^a3*…*pk^ak,则由 约数个数定理可知n的正约数有(a?+1)(a?+1)(a?+1)…(ak+1)个。
通过以上两个定理，这题就变得非常简单了。100！=1*2*......*100，那么我们可以将其中的非素数通过分解质因数变成素数，这样就符合唯一分解定理了，然后用数组存储这些素数的个数，到最后用一个for配合约数和定理便大功告成了。

代码：
#include using namespace std; typedef long long LL; int a[100]; LL s=1; int main() { for(int i=2; i<=100; i++) { //唯一分解定理 int j=i; for(int k=2; k<=j; k++) { //分解质因数 while(j%k==0) { a[k]++; //存储分解出素数的个数 j/=k; } } } for(int i=2; i<=100; i++) if(a[i]>0) s=s*(1+a[i]); //约数和定理 cout<




C 含2天数蓝桥杯|蓝桥杯31天冲刺打卡（Day9）
文章图片


解析： 这是一道非常简单的模拟题，就是枚举1900年1月1日到9999年12月31日的所有日期，并判定年月日中是否含2这个数字，注意判断闰年。

代码：
#include #include #include using namespace std; int date[]= {0,31,28,31,30,31,30,31,31,30,31,30,31}; int sum=0; bool check(int n) { while(n) { if(n%10==2) return true; n/=10; } return false; }int main() { for(int year=1900; year<=9999; year++) { if(year%400==0 || (year%4==0 && year%100!=0)) date[2]=29; //闰年 else date[2]=28; for(int month=1; month<=12; month++) for(int day=1; day<=date[month]; day++) { if(check(year) || check(month) || check(day)) sum++; } } cout<



D k倍区间 蓝桥杯|蓝桥杯31天冲刺打卡（Day9）
文章图片

输出：6

解析： 这道题是一道典型的前缀和和同余定理的题目，你也可以理解为是一道数学题。小伙伴们可能并不知道前缀和和同余定理是什么，下面我给大家科普一下。
一维前缀和：假设x1,x2,...,xn是元素，y1,y2,...yn是存储前缀和的容器，那么y1=x1, y2=x1+x2, y3=x1+x2+x3,y4=x1+x2+x3+x4,...yn=x1+x2+x3+...+xn，像这样关系的就是一维前缀和。为什么我要说这是一维前缀和呢？因为还有二维的，三维的，甚至n维的。
同余定理：《离散数学》中是这样定义的： 设m是正整数，a和b是整数.如果m | a-b，则称a模m同余于b，或a与b模m同余.其充要条件是：a与b除以m的余数相等，即a mod m = b mod m。
题目说到连续子序列，也就是[1,5],[1,2],[2,3],[10,100]......形如这样的序列。而前缀和为什么适用于本题，例如：[1,5]则S5，[5,9]则S9-S4，这里面的Si都是前缀和（前i个数相加）。题中说到连续子序列之和是k的倍数，则称其为k倍区间，问有几个。
用样例举例吧。样例输入5个数，k=2，也就是连续子序列之和要是2的倍数。前缀和就是s1=1, s2=3, s3=6, s4=10, s5=15，那么哪里用到了同余定理呢？
我们仔细观察一下，s1,s2,s5都是除以2余1，s3,s4除以2余0，这说明什么？说明：s2-s1, s5-s1, s5-s2, s3, s4, s4-s3 都是k倍区间。s2-s1=2, s5-s1=14，正好就是2的倍数。
因此我们可以先求得前缀和，再找出前缀和相同的余数有几个，再将其分类相加。这里注意一下，s1,s2,s5是余1，共3个，即(n-1)*n/2个；而s3,s4余0，也就是本身也是2的倍数，所以也有3个，即(n+1)*n/2个。
代码：
#include #include #include using namespace std; typedef long long LL; int n,k; int a[100005]; LL s[100005],sum[100005],cnt; int main() { cin>>n>>k; for(int i=1; i<=n; i++) { cin>>a[i]; s[i]=s[i-1]+a[i]; //前缀和 } for(int i=1; i<=n; i++) sum[s[i] % k]++; // 算同余的个数 for(int i=0; i


    推荐阅读


    上一篇：#|蓝桥杯31天冲刺打卡题解（Day10）

    下一篇：蓝桥杯|蓝桥杯AcWing学习笔记 4-3排序的学习（附相关蓝桥真题（小朋友排队）(Java)）