Gnomeshgh112

分类

/ 注册

全部文章（共16篇）

题解 | ranko的手表-简单思路

简单思路：遍历所有的时间，即从0到1439。将时间转换为XX:XX的格式看给定的两个时间是否符合格式，把符合格式的保存起来。遍历所有符合格式时间的最大最小值。思路简单，但是写起来稍微有点麻烦。 #include <bits/stdc++.h> #include <string>...

2025-04-22

1 10

题解 | 【模板】二维前缀和-1base玩家的狂喜

1base玩家的狂喜a数组表示原数数据，b数组表示前缀和。b[i][j]表示a中从[0][0]到[i][j]的所有元素的和。使用一个循环维护b数组既可。结果中，只需要返回b[x2][y2] - b[x2][y1 - 1] - b[x1 - 1][y2] + b[x1 - 1][y1 - 1]既可。画...

2025-04-16

1 14

题解 | 【模板】前缀和

1 base玩家的福音a数组表示原来的数据，b[i]表示[0, i]的a数组的和。使用一个循环维护既可那么[l, r]的和就是b[r] - b[l - 1]; #include <bits/stdc++.h> using namespace std; int main() { ...

2025-04-15

1 11

题解 | abb

从后往前遍历，遍历到i位置时，统计大于i的字符中，有哪些字符是不等于s[i]，并且数量大于等于2的。如果数量大雨等于2，那么这些字符都可以和i位置的字符组成abb的格式。使用一个数组统计，从后往前遍历一遍既可得到答案。 #include <bits/stdc++.h> using nam...

2025-04-14

1 19

题解 | 【模板】完全背包

问题1：dp[i]表示背包最大容量为i的情况下，能装下的最多价值。由于完全背包中，每个物品可以选择无数次。一种比较简单的思路是，每一个物品都copy足够多次，多到单独选择任意一个物品都能够填满整个背包。这样将物品数量增加，将问题转换为0 1背包。但是这种思路会被卡。另外的思路：考虑在0 1背包中，是...

2025-04-11

1 16

题解 | 小数字

在数字大于3的时候，统一使用开根号的方式是最小的。在数字小于等于3的时候，统一使用减1的方式是最小的。 #include <bits/stdc++.h> using namespace std; int main() { int T; cin >> T; ...

2025-04-11

2 14

题解 | 【模板】01背包

问题1：01背包经典问题。dp[i][j]表示考虑前i个物品，背包最大容量为j的时候，能装下的最大价值。转移方程：if (a[i] <= j) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + b[i]);由于dp[i]的变化只与dp[i -...

2025-04-10

1 14

题解 | [NOIP2001]装箱问题，0-1背包，dp模板

0-1背包的变型dp[i][j]表示考虑了前i个物品，当背包大小为j的时候，剩余的最少空间。初始化：起初一个物品都没有放入，所以dp[0][j] = j；转移方程：if (a[i] < j) dp[i][j] = min(dp[i - 1][j], dp[j - a[i]]);else dp[...

2025-04-09

1 14

题解 | 最长公共子序列(一)

DP的模板题将s1作为短的字符串，s2作为长的字符串。考虑空间复杂度n*m的做法，定义dp[n][m]，dp[i][j]表示考虑s2的前 i 位和s1的前 j 位的最长公共子序列的结果状态转移：if (s2[i] == s1[j]) dp[i][j] = max(dp[i - 1][j], dp[i...

2025-04-08

1 12

题解 | 最长上升子序列(一)

DP的模板题目。dp[i]表示以a[i]为结尾的最长上升子序列的长度。dp[i] = max(dp[i], dp[j] + 1);其中，j < i并且a[j] < a[i]。遍历所有的i, j。计算出的dp数组中的最大值即为结果。 #include <bits/stdc++.h&g...

2025-04-07

1 15