Ray.C.L

题解

/ 注册

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

蓝魔法师（树形DP）

思路：树上求方案，dp[i][j]表示以i的子树里连通块个数为j的方案数（j<=k）这里我们有2个选择， 1.删除当前边,此时节点u与他的的子节点v所能构成的方案数就是dp[u][x]乘上dp[v][1——x] 2.不删除当前边,此时节点u与节点v构成i+j（i为u的连通块个数,j为v的连通...

2020-08-05

0 703

追债之旅（最短路）

思路：平时我们学最短路dis[i]表示从1-i的最短路是多少，那么题设添加了一个条件我们也多一维dis[i][j]（j<=k）表示从1-i经过j天的最小花费，在跑最短路的时候判断一下是否超过K次，最后在dis[n][1——k]遍历一遍找最小值 #include <cstdio> #...

2020-08-05

0 629

购物

思路：和背包长得像，那么我们就往背包上想，dp[i][j]表示前i天我们买了j个糖果的最小花费，dp[i][j]可由dp[i-1][k]转移得到，那么怎么转移？j的范围要<=min(n,im)k就最小从i-1个糖果开始（再小就不符合题意）最大到min(j,min(n,(i-1)*m))当第i-...

2020-08-04

0 620

小A的最短路（LCA）

思路：在树上找2点的最短距离，很容易想到LCA，那么我们在树上找a,b的最短距离，因为缆车的存在所以有3种找法，一种是直接从a节点到b，第二种是a先到缆车x加上b到缆车y的距离，第三种就是a到缆车y加上b到缆车x的距离，我们取个最小值（~ 用C++11会TLE ~） #include <cst...

2020-07-31

0 564

兔子的区间密码

思路：异或值最大，我们就让每一位不同的尽可能多，那么给你区间l,r我们将l,r变成成2进制高位补齐，为了不超过L-R区间从高位向低位遍历时，遇到相同的我们就继续走，如果遇到某一位不同那说明从这一位开始后面的每一位0,1我们可以任选，使得从当前位置到后面的每一位异或后变成1，此时值最大 #includ...

2020-07-31

0 649

Xor path

思路：当一个数的异或次数为偶数时那么他没有贡献度，所以我们只需要看没个点被走了几次如果是奇数次那么他有贡献度，问题就变成如何求点被走了几次，我们用个数组表示一个个点的儿子个数是多少，假设v是u的儿子，通过dfs遍历u的整个子树，得到儿子的个数，那么从u-》v，u的次数就是p[v] * (n-p[v]...

2020-07-31

0 472

涂色PAINT

思路：用dp[i][j]表示从i到j涂好色的最少次数，从RGBGR这个样例我们可以发现，后面的颜色可以是前面就图好了，那么可以得当i,j相同时，这个i位置的颜色就是再涂区间i+1,j时涂好的，j位置是再涂区间i,j-1时涂好的dp[i][j]=min(dp[i+1][j],dp[i][j-1])。i...

2020-07-29

0 698

每日一题生日快乐（dfs+思维）

思路：我们用dfs去想,首先如果此时只有一个人那我们就直接返回答案，dfs（x，y，n）表示边长为x,y,切给n个人长边与短边之比最大值最小的值是多少，为了保证面积相同每次切若沿着x切必定是x/n的倍数若沿着y切必定是y/n的倍数，我们要看切完后分给多少个人，就看他当前切的是多少倍，然后我们按X,Y...

2020-07-16

0 682

平衡二叉树

思路：根据题意我们让左子树为高度n的满二叉树，右子树上的点尽可能少，那么我们首先吧他的高度拉满使其为n-m-1，此时我们在右子树的左子树上高度拉满点最少，然后如果还有点，那么为了维持平衡且让右子树点最少，我们吧点加到i-m+1的树上，可得方程dp[i]=dp[i-1]+dp[i-m-1]。dp[i]...

2020-07-06

0 509

毒瘤xor

思路：我们要他异或的和最大那么我们对第i位为1时X的第i为0，第i位为0时X的第i位为1，这时我们需要知道区间L-R的第i位是1多还是0多，用前缀和的思想sum[i][j]表示从1到第i个数的第j位上1的个数之和，要保证x最小那么我们再1的个数和0的个数相同的情况下将X的第i位置0 #include...

2020-07-03

0 564