【cf698X】Codeforces Round #363 (Div. 1)

2016年7月20日1,9480

A. Vacations

题意:给出每天contest和gym的开关状态,不能连续俩天参加相同活动,问n天最少休息多少天

用F(i,0-2)表示前i天,第i天的状态为(rest,contest,sport),最多能有多少天不休息

简单dp一下

B. Fix a Tree

给出n个结点的父亲,问至少修改多少个能够使得其变成一棵树

先用拓扑排序消去外向树,剩下的每个环要选出一个当根,然后再把所有的环连成树

答案是环数-(是否存在自环)

C.LRU

有n种物品,一个长度为K的缓存,每次以pi概率询问i物品是否在缓存中,不在则加入缓存,缓存物品超过K个丢弃最早加入的物品

问10^100次询问后,每个物品在缓存内的概率

用f(x)表示缓存里的物品状态数为x的概率,枚举一个不在缓存里的物品i,则

\[f(x|2^{i-1}) += f(x)*(p_i/ \sum_{i \in }p_i)\]