小狐今天睡大觉

分类

/ 注册

全部文章（共44篇）

题解 | 小红的双排列删除得分

使用前缀和+线性dp解决该问题。pre[i]前缀和数组 pre[i] = a[1]+...+a[i]dp[i] 前i个元素的最大得分pos[x]位置数组记录数字x最后一次出现的位置对于每一个位置：如果a[i]是第一次出现(pos[a[i]]==0)，将a[i]位置记录下来，当前的最大得分不变 dp...

2025-12-28

0 16

题解 | 【模板】差分

如果每一次操作都直接操作原数组，在极端情况下达到O(n^2)导致超时。采用差分思想进行数组操作：实现一个差分数组，该数组的元素置零，该数组用来表示多个patch区间，区间头为差分数，区间末尾为-差分数。维护cnt表示当前patch大小，最后一次性加到原数组里。 #include <iostre...

2025-12-28

0 15

题解 | 数楼梯

动态规划做法：上第一个台阶有1种上法上第二个台阶有2种上法(1+1或2)接下来的每个台阶都可以通过前两个台阶的上法数量得到(因为最大只能上两个台阶)，无论是动态规划还是递归都满足这种条件。dp[i]表示第i个台阶有几种上法状态转移方程： dp[i] = dp[i-1] + dp[i-2]最后dp[n...

2025-12-28

0 18

题解 | 变幻莫测

来点花活吧。规则很简单对于位置A,B 操作只有两个 1.交换数值位置 2. A=X+Y, B=X-Y如果带入就会发现，一共就只有以下几种情况：x==y 无需操作，A=B成立x=0, y=n 首先操作1: A=n、B=0，然后操作2: A=n+0、B=n-0x=n, y=0 直接操作2: A=n+0...

2025-12-28

0 17

题解 | 小红取数

瞪眼法可知，奇数*奇数=奇数奇数*偶数=偶数偶数*偶数=偶数所以只要有奇数，结果一定可以为奇数；一旦没有奇数，再怎么选都不可能使乘积为奇数。与运算(&)求奇偶：通过 n&1 二进制下判断末尾是否为1，为1就是奇数，为0就是偶数，效果与n%2==0相同，但是效率高。二进制1001 ...

2025-12-28

0 17

题解 | abb

由题可知样例abcbcc被分为abb*1、acc*3、bcc*3、bcc*1。不妨将问题简化为求对于'a' 后面的相同的字符的个数，也就是前缀和。例如 0位的'a' 后面有3个c、2个b，全排列次数为c: 3*(3-1)/2 = 3b: 2*(2-1)/2 = 1所以acc*3、abb*1建立长...

2025-12-28

0 22

题解 | 最大子数组和

使用动态规划解决。建立dp数组，初始化置零，dp[i]表示从首位到i的当前最大子数组的和。因为数据范围-10000~10000，所以会有一种情况：前面的数的和加上当前数字，结果反而没有当前数字大，说明前面的数字的和是负数，拖了真正的大数(当前数字)的后腿。这种情况下就要丢掉前面的数，从当前数字算起。...

2025-12-28

0 13

题解 | 矩阵的最小路径和

只需要每次把数字左边和数字上面的两个数字取最小的一个即可(数字只能从这两个方向移动)。如果另外开一个dp数组大概率存不下。所以直接操作原数组，注意边界位置，样例结果为11的就是忘记处理第一行和第一列了。状态转移方程：dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + v[...

2025-12-27

0 18

题解 | 数字三角形

读三角形进二维数组，由题可知三角形第n行有n个数，所以行的下标等于该行数字个数。做dp二维数组，初始化置零。每行首位数字仅需要考虑它的上一行的首位数字，所以当循环到第一列时用上一行首位加上当前数字；每行末尾数字仅需要考虑它的上一行的末尾数字，所以当循环到最后一列时用上一行末尾位加上当前数字；中间数字...

2025-12-27

0 15

题解 | 点到直线距离

#include <bits/stdc++.h> #include <cmath> using namespace std; struct point{ double x,y; point(double A,double B){ x=A,y=...

2025-12-25

0 18