CCPC-Final2017
A - Dogs and Cages
签到题，输出$n-1$
B - Same Dight
不可做题
C - Rich Game
前期水题，二分答案后判断，输0：11，赢11：9。特派输赚得多的情况
D - Mr.Panda and Circles
FFT，不会做
E - Evil Forest
签到题，输出$\sum x*1.1$，比赛时用了实数搞笑WA了一发
F - Fair Lottery
有$N$组人，每组人有$a_i$个，可以进行若干次选择，每次选择一些至少有$M$个人的组，这些组的人都中奖。现在要使每个人中奖概率相等，且中奖概率最大。$N\leq10,M,a_i\leq100$
中后期题，先二分答案$p$，判断是否可行。枚举所有选人的$2^N$种情况，对其中可以选择的情况，选中的人$+p$，没有选中的人$+(p-1)$，那么最后要使得所有的人都$\geq 0$，且至少选择一种开奖情况，直接单纯形判断解是否存在即可。时间复杂度$O(kSimplex)$。
G - Alice's Stamps
有$N$种集合，每个集合包含$[L_i,R_i]$中所有元素，现在选择其中$K$个集合，使得选择集合的并集最大。$N,K,max(L_i,R_i)\leq 2000$。
前中期题，先删去互相包含的集合，对剩下的集合直接进行贪心+DP。令$f[i][j]$表示选到第$i$个集合选了$j$个最多选多少个元素，那么一定从$f[pre[i]][j-1]$转移过来，$pre[i]$表示和$i$连接的最前面的集合，或者直接从一个不和它有交的集合转移过来，记一个前缀最大值即可。时间复杂度$O(n^2)$。
H - Equidistance
线性代数题，队友过的
I - Inkopolis
$N$个点的基环树，$M$次操作，每次改变一条边颜色并询问基环树的联通块数。$N,M\leq200000$。
中期题，先考虑树上情况，如果是加边，那么如果改的一条边两端都有同色联通块答案$-1$，两端都没有同色联通块答案$+1$，删边亦然。直接每个点套一个map就可以维护了。考虑基环树，先将一条环边删去，每次求答案时考虑将环边加入的情况，也是类似地判断两端是否有同色联通块。特殊地，如果环上都是同一个颜色，答案$-1$。时间复杂度$O((N+M)lgN)$。
J - Subway Chasing
差分约束，队友过的
K - Knightmare
当步数比较多时，差分找规律，发现$\Delta(n)=28n-20$
评论 (0)
