不要为打翻的牛奶哭泣

分类

题解(1)

/ 注册

全部文章（共66篇）

题解 | 小红的魔法药剂

关键发现：对于每种药剂，我们只需要考虑两种方案：直接购买红色版本，花费用其他两种红色药剂配置蓝色版本，花费选择这两种方案中花费较小的即可贪心策略：对于第 i 种药剂，比较：直接购买的花费配置的花费（u和v是配方中指定的两种药剂）选择较小值作为获得这种药剂的花费具体步骤：读入所有药剂的价格和配...

2025-05-17

0 11

题解 | 小红的好数组

这是一个贪心问题，可以通过以下步骤解决：关键发现：要使数组不是好数组，就要破坏所有长度为3的非降序子数组对于连续的三个数 a[i-1], a[i], a[i+1]：如果 a[i] >= a[i-1] 且 a[i] <= a[i+1]，这就是一个非降序子数组我们必须修改中间的数 a[i] ...

2025-05-17

0 13

题解 | 分组

这是一个数学问题，可以通过以下步骤解决：关键发现：要使组数最多，应该尽可能让每组人数最少每组至少要有3人所有人必须被分配到某个组中数学推导：设最多可以分成 x 组每组至少3人，所以总人数至少需要 3x 人因此必须满足：3x ≤ n解得：x ≤ n/3所以答案就是 ⌊n/3⌋具体步骤：直接计算 n/3...

2025-05-17

0 13

题解 | 小红的多彩糖葫芦

这是一个模拟问题，可以通过以下步骤解决：关键发现：小红只能从上往下吃遇到相同颜色就会停止需要记录上一个吃的糖葫芦的颜色模拟策略：从第一个糖葫芦开始吃记录上一个吃的糖葫芦颜色如果下一个糖葫芦颜色相同，就停止否则继续吃并更新上一个颜色具体步骤：遍历字符串维护上一个颜色和已吃数量遇到相同颜色就退出循环 #...

2025-05-17

0 11

题解 | 小红的魔法药剂

这是一个贪心问题，可以通过以下步骤解决：关键发现：对于每种药剂，我们只需要考虑两种方案：直接购买红色版本，花费用其他两种红色药剂配置蓝色版本，花费选择这两种方案中花费较小的即可贪心策略：对于第 i 种药剂，比较：直接购买的花费配置的花费（u和v是配方中指定的两种药剂）选择较小值作为获得这种药...

2025-05-17

0 12

题解 | 郊区春游

题意：一开始就在旅游的几个点选一个作为起点，然后这个点就算游过了，游完别的景点在最后一个景点停下即可。用dp[i][j]，i表示状态（哪些点游过，哪些点没有），j表示最后停留在哪个点。具体看代码详细注释： #include <bits/stdc++.h> using namespace ...

2025-05-08

0 14

题解 | 数位染色

核心思想：将数字转为字符串，计算所有数位之和如果能找到一些数位，使其和为，则可以实现要求本质是一个子集和问题解决方案：先判断总和是否为偶数（如果为奇数则无解）使用状态压缩DP或DFS判断是否存在子集和为由于数据范围较小（最多18位数字），可以直接DFS #include <bits/st...

2025-05-08

0 14

题解 | [ZJOI2010]COUNT 数字计数

对于大范围内的数字统计，需要使用数位DP的方法：将问题转化为求，表示到中每个数字出现的次数则区间的答案为对于计算：考虑每一位的贡献例如对于数字：个位：每个数，各出现次十位：每个数，每个数字在十位上出现次百位：每个数，每个数字在百位上出现次千位：出现...

2025-05-08

0 13

题解 | 串

不妨令表示枚举到第个位置的时候状态为其中，状态是当前是否已满足条件——已出现""的子序列而状态是当前是否已经出现了字母发现总共的状态只有个，记忆化搜索一下即可，每个状态最多只会遍历一次。ps：我本地爆栈了，交上去居然过了，非常神奇。时间复杂度 #in...

2025-05-08

0 13

题解 | 最少的完全平方数

完全背包的变种，令dpjdpj表示取到第ii个数的容量为jj的背包（完全平方数之和），那么dpjdpj的最大值一定是jj本身（j∗1j∗1），那么从2≤i≤n2≤i≤n之间做完全背包，有状态转移方程：dpj=min⁡(dpj−i2+1,dpj)dpj=min(dpj−i2+1,dpj) ...

2025-05-08

0 14