2021牛客暑期多校训练营4
AC Codes
B. Sample Game
C. LCS
构造 $3$ 个长度为 $n$ 的字符串 $s_1,s_2,s_3$ ，使得 $LCS(s1,s2)=a,LCS(s2,s3)=b,LCS(s1,s3)=c$ ，$a,b,c$ 是给定的数字且 $a,b,c\leq n$ 。LCS是最长公共子序列。
先提取公共前缀 $\min(a,b,c)$ ，然后构造这样三个字符串，不能构造则无解：
ABDX
ABCY
ACDZ
E. Tree Xor
F. Just a joke
G. Product
I. Inverse Pair
给定一个大小为 $N$ 的排列 $A$ ，你可以对每个 $A_i$ 加上 $1$ 或者不操作。询问逆序对数的最小值。
由于只能 $+1$ ，因此能够消除的逆序对只有形如 $(X+1,X)$ 这样的。因此我们需要找的就是这类数对的数量，最后用逆序对总数减去即可。