其实是牛哥

题解

/ 注册

全部文章 / 题解（共40篇）

题解 | #【模板】01背包#

01背包难度：3星设 dp[i][j]dp[i][j]dp[i][j] 为前iii个物品，背包容量为jjj的最大价值。那么考虑第iii个物品是否放入，有两种情况：如果不放，那么等同于前i−1i-1i−1个物品，容量为jjj的背包的最优方案。如果放，那么等同于前i−1i-1i−1个物品，容...

C++

2021-10-19

16 846

题解 | #小红取数#

小红取数难度：3星首先第一个想法是，开一个dp数组，dp[i]dp[i]dp[i] 代表取前i个数的最大值。那么dp[i]怎么求呢？很明显，如果要取了第 iii 个数 a[i]a[i]a[i] ，满足和能被k整除，那么就有个限制：前i-1个数里，满足取的数之和除以k的余数为 k−a[i]k-a...

C++

2021-10-19

4 1290

官方题解 | #字母收集#

字母收集难度：2星经典的二维dp题目。设从起点到当前点的最大收益为 dp[i][j]dp[i][j]dp[i][j]，那么显然当前点 (i,j)(i,j)(i,j) 要么从 (i−1,j)(i-1,j)(i−1,j) 过来，要么从 (i,j−1)(i,j-1)(i,j−1) 过来。因此有dp方程...

2021-10-19

1 433

题解 | #【模板】二维差分#

【模板】二维差分难度：3星类似二维前缀和的套路，开一个差分数组 sumsumsum，对于左上角 (x1,y1)(x_1,y_1)(x1,y1) 、右下角 (x2,y2)(x_2,y_2)(x2,y2) 的矩形所有数加上 kkk ，我们只需要把 sum[x1][y1]sum[x_1][y_...

C++

2021-10-19

1 422

题解 | #【模板】差分#

【模板】差分难度：2星差分模板题。如果每次操作都是 O(n)O(n)O(n) 复杂度进行模拟的话，肯定会超时。我们观察到，对于一个数组，如果让 a[l]a[l]a[l] 加 kkk ，a[r+1]a[r+1]a[r+1] 减 kkk ，做一个前缀和之后，相当于 [l,r][l,r][l,r] ...

C++

2021-10-19

5 673

官方题解 | #【模板】二维前缀和#

【模板】二位前缀和难度：3星二维前缀和模板题。设 sum[i][j]sum[i][j]sum[i][j] 为左上角坐标为 [0,0][0,0][0,0] ，右下角坐标为 [i,j][i,j][i,j] 的子矩阵所有数之和。那么观察下图：我们要求粉色部分的所有数之和（即④号），可以用下面的方式...

2021-10-19

5 852

官方题解 | #abb#

abb 难度：3星提示 1：对于每个字母 ch，找到后面和 ch 不等的两个相等字母的个数 cnt 即可，贡献为 Ccnt2=cnt∗(cnt−1)/2C_{cnt}^2=cnt*(cnt-1)/2Ccnt2=cnt∗(cnt−1)/2 提示 2：快速得出每个 cnt 的方式：开一个后缀和数组 ...

C++

2021-10-19

23 673

官方题解 | #【模板】前缀和#

【模板】前缀和难度：2星前缀和模板题。我们定义 sum[i]sum[i]sum[i] 为前 iii 个数之和，可以通过预处理 O(n)O(n)O(n) 求出所有的 sum[i]sum[i]sum[i]，那么查询区间 [l,r][l,r][l,r] 中所有数之和只需要输出 sum[r]−sum[l...

C++

2021-10-19

3 615

官方题解 | #nico和niconiconi#

nico和niconiconi 难度：3星计 dp[i]dp[i]dp[i] 代表前 iii 个字符的计数最大值。那么可得转移方程：若取当前子串"nico"： if(substring(i−3,i)==nico)thenif(substring(i-3,i)==nico)thenif(subs...

C++

2021-10-19

4 622

题解 | #不相邻取数#

不相邻取数难度：2星设 dp[i][0]dp[i][0]dp[i][0] 为不取第 iii 个数的情况下，前 iii 个数不相邻取数的最大值；dp[i][1]dp[i][1]dp[i][1] 为取第 iii 个数的情况下，前 iii 个数不相邻取数的最大值。那么有转移方程：不取当前数，那么前一...

C++

2021-10-19

9 995