Day 10

在被正睿OI的各种拆位神仙操作后，今天拿到的是一套命名诡异的题目（似乎都是红歌？）。然后根据惯例爆零了qwq

T1 强军战歌

题目的大致意思是给你一个序列，求有多少种合法的删数方式使其成为一个不降的子序列。其中合法指最后一个删除的数放回后序列不满足单调不降。
我们考虑反向思考一波。因为所有的不合法序列都是删除的是某个单调不降的子序列的某个数构成的，那么我们可以很容易地想到：对于每个单调不降的子序列，我们删除其中任意一个数，都能构成一个不合法的删数方案，并且所有的不合法方案一定是这样产生的，我们可以考虑用树状数组维护来计算出长度为l的不降序列个数b_i，答案就是n!-\sum\limits_{i=1}^{n}(b_i * i)

T2 当那一天到来

妈耶怎么就考了题博弈论啊……看来叫NOIP模拟赛的可能都是神题啊【趴
显然，这个游戏存在平局的情况，这个游戏并不是有向图游戏。
由于甲、乙两个玩家一定采用最优策略，他们一定是走到中间点的两侧。简单证明一下就是若某一步甲走更优，则甲一定会在可能的情况下走这一步，乙一定会不让甲走这一步（即乙自己走一步），反之亦然。由于甲乙轮流行动，甲乙两人在每一轮一定会各走一步。
这样游戏结束时甲乙两人一定在中点两侧。我们分n为奇数和偶数两种情况考虑。
对于n为偶数的情况，最后结束时甲乙在\frac{n}{2}或\frac{n}{2}+1。由于最后一步是由甲走出的，只要在这两个点中任意一个点甲能够得到多于乙的分，甲就一定能取胜。
对于n为奇数的情况，最后结束时甲乙在\frac{n}{2}，\frac{n}{2}+1或\frac{n}{2}+2。由于最后一步由乙走出，只有在这三个点甲的分数都高于乙，甲才一定能够取胜。若\frac{n}{2}+1甲分数低于乙或\frac{n}{2}和\frac{n}{2}+2中任意一个低于乙，则乙一定有取胜的方案。否则则是平局局面。

T3 如果今天战争爆发

皇后游戏
这题可以说非常明显的是皇后游戏的变形了。我们考虑何时交换两个物品的加工顺序使得答案一定更优，根据该式子排序即可。