AcWing第152场周赛题解

type

status

date

slug

summary

📝 主旨内容

幸运数

如果一个整数能够被 6 或 8 整除，就称该整数为一个幸运数。

给定整数 n，请你计算 [1,n] 范围内的幸运数的数量。

输入格式

一个整数 n。

输出格式

一个整数，表示 [1,n] 范围内的幸运数的数量。

数据范围

前 3 个测试点满足 1≤n≤10。

所有测试点满足 1≤n≤100。

输入样例：

输出样例：

题解：

💡

数据范围小，可以直接遍历，也可以根据容斥原理进行优化

反转字符串

给定 n 个由小写字母构成的字符串。

你可以对其中的任意个字符串进行反转操作（例如将 abc 反转为 cba）。

不同的字符串的反转代价可能不同，具体来说反转第 i 个字符串的代价为 ci。

我们希望所有反转操作完成后，n 个字符串能够符合字典序排列。

请你计算，为了达成这一目的所需的最小总代价。

输入格式

第一行包含整数 n。

第二行包含 n 个整数 c1,c2,…,cn。

接下来 n 行，每行包含一个给定字符串。

输出格式

如果可以达成目的，则输出所需的最小总代价，否则输出 -1。

数据范围

前 6 个测试点满足 2≤n≤5。

所有测试点满足 2≤n≤10^5，0≤ci≤10^9，所有给定字符串非空且总长度不超过 10^5。

输入样例1：

输出样例1：

输入样例2：

输出样例2：

输入样例3：

输出样例3：

输入样例4：

输出样例4：

题解：

💡

题目看了好久，才看懂原来是要多个字符串保证字典序。每个字符串有反转和不反转两个状态，下一个字符串可以从上一个字符串的状态转移过来，转移的条件就是保证字典序

魔法植物

你正在挑战植物大战僵尸的无尽模式。

你有且只有两个攻击力强大的魔法植物----向日葵和阳光菇。

向日葵拥有 x 点法力值，阳光菇拥有 y 点法力值。

每一回合你都需要派出一个植物迎战僵尸。

僵尸的力量在不断增加，消灭第 1 回合的僵尸需要消耗 1 点法力值，消灭第 2 回合的僵尸需要消耗 2 点法力值，以此类推。

在一回合中，如果你派出的植物的当前法力值不低于消灭僵尸所需的法力值，则该植物消耗相应法力值消灭僵尸，使得你在该回合得以存活，否则该回合挑战失败，僵尸吃掉你的脑子。

假设通过合理安排植物的迎战顺序，你最多可以存活 h 个回合。

你的任务不是输出 h，而是计算并输出一共有多少种不同的方案可以让你达成存活最大回合数 h。

由于结果可能很大，你只需要输出对 10^9+7 取模后的结果。

注意，通过某一回合才能挑战下一回合，不存在跳过某一回合的可能。

例如，当 x=4,y=6 时，最多可以存活 4 个回合，最佳方案一共有两种，分别为：

四个回合依次派出阳光菇、阳光菇、阳光菇、向日葵。

四个回合依次派出向日葵、阳光菇、向日葵、阳光菇。

输入格式

共一行，包含两个整数 x,y。

输出格式

一个整数，表示方案数对 10^9+7 取模后的结果。

数据范围

前 44 个测试点满足 0≤x,y≤10。

所有测试点满足 0≤x,y≤2×10^5，x+y≥1。

输入样例1：

输出样例1：

输入样例2：

输出样例2：

输入样例3：

输出样例3：

题解：

💡

看了好久才看懂题目，是你只有两类植物，每一类各一个。那后面就顺其自然了，n*(n+1)/2 ≤ x + y ，转换为01背包问题，f[i]表示给x植物分配总法力值为i的僵尸的方案数，最后的答案就是剩下的僵尸法力值n*(n+1)/2 - i 小于等于y的方案数之和

🤗 总结归纳

整体还是比较困难，DP永远的伤永远的痛，题面我也是看了很久哈哈哈

📝 主旨内容

幸运数

输入格式

输出格式

数据范围

输入样例：

输出样例：

题解：

反转字符串

输入格式

输出格式

数据范围

输入样例1：

输出样例1：

输入样例2：

输出样例2：

输入样例3：

输出样例3：

输入样例4：

输出样例4：

题解：

魔法植物

输入格式

输出格式

数据范围

输入样例1：

输出样例1：

输入样例2：

输出样例2：

输入样例3：

输出样例3：

题解：

🤗 总结归纳

📎 参考文章