bibibibi

分类

题解(21)

/ 注册

全部文章（共21篇）

题解 | #红和蓝#

描述给定一棵树，对每个节点用两种颜色染色，要求每个点周围只有一个点和其同色，如果可以输出方案，如果不可以输出-1 思路写的好拉啊？但是没想到很优雅的写法啊？本质上是个匹配的问题，即树上每个点只能匹配一个点，问可不可以每个点都有匹配，设树的根为111，dp[i][0]dp[i][0]dp[i]...

C++

2021-11-15

0 530

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

描述给定一个区间[a,b][a,b][a,b]，为在这个区间当中[0,9]每个数字出现在各个数位上的次数思路数位dp模板题目，设dp[i][j][k]dp[i][j][k]dp[i][j][k]表示考虑到第iii位，要计算的数是jjj，并且jjj之前出现了kkk次的方案数，采用记忆化搜索的方...

C++

2021-11-15

1 683

题解 | #合并回文子串#

描述给定两个字符串a和b，将两个字符串合并为c，要求两个字符串内部的顺序不变，求c的最长回文子串最大为多大思路区间dp的入门题目，设dp[la][ra][lb][rb]dp[la][ra][lb][rb]dp[la][ra][lb][rb]表示考虑字符串a的[la,ra)[la,ra)[la...

C++

2021-11-15

0 535

题解 | #[CQOI2007]涂色PAINT#

描述给一个长度为nnn的空字符串，每次选定一个子串染色，问将字符串染成目标颜色的最小次数思路经典的区间dp的题目，设dp[i][j]dp[i][j]dp[i][j]表示将区间[i,j][i,j][i,j]染成目标颜色的最小花费，转移方程为 dp[i][j]={mink∈[i,j](dp[i...

C++

2021-11-15

0 428

题解 | #小红取数#

描述给一个数组，要求从数组中选取一些数，使得这些数的和为kkk的倍数且和最大思路类似于背包的一个题，设dp[n][m]dp[n][m]dp[n][m]表示考虑前nnn个数，选取的数对kkk取模为mmm的最大价值转移方程为dp[n][m]=dp[n−1][(m−a[n])%k]+a[n]dp...

C++

2021-11-09

0 613

题解 | #旅游#

描述在一棵树上选择一些点，要求选择的点不相邻，问最多选多少点思路设dp[i][0]dp[i][0]dp[i][0]表示以iii为根的子树且不选iii节点最多能选多少点，dp[i][1]dp[i][1]dp[i][1]表示以iii为根的子树且选iii节点最多能选多少点，令树的根为sss，由于s...

C++

2021-11-09

0 436

题解 | #串#

描述问有多少字符串满足以下条件：长度不超过nnn 包含子序列us 结果对1e9+71e9+71e9+7取模思路典型的dp问题，设dp[n][0]dp[n][0]dp[n][0]表示长度为nnn且不包含字母u的字符串数目，dp[n][1]dp[n][1]dp[n][1]表示长度为nnn字...

C++

2021-11-09

3 412

题解 | #字母收集#

描述给一个n∗mn*mn∗m的字母矩阵，每个字母对应一个价值，问从左上角出发所能达到的最大价值思路二维DP，令dp[i][j]dp[i][j]dp[i][j]表示从左上角到达(i,j)(i,j)(i,j)所能得到的最大价值，则答案为dp[n][m]dp[n][m]dp[n][m]，初始化时，...

C++

2021-11-07

0 410

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

描述给一个长度为nnn的数组aaa，mmm次操作，左上角为(x1,y1)(x_1,y_1)(x1,y1)，右下角为(x2,y2)(x_2,y_2)(x2,y2)加kkk，问mmm次操作后的数组思路差分模板题，由于仅有一次查询，因此可以利用前缀和的性质，设数组sumsumsum表示mm...

C++

2021-11-07

4 639

题解 | #【模板】差分#

描述给一个长度为nnn的数组aaa，mmm次操作，每次将区间[l,r][l,r][l,r]加kkk，问mmm次操作后的数组思路差分模板题，由于仅有一次查询，因此可以利用前缀和的性质，设数组sumsumsum表示mmm次操作后，每个位置增加的数为多少，则每次操作将sum[l]+ksum[l]+...

C++

2021-11-07

0 434