问题 A: 天使的爱情红箭题目描述为保证简单本训练所有题面剧情均已做删减。你相信天使吗Lonely 与他的女朋友分手后十分伤心悲痛欲绝下来到天台。突然出现一只天使她以为 Lonely 想要轻生于是急忙制止并说是来拯救 Lonely 的。天使自称是灵儿Lonely 有着入骨的中二病因此他对天使的出现表示非常惊喜。灵儿拿出一对翅膀和一支射中别人便可以让TA爱上自己的红箭问 Lonely 想要哪个。一个是能够自由地飞翔的翅膀一个是能力非常强的红箭权衡利弊之下他选择了全都要。于是灵儿便把两者都给了 Lonely表示自己是特级天使可以让主人同时这拥有两种物品。灵儿对 Lonely 说道红箭拥有三级等级越高消耗的身体能量越多它们可以抽象为具体的数字即分别为1,5,11点。天使可以看到人的身体承受上限即最多可以承受多少点能量的红箭的攻击只有红箭能量总和等于人的身体承受上限才可以被控制。Lonely 想要试试红箭的效果于是他在路上随便找了一个小姐姐灵儿告诉 Lonely 她的身体承受上限是 nnn点Lonely 很快便知道他至少要使用多少红箭才可以控制小姐姐了。输入仅一行一个正整数 nnn。输出仅一行一个正整数表示需要的红箭数。输入输出样例样例输入 #1复制15样例输出 #1复制3样例输入 #2复制12样例输出 #2复制2提示对于样例数据 1最佳方案是 155551555515555使用到 3 个红箭。对于样例数据 2最佳方案是 121111211 112111使用到 2 个红箭。对于 100%100\%100% 的数据保证 n≤106n\leq 10^6n≤106。假设 Lonely 拥有无限的能量即1,5,11的红箭无数个。把递归顺序改成了11 → 5 → 1这样大的步长先走能更快接近目标减少递归深度。#includeiostream #includevector #define int long long using namespace std; int n; int ans 0x3f3f3f3f; const int N 1e6 10; vectorintmemo(N, 0x3f3f3f3f); void dfs(int i, int cnt) { if (i n) return; if (cnt memo[i]) return; memo[i] cnt; if (i n) { ans min(ans, cnt); return; } //把递归顺序改成了 11 → 5 → 1 //这样大的步长先走能更快接近目标减少递归深度。 dfs(i 11, cnt 1); dfs(i 5, cnt 1); dfs(i 1, cnt 1); } signed main() { cin n; dfs(0, 0); cout ans; return 0; }问题 B: 巧合与陷阱题目描述WLY 提到我们11到运动场nm有些距离应当规划一下如何飞。身为继承者的 WLY 也有翅膀由于有翅膀所以可以无视地面的障碍物地图内所有的方格均可以进入。在两天使一人的注视下聪明的 Lonely 看了一眼地图便说出了可能的走法有多少种。输入一行两个正整数 nnn 和 mmm代表身处 nnn 行 mmm 列的地图中。输出在保证 Lonely 和 WLY 小姐姐只能向下或者向右走的前提下Lonely 走到运动场一共有多少种走法输入输出样例样例输入 #1复制1 5样例输出 #1复制1样例输入 #2复制2 4样例输出 #2复制4样例输入 #3复制3 4样例输出 #3复制10提示对于第一组样例1×5 的地图大小只有一条路可以走即1,1-1,5对于第二组样例2×4 的地图大小有四种走法1,1-1,2-1,3-1,4-2,41,1-1,2-1,3-2,3-2,41,1-1,2-2,2-2,3-2,41,1-2,1-2,2-2,3-2,4对于 100%100\%100% 的数据保证 n,m≤100n,m \leq 100n,m≤100。注意需要使用long long数据类型题目保证答案的范围处于long long的范围内。记得开long long。#includeiostream #includevector #define int long long using namespace std; signed main() { int n, m; cin n m; vectorvectorintdp(110, vectorint(110)); for (int i 0;i 110;i) { dp[i][1] 1; dp[1][i] 1; } for (int i 2;i n;i) { for (int j 2;j m;j) { dp[i][j] dp[i - 1][j] dp[i][j - 1]; //cout dp[i][j] ; } //cout \n; } cout dp[n][m]; return 0; }问题 C: 隐匿深处的弱点[提交] [视频] [状态]题目描述灵儿还是告诉了 Lonely 箭都存在的弱点将白箭的上半部分抽象为金字塔形共有 nnn 层存在一些点上面有脆弱度数字从第一层开始向下每层需要向左或者向右移动并将路径上的数字累加到达最底层即白箭的过渡层时如果某点的路径中存在所有路径的最小的累加和那么称这一点为这支箭的脆弱点。使用任意类型的箭攻击这一点即可摧毁该箭。输入第一行一个正整数 nnn代表金字塔的层数。下面 nnn 行每行存在 iii 个正整数iii 代表层数。输出输出从第一层到底层任意点的路径使得路径经过的数字之和最小的最小值。每一步可以走到左下方的点也可以到达右下方的点输入输出样例样例输入 #1复制5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11样例输出 #1复制49提示13-8-7-14-7对于 100%100\%100% 的数据保证 1≤n≤1001 \leq n \leq 1001≤n≤100。金字塔中的数字不会超过 1000。#includeiostream #includevector #define int long long using namespace std; signed main() { int n; cin n; vectorvectorinttower(n, vectorint(n)); for (int i 0;i n;i) { for (int j 0;j i;j) cin tower[i][j]; } auto dp tower; for (int i n - 2;i 0;i--) { for (int j 0;j i;j) { dp[i][j] min(dp[i 1][j], dp[i 1][j 1]); } } cout dp[0][0]; return 0; }问题 D: 就这你也不想让我这么容易就进来吧题目描述灵儿说大叔是一级天使拥有翅膀和红箭但是没有白箭。而 WLY 是二级天使只有翅膀。特级天使一共有三个。大叔说他家中私藏了很多武器可以提升他们的战斗力弥补一下 WLY 和他没有白箭的短板。三人三天使讨论了一会打算一同前往。大叔家的底下仓库有个密码门门上有一串数字正好 nnn 个大叔给出了两个提示想看看 Lonely 能否猜出密码有几位1.密码是升序的2.密码的位数要尽可能多输入第一行一个正整数 nnn表示一共有 nnn 个数字。第二行为 nnn 个正整数a1 ,a2 ,a3 ,a4 ,a5 ,a6 ,a7 ....an输出求它的一个子序列设为s1 ,s2 ,…sn使得这个子序列满足这样的性质s1s2s3...sn并且这个序列的长度最长。输出这个最长子序列的长度。输入输出样例样例输入 #1复制7 1 7 3 5 9 4 8样例输出 #1复制4提示选择数字 1,3,4,8 或 1,3,5,8 均可以满足条件故密码的位数为 4。(1≤N≤1000)(1 \le N \le 1000)(1≤N≤1000)数字的范围是 [0,10000][0, 10000][0,10000]。最长上升子序列。#includeiostream #includevector #define int long long using namespace std; signed main() { int n; cin n; vectorinta(n); for (int i 0;i n;i) cin a[i]; vectorintdp(n); //每个元素自身可以作为一个长度为 1 的上升子序列 for (int i 0;i n;i) dp[i] 1; for (int i 0;i n;i) { for (int j i;j n;j) { if (a[i] a[j]) dp[j] max(dp[i] 1, dp[j]); } } //遍历整个 dp 数组找出其中的最大值 //因为最长上升子序列不一定以最后一个元素结尾 int ans 0; for (int i 0;i n;i) ans max(ans, dp[i]); cout ans; return 0; }问题 E: 还没装够呢题目描述Lonely 一行人成功抵达大叔的地下密室看到一堆武器装备他们惊呆了。大叔分给 Lonely 一个容积为 MMM 大背包让他们挑选自己觉得用得上的带走就行。他们一时竟然不知道选什么好。灵儿帮助他们数出一共有 NNN 种物品每种物品只有一件并分析出了物品的重量 wiw_iwi​ 和她认为的价值 did_idi​ (wi,di231−1)(w_i,d_i2^{31}-1)(wi​,di​231−1)。想要让背包尽可能装满的同时要让价值最大化这下轮到 Lonely 头痛了不过有贴心的 WLY 在旁“我来帮你吧~收拾东西什么的我可擅长了”。(N≤3500,M≤13000)(N \le 3500, M \le 13000)(N≤3500,M≤13000)输入第一行是整数 NNN 和 MMM。第二行到第 N1N1N1 行每行两个整数 WWW 和 DDD 描述一个物品的体积和价值。输出输出一个整数表示能放入背包的物品的最大价值总和。输入输出样例样例输入 #1复制4 6 1 4 2 6 3 12 2 7样例输出 #1复制2301背包。#includeiostream #includevector #define int long long using namespace std; signed main() { int n, V; cin n V; vectorintv(n1); vectorintw(n1); for (int i 1;i n;i) { cin v[i] w[i]; } vectorvectorintdp(n 1, vectorint(V 1)); for (int i 1;i n;i) { for (int j 0;j V;j) { dp[i][j] dp[i - 1][j]; if (j v[i]) dp[i][j] max(dp[i][j], dp[i - 1][j - v[i]] w[i]); } } cout dp[n][V]; return 0; }问题 F: 学会正确使用翅膀很关键题目描述打包完毕他们现在要赶往大叔被困地距离为 nnn 利用翅膀的迭进能力可以更迅速的到达但是要注意不要超过距离 nnn。如果使用迭进能力则可以双倍已经行驶过的路程否则路程1。换句话说假设现在已经前进了 xxx 距离可以选择将距离变为 2x2x2x或者 x1x1x1无论选择哪一项都视为飞行次数1。初始时路程为 1。输入仅一行一个正整数 nnn。输出仅一行一个正整数表示最少飞行次数。输入输出样例样例输入 #1复制16样例输出 #1复制4样例输入 #2复制5样例输出 #2复制3提示样例数据11→2→4→8→161\to 2\to 4\to8\to 161→2→4→8→16共 4 次。样例数据21→2→4→51\to 2\to 4\to 51→2→4→5共 3 次。对于 100%100\%100% 的数据n≤106n\leq 10^6n≤106。这题说实话我没有dp的思路第一想法是dfs。然后第一次dfs还超时了因为没有开记忆数组。#includeiostream #includevector #define int long long using namespace std; int n; int ans 0x3f3f3f3f; const int N 1e7 10; //记得开记忆数组不然会超时。 vectorintmemo(N, 0x3f3f3f3f); void dfs(int i, int cnt) { if (i n) return; if (cnt memo[i]) return; memo[i] cnt; if (i n) { ans min(ans, cnt); return; } dfs(i 1, cnt 1); dfs(i * 2, cnt 1); } signed main() { cin n; dfs(1, 0); cout ans; return 0; }问题 G: 放置自动弩题目描述无论是灵儿说出的话还是她所拥有的【红箭】和【白箭】都使 Lonely 不得不吐槽她到底是天使还是魔鬼。灵儿却对此不以为然她认为并无恶魔这种东西要真说恶魔也只存在于人心中。Lonely 询问灵儿能否帮忙计算一下自动弩放在哪里比较好灵儿想了想给他推荐出了 nnn 个放置自动弩的地点用m1,m2,…,mnm_1, m_2, \dots , m_nm1​,m2​,…,mn​ 来表示他们的相对位置。由于地段关系每个地点会产生的影响不同灵儿给出了她预估的每处可能产生的影响力用 pip_ipi​ 表示在 mim_imi​ 处放置自动弩的影响力。为了避免自动弩被快速破坏弩之间的距离必须大于 kkk。在二人二天使的商讨下他们很快就找到了最合适放置自动弩的几个地点。输入输入包含若干组测试数据。第一行是整数 TTT (1≤T≤1000)(1 \le T \le 1000)(1≤T≤1000)表明有 TTT 组测试数据。紧接着有 TTT 组连续的测试。每组测试数据有 333 行。第 111 行: 地点总数 nnn (n100)(n \lt 100)(n100)距离限制 kkk (0k1000)(0 \lt k \lt 1000)(0k1000)。第 222 行: nnn 个地点的位置 m1,m2,…,mnm_1, m_2, \dots, m_nm1​,m2​,…,mn​ (0mi1000000(0 \lt m_i \lt 1000000(0mi​1000000 且为整数升序排列)))。第 333 行: nnn 个地点的影响力 p1,p2,…,pnp_1, p_2, \dots, p_np1​,p2​,…,pn​ (0pi1000(0 \lt p_i \lt 1000(0pi​1000 且为整数)))。输出对于每组测试数据可能的最大影响力。输入输出样例样例输入 #1复制2 3 11 1 2 15 10 2 30 3 16 1 2 15 10 2 30样例输出 #1复制40 30提示在第一组数据中选择在位置 1 和位置 15 的地点总影响力为40。由于距离之间必须大于11所以 2 位置无法放置弩。假设弩是无限的你只需要选择地点并计算最大影响力即可。#includeiostream #includealgorithm #includevector #define int long long using namespace std; struct node { int val;//影响力 int pos;//位置 }; bool cmp(struct node a, struct node b) { return a.pos b.pos; } signed main() { int t; cin t; while (t--) { // n:地点数量k:最小距离限制 int n, k; cin n k; vectorstruct nodeplace(n); for (int i 0;i n;i) cin place[i].pos; for (int i 0;i n;i) cin place[i].val; //将所有地点按位置从小到大排序 sort(place.begin(), place.end(), cmp); //dp[i]表示考虑前i1个地点时的最大总影响力 vectorintdp(n); int maxn 0; for (int i 0;i n;i) { //每个地点至少可以只选自己 //所以初始值设为自己的影响力 dp[i] place[i].val; } for (int i 0;i n;i) { //看前面哪些位置可以搭配 for (int j 0;j i;j) { //地点i和地点j的距离是否大于k if (place[i].pos place[j].pos k) { //dp[i] max(原来的值, 选j的最优解 选i的价值) dp[i] max(dp[i], dp[j] place[i].val); } } //也可以不选当前位置继承前面的最优解 if (i 0) dp[i] max(dp[i], dp[i - 1]); } //考虑所有n个地点时的最大总影响力 cout dp[n - 1] \n; } return 0; }问题 H: 仅剩的可能性题目描述准备完毕排列分散的自动弩接连射出看守者们一个个被击中依次倒下......射出的那是...白箭Lonely 不可置信地看向灵儿虽然她没有办法影响到世界但是可以改变她的箭。“目的达到了就好啦~”天使灵儿在旁边莞尔一笑不禁让 Lonely 毛骨悚然。在那一刻Lonely 甚至分不清灵儿到底是想要救人还是杀人或许继承者对她来说更为重要吧。门开了大叔出来了表现的很虚弱。他仿佛已经支撑不住拼命想说什么不知为何却说不出口。大叔用手在地上写下了一些数字便永远的倒了下去。Lonely 知道这是他们之间约定的密码包含字母 A-Z 的消息会通过以下映射进行编码 ‘A’ - “1”‘B’ - “2”…‘Z’ - “26”要 解码 已编码的消息所有数字必须基于上述映射的方法反向映射回字母可能有多种方法。例如“11106” 可以映射为“AAJF” 将消息分组为 (1 1 10 6) “KJF” 将消息分组为 (11 10 6) 注意消息不能分组为 (1 11 06) 因为 “06” 不能映射为 “F” 这是由于 “6” 和 “06” 在映射中并不等价。Lonely 很快算出了一共有多少种解码方法但是大叔好像并没有告诉怎么分割啊灵儿在旁边看着这一切突然像是想到了什么“不好快走”。输入输入一行只包含一个只含数字的非空字符串 s。输出返回解码方法的总数 。题目数据保证答案肯定是一个 32 位 的整数。输入输出样例样例输入 #1226样例输出 #13样例输入 #206样例输出 #20