其实是牛哥 - 个人主页动态

2021-10-19 16:02

官方题解 | #[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][p]dp[i][j][p] = dp[i-1][k][p]dp[i][j][p]=dp[i−1][k][p] 其中 iii 是数字长度， jjj 是第 iii 位数字的首位， kkk 是第 i−1i-1i−1 位数字。即长度为 iii 的所有数字一定包含了长度是 i−1i-1i−1 的数中出现的所...

0 点赞评论收藏

2021-10-19 16:00

清华大学数字IC前端设计

官方题解 | #串#

串 难度：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个字符中包含 ususus 子序列的情况数量。 由于字符串中 uuu 之前是否存在 sss 对结果不产生影响，因此也可以直接不考虑前i个字符中是否包含 sss 的情况。 可得转移方程： dp[i][0]=dp[i−1][0]∗25dp[i][0] = dp[i-1][0]*25dp[i][0]=dp[i−...

0 点赞评论收藏

2021-10-19 15:59

清华大学数字IC前端设计

官方题解 | #郊区春游#

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

0 点赞评论收藏

2021-10-19 15:57

清华大学数字IC前端设计

题解 | #红和蓝#

红和蓝 难度：4星 可以先树形dp预处理出每个节点子树的节点个数。那么当且仅当每个节点满足以下条件有解： 若当前节点x与父节点颜色相同，那么它的子节点子树大小必须为偶数，子节点颜色和x不同。 若当前节点x与父节点颜色不同，那么它的子节点子树大小一定有且仅有一个奇数、其他的均为偶数。x的“奇数大小子树”的那个子节点颜色和x相同，其他都和x不同。 #include<bits/stdc++.h> using namespace std; vector<int>g[200020]; int dp[200020]; int su(int x,int pr){ ...

0 点赞评论收藏

2021-10-19 15:55

清华大学数字IC前端设计

官方题解 | #旅游#

旅游 难度：3星 这道题要求我们在树上取尽可能多的点，但要求不能有两个点相邻。并且要求 sss 点一定要取到。 和“不相邻取数”那道题思路类似，我们定义 dp[i][0]dp[i][0]dp[i][0] 代表不取 iii 点时，以 iii 为根的子树能取的点数量最大值。定义 dp[i][0]dp[i][0]dp[i][0] 代表取了 iii 点时，以 iii 为根的子树能取的点数量最大值。 然后我们以 sss 为根进行dfs，这样可以把子树状态转移到当前节点的状态。dfs结束后，由于 xxx 点是必须遍历到的，所以 xxx 周围的一定不能选，只需要统计对应的 dp[i][0]dp[i][0]...

0 点赞评论收藏

2021-10-19 15:53

清华大学数字IC前端设计

题解 | #小红的树#

小红的树 难度：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]=∑x是i的孩子dp[x]+[i为红点] 只需要在dfs的时候进行转移即可。 #include<bits/stdc++.h> using namespace std; vector<int>g[100020]; int dp[100010]; string s; int ...

0 点赞评论收藏

2021-10-19 15:52

清华大学数字IC前端设计

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

合并回文子串 难度：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），那么显然最终答案是所有 dp 值为 1 的对应 (j−i+1)+(p−k+1)(j-i+1)+(p-k+1)(j−i+1)+(p−k+1) 的最大值。 dp 方程的转移方法是： dp[i][j][k][p]=1dp[i][j][k][p]=1dp[i][j][k][p]=1 的充要条件是：满足以下 4 个条件任意...

0 点赞评论收藏

2021-10-19 15:48

清华大学数字IC前端设计

官方题解 | #[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] 转移而来。若 s[i]==s[i+1]s[i]==s[i+1]s[i]==s[i+1] 或者 s[i]==s[j]s[i]==s[j]s[i]==s[j] 那么不需要额外的次数，否则次数加一。 ① dp[i][j]dp[i][j]dp[i][j] 由 dp[i][j−1]dp[i][j-1]dp[i][j−1] ...

0 点赞评论收藏

2021-10-19 15:44

