RK_little
RK_little
全部文章
题解
翻译(1)
归档
标签
去牛客网
登录
/
注册
rk$ blog
~ welcom ~
全部文章
/ 题解
(共38篇)
2022-W1-A 九小时九个人九扇门
九小时九个人九扇门 对于每个人来说,他们都有一个数,并且这些数的范围是 [0 , 9] 我们很容易的想到使用DP的思路来解决问题。 我们设 f[n , m] 表示前 n 个人一共可以组合出来多少个结果为 m 的个数。 那么我们便可以得到这样的转移式子对于第 i 个人来说,其本身就是一种情况,因此 f...
动态规划
2022-01-25
3
604
CF24D Broken robot
CF24D Broken robot 题意 我们有 N×MN \times MN×M 大小的网格。我们有一个点,他可能会向左中右下(不会突破边界),这四个方向走动。我们的目标是最后一行,求解从点 (x , y) 走到最后一行的期望步数是多少。 思路 假设我们当前处于第 iii 行。我们可以得到如下的...
高斯消元
后效性处理
2022-01-22
0
367
P1272 重建道路
P1272 重建道路 题意 给出一颗有 n 个节点的树,求问分解出一个含有 p 个节点的子树最少需要删去多少条边。 思路 假设我们要以一个节点为根,那么我们不妨定义 f[i , j] 用以表示节点 i 包括其根形成了具有 j 个结点的子树。 那么对于一个节点 u,我们可以直接得到f[u ,1] 的值...
树形DP
2022-01-21
0
314
P2495 消耗战
P2495 消耗战 题意 我们有一个树,它的根节点为 1 ,它的每条边都有相应的权值,我们每次都会产生一些点,要求如果要将这些点通过删边的方式使之不与根节点相连,求删去边权和的最小值。 思路 暴力 如何暴力做? 设 f[i] 表示所有的处理完这点的最小值 第一步,当我们输入我们所有的点之后,我们将所...
虚树
树形DP
2022-01-19
0
391
P4381 Island
P4381 Island 题意 有 nnn 个点,每个点 iii 都有一条出发到 aia_iai 的边有权值 wiw_iwi 。 求这些点形成的基环树他们的直径之和。 思路 对于这样的一个基环树 11 3 23 15 8 10 7 12 9 7 1 3 10 6 2 5 15 3 2 5 1 1...
单调队列
基环树
2022-01-18
0
321
P2607 骑士
P2607 骑士 题意 有 nnn 个点,第 iii 个点连着 aia_iai 点。其中每个点都有一个权值。对于每条边而言,其两端的点不可以同时加入总和。我们要求总和最大值。 思路 可以借鉴之前的blog 首先,这个图可以看出是一个个基环数组成。我们要求的就是所有基环数的总和最大值的和。 对于一个...
基环树
树形DP
2022-01-18
0
334
CF1627D No Adding
CF1627D No Adding 题意 有一组两两各不相同的数字,每次我们可以进行如下的操作。 取两个数字 [x,y] 如果 gcd(x,y) 没有在这组数字中将其加入这组数据。 求问,最多可以加多少组数字。 思路 如果将每个数字进行唯一分解的话,我们可以发现我们添加的数字就是那些数字的相同部分。...
数组
数学
2022-01-16
0
364
CF1624 F
CF1624 F 题意简述 这是一道交互式题目。 有一个数 xxx 和一个数 nnn 其中 1≤x<n1\le x < n1≤x<n 你可以进行如下的询问: + c 将 xxx 的值变为 x+cx + cx+c 其中 1≤c<n1\le c < n1≤c<n ...
贪心
二分查找
2022-01-13
0
289
题解 | 普及组周赛27
普及组周赛27 A 首先能围住一定是在 x 轴和 y 轴上都有 由两点之间线段最短可知,围栏的长度就是这两点间的距离 所以找最短的 x 和 y 就可以啦。 code B 就推导一下就可以啦 code C 如果 k > 1 那么成倍增长一定比一个一个加快,所以模拟就可以了。 code D 两...
2021-07-09
0
405
B - 系数
B - 系数 这个题目证明方法暂时没有想出来,但是已经可以通过打表的方式解决掉了。 化简 首先 , 在取模的意义下 然后我所要的第 k 项就是 那么只要求出 最后的组合数关于 3 取模的值即可。 首先有如下的打表代码 。 打表 #include<iostream> using nam...
2021-02-25
6
509
首页
上一页
1
2
3
4
下一页
末页