©2020-2024 ioDraw All rights reserved
第一题：三角回文数
问题描述
对于正整数 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 的数组: A 1 ,A 2 ,A 3 ,…A N 恰好是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 ≤10 5 , 1≤K ≤10 3 ，给定的 n 个数均不超过 10 8 。
输出描述
输出一行一个整数代表所求的和。
输入输出样例 输入 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; }