其实是牛哥

题解

/ 注册

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

题解 |这题绝了 #每个6/7级用户活跃情况#

SELECT user_info.uid as uid, ifnull(act_month_total, 0) as act_month_total, ifnull(act_days_2021, 0) as act_days_2021, ifnull(act_days_202...

Mysql

2021-10-20

0 625

官方题解 | #[ZJOI2010]COUNT 数字计数#

数字计数难度：5星解法1 我们设 dp[i][j][k]dp[i][j][k]dp[i][j][k] 为长度为 iii ，首位是 jjj 的数字中 kkk 出现的次数。推导递推关系时我们枚举长度为 iii 的数字中首位和次首位的数字，即可得递推关系 dp[i][j][p]=dp[i−1][k]...

2021-10-19

0 1042

官方题解 | #串#

串难度：4星 dp[i][0]dp[i][0]dp[i][0] 为前iii个字符中不包含字母 uuu 的情况数量。 dp[i][1]dp[i][1]dp[i][1]为前i个字符中包含字母 uuu 且不包含 ususus 子序列的情况数量 dp[i][2]dp[i][2]dp[i][2]为前i个字符...

2021-10-19

0 469

官方题解 | #郊区春游#

郊区春游难度：5星解法1 我们设 dp[i][j]dp[i][j]dp[i][j] 为状态值为 iii ，并以 jjj 号地点为终点的路程最小值。其中状态值是指每个地点是否走过的状态的二进制，1代表走过，0代表没走过。那么转移方程是： if((1<<k)&i==1)then...

C++

2021-10-19

3 829

题解 | #红和蓝#

红和蓝难度：4星可以先树形dp预处理出每个节点子树的节点个数。那么当且仅当每个节点满足以下条件有解：若当前节点x与父节点颜色相同，那么它的子节点子树大小必须为偶数，子节点颜色和x不同。若当前节点x与父节点颜色不同，那么它的子节点子树大小一定有且仅有一个奇数、其他的均为偶数。x的“奇数...

C++

2021-10-19

1 790

官方题解 | #旅游#

旅游难度：3星这道题要求我们在树上取尽可能多的点，但要求不能有两个点相邻。并且要求 sss 点一定要取到。和“不相邻取数”那道题思路类似，我们定义 dp[i][0]dp[i][0]dp[i][0] 代表不取 iii 点时，以 iii 为根的子树能取的点数量最大值。定义 dp[i][0]dp[...

C++

2021-10-19

0 345

题解 | #小红的树#

小红的树难度：2星树形dp模板题。我们先预处理出每个节点子树的红色节点的数量。定义 dp[i]dp[i]dp[i] 为以 iii 为根的子树的红色节点的数量，那么转移方程是： dp[i]=∑x是i的孩子dp[x]+[i为红点]dp[i]=\sum_{x是i的孩子}dp[x]+[i为红点]dp[i...

C++

2021-10-19

0 855

官方题解 | #合并回文子串#

合并回文子串难度：4星定义 dp[i][j][k][p]dp[i][j][k][p]dp[i][j][k][p] 为 a 字符串的 [i,j][i,j][i,j] 区间、 b 字符串的 [k,p][k,p][k,p] 区间是否能构成回文子串（若能构成则 dp 值为1，反之则为0），那么显然最终答...

C++

2021-10-19

1 497

官方题解 | #[CQOI2007]涂色PAINT#

涂色PAINT 难度：3星定义 dp[i][j]dp[i][j]dp[i][j] 为 [i,j][i,j][i,j] 区间的涂色次数的最小值。那么有3种转移方式： ① dp[i][j]dp[i][j]dp[i][j] 由 dp[i+1][j]dp[i+1][j]dp[i+1][j] 转移而来。若 ...

2021-10-19

0 397

题解 | #【模板】完全背包#

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

C++

2021-10-19

8 875