蓝桥杯第五天刷题

第一题：数的分解 题目描述 本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。 把 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≤10 4 )，表示考试人数。 接下来 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; }