Codeforces Round #333(Div.1) 解题报告

随便和队友拉的一场练练……

题目质量还是挺不错的(

比赛链接(601)

A – The Two Routes

由题可得,1 到 n 的这条边要么是公路,要么是铁路,也就是说要么公交车直达,要么火车直达。如果是公路的话,铁路的最短路就是答案;如果是铁路的话,公路的最短路就是答案。

Code by ZXyang

B – Lipshitz Sequence

不难发现 $\lceil\frac{|h_j-h_i|}{j-i}\rceil$ 取最大的一个必要条件就是 $|i-j|=1$,即相邻。这个画画图实际上就很显然了。

然后,这题要求所有的子区间的 $L(h)$,我们可以发现,对于一个最大的 $L(h)$,它可以影响一部分区间。我们先对 $h_i$ 做差分,然后实际上就是要找当前这个差分值所影响的区间。这个可以用单调栈来预处理,然后查询就很简单了。

Code by Vingying

C – Kleofáš and the n-thlon

期望dp嘛。设 $dp(i,j)$ 表示一个人打到第 $i$ 场比赛,当前得分为 $j$ 的概率。

对于前面而言,转移的时候我们实际上不需要管每个人的具体得分是多少,而是看这个人得这分数的概率是多少。首先,我们知道 Kleofáš 每一场的分数,那么对于其他人而言,他这一场肯定不能得与 Kleofáš 相同的分数。于是转移方程就出来了:$dp(i,j)=\sum\limits_{k=1}^{k\ne x_i and \min(j,m)}\frac{dp(i-1,j-k)}{(m-1)}$,最后我们只需要求 $\sum\limits_{j=1}^{(\sum{x_i})-1}dp(n,j)$ 就行。

Code by ZXyang

D – Acyclic Organic Compounds

据 hrdg 说这就是一个裸的 Trie 树合并……

Code by HeRaNO

E – A Museum Robbery

来啦来啦,动态维护 0-1 背包题来辣(

这个题第三种操作刚开始愣是没看懂,结果是让求当背包容量为 $1,2,…,k$ 时的最大价值。

来复习一下 0-1 背包吧:设 $dp(i,j)$ 表示当前到第 $i$ 个物品,背包容量为 $j$ 的最大价值。容易写出方程:$dp(i,j)=max(dp(i-1,j),dp(i-1,j-w_i)+v_i)$ ,其中 $w_i$ 是物品体积,$v_i$ 是物品价值。其中 $j$ 要倒序枚举,因为每种物品我们只能选一个。

回到这道题:我们显然不能每次都去求一次 0-1 背包,否则复杂度为 $\mathcal{O}(nkq)$,显然接受不了。

注意到:我们每一次增删物品对哪些询问会有影响呢?对于每一个询问,显然是询问当前有的物品。我们可以预处理出每一个物品在集合内出现的时间(记为 $s_i$)和被删的时间(记为 $e_i$),那么设时间区间为 $[l,r]$,如果一个询问在这个时间范围内,那么显然所询问的就是满足 $s_i\leq l$ 且 $r\leq e_i$ 的物品,因为这些物品在我询问的时候一定都在这个区间内。

所以,我们可以考虑对时间分治:将满足条件的物品拿来跑一次 0-1 背包,得到的答案可能会影响好几个询问,然后对于剩下的物品,就直接划分到左右两个区间依次分治下去就行。复杂度 $\mathcal{O}(nk\log q)$。

然后算答案的时候不要用快速幂……可以先预处理出不同幂的值然后再计算,否则会 t 掉。

话说 C++17 64位 跑得是真的快……不过本身好像比较玄学?

Code by Vingying

 

发表评论