RK_little

分类

翻译(1) 题解(39)

/ 注册

全部文章（共38篇）

2022-W1-A 九小时九个人九扇门

九小时九个人九扇门对于每个人来说，他们都有一个数，并且这些数的范围是 [0 , 9] 我们很容易的想到使用DP的思路来解决问题。我们设 f[n , m] 表示前 n 个人一共可以组合出来多少个结果为 m 的个数。那么我们便可以得到这样的转移式子对于第 i 个人来说，其本身就是一种情况，因此 f...

动态规划

2022-01-25

3 644

CF24D Broken robot

CF24D Broken robot 题意我们有 N×MN \times MN×M 大小的网格。我们有一个点，他可能会向左中右下(不会突破边界)，这四个方向走动。我们的目标是最后一行，求解从点 (x , y) 走到最后一行的期望步数是多少。思路假设我们当前处于第 iii 行。我们可以得到如下的...

高斯消元后效性处理

2022-01-22

0 396

P1272 重建道路

P1272 重建道路题意给出一颗有 n 个节点的树，求问分解出一个含有 p 个节点的子树最少需要删去多少条边。思路假设我们要以一个节点为根，那么我们不妨定义 f[i , j] 用以表示节点 i 包括其根形成了具有 j 个结点的子树。那么对于一个节点 u，我们可以直接得到f[u ,1] 的值...

树形DP

2022-01-21

0 350

P2495 消耗战

P2495 消耗战题意我们有一个树，它的根节点为 1 ，它的每条边都有相应的权值，我们每次都会产生一些点，要求如果要将这些点通过删边的方式使之不与根节点相连，求删去边权和的最小值。思路暴力如何暴力做？设 f[i] 表示所有的处理完这点的最小值第一步，当我们输入我们所有的点之后，我们将所...

虚树树形DP

2022-01-19

0 428

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 351

P2607 骑士

P2607 骑士题意有 nnn 个点，第 iii 个点连着 aia_iai 点。其中每个点都有一个权值。对于每条边而言，其两端的点不可以同时加入总和。我们要求总和最大值。思路可以借鉴之前的blog 首先，这个图可以看出是一个个基环数组成。我们要求的就是所有基环数的总和最大值的和。对于一个...

基环树树形DP

2022-01-18

0 366

CF1627D No Adding

CF1627D No Adding 题意有一组两两各不相同的数字，每次我们可以进行如下的操作。取两个数字 [x,y] 如果 gcd(x,y) 没有在这组数字中将其加入这组数据。求问，最多可以加多少组数字。思路如果将每个数字进行唯一分解的话，我们可以发现我们添加的数字就是那些数字的相同部分。...

数组数学

2022-01-16

0 393

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 305

题解 | 普及组周赛27

普及组周赛27 A 首先能围住一定是在 x 轴和 y 轴上都有由两点之间线段最短可知，围栏的长度就是这两点间的距离所以找最短的 x 和 y 就可以啦。 code B 就推导一下就可以啦 code C 如果 k > 1 那么成倍增长一定比一个一个加快，所以模拟就可以了。 code D 两...

2021-07-09

0 444

B - 系数

B - 系数这个题目证明方法暂时没有想出来，但是已经可以通过打表的方式解决掉了。化简首先，在取模的意义下然后我所要的第 k 项就是那么只要求出最后的组合数关于 3 取模的值即可。首先有如下的打表代码。打表 #include<iostream> using nam...

2021-02-25

6 549