shyyhs

题解

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

/ 注册

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

蓝魔法师来自专栏

思路思路应该算是比较简单吧...难点在于时间复杂度的证明.因为这题和的范围都是以内的.题目是让你切成若干份,每份大小都不超过,因为是一棵树,所以很容易想到树形.对于树形,我们很容易想到利用子树就行转移.那么我们要转移什么,才能让子树来跟新父节点呢?很显然的一个东西,我可以和子树分割,也可以不和子树...

dp

2021-03-05

2 938

Tree 来自专栏

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

dp

2021-03-03

8 854

The Cow Lineup 来自专栏

思路这题用类似进制的思想做,纵所周知,想要表示的几位数,那么在每一位上的都是可取的.那么我们直接遍历看是否都存在,看有多少都存在的段,答案就是这些段啦. 代码 #include <stdio.h> #include <string.h> using namespace st...

思维题

2021-03-02

3 859

区区区间来自专栏

思路只要记录线段树所有区间的一个左端点的值这个题就可以做完..我们可以假设这个左端点是,对于每次修改操作,我们只要知道左端点的值,我们这个区间修改的值就会变得已知,就可以更新,子区间的值也可以更新.总之还是线段树不熟练~. 代码 #include <bits/stdc++.h> usi...

线段树

2021-03-01

0 931

Inna and Sequence 来自专栏

思路对于这些操作全可以放到树状数组上进行,我们用权值记录,到了哪个位子有多少个数,假如要删除,我们直接二分query那个位子就好了,然后把那个点标记成-1,然后输出的时候-1就不输出,其他就输出.. 代码 #include <bits/stdc++.h> using namespace...

树状数组二分

2021-02-25

0 642

Coprime Subsequences 来自专栏

题目: 问你有多少子序列gcd为1. 思路: gcd为的数,是不是等于都包含因子的个数-包含因子的个数-包含因子的个数-包含因子5的个数+包含因子的个数...这样容斥一下.其实就是一个莫比乌斯函数.包含因子的个数的子序列,假设因子是个,那么方案数是不是.选/不选-全不选. 代码: #include ...

容斥原理

2021-02-24

2 664

Weak Memory 来自专栏

思路思路一眼就出来了...对吧?,但是时间还是卡的紧的啊...二分最小的油量,然后bfs这个地图,注意不要像普通的bfs一样标记...dij优先下油量多的地方,假如可以就缩小,不可以就放大..注意: if(T.val-1>use[v]) use[v]=T.val-1,q.push({v...

二分 dij

2021-02-23

1 851

PLEASE 来自专栏

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

数学 dp

2021-02-21

2 760

Giving Awards 来自专栏

思路: 因为给定的是个有向图,所以一定有解,构造方案就是把这个u当前它欠钱的人先安排好,然后直接输出方案就是一组解了...其实就是按dfs序统计即可啦... 代码: #include <bits/stdc++.h> using namespace std; const int N=1e5...

dfs

2021-02-21

1 583

Microtransactions (hard version) 来自专栏

思路二分答案,贪心验证.我们二分出最少需要多少天可以做完.然后贪心的把所有做的,推到我们二分答案限度内的最后一天,不是在我二分答案外的最后一天.不然类似下面的数据就过不去. 4 7 23 78 12 46 100 1 41 3 213 2 321 3 12 2 87 1 76 2 213然后本题...

二分贪心

2021-02-19

2 729