蓝桥杯专题（一）《C语言》
一.年号字串
题目链接https://www.lanqiao.cn/problems/605/learning/
小明用字母 A 对应数字 1，B 对应 2，以此类推，用 Z 对应 26。对于 27 以上的数字，小明用两位或更长位的字符串来对应，例如 A A对应 27，AB 对应 28，AZ 对应 52，LQ 对应 329。
请问 2019 对应的字符串是什么？
思路
A~Z分别对应数字1~26，这个不难理解。
解释一下LQ：先对329取余，然后再对329相除，这样下去直到329为0结束过程。
329%26=17，17对应的就是题目说的 Q ，而在计算机中应该再加64（64对应的ASCII码为@，65 对应字符A，想一下为什么这里不加65而加64）,再让329/26=12，再让12%26=12，此时12 对 应的就是 L 。
#include #include int main(int argc, char *argv[])//这里main括号内的不用管，就相当于main（）,因为括号内的变量在主函数没有用到{ // 请在此输入您的代码 char s[5]; int sum=2019;int i=0; while(sum!=0) { s[i++]=sum%26+64; sum/=26; } for(int j=i-1;j>=0;j--) //从后遍历 { printf("%c",s[j]); } return 0;}二.数列求值
题目链接https://www.lanqiao.cn/problems/600/learning/
给定数列 1, 1, 1, 3, 5, 9, 17，⋯，从第 4 项开始，每项都是前 3 项的和。
求第 20190324 项的最后 4 位数字。
思路
这道题和斐波那契数比较相似，感兴趣的童鞋可以看一看 ——> 斐波那契数
一种方法可以用一个数组 a，a1=[1], a2=[1], a3=[1],那么求之后的每一项就是a[n]=a[n-1]+a[n-2]+a[n-3]。
#includeint main(){int a[20190324]={1,1,1}; for(int i=3;i<20190324;i++) { a[i]=(a[i-1]+a[i-2]+a[i-3])%10000; //因为需要取后4位数字 } printf("%d",a[20190323]);}那么取余后的结果会不会影响下一个数的大小呢（这是一个需要思考的问题）
第二种方法
#includeint main(){ int a = 1, b = 1, c = 1;int d; for (int i = 4; i <=20190324; i++) { d = (a + b + c)%10000;//因为题目说过要后4位，所以呢对数取余10000 a = b; b = c; c = d; } printf("%d",d); return 0;}三.数的分解
题目链接https://www.lanqiao.cn/problems/606/learning/
把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包含数字 2 和 4，一共有多少种不同的分解方法？
注意交换 3 个整数的顺序被视为同一种方法，例如 1000+1001+18和 1001+1000+18 被视为同一种。
思路
让数字对10进行取余，判断2和4是否出现，循环比较简单，看如下代码，注意注释的一些细节就可以了
#include #include #includeint judge(int n) //判断是否有2和4的出现{ while(n) { if(n%10==2||n%10==4)return false; n/=10; }return true;}int main(){ // 请在此输入您的代码 int k; int cnt=0; for(int i=1;i<2019;i++) { for(int j=1;j<2019;j++) { k=2019-i-j; if(i<j&&j<k&&judge(i)&&judge(j)&&judge(k)) //注意这里i<j&&j<k不能写成i<j<k { cnt++; } } } printf("%d",cnt); return 0;}四.特别数的和
题目链接https://www.lanqiao.cn/problems/191/learning/
小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。
请问，在 1 到 n 中，所有这样的数的和是多少？
思路
与上面一道题比较类似，主要是取余判断2，0，1，9的出现
#include #include int judge(int n){ while(n){ if(n%10==2||n%10==1||n%10==1||n%10==9||n%10==0)return 1; n/=10;}return 0;}int main(int argc, char *argv[]){ int cnt=0; // 请在此输入您的代码 int n; scanf("%d",&n); for(int i=1;i<=n;i++) { if(judge(i))cnt+=i;//if(judge(i))表示if judge(i)不等于0 } printf("%d",cnt); return 0;}if(judge(i))等同于 if(judge(i)!=0)
五.完全二叉树的权值
题目链接https://www.lanqiao.cn/problems/183/learning/题目描述
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从 上到下、从左到右的顺序依次是 A1, A2, ··· AN如下图所示：
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点 权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 1。
输入描述
第一行包含一个整数 N（1<=N<=）。
第二行包含 N 个整数 A1, A2, ··· AN （-<=N<=
）。
输出描述
输出一个整数代表答案。
输入输出样例
示例
输入
71 6 5 4 3 2 1输出
2思路
求出每个深度对应数的总和，这里用一个sum数组确定每一深度对应的权值之和，然后求这个数组的最大值。
这里 k=log(i)/log(2)来源于下面这个公式
说明：看一下第三层 A4~A7把 i= 4~7分别代入公式，发现k都为2；
#include #include int main(int argc, char *argv[]){ int temp=0,i,k; int ans,max=0,n; int sum[100001]={0}; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&temp); k=log(i)/log(2)+1; //k表示每个i所对应的深度 sum[k]+=temp; } int deep=log(n)/log(2)+1; //deep为n对应的深度 for(i=1;i<=deep;i++) { if(max<sum[i]) { max=sum[i]; ans=i; } } printf("%d",ans);return 0;}六.等差数列
题目链接https://www.lanqiao.cn/problems/192/learning/
题目描述
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？
输入描述
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,··· ,AN。(注意 A1 ∼ AN 并不一定是按等差数列中的顺序给出)
其中，2<=N<= , 0<=Ai<=
。
输出描述
输出一个整数表示答案。
输入输出样例
示例
输入
52 6 4 10 20输出
10样例说明： 包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。
思路
先排序然后找最大和最小值，找公差 求等差数列个数a[n-1]-a[0])/x+1
#include #include #include const int maxn=100010;int cmp(const void*a,const void*b) //排序从小到大{ return*(int*)a-*(int*)b;}int main(){ int n,a[maxn]; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a[i]); } qsort(a,n,sizeof(int),cmp);//从小到大排序 int x=a[1]-a[0]; for(int i=1;i<n-1;i++) //找最小值 x=fmin(x,a[i+1]-a[i]); if(x!=0) printf("%d",(a[n-1]-a[0])/x+1); else printf("%d",n); return 0;}