大太阳shy 的Blog

大太阳shy 的Blog

古明地觉天下第一可爱~

【2019】纪中Life_2 Day1

posted on 2019-10-26 21:18:29 | under 纪中life |

By shy

She wants to go home,

but nobody's home.


在期中考来临之际我又当了逃兵第二次来到了美丽的 纪中

没有期中考的感觉真好。

题解

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(nlogn)的。 以上两种方法,期望得分 100。


.END