清华大学数字IC前端设计

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

完全背包 难度：3星 设 dp[i][j]dp[i][j]dp[i][j] 为前iii个物品，背包容量为jjj的最大价值。 那么考虑第iii个物品是否放入，有两种情况： 如果不放，那么等同于前i−1i-1i−1个物品，容量为jjj的背包的最优方案。 如果放，又可以分为放1个，2个....k个，同01背包的转移方程, 只不过max中的2项就变成了k−1k-1k−1项： dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]]+w[i],dp[i−1][j−2v[i]]+2w[i],...,dp[i−1][j−kv[i]]+kw[i])dp[i][j] = max(dp[...

wangxin-dlut：我就一直疑惑，当可以加入无限个第i个物品，为什么不用对加入k个i进行循环判断，原来是这样，谢谢老哥

0 点赞评论收藏

2021-10-19 15:27

清华大学数字IC前端设计

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

01背包 难度：3星 设 dp[i][j]dp[i][j]dp[i][j] 为前iii个物品，背包容量为jjj的最大价值。 那么考虑第iii个物品是否放入，有两种情况： 如果不放，那么等同于前i−1i-1i−1个物品，容量为jjj的背包的最优方案。 如果放，那么等同于前i−1i-1i−1个物品，容量为j−v[i]j-v[i]j−v[i]的背包的最优方案，再加上第iii个物品的价值。 那么可以得到转移方程： dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]]+w[i]dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+w[i]dp...

0 点赞评论收藏

2021-10-19 15:25

清华大学数字IC前端设计

题解 | #小红取数#

小红取数 难度：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[i]k−a[i] ，之后加上 a[i]a[i]a[i] 才能正好被k整除。 所以一维数组是不够的，需要开二维数组：dp[i][j]dp[i][j]dp[i][j] 代表前 iii 个数里面，取一些数，相加的和除以 kkk 的余数为 jjj 的最大值。 这样就得到转移方程： dp[i][(j+a[i...

0 点赞评论收藏

2021-10-19 15:23

清华大学数字IC前端设计

官方题解 | #字母收集#

字母收集 难度：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方程： dp[i][j]=max(dp[i−1][j],dp[i][j−1])+val[i][j]dp[i][j]=max(dp[i-1][j],dp[i][j-1])+val[i][j]dp[i][j]=max(dp[i−1][j],dp[i][j−1])+val[i][j] 其中 val[i][j]...

0 点赞评论收藏

2021-10-19 15:22

清华大学数字IC前端设计

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

【模板】二维差分 难度：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_1]sum[x1][y1] 加上 kkk ， sum[x2+1][y1]sum[x_2+1][y_1]sum[x2+1][y1] 减去 kkk， sum[x1][y2+1]sum[x_1][y_2+1]sum[x1][y2+1] 减去 kkk，sum[x2+1][y2+1]sum[x_2...

0 点赞评论收藏

2021-10-19 15:19

清华大学数字IC前端设计

题解 | #【模板】差分#

【模板】差分 难度：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] 区间内每个数都加上了 kkk 。 所以我们只需要对所有的操作做如上处理（单次处理 O(1)O(1)O(1) 复杂度），最后做一个前缀和就行了。 #include<bits/stdc++.h> using namespace std; long long a[101010],dp[1010...

0 点赞评论收藏

2021-10-19 15:18

清华大学数字IC前端设计

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

【模板】二位前缀和 难度：3星 二维前缀和模板题。设 sum[i][j]sum[i][j]sum[i][j] 为左上角坐标为 [0,0][0,0][0,0] ，右下角坐标为 [i,j][i,j][i,j] 的子矩阵所有数之和。那么观察下图： 我们要求粉色部分的所有数之和（即④号），可以用下面的方式来求： sum[x2][y2]sum[x_2][y_2]sum[x2][y2]: ①+②+③+④ sum[x1−1][y2]sum[x_1-1][y_2]sum[x1−1][y2]: ①+③ sum[x2][y1−1]sum[x_2][y_1-1]sum[x2][y1−1]: ①+② s...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：