CCPC-Final2017

orz hhw posted @ 2017年12月13日 16:32 in 做题记录 with tags ACM 解题报告 , 52 阅读

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$