yngcy

分类

刷题(39) 编程工具(1) 题解(4)

/ 注册

全部文章（共49篇）

codeforces1670F Jee, You See?（DP/位运算/前缀和/组合数）

题目链接：codeforces 1670F 题目思路：首先，对于 sum，有 s u m = a 1 + a 2 + ⋯ + a n sum = a_1 + a_2 + \cdots + a_n sum=a1+a2+⋯+an 根据前缀的思想，所以得到 ans = sum[r] - su...

2024-03-16

0 0

codeforeces1748C Zero-Sum Prefixes（贪心）

题目链接：codeforeces 1748C 题目思路：首先，不难想到修改的次数要最少；其次，对于一次修改，影响的是前缀和的后缀。因此，根据贪心思想，可以找原数组非零段，用它前面的0修改成这段前缀和的值出现次数最多的那个数的相反数即可。参考代码： #include <bits/st...

2024-03-16

0 0

题解 | #小美的子序列#

题意多行字符串中，每行只取一个字母，问是否能构成字符串中包含 “meituan”。例如，“mmmmmeemeituaaattn” 包含 “meituan”，而 “emituan” 并不包含 “meituan”。思路暴力遍历即可，当找到一个字符后，继续找下一个目标字符，不用考虑顺序问题。 imp...

Java 字符串

2024-03-16

0 551

题解 | #小美的排列构造#

题意要求构造一个排列，在这个排列中，每个相邻项的和记为，记的最大值为，最小值为，要使得最小的一个序列。思路我们的目的是让相邻的两项和尽可能接近，比较容易想到等差公式中的“首项加末项”。例如，的情况：先取 1 和 5，得到的和是 6。此时序列为；再取 2 和 4，得到的...

Java 双指针贪心

2024-03-16

0 437

题解 | #牛奶供应问题#

思路本以为要用到动态规划，其实不用，en 贪不会有什么问题。根据贪心策略，对于当前任务 taskDurations[i]，肯定是把其安排在最早空闲的生产线上。于是用优先队列（大根堆）维护每条生产线所执行时间，然后模拟即可。时间复杂度为，空间复杂度为。参考代码 import jav...

2023-11-02

0 318

题解 | #牛牛的最大栈#

思路最小栈的变体。使用双栈解决，一个维护原本的栈，一个维护当前最大值的栈。最大栈的意义在于栈顶就是原始栈的最大值，即栈中的元素是非递减的。时间复杂度为，空间复杂度为，其中表示操作数的大小。参考代码 import java.util.*; public class Solution...

2023-10-31

0 409

题解 | #牛牛的目标特征数#

思路凑硬币原题。考点是完全背包，即每种物品可以选无限个。定义 f[j] 表示前个物品中选择物品总面值为时的总硬币数。定义状态转移方程：f[j] = max(f[j], f[j - features[i]] + 1)。即考虑从之前的状态中比较面值为和面值为硬币的数量。如果选择前者...

2023-10-31

0 250

题解 | #牛牛的桶排序#

思路桶排。观察到数据范围是，所以设置一个偏移量 offset 即可。最后空间复杂度为，时间复杂度为。参考代码 import java.util.*; public class Solution { int[] bucket = new int[100000 + 10]; ...

2023-10-31

0 280

题解 | #数的选择#

思路根据贪心思想，数组的元素尽量大，而数组的元素尽量小，并且不难想到，的长度应始终满足。不妨先对数组进行排序（假设从小到大），然后从后面开始选择，从数组前面开始选择。然后枚举数组长度，求和比较是否满足即可。为了加快求和的速度，用前缀和即可。最后时间复杂度为，空间复杂...

2023-10-30

1 213