蓝桥杯刷题第七天

第一题：三角回文数

问题描述
对于正整数 n, 如果存在正整数 k 使得2n=1+2+3+⋯+k=2k(k+1), 则 n 称为三角数。例如, 66066 是一个三角数, 因为 66066=1+2+3+⋯+363。
如果一个整数从左到右读出所有数位上的数字, 与从右到左读出所有数位 上的数字是一样的, 则称这个数为回文数。例如, 66066 是一个回文数, 8778 也是一个回文数。
如果一个整数 n 既是三角数又是回文数, 我们称它为三角回文数。例如 66066 是三角回文数。
请问, 第一个大于 20220514 的三角回文数是多少?
答案提交
这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。
运行限制
最大运行时间：1s
最大运行内存: 256M

三角回文数,先求三角数，大于20220514， 再判断该数是否是回文数

#include<iostream>
using namespace std;int main(){int ans = 0;for(int i = 1; ; i ++){ans += i;if(ans > 20220514){int t = ans, x = 0;while(t){x *= 10;x += t % 10;t /= 10;}if(ans == x){cout<<ans<<endl;return 0;}}}return 0;
}

第二题：数数

问题描述
任何一个大于 1 的正整数都能被分解为若干个质数相乘, 比如 28=2×2×7 被分解为了三个质数相乘。请问在区间 [2333333, 23333333] 中有多少个正整数 可以被分解为 12 个质数相乘?
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。
运行限制
最大运行时间：1s
最大运行内存: 512M

直接暴力求解，枚举，检查是否有12个质因数

最后一个记得还要算进去

第一种解法要时间长一点，在蓝桥杯oj上面跑会超时

第二种解法的话，就是建立了一个数组保存取模结果

#include<iostream>
using namespace std;bool check(int x){int res = 0;for(int i = 2; i <= x / i; i++){if(x % i == 0){while(x % i == 0){x /= i;res++;}}}if(x != 1) res ++;if(res == 12) return true;return false;
}int main(){int ans = 0;for(int i = 2333333; i <= 23333333; i++)if(check(i)) ans++;cout<<ans<<endl;return 0;
}

#include<iostream>
#include<vector>
using namespace std;const int L = 2333333, R = 23333333;
int s[R + 10], ans;
vector<int> p;int main(){for(int i = 2; i <= R; i++){if(!s[i]) s[i] = 1, p.push_back(i);if(i >= L && s[i] == 12) ans++;for(auto x : p){if(x * i > R) break;s[x * i] = s[i] + 1;}}cout<<ans<<endl;return 0;
}

第三题：数组切分

问题描述
已知一个长度为 N 的数组: A1,A2,A3,…AN 恰好是1∼N 的一个排列。现 在要求你将 A 数组切分成若干个 (最少一个, 最多 N 个) 连续的子数组, 并且 每个子数组中包含的整数恰好可以组成一段连续的自然数。
例如对于 A=1,3,2,4, 一共有 5 种切分方法:
13241324 : 每个单独的数显然是 (长度为 1 的) 一段连续的自然数。
{1}{3,2}{4}:{3,2}包含 2 到 3 , 是 一段连续的自然数, 另外 1 和 4显然 也是。
{1}{3,2,4}:{3,2,4} 包含 2 到 4 , 是一段连续的自然数, 另外 1 显然也是。
{1,3,2}{4}:{1,3,2} 包含 1 到 3 , 是 一段连续的自然数, 另外 4 显然也是。
{1,3,2,4}{1,3,2,4} : 只有一个子数组, 包含 1 到 4 , 是 一段连续的自然数。
输入格式
第一行包含一个整数 N 。第二行包含 N 个整数, 代表 A 数组。
输出格式
输出一个整数表示答案。由于答案可能很大, 所以输出其对 1000000007 取 模后的值

样例输入

4
1 3 2 4

样例输出

5

大佬的思路，没想出来，是线性dp

连续区间特性是，最大元素和最小元素的差值，就是区间左右端点3的差值

#include<iostream>
using namespace std;typedef long long LL;
const int N = 200010, M = 1000000007;
int n, a[N], f[N];int main(){scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);f[0] = 1;for(int i = 1; i <= n; i++){int maxu = a[i], minu = a[i];for(int j = i; j >= 1; j--){maxu = max(maxu, a[j]);minu = min(minu, a[j]);if(maxu - minu == i - j)f[i] = (LL)(f[i] + f[j - 1]) % M;}}cout<<f[n]<<endl;return 0;
}

第四题：倍数问题

题目描述
众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。数据保证一定有解。
输入描述
第一行包括 2 个正整数n, K。
第二行 n 个正整数，代表给定的 n 个数。
其中，1≤n ≤105, 1≤K ≤103，给定的 n 个数均不超过 108。
输出描述
输出一行一个整数代表所求的和。
输入输出样例

输入

4 3
1 2 3 4

输出

9

看大佬代码写的，思路很好

想成背包问题来解决

#include<cstring>
#include<set>
#include<iostream>
using namespace std;typedef long long LL;
const int N = 1010;
int n, k, f[4][N];
multiset<int, greater<int> >st[N];int main(){scanf("%d%d", &n, &k);for(int i = 1; i <= n; i++){int x; cin>>x;st[x % k].insert(x);}memset(f, -0x3f, sizeof f);f[0][0] = 0;for(int i = 0; i < k; i++){int cnt = 0;for(int num : st[i]){for(int j = 3; j >= 1; j--)for(int v = k - 1; v >= 0; v--)f[j][v] = max(f[j][v], f[j-1][(v - num % k + k) % k] + num);if(++cnt == 3) break;}}cout<<f[3][0]<<endl;return 0;
}