Seventh Mist

8VC Venture Cup 2016 Elimination Round

这场打得还算比较顺利……

开场很快切了前4题, 虽然说卡了一下, 但都是一遍AC的……后面也没cha什么人, 一直在想题, 然而最后还是没有出G……就6题滚粗啦.

A. Robot Sequence

给你一个由U, D, L, R组成的字符串, 问有多少个子串, 使得这个子串中U和D的数量相等并且L和R的数量相等. 字符串长度n200n \le 200

暴力枚举一下.

B. Cards

你有nn张牌, 每张牌都是红绿蓝三种颜色之一. 有两种操作: 1. 拿两张不同颜色的牌去换一张第三种颜色的牌; 2. 拿两张相同颜色的牌换一张和它们颜色相同的牌. 问最后可能剩下哪些颜色? 1n2001 \le n \le 200

本来我在想O(1)O(1)算法……但队爷直接来了一句“记忆化搜索”, 然后我就弃疗去打记搜啦.

C. Block Towers

给定nnmm, 你需要选出一个大小为n+mn + m的数的集合, 使得它能够被分成一个大小为nn的集合和一个大小为mm的集合, 并且大小为nn的集合中全是22的倍数, 大小为mm的集合中全是33的倍数. 0n,m1000000,n+m>00 \le n, m \le 1000000, n + m \> 0

二分答案.

给定一个数xx, 答案小于等于xx的充要条件是x2n\left \lfloor \frac{x}{2} \right \rfloor \ge n, x3m\left \lfloor \frac{x}{3} \right \rfloor \ge m, 并且x2+x3x6n+m\left \lfloor \frac{x}{2} \right \rfloor + \left \lfloor \frac{x}{3} \right \rfloor - \left \lfloor \frac{x}{6} \right \rfloor \ge n + m.

D. Jerry’s Protest

Andrew 和Jerry在玩一个游戏: 在一个箱子里有nn个球, 第ii个球的权值为aia_i(保证aia_i互不相同), Harry每次从中取出两个等概率地分配给Andrew和Jerry, 得到的球的权值大的一方获胜. 这样重复三轮, 最后的赢的轮数多的人获胜. 现在你需要计算Andrew赢得第一轮和第二轮, Jerry赢了第三轮, 并且Jerry所得到的球的权值和大于Andrew的权值和的概率. 2n2000,1ai50002 \le n \le 2000, 1 \le a_i \le 5000.

暴力枚举前两轮的情况, 然后再枚举第三轮并计算答案.

E. Simple Skewness

给定nn个数, 你需要选出一个子集(可重集合), 使得它的平均数减去中位数的值(称其为偏度)尽可能大. 1n2000001 \le n \le 200000, 0ai10000000 \le a_i \le 1000000, 时限3秒.

首先, 答案肯定大于等于00. 考虑到这一点, 我们就容易得到一个非常重要的性质: 大小为偶数的集合一定不是最优方案, 因为我们可以把它中间的两个数中较大的一个删除掉, 从而使答案变大. 证明如下:

设中间的两个数为aa, bb, 总共有m+1m + 1个数, 除bb外的数的平均值为xx.

那么, 在删除之前平均数减中位数等于mx+am+1a+b2\frac{mx + a}{m + 1} - \frac{a + b}{2}, 在删除之后为xax - a.

要证

mx+am+1a+b2xa\displaystyle \frac{mx + a}{m + 1} - \frac{a + b}{2} \le x - a

只需

mx+am+1xa+b2a=ba2\displaystyle \frac{mx + a}{m + 1} - x \le \frac{a + b}{2} - a = \frac{b - a}{2}

axm+1ba2\displaystyle \frac{a - x}{m + 1} \le \frac{b - a}{2}

不妨假定xax \ge a(因为当x<ax \< a时答案小于00, 而我们已经证明答案至少是00), 因此axm+10ba2\frac{a - x}{m + 1} \le 0 \le \frac{b - a}{2}, 证毕.

