🌑

小羊儿的心情天空

Camp Day4 Div2

Jan 23, 2019 由 小羊

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

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

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

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

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

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

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

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

dp[n][s]=qzh[n1][n1]qzh[n1][ns]dp[n][s] = qzh[n-1][n-1] - qzh[n-1][n-s]

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

Problem A - 夺宝奇兵

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

Problem F - 小小马

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

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

Problem I - 咆咆咆哮

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

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

xXax+x∉Xbx=xXcx+i=1nbi\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

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