Camp Day4 Div2
Jan 23, 2019 由 小羊
Problem G - 置置置换
满足条件的排列的模样是这样的:
↓↑↓↑↓↑↓↑↓↑↓↑↓↑⋯
那么它的对偶排列是这样的
↑↓↑↓↑↓↑↓↑↓↑↓↑↓⋯
先证明一个引理:已有一个符合条件的长度为 n 的排列时,对于任意一个 i,将该排列中所有大于等于 i 的元素增一,那么排列的增减性不变。由于排列具有局部性质,那么我们可以只考虑一个局部。如果局部中最小的元素增大了,那么最大的元素同时增大;如果局部中较大的元素增大了,那么不影响大小的偏序关系。
于是想要生成长度为 n 的排列时,可以从长度为 n−1 的排列转移而来。考虑生成以 i 为起始元素的排列,我们可以将所有大于 i 的对偶子串接在后面,并将该子串中大于 i 的元素增一。这样,我们就可以得到排列的构造方式了。
记 dp[n][s] 为长度为 n 的序列,以 s 为起始元素的排列个数,那么满足这样的一个转移方程:
dp[n][s]=i=n−s+1∑n−1dp[n−1][i]
由于数据范围 1≤n≤1000,那么这样转移是 O(n3) 的。观察到 dp[n−1][i] 在后期不会被修改,并且这是一个前缀和的形式,那么我们可以令
qzh[n][s]=i=1∑sdp[n][s]
这样我们可以边转移边求前缀和,并且新的转移方程
dp[n][s]=qzh[n−1][n−1]−qzh[n−1][n−s]
这样的转移是 O(n2) 的。
Problem A - 夺宝奇兵
观察走的路线可以知道:在路线中,A1,0A2,0+A2,1A1,1 与 A1,0A2,1+A2,0A1,1 这两种组合方式必然二选一,并且 An,0An,1 一定是会选入的,那么直接一遍扫描计算答案即可。
Problem F - 小小马
首先会知道,马每次跳会改变目标点的奇偶性。所以,如果起终点的奇偶性相同,那么不同颜色点必然是不同的。所以这时候可以忽略。
然后当宽度为 2 时,马只能左前右后跳,所以简单判断一下。如果 n=3,m=3,那么 (2,2) 和其他点就是孤立的,所以判断一下。当更大时,马可以跳满全场,所以~
Problem I - 咆咆咆哮
显然把所有的魔术性卡牌放在最后,这样魔法加成是最大的。因为不知道答案的攻击性卡牌数量,那么可以来一个枚举。
假设目前枚举的是有 x 张攻击性卡牌,那么有 n−x 张魔术性卡牌。考虑利用一个新的权值 ci=ai−bi,那么
x∈X∑ax+x∈X∑bx=x∈X∑cx+i=1∑nbi
所以贪心的选择 ci 前 x 大的几张卡牌作为攻击性卡牌,就可以得到这样的一个权值。对每种枚举的最大值取最大,就可以得到这道题的答案了。