平凡的小白

未归档

题解(64)

/ 注册

全部文章 / 未归档（共47篇）

DNA Sequence

DNA Sequence 题意：题目给m个病毒串，问不包含病毒串的长度为n的DNA p段有几个难度：两颗星思路：这个图是例子{“ACG”,”C”},构建树后如图所示，从每个结点出发都有4条边（A,T,C,G）•从状态0出发走一步有4种走法： –走A到状态1（安全）； –走C到状态4（危险...

dp状态压缩 AC自动机

2020-04-08

2 727

【每日一题】4月9日 Running Median 动态中位数来自专栏

Running Median 思路：用两个优先队列，一个维护大的一半，一个维护小的一半，小的一半放在根结点最大的优先队列q1里，大的一半放在根结点最小的优先队列q2里，如果q1中的数比q2多1个以上，就把q1的顶点移到q2中去；如果q2中的数比q1多1个以上，就把q2的顶点移到q1中去。如果q1....

对顶堆优先队列

2020-04-08

2 716

【每日一题】黑白树来自专栏

黑白树思路： 1.当一个点没有被下方已经选了的点覆盖到的时候，我们选择一个它或者它下方的能向上覆盖的最远的点。2.另外，其实我们也并不关心这个点选的哪个，只需要知道往上能覆盖多远就行了，这个值其实可以直接维护到k数组里面，实际操作就是：首先处理的一定是叶子结点y，它的k值就是题目输入的值，它父亲结...

DFS 贪心树状dp

2020-04-08

0 578

【每日一题】Shortest Path 来自专栏

Shortest Path 思路：由题意可知是一个树形结构。若要使两两之间边权最小，尽量不能选重边，也就是说尽可能在节点所在子树里寻找答案。显然与叶子节点相连的边必须选。假设当前结点为x，如果tot[x]&1==1也就是x的子树的结点数(包括x自己)为奇数时，x和父亲的边就一定要选，即答案...

DFS 树状结构

2020-04-08

1 507

枚举优化

数码 1.解释： 1.最先想到的就是直接模拟了，引用每日一题的例子：eg:l=3 r=6:x=3 因子有1 3x=4 因子有1 2 4x=5 因子有1 5x=6 因子有1 2 3 6会发现当确定一个因子1时，另外一个因子为3，4，5，6(6=6/1);当确定一个因子2时，另外一个...

枚举优化

2020-04-08

1 553

dfs序

树思路：感觉和dfs序联系不大，画个图后发现涂颜色只有两种方案(引用每日一题的图片)：1.使用用过的颜色，但是一定要和它处理过的父结点或者儿子结点涂一样的颜色，只有这样才能保证一样颜色的点在一个路径上；2。使用没用过的颜色，已经用了j-1种颜色，所以还剩k-j+1种颜色可以涂可以用dp来求解...

dfs序

2020-04-07

1 824

牛客OI周赛15-普及组

嘀咕一下：原本以为和前几次的的题目一样的难度，结果我就会写一题，线段树当时还没学，多组背包还不会，但是其实这个难度还是可以接受的传送门 A-咪咪游戏题目大意：每次询问你一个字符串，判断是否由mq连接而成难度：看懂了题目要你做什么就很好做出来了，一道签到题题目类型：模拟思路： 1.由mq连...

树状数组线段树思维 dp

2020-04-07

2 577