Camp Day4 Div2

Problem G – 置置置换

满足条件的排列的模样是这样的:

\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\cdots

那么它的对偶排列是这样的

\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\cdots

先证明一个引理:已有一个符合条件的长度为 n 的排列时,对于任意一个 i,将该排列中所有大于等于 i 的元素增一,那么排列的增减性不变。由于排列具有局部性质,那么我们可以只考虑一个局部。如果局部中最小的元素增大了,那么最大的元素同时增大;如果局部中较大的元素增大了,那么不影响大小的偏序关系。

于是想要生成长度为 n 的排列时,可以从长度为 n-1 的排列转移而来。考虑生成以 i 为起始元素的排列,我们可以将所有大于 i 的对偶子串接在后面,并将该子串中大于 i 的元素增一。这样,我们就可以得到排列的构造方式了。

dp[n][s] 为长度为 n 的序列,以 s 为起始元素的排列个数,那么满足这样的一个转移方程:

dp[n][s] = \sum_{i=n-s+1}^{n-1} dp[n-1][i]

由于数据范围 1 \le n \le 1000,那么这样转移是 O(n^3) 的。观察到 dp[n-1][i] 在后期不会被修改,并且这是一个前缀和的形式,那么我们可以令

qzh[n][s] = \sum_{i=1}^{s} dp[n][s]

这样我们可以边转移边求前缀和,并且新的转移方程

dp[n][s] = qzh[n-1][n-1] – qzh[n-1][n-s]

这样的转移是 O(n^2) 的。

Problem A – 夺宝奇兵

观察走的路线可以知道:在路线中,A_{1,0}A_{2,0}+A_{2,1}A_{1,1}A_{1,0}A_{2,1}+A_{2,0}A_{1,1} 这两种组合方式必然二选一,并且 A_{n,0}A_{n,1} 一定是会选入的,那么直接一遍扫描计算答案即可。

Problem F – 小小马

首先会知道,马每次跳会改变目标点的奇偶性。所以,如果起终点的奇偶性相同,那么不同颜色点必然是不同的。所以这时候可以忽略。

然后当宽度为 2 时,马只能左前右后跳,所以简单判断一下。如果 n=3,m=3,那么 (2,2) 和其他点就是孤立的,所以判断一下。当更大时,马可以跳满全场,所以~

Problem I – 咆咆咆哮

显然把所有的魔术性卡牌放在最后,这样魔法加成是最大的。因为不知道答案的攻击性卡牌数量,那么可以来一个枚举。

假设目前枚举的是有 x 张攻击性卡牌,那么有 n-x 张魔术性卡牌。考虑利用一个新的权值 c_i=a_i-b_i,那么

\sum_{x \in X}a_x + \sum_{x \not\in X}b_x = \sum_{x \in X}c_x + \sum_{i=1}^n b_i

所以贪心的选择 c_ix 大的几张卡牌作为攻击性卡牌,就可以得到这样的一个权值。对每种枚举的最大值取最大,就可以得到这道题的答案了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注