shyyhs

题解

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38)

/ 注册

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

Tree 来自专栏

思路应该是个比较基础的换根吧...我相信我再做几个换根应该都能做出来的!令表示这个节点的联通点集的数量.那么一个很显然的一个方程就是其中是的子节点.这个点的联通点集数量就是子节点的联通点集数量的选取,以及不选取的方案数的乘积.由此我们可以的算出一个点的答案是多少.然后考虑换根,的子节点的答案怎么算...

dp

2021-03-03

8 855

PLEASE 来自专栏

前言一个推式子的题目.题目给你三个杯子,以及一个币,开始的时候币在中间杯子,每次你都可以控制两侧杯子和中间杯子交换,问你次之后在中间杯子的概率.其中. 思路粗略的想一想会发现,分母是,因为下一层状态数一定是上一层的两倍.假设我们令表示到了第次,的状态数,很显然的是一定不可以产生,而其他每次一定可...

数学 dp

2021-02-21

2 760

Work Group 来自专栏

思路定义表示为根节点的子树选取奇数/偶数个数所获得的最大权值是多少.然后直接dfs转移即可. 代码 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5,M=2; co...

dp

2021-02-10

2 663

Relay Race 来自专栏

思路: 比较细节的一个题目,类似<传纸条>.但是<传纸条>那题点权只有正数,而这题点权有负数,我们还是设立和传纸条那题的方程.令表示到了第步,第一个位于的行的位子,第二个位于行的位子能够获得的.那么方程真的很好写,这里就不叙述了. 细节 1.因为这里有负权,不是说两条路不重...

dp

2021-02-08

2 647

Spy Syndrome 2 来自专栏

思路: 观察到只有,而所有子串的各自的长度不超过.那么很显然的一种方法,就是进行串的一一匹配.因为答案保证一定有解,我们只需要记录一种合法解即可,那么我们记录当前合法的哈希值,然后用记录每个子串哈希值对应的字符串.然后就是一个一般的线性了.本题没有什么坑点,对于哈希,我们采取进制数处理即可,然后用 ...

dp 哈希

2021-02-07

4 612

Stars Drawing (Hard Edition) 来自专栏

思路: 这题思路还是比较好的,对于这种十字形状的图形,我们可以设置一个表示这个点上下左右四个方向可以延续的长度是多少.然后转移十分简单,这里就不写了.然后我们贪心的把每个可以取的位子全部取了,都取.最后再前缀记录一下是否被全部覆盖,假如存在没有被覆盖的,那么答案就输出.否则就是所有存在里的答案了. ...

贪心 dp

2021-02-07

4 613

Classy Numbers 来自专栏

思路: 了解过数位的,这题一定是可以写出来的.我们用表示到了第i位无限制的条件下填了个~的方案数.然后对于限制和非限制进行一个讨论即可.就是一个简单的递归,最后答案是.但是有个细节值得注意,了我一会,就是你应该放到返回答案的前面,不然就会出..数组越界.(因为我只开了.) 代码: #include ...

dp

2021-02-07

6 627

Dima and Salad 来自专栏

思路: 一道很不错的01背包问题,比那些普及-的模板题好太多了. 首先假如你不往背包的方向想,那么我们肯定有个贼简单的想法,表示到了第个,第一个的权值为,第二个的权值为的是否存在,个人觉得内存是没问题的,分析下时间复杂度是的,显然不可取. 那么我们往背包考虑,把每个物品的体积看成,权值为.然后做一次...

dp

2021-02-03

3 635

Subsequences (hard version) 来自专栏

思路: 我们令表示到了第i个位子,长度为j且不同的字符串有多少.很显然,到了第i个位子,长度为j,第j个位子可以选,然后前面选取j-1个长度,或者第j个位子不选,前面选取j的长度.但是这样会有重复的,这时就要容斥一下了,所包含的重复状态一定是.然后第i个选长度为0的方案数都是1.这个题就解决了.当然...

dp

2021-02-03

3 753

Beautiful Array 来自专栏

思路: 首先我们知道最大连续子序列的和的dp方程是:.这题要我们求使得某一度乘以,然后求.一个显然的暴力是左边求一次最大连续子序列,右边求一次最大连续子序列,然后中间乘以.但是这样的时间复杂度是的,显然不可取.那我们换种思路直接线性dp.令表示到了第几个数,状态是哪个.这里我们设立三个状态::表示以...

dp

2021-01-31

3 617