issue是云哥的小迷×呀

题解

未归档(1)

/ 注册

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

牛客练习赛74 CCA的期望(累加期望和)

传送门求期望的套路题转化为每个点染成黑色期望的累加和那么如果本来就是黑色,期望直接加上如果是白色,概率是多少呢??实际上可以考虑这个点在多少的最短路径上选点有种方式再计算有条最短路径经过这个点,那么一次操作覆盖这个点概率为那么至少覆盖一次期望就是累加即可至于一个点在多少最短路径上,...

2020-12-20

5 586

[SCOI2015]国旗计划

非常考验技巧的一题...emm这个我最不会了... 首先断环为链,也就是把士兵和站台复制一份放在后面,这样只需要考虑覆盖一个区间而已因为区间两两不包含,所以当选择了第个士兵后现在覆盖了那么从左端点不大于里选,一定是选右端点最大的最优秀了那么这样选择的士兵就固定了... 关键就找下一个士兵的过...

2020-11-27

2 703

A and B and Lecture Rooms

这题的思维难度并不很大但是细节有一点点需要注意首先两点间的距离如果是奇数必定无解如果是偶数,那么可以找到中间的那个点,必定满足条件而且从延伸出去的各种分支,只要不是包含的分枝都是满足条件的因为两点都是从拐过去的这个规律在任意时刻都是适用的但是当deep[l]==deep[r]注意一下计...

2020-11-27

2 729

[AHOI2008]MEET 紧急集合

不会证明,只会观察..... 两点肯定到最好三点求出两两的,然后....观察!! 发现三点的最短路就是用两条链把三点穿起来所以距离是两两距离和除以二然后三个最多有一个和其他的不同那么就选那个相同的点作为集合点,这样只会有一个点需要多走 #include <iostream> us...

2020-11-27

2 842

1029E.Tree with Small Distances(经典树dp)

传送门观察发现一定是从连出来的边最划算而且连到一个点之后,这个点周围的所有点都是满足要求的. 定义为和有连边为通过父亲到为通过儿子到那么那么但是如果的儿子没有一个和有边,还需要选一个儿子和相连... #include <bits/stdc++.h> using names...

2020-11-26

2 691

Bookshelves

定义为前个书分成组的最大价值这么转移是有后效性的价值不是越大越好观察到价值计算是与运算,可以一位一位单独考虑比如,如果每组都能凑齐,那这一位上必然是然后考虑能否凑齐,但是同时也要凑齐... 就这样一位一位去判断还是比较显然的.... #include <bits/stdc++.h&...

2020-11-26

3 836

Colorful Tree

好难写....完全想不到,也不会证明抄的https://ac.nowcoder.com/acm/problem/blogs/200179 好厉害呜呜 #include <bits/stdc++.h> using namespace std; typedef long long ll;...

2020-11-07

4 749

CF570D Tree Requests(dsu---板子题)

传送门使用数组表示当前子树内,深度字母为的有多少个那么可以开始,这样与有关的所有询问都可以快速得出解差不多就是板子了储存询问用或链式前向星 #include <bits/stdc++.h> using namespace std; const int maxn = 5e5+19;...

2020-11-07

4 838

选点

传送门注意一下这两句话如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；如果在左子树选了一个点，在右子树中选的其他点要比它小。根节点比子节点都要小右子树比左子树都要大所以可以跑序维护最长上升子序列来写 #include <bits/stdc++.h> using...

2020-11-07

4 723

Military Problem

不知道为什么这么裸... vec存图排个序然后按照dfs的顺序给节点小到大编号顺被维护一个表示节点编号是的是哪个节点... #include <bits/stdc++.h> using namespace std; const int maxn = 8e5+10; struct ed...

2020-11-07

3 704