一.年号字串

题目链接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 <stdio.h>
#include <stdlib.h>

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]。

#include<stdio.h>

int 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]);
}

那么取余后的结果会不会影响下一个数的大小呢（这是一个需要思考的问题） 

第二种方法

#include<stdio.h>

int 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 <stdio.h>
#include <stdlib.h>
#include<stdbool.h>
int 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 <stdio.h>
#include <stdlib.h>
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<=）。

输出描述

输出一个整数代表答案。

输入输出样例

示例

输入

7
1 6 5 4 3 2 1

 输出

2

 思路

求出每个深度对应数的总和，这里用一个sum数组确定每一深度对应的权值之和，然后求这个数组的最大值。

这里 k=log(i)/log(2)来源于下面这个公式

 说明：看一下第三层 A4~A7把 i= 4~7分别代入公式，发现k都为2；

#include <stdio.h>
#include <stdlib.h>

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<=。

输出描述

输出一个整数表示答案。

输入输出样例

示例

输入

5
2 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 <stdio.h>
#include <stdlib.h>
#include <math.h>
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;
}