题目链接
https://codeforces.com/gym/102007
A- A Prize No One Can Win
题目大意
给一个序列，每个数表示物品的价值，要求选择一些数，使得任意两个物品的价格不能严格大于W
分析思考
必然是最大的两个相加不大于w 即可。
但是这个题的特殊情况就是：考虑所有物品都大于W
B-Birthday Boy
题目大意
给你一些日期，表示同事的生日。要找到一个日期。离上一次同事过生日最久
分析思考
这是一个需要细心的模拟题。
那么计算两个日期之间的距离。要仔细一点。
C-Cardboard Container
题目大意
给定一个V，要求出一个立方体，满足表面积最小
分析思考
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[k]=k!−（大于等于一个有序元素的序列的方案数）
我们考虑第一个有序元素如果是 a[i]的话。
那么，前 i−1个元素是无序的，后面的数可以任意排， P[i-1] * (k-i)!
P[k]=k!−∑i=1kP[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≤10）个隐藏处，每个隐藏处有一个容量上限，让n个点，都跑到隐藏处中，问最短时间。
分析思考
我们把n个点以到各个隐藏处的最短时间为权值，如果一个点能够到达一个隐藏处，则在两者之间建一条边，构成一个网络流。
如果能够拉满流的话就可以找到解
但是这样的话，时间复杂度过高，由于点的个数非常多，所以网络流是无法跑的。
因此。我们只要考虑对对于一些能够到达的相同s点的那些点来说，可以合并成1个点，这样我们就可以把所有的点转化为1024种不同的点了。
那么在原来的图中成立的结论，在新的图中自然也成立。
J-Janitor Troubles
题目大意
给定四条边，求四边形面积最大是多少
分析思考
四边形面积的求法有很多种，我们知道，四边形的面积 S=AC∗BD∗sinθ
所以，已知AB,BC,CD,DA时，选择三分一下对角线长度
K-Kingpin Escapev
题目大意
给一颗树，问至少添加多少条边，能够使得删去任意一条边后，根结点依然能够达到其他结点
分析思考
首先，我们要实现，在图中不存在度为1的点，这样才可能满足条件。
因此此问题只需要对叶子结点进行连边。设叶子结点的个数为 l,所以我们可知，答案 ≥⌈l/2⌉
但是，如果在一个子树内，内部两两进行连接，就是不可行的。所以。我们就必须要考虑与外部的点相连。
那么给所有的点，按照DFS序，写一个编号。
我们可以知道 当我距离取 ⌊l/2⌋，必然可以保证能够跨越一个子树。
所以，我们让 vi与 vi+⌊l/2⌋ 匹配，就可以满足要求了
PS：H题还没有看懂。暂时留着等待更新
京公网安备 11010502036488号