牛客练习赛92题解

A.D与数列

题意：给定三个数N,A，B,让我们构造一个序列满足该序列的中位数是A,平均数是B,序列中的数可以重复

题解：那么既然数是可以重复的，那么我们就可以输出先n-1个A
如果假设第n个数A,A<B,就给第n个数加上abs(n * (A - B))，如果A < B就给第n个数减去abs(n*(A - B)),就可以了
但是我比赛的时候写了一个很***的做法，使得n个数是不一样的，就很浪费时间

B.D与集合

题意：给定一个序列$a_1...a_n$，并给定一个数k,要求要这n个数分成k个集合，使每个集合的和都是非负数

题解：要求是非负数，如果我们把负数和正数放到一个集合中，就会使问题变得很难考虑，那么我们考虑将负数和正数分开考虑，不让他们在同一个集合中，至于0，随便塞到一个负数或者正数的集合就行了
那么我们最多就会有cnt = （负数个数）+ （正数个数）个集合，随便合并两个正数或者两个负数集合，我们就会得到cnt - 1个集合，一次类推
如果k大于了我们上限cnt个集合，就是无解，然后我交了，wa了几发，发现我们这种构造方法，最少能构造2个集合，那么k为1个时候，这种构造方法没有考虑，特判一下k为1就行了

C.D与c

题意：有两张无向图，都有n个点，第一张图有a条边，第二张图有b条边，问有多少种可能使得两张图至少有一条边相同

题解：这道题我一开始读假题了，把题目中说的没有重边和自环看成了两张图中不能有环，给我想了好久，发现自己读假题了，然后发现就是一个简单的排列组合问题，然后就开始对不起高中老师，把至少有一条边相同考虑错了，显然如果直接求解答案，那么我们需要考虑有1条边相同…到min(a,b)条边相同，就很麻烦，正难则反，我们考虑用总情况数-一条边也不同的数量 就得到了答案ans = c(m, a) * c(m, b) - c(m, a) * c(m - a, b) (m = n * (n + 1) / 2)

D.D与s

题意：有一张无向图，有n个点，m条边，图上有k个关键点，某人站在1号点，每一秒从图上删除一条边，假设某人在u点，存在一条边edge(u,v),那么他就可以这一秒内移动到v点，问此人是否能到达一个关键点，两人均采取最优策略

题解：这个问题考虑起来貌似很难，那么我们来想一想那些情况是必然能到达关键点的，假如当前所在点为u，如果有2个以上关键点与之相连，那么此人就能必胜，那么当前所在点就是一个必胜点，那么如果一个点与两个必胜点相连，那么当前也为必胜点，那么我们对整张图做一遍类似于拓扑排序的遍历标记必胜点，如果1号点为必胜点，那么即为"yes"

D.D与太阳

这道题是一道使用随机化的题目，以前从来没见过，交了四五十发，终于过了，暂时没觉得有什么价值，等以后发现有价值了再来写题解把