蓝桥杯第五天刷题

第一题：数的分解

题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包含数字 2和 4，一共有多少种不同的分解方法？
注意交换 3 个整数的顺序被视为同一种方法，例如 1000+1001+181000+1001+18 和 1001+1000+181001+1000+18 被视为同一种。
运行限制
最大运行时间：1s
最大运行内存: 128M

枚举第一个数，和第二个数，第三个数就等于总数减去前两个数之和

然后要确保方法相同，即i < j < k，再检查是否包括2或4

#include<iostream>
using namespace std;

bool check(int x){
  while(x){
    int t = x % 10;
    if(t == 2 || t == 4) return false;
    x /= 10;
  }
  return true;
}

int main(){
  int ans = 0;

  for(int i = 1; i <= 2019; i++)
    for(int j = i + 1; j <= 2019; j++){
      int k = 2019 - i - j;
      if(k > j && j > i){
        if(check(i) && check(j) && check(k)) ans++;
      }
    }

  cout<<ans<<endl;
  return 0;
}

第二题：猜生日

题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
今年的植树节（2012 年 3 月 12 日），小明和他的叔叔还有小伙伴们一起去植树。休息的时候，小明的同学问他叔叔多大年纪，他叔叔说：“我说个题目，看你们谁先猜出来！”
“把我出生的年月日连起来拼成一个 8 位数（月、日不足两位前补 0）正好可以被今天的年、月、日整除！”
他想了想，又补充到：“再给个提示，我是 6 月出生的。”
根据这些信息，请你帮小明算一下，他叔叔的出生年月日。
格式是年月日连成的 8 位数。例如，如果是 1948 年 6 月 12 日，就写：19480612。
运行限制
最大运行时间：1s
最大运行内存: 128M

想到回文日期那道题，就顺便把检查日期是否合法给打了一遍

这道题就是枚举，加判断

#include<iostream>
using namespace std;

bool isleap(int year){
  return year % 400 == 0 || (year % 4 == 0 && year % 100 != 0);
}

bool isright(int n){
  int year = n / 10000;
  int month = n / 100 % 100;
  int day = n % 100;
  if(day > 31) return false;
  if(month > 12 || month < 1) return false;
  if(month == 2) 
    if(isleap(year) && day > 29) return false;
    else if (!isleap(year) && day > 28) return false;
  if(month == 4 || month == 6 || month == 9 || month == 11)
    if(day > 30) return false;
  return true;
}

bool isright2(int n){
  int year = n / 10000;
  int month = n / 100 % 100;
  int day = n % 100;
  if(day > 30) return false;
  if(month != 6) return false;
  return true;
}

int main(){

  int a = 2012, b = 3, c = 12;
  for(int i = 19480612; i <= 20120312; i++){
    if(isright2(i) && i % a == 0 && i % b == 0 && i % c == 0){
      cout<<i<<endl;
      break;
    }
  }

  return 0;
}

第三题：成绩统计

题目描述
小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是一个 0 到 100 的整数。
如果得分至少是 60 分，则称为及格。如果得分至少为 85 分，则称为优秀。
请计算及格率和优秀率，用百分数表示，百分号前的部分四舍五入保留整 数。
输入描述
输入的第一行包含一个整数 n (1≤n≤104)，表示考试人数。
接下来 n 行，每行包含一个 0 至 100 的整数，表示一个学生的得分。
输出描述
输出两行，每行一个百分数，分别表示及格率和优秀率。百分号前的部分 四舍五入保留整数。
输入输出样例

输入

7
80
92
56
74
88
100
0

输出

71%
43%

至少可以等于，然后要除先乘100，四舍五入round函数

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;

int n;

int main(){
  scanf("%d", &n);

  int x = 0 , y = 0, t = n;
  while(t --){
    int a;
    scanf("%d", &a);
    if(a >= 85)
      x++;
    else if( a >= 60)
      y++;
  }

  float i = (x + y) * 100.0 / n;
  float j = x * 100.0 / n;

  cout<<round(i)<<"%"<<endl;
  cout<<round(j)<<"%"<<endl;
  return 0;
}

第四题：最大和

问题描述
小蓝在玩一个寻宝游戏, 游戏在一条笔直的道路上进行, 道路被分成了 n 个方格, 依次编号 1 至 n, 每个方格上都有一个宝物, 宝物的分值是一个整数 (包括正数、负数和零), 当进入一个方格时即获得方格中宝物的分值。小蓝可 以获得的总分值是他从方格中获得的分值之和。
小蓝开始时站在方格 1 上并获得了方格 1 上宝物的分值, 他要经过若干步 到达方格 n。
当小蓝站在方格 p 上时, 他可以选择跳到 p+1 到 p+D(n−p) 这些方格 中的一个, 其中 D(1)=1,D(x)(x>1) 定义为 x 的最小质因数。
给定每个方格中宝物的分值, 请问小蓝能获得的最大总分值是多少。
输入格式
输入的第一行包含一个正整数 n 。
第二行包含 n 个整数, 依次表示每个方格中宝物的分值。
输出格式
输出一行包含一个整数, 表示答案。

样例输入

5

1 -2 -1 3 5

样例输出

8

最长上升子序列问题

状态是从 1到 n-p的最小质数（套模板）

为负，初始化为无穷小

n * 1e5 > int，用long long,虽然题目测试数据没有，但是分析可能会

#include<iostream>
#include<cstring>
using namespace std;

const int N = 10010;
typedef long long LL;
int n;
LL a[N], f[N];

bool check(int x){
  for(int i = 2; i <= x / i; i++)
    if(x % i == 0)
      return false;
  return true;
}

int D(int x){
  if(x == 1) return 1;
  int i;
  for(i = 2; i <= x; i++)
    if(check(i) && x % i == 0)
      break;
  return i;
}

int main(){
  scanf("%d", &n);

  for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);

  memset(f, -0x3f, sizeof f);
  f[1] = a[1];
  for(int i = 1; i <= n; i++){
    int d = D(n - i);
    for(int j = 1; j <= d; j++){
      if(i + j > n) break;
      f[i + j] = max(f[i + j], f[i] + a[j + i]);
    }
  }

  cout<<f[n]<<endl;
  return 0;
}