【2019】纪中Life_2 Day1

# By shy >She wants to go home, >but nobody's home. ------------ 在期中考来临之际我又~~当了逃兵~~第二次来到了~~美丽的~~ `纪中`。 ~~没有期中考的感觉真好。~~ ## [题解](https://gmoj.net/senior/index.php/main/download/6387/solution_day2.pdf/0/solution_path) ## 1.小w与卡牌游戏 小w和小c各有n张扑克牌，每张牌上都有一个数字。游戏共进行n轮，每轮两人各会出一张扑克牌。 对于每一轮，牌面上数字大的人获胜并获得一分。鉴于小w是卡牌高手，所以他会让着小c。因此如果两张牌面的数字相同，则小c获胜。 小w获取了小c手上所有卡牌上的数字以及小c的出牌顺序，他想要知道一种出牌顺序，使得它的得分最多。 特别地，如果有多种合法的出牌顺序，他希望出牌顺序的字典序最大。 对于30%的数据，n<=10 对于另外20%的数据，数据保证只存在一种使小w得分最高的方案 对于100%的数据，n<=1000 数据保证1<=ci,wi<=10^9 ------------ 考场上写对30%枚举全排列计算最大得分，另外20%用二分图匹配，拿了50。 ### Solution： 步骤一、 如果没有字典序最大的要求，那么我们可以贪心地解决这个问题。将小c的牌和小w的牌都排序，从小到大考虑小 w 的牌，对于小 w 手上的每张牌，让它对上小c的手牌里比它小的所有牌中最大的那张即可。如果只有一种合法方案，这种做法可以获得最优解，时间复杂度 O(nlogn)。 步骤二、 我们先使用步骤一的方法求出小 w 的最高可能得分，然后再解决字典序最大这个要求。对于这个要求，我们可以从前往后一位一位贪心的解决。对于每一位，我们贪心地选择在不影响最高得分的情况下数字最大的牌。这个问题可以通过二分答案再贪心判定解决。对于每一位先二分这位填什么数字，再对于这个位置之后的位置使用步骤一贪心判定即可。 ------------ ### 2.小w学图论（graph） ### Solution: 对于一张完整图，它的染色方案数= $$\prod_{i=1}^n n-g[i]$$ 其中g[i]表示与 i 节点相连的编号大于 i 的节点数。 证明：考虑按照节点编号的顺序从大到小给节点染色，对于每个节点 i，所有和它相 邻的编号比它大的g[i]个节点都已经被染色，且这些节点两两之间都有连边，因此这些节点 两两颜色不同。因此对于节点 i，可供使用的染色方案数就是 n-g[i]。 因为边数最多 n^2 条，我们可以 O(n^2)暴力地把图建出来，对于每个点求出g[i]，把 n-g[i]乘起来即可。 时间复杂度 O(n^2)，期望得分 60。 对于100%： 其实不用把图建出来。对于每个节点维护一个和他相邻，边权比它大的节点的集合。 从小到大枚举每个节点 i，然后把节点 i 的邻集合并到和 i 相邻的所有节点中编号最小的 那个节点的集合即可。对于每个节点维护一个 set，合并可以使用启发式合并，这样时间复杂度就是 O(n*(logn)^2)。当然也可以对于每个节点建一棵动态开点的线段树，用线段树合并，这样时间复杂度就是O(n*logn)的。 以上两种方法，期望得分 100。 ------------ .END