DaMing

题解

/ 注册

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

B-经商(并查集+01背包)

题目描述任务一：有n个人，每个人只能选一次，会消耗a[i]精力得到b[i]收益，现有的精力值为C,求可以到达的最大收益思路这么看就是一个简单的01背包问题（用一维的话注意从大到小枚举c（精力））任务二这n个人之间存在友谊关系，我们只能选择跟1有关系的人，思路用简单的并查集维护，在01任务1求解的时候...

并查集 dp

2020-06-04

0 783

小A与小B(bfs/枚举/双向)

两种bfs解法解法一（315ms）：关于这种解，我最后放了个33%的代码，有没有大佬指正一下错误应该错在关于B的移动方式了。思路让A在图上跑一次bfs记录A到达每个点的最短时间让B在图上跑一次bfs记录B到图上每个点的最短时间然后枚举每个点让他们在这里相遇，取最小值注意小B每次是跑两个点代码 ...

bfs

2020-06-04

0 887

CQOI2010]扑克牌(二分答案)

题目描述： n种牌，每种a[i]个， m张万能牌，一次只可以代替一种牌组成一套的条件：每种牌各一张求最多组成的套数题解直接二分答案（最多能组成的套数）如果该种牌不够那么差的牌=mid-a[i]差几张我们就用几张joker 代替因为我们要组成mid套牌每套牌最多有一个joker 所以设添加t...

2020-06-03

0 750

德玛西亚万岁（状压dp）

由于状压dp是在位运算的基础上进行的，所以先了解一下一些基础的位运算操作我们把每一行的状态用二进制储存起来 ll x=read(); a[i]=(a[i]<<1)+x;假如输入的是101那么a[i]的变化过程为a[i]=1a[i]=2a[i]=55的二进制刚好是1...

2020-06-03

1 594

关押罪犯（并查集）

题目描述S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同...

2020-06-02

4 1470

任意点（并查集）

一个并查集的裸体对于两个点在什么情况下可以联通：横坐标相同或者纵坐标相同（在同一行或者同一列）然后求图中有几个联通块就可以了，假如有n个联通块，我需要加n-1个点能够使他们全部联通使得任两点之间可以互相到达代码 #include <map> #include <set> #i...

2020-06-02

0 706

加边的无向图（并查集）

并查集的裸体问加几条边可以使图中的点两两到达就是使图成为连通图也就是说所有点的根节点都指向一个点用数组p[j]记录j节点的根节点也就是说对于所有的点有且仅有一个点的 p[i]=i，也就是唯一的父亲节点如果有两个就说明图中有两个连通块也就是需要一条边取联通这两个块以此类推代码 #includ...

2020-06-02

1 1015

Cut（贪心/排序）

因为我们要求总代价最大，所以大的数字我们要让他尽可能晚的从序列中分割出来，因为这样就可以在每次算代价的时候都加上这个大的数字，这样就会使最后的总代价最大代码 #include <map> #include <set> #include <cmath> #inclu...

贪心

2020-06-02

1 650

旅游（树形dp）

题目描述Cwbc和XHRlyb生活在s市，这天他们打算一起出去旅游。旅行地图上有n个城市，它们之间通过n-1条道路联通。Cwbc和XHRlyb第一天会在s市住宿，并游览与它距离不超过1的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。他们不想住在一个已经浏览过的城市，又想...

树形dp

2020-06-01

3 861

Protecting the Flower(贪心)

一开口就是老贪心题了题意要求牛吃掉的最少的花，我们知道1.如果把运输时间短的牛放在前面先运输过去，可以减少牛吃花的数量2.如果把牛每分钟吃花多的放在前面也可减少牛吃花的数量定义r=t/d以上两种情况 t越大越靠前， d越小越靠前， ****综上所以r越大越靠前 #include <map&...

贪心

2020-05-30

1 551