因此我们可以枚举中位数, 然后三分数的个数(平均值关于长度显然是单峰的, 因为这相当于往一个有一些数的箱子里扔一些递减的数).

时间复杂度: O(nlogn)O(n \log n).

F. Group Projects

你需要把nn个数a1na_{1 \ldots n}分成若干组, 你需要求极差和小于等于kk的方案数. 1n200,0k1000,1ai5001 \le n \le 200, 0 \le k \le 1000, 1 \le a_i \le 500

这是一个比较巧妙的DP.

不妨先把aia_i排序, 然后一组肯定是一个连续的区间, 设f[i][j][k]f[i][j][k]表示做到第ii个数, 目前有jj个组开着, 不平衡度为kk的最小方案数.

那么, 当我们枚举到一个数的时候, 有44种决策:

  1. 新开一组;
  2. 关闭一组(这一组不能接受新元素了, 也就是说, 这一组的最大值就是aia_i了);
  3. 加入到一组中;
  4. 自己单独成一组(这是一种特殊情况).

分别转移即可.

注意我们可以动态维护不平衡度的和(感谢@C_SUNSHINE): 我们只需要每次把不平衡度加上j(aiai1)j \cdot (a_i - a_{i - 1})就可以了. (不过据说不这么做也是能AC的).

G. Raffles

你现在要去抽奖. 有nn个箱子, 你手上有tt张票, 第ii个箱子里面初始有lil_i张票, 假如你分配给第ii个箱子tit_i张票, 那么你就能够以titi+li\frac{t_i}{t_i + l_i}的概率获得这个箱子的奖品. 第ii个箱子的奖品价值为pip_i. 抽奖规则规定对于每个箱子, 都必须有tilit_i \le l_i. 现在有qq组询问, 对于每一组询问, 可能会把某个lil_i加上11或者减去11, 你需要给出这次操作后, 怎么分配票才能使得期望最大, 并输出最大的期望. 1n,t,q200000,1pi,li10001 \le n, t, q \le 200000, 1 \le p_i, l_i \le 1000, 时限5秒.

如果没有修改的话, 我们可以贪心(考虑到票的边际效用): 每次找到往哪个箱子投票能够使期望增大得最多, 然后投到对应的箱子里.

接下来有一个结论, 当某个lil_i变化11时, tit_i至多变化11. 下面我们设原来有一个箱子iiti=at_i = a, ti+li=bt_i + l_i = b, 另外一个箱子jjtj=c,tj+lj=dt_j = c, t_j + l_j = d, 然后我们看看如果li=li+1l^\prime_i = l_i + 1导致ii减少两张票, 并且jj增加至少一张票, 会发生什么(感谢 @AcrossTheSky 给予了证明).

考虑到jj拿到了给ii的票, 因此必须有:

pj(c+1d+1cd)>pi(a1ba2b1)>pi(ab+1a1b)\displaystyle p_j ( \frac{c + 1}{d + 1} - \frac{c}{d} ) \> p_i (\frac{a - 1}{b} - \frac{a - 2}{b - 1}) \> p_i(\frac{a}{b + 1} - \frac{a - 1}{b} )

pi(ab+1a1b)>pi(a+1b+1ab)>pj(c+1d+1cd)\displaystyle p_i(\frac{a}{b + 1} - \frac{a - 1}{b}) \> p_i(\frac{a + 1}{b + 1} - \frac{a}{b}) \> p_j(\frac{c + 1}{d + 1} - \frac{c}{d})

(最后一个不等号是因为在li=li+1l^\prime_i = l_i + 1之前, 我们把票给了ii而不是jj), 这就导致了矛盾, 证毕.

这是增加一张票的情况, 而减少票我们可以看做是增加票的逆过程.

因此我们用两个堆(带删除的堆, 我直接用了set)维护一下, 就可以了.

时间复杂度: O((n+q)logn)O((n + q) \log n).