day 1- 2018-benelux-algorithm-programming-contest-bapc-18

题目链接
https://codeforces.com/gym/102007

A- A Prize No One Can Win

题目大意

给一个序列，每个数表示物品的价值，要求选择一些数，使得任意两个物品的价格不能严格大于W

分析思考

必然是最大的两个相加不大于w 即可。
但是这个题的特殊情况就是：考虑所有物品都大于W

B-Birthday Boy

题目大意

给你一些日期，表示同事的生日。要找到一个日期。离上一次同事过生日最久

分析思考

这是一个需要细心的模拟题。
那么计算两个日期之间的距离。要仔细一点。

C-Cardboard Container

题目大意

给定一个V，要求出一个立方体，满足表面积最小

分析思考

$v=a\ast b\ast c$v=a∗b∗c
枚举a 然后令 b,c最接近即可。

D-Driver Disagreement

题目大意

在一个图上，起点有可能在A 或者B ,那么从A 出发，向左，向右分别可以到达不同的位置，每个点都有一个标记颜色。那么最少需要多少步，才能区分出当前是在A点还是B点。

分析思考

这其实是一个有限自动机。
那么，如果要判断是否存在这样条路能够区分AB，只需要暴力BFS即可。
但是由于这个题目他的数据范围有些大。所以直接暴力BFS的复杂度显然有些高。
因此，考虑这里的优化

如果我们已知 (a,b)是无法判断的，(b,c)也是无法判断的
那么可以推出 （a,c）也是无法判断的。

证明过程

已知a,b是无法区分的 ，b,c也是无法区分的
那么 我们假设 a,c是可以区分的。
那么我们找到一条路径从a出发 到达一个点的颜色 是白色，相同路径从c出发到达的点是黑色。那么我们从b出发能到达的点到底是什么颜色呢？

很显然 b的颜色矛盾，所以a,b ,b,c无法区分，那么 a,c也是无法区分的。

那么知道了上面的结论，怎么样能够减少我们在BFS时候的状态呢？
我们假设我们加入BFS队列中的状态（a,b)就是无法区分的状态。
那么 当我加入(a,b),(b,c)的时候，就不用再加入（a,c)了。

如果说(a,c)确实是无法区分的话，这样做显然没有错。
那么如果说（a,c)是可以区分的，那么必然有(a,b) 或者（b,c）中一个是可以区分的，而这两种状态我们已经加入队列中了。所以不加入(a,c)不会影响结果的正确性

所以这个题目我们采用并查集。如果我们判断到状态(A,B)的时候，就把A,B加入并查集。然后如果更新到 A’,B’在同一个并查集中的时候，就不要更新了。

E-Entirely Unsorted Sequences

题目大意

定义有序元素x 满足 它前面所有的元素都比他小。它后面所有的元素都比它大。
给定一个序列。使得序列中所有的数都不是有序元素的方案数。

分析思考

对于这个题目，我们分两步做。
第一步，假设给定的序列中所有元素都是不相同的。
第二步，考虑这个序列中的重复元素。

令 p[k] 表示 k个不相同的元素可以组成的方案数

$p\left[k\right]=k!-（大于等于一个有序元素的序列的方案数）$p[k]=k!−（大于等于一个有序元素的序列的方案数）

我们考虑第一个有序元素如果是 $a\left[i\right]$a[i]的话。
那么，前 $i-1$i−1个元素是无序的，后面的数可以任意排， P[i-1] * (k-i)!

$P\left[k\right]=k!-{\sum }_{i=1}^{k}P[i-1]\ast (k-i)!$P[k]=k!−∑i=1k​P[i−1]∗(k−i)!

那么我们就可以求出有n个元素的情况了。

那么如果有重复的数据要怎么处理呢？

对于重复数据 假设 x 有cnt[x]个的话，只要除以 cnt[x]!就可以了

F- Financial Planning

题目大意

我们有n个项目，每个项目需要投资 a ，每天获益b，问最少几天，能够收益m元（收益指将投资的钱都还上后能够赚的钱）

分析思考

二分答案 x，如果一个项目经过x天后，能够赚钱，则计算赚的钱。加起来看看能不能超过m

G-Game Night

题目大意

给定一个序列，包含ABC，他们围成环，此时，需要把，A,B,C都放在一起
例如 ABABCBCAC -> AAABBBCCC
问最少有多少个元素需要交换位置

分析思考

统计 枚举A的起点，然后，暴力计算先B后C 和先C后B两种情况。计算不再位置上的元素个数

I-In case of an Invasion, please…

题目大意

给定一个带权图，图上有n个点，和s（ $s\le 10$s≤10）个隐藏处，每个隐藏处有一个容量上限，让n个点，都跑到隐藏处中，问最短时间。

分析思考

我们把n个点以到各个隐藏处的最短时间为权值，如果一个点能够到达一个隐藏处，则在两者之间建一条边，构成一个网络流。
如果能够拉满流的话就可以找到解

但是这样的话，时间复杂度过高，由于点的个数非常多，所以网络流是无法跑的。

因此。我们只要考虑对对于一些能够到达的相同s点的那些点来说，可以合并成1个点，这样我们就可以把所有的点转化为1024种不同的点了。

那么在原来的图中成立的结论，在新的图中自然也成立。

J-Janitor Troubles

题目大意

给定四条边，求四边形面积最大是多少

分析思考

四边形面积的求法有很多种，我们知道，四边形的面积 $S=AC\ast BD\ast sin\theta$S=AC∗BD∗sinθ

所以，已知AB,BC,CD,DA时，选择三分一下对角线长度

K-Kingpin Escapev

题目大意

给一颗树，问至少添加多少条边，能够使得删去任意一条边后，根结点依然能够达到其他结点

分析思考

首先，我们要实现，在图中不存在度为1的点，这样才可能满足条件。

因此此问题只需要对叶子结点进行连边。设叶子结点的个数为 $l$l,所以我们可知，答案 $\ge \lceil l/2\rceil$≥⌈l/2⌉

但是，如果在一个子树内，内部两两进行连接，就是不可行的。所以。我们就必须要考虑与外部的点相连。
那么给所有的点，按照DFS序，写一个编号。
我们可以知道 当我距离取 $\lfloor l/2\rfloor$⌊l/2⌋，必然可以保证能够跨越一个子树。
所以，我们让 $v_i$vi​与 $v_{i+\lfloor l/2\rfloor }$vi+⌊l/2⌋​ 匹配，就可以满足要求了

PS：H题还没有看懂。暂时留着等待更新