Codeforces 1786 / Codeforces Round #850 (Div.2)

Codeforces Round #850 (Div.2)

https://codeforces.com/contest/1786

Problem A1 Non-alternating Deck (easy version)

Problem A2 Alternating Deck (hard version)

注意到最多进行 \(O(\sqrt n)\) 步，直接模拟即可。

Problem B Cake Assembly Line

题目保证了一定是 \(n\) 个蛋糕和 \(n\) 个巧克力喷枪，且巧克力喷枪长度不会超过蛋糕长度。那么每个喷枪一定需要一个蛋糕接住，不然巧克力就会掉在地上。同时每个喷枪不能被大于一个蛋糕接住的，因为蛋糕中间有空隙，空隙处的巧克力会掉在地上。题目按顺序给出蛋糕和巧克力喷枪，那么一定是第 \(i\) 个巧克力喷枪对应第 \(i\) 个蛋糕。每个蛋糕可以选择左端点和喷枪的左端点对齐，或者右端点和喷枪的右端点对齐，那么移动范围构成一个区间。

因此，有解当且仅当这 \(n\) 个区间有交。判交是简单的，直接看这些区间的最大左端点是否不超过最小右端点即可。但是我场上忘了写了个排序 vector 艹，鉴定为学傻了。

Problem C Monsters (easy version)

最后一定排成 \(1\) 开始的值域连续段，贪心，如果当前存在值为 \(x\) 的元素就不需要花费任何代价，否则选择把大于 \(x\) 的最小元素改为 \(x\)，multiset 模拟即可。

Problem D Letter Exchange

用 \(0,1,2\) 来代替这三种字符。考虑最后每个人一定有若干个操作需求，形如：需要把 \(a\) 交换出去，同时交换进来一个 \(b\)。用 \(a \to b\) 来表示。

考虑对于任意 \(a \neq b\)，如果存在一个 \(a \to b\) 和一个 \(b \to a\)，那么它们组成一次操作就可以同时满足两次需求，要优先进行。

考虑最后剩下的情况。一定是若干数量的 \(a \to b, b \to c, c \to a\)。它们的数量应该是相等的 —— 因为题目保证了每种字符正好 \(n\) 个。不难发现，对于一个 \(a \to b, b \to c,c \to a\)，采用以下策略最优：对 \(a \to b,b \to c\) 进行操作，把第一个人的 \(a\) 和第二个人的 \(b\) 进行交换，这个时候第一个人满足需求了，第二个人的需求变为 \(a \to c\)，和 \(c \to a\) 组成一次操作。

Code

Problem E Monsters (hard version)

血的教训：把问题往能看得见摸得着的方向转化。

注意到序列 \([1,1,1,2,3,3,5]\)，后面的两个 \(1\) 和一个 \(3\) 是没有用的，删去后变为 \([1,2,3,5]\) 不影响答案。考虑一个数有用的条件到底是什么？

我们时刻维护一个每个数都有用的序列。初始为空，每次加入一个元素 \(x\) 之后，不难发现如果此时序列中小于等于 \(x\) 的数数量大于 \(x\)，那么 \(x\) 是没有用的，直接删去即可。

否则把 \(x\) 插入后会把原来至多一个有用的数变为没用的，如果可以支持查找 + 删除，那么题目就解决了。

考虑使用线段树维护 \(x - c(x)\)，其中 \(c(x)\) 表示小于等于 \(x\) 的数的数量。插入 \(x\) 则对应 \([x,n]\) 区间 \(-1\)，删除同理，另外支持定位全局最小值，这是简单的。

Code

Problem F Wooden Spoon

直接考虑刻画整个方案的产生过程。考虑一个玩家 \(a_n\) 得奖对应了一个序列 \(1 = a_{0}< a_1< a_2< \cdots< a_{n}\)，其中 \(a_{n-1}\) 打败 \(a_{n}\)，\(a_{n-2}\) 打败 \(a_{n-1}\)，以此类推。

考虑在确定序列的情况下，这个序列的产生次数。首先 \(a_{n}\) 可以放在 \(2^{n}\) 个位置中任意一个上面，\(a_{n-1}\) 必须放到 \(a_n\) 旁边。\(a_{n-2}\) 必须先成为 \(2\) 个人中的胜者，另 \(1\) 个人必须比 \(a_{n-2}\) 大，且不能和 \(a_{n-1},a_{n}\) 相同，方案为 \(2^n - a_{n-2} - 2\)。\(2\) 个人随便排列即可，排列方案数为 \(2!\)。

一般地，对于 \(a_{n-i}\)，有 \(\dbinom{2^n - a_{n-i} - 2^{i-1}}{2^{i-1} - 1}\) 种选择子树的方法，\((2^{i-1})!\) 种排列方法。

对于所有序列求解可以考虑 DP。设 \(d(i,j)\) 表示选了第 \(i\) 个元素，最后一个元素为 \(j\)，的所有序列的产生次数之和。记 \(f(i,v) = (2^{i-1})!\dbinom{2^n - v - 2^{i-1}}{2^{i-1} - 1}\)，即 \(a_{n-i} = v\) 的排列方法数。

考虑转移。有 \(d(0,1) = f(n,1)\)，其它的 \(d(0,x)\) 均为 \(0\)。转移有 \(d(i,v) = f(n-i,v) \sum \limits_{w=1}^{v-1} d(i-1,w)\)。记录上一层的前缀和即可，时间复杂度 \(O(n2^n)\)。

Code