VK Cup 2016 Round 1(Div.2 Edition)[Codeforces #658]

=。=昨天看了下这个0点的比赛,作为蒟蒻也就能做做div2……

英文题面戳[这里]喵~

A题:Bear and Reverse Radewoosh

(此题时间2秒)大概意思就是小熊Limak和Radewoosh要进行一场算法比赛(=。=),一共有n道题,每道题他们都会做,第i道题的基础分数是 \({p_i}\) ,他们均需要 \({t_i}\) 的时间完成这一道题,完成这道题得分为 \(\max (0,{p_i} - ct)\) ,其中p是当前时间,c是一个常数。保证输入题目的得分和时间都是递增的,Limak按照严格从前往后的顺序做题,而Radewoosh严格按从后往前的顺序。问他们都做完所有题的情况下,谁的得分更高。

输入3行,第一行为n和c \((1 \le n \le 50,1 \le c \le 1000)\) ,第二行n个数分别是每道题的基础分数 \({p_i}(1 \le {p_i} \le 1000,{p_i} < {p_{i + 1}})\) ,第三行为每道题的时间 \({t_i}(1\, \le \,{t_i}\, \le \,1000,\,{t_i}\, < \,{t_{i\, + \,1}})\)

输出1行,如果Limak分数高输出"Limak", Radewoosh分数高输出"Radewoosh",一样高则输出"Tie"(不含引号)。


常规的暴力模拟题。时间复杂度O(n), 空间复杂度O(n);

代码部分:

B题:Bear and Displayed Friends

(此题时间2秒)Limak有n个朋友,第i个朋友的友好度为 \({t_i}\) ,保证所有 \({t_i}\) 均不相等。

他还有一个朋友列表,这个列表同时只能显示友好度最高的k个朋友,一开始列表为空。

现在有两种操作,第一种操作是把第i个朋友添加进列表(保证对于每个朋友最多只有一次操作1),第二种是询问第i个朋友是否在列表的显示范围内。

输入第一行为n, k, q(q为操作总数)满足 \(1\, \le \,n,\,q\, \le \,150\,000,\,1\, \le \,k\, \le \,min(6,\,n)\) ,接下来一行有n个整数 \({t_i}(1\, \le \,{t_i}\, \le \,{10^9})\)

接下来的q行每行两个整数 \({t_i},{id_i}\) 分别代表操作类型和朋友编号。第一种操作类型为1,第二种操作类型为2。

对于每个操作2输出一行,如果在列表范围内为"YES",不在为"NO"(不含引号)。


 

只要维护一个set就可以啦。1操作需要判断一下,如果set的size小于k就直接插,否则判断set内的最小元素是否小于待插入元素,如果是就删除最小元素并把对应的友好度插入set,否则什么也不做。2操作就查找一下对应的友好度是否在set中即可。由于k非常小(<=6)甚至可以使用数组模拟。

时间复杂度O(qlogk), 空间复杂度O(n+k)

代码部分:

C题:Bear and Forgotten Tree 3

(此题时间2秒)题目大意:有一棵树有n个点,分别标号1~n,直径(即树上距离最远的两个点间距离)为d,以1号点为根节点的深度为h,请你输出一棵合法树的所有边,如果没有这样的树输出一行-1。

输入一行为3个整数n, d, h \((2\, \le \,n\, \le \,100\,000,\,1\, \le \,h\, \le \,d\, \le \,n\, - \,1)\)

输出n-1行每行两个整数代表一条边连接的两个点或只有一行-1。


这道题使用很简单的构造解法就可以解决。首先特判一下n==2时d只能等于2,h可以等于1或2直接输出。当n大于3时需要判断一下以下条件是否满足: \(\max (2,h) \le d \le 2h\) 。如果不满足直接输出-1,否则开始构造。首先从1号点到h+1号点连成一条链,然后需要判断一下,如果d == h就把其他所有点接到2号点上,否则在连接一条长度为d-h的链再把其他所有点接到1号点(插成个菊花图)就可以啦~

时间复杂度O(n),空间复杂度O(1)

代码部分:

D题:Bear and Polynomials

(此题时间2秒)Limak现在有一个“有效的”多项式 \(P(x) = \sum\limits_{i = 0}^n {{a_i}{x^i}} \) 。一个多项式被认为是“有效的”必须满足以下条件:

1.它的所有系数均为整数。

2.它的所有系数的绝对值 \(\left| {{a_i}} \right| \le k\)

3.它是一个n次多项式(即 \({a_n} \ne 0\) )。

Limak发现 \(P(2) \ne 0\) 所以他很苦恼,想让你帮忙只修改一个系数的值使P(2)==0,并且保证修改后的多项式是有效的,为了简化问题,只需输出不同的修改方案的总数。

输入两行,第一行是两个整数n, k \((1\, \le \,n\, \le \,200\,000,\,1\, \le \,k\, \le \,{10^9})\)

第二行是n+1个整数代表 \({a_0} \cdots {a_n}(\left| {{a_i}} \right|\, \le \,k,\,{a_n}\, \ne \,0)\)

输出一行一个整数,代表不同的修改方案的总数。


这道题是为数不多的高精度题。(虽然也许有别的解法)只要写一个二进制的高精度数代表P(2)的值就可以啦,对于输入的 \({a_i}\) 只要把sum从第i位开始累加它的二进制数值,就可以算出sum的值(具体实现细节见代码)。接下来只需要找出这个高精度数中出现1的部分,如果这个部分的长度大于32直接输出0(因为他一定大于k),否则用两个指针(造一个滑动窗口)从1部分的起点滑到终点,对于每一个位置算出第i位到第i+32位的数(它们中间包含高精度数中的所有1)然后判断一下第i个系数减去它的绝对值是否小于等于k,很容易证明计算次数<=64, 对于第n个还需要特判一下,在注意一下边界就可以了(还有注意开long long)。总之是一道很考验代码能力的题(=。=)

时间复杂度O(n),空间复杂度O(n)
代码部分:

[更新1.0.1]E题:Bear and Contribution

这题蒟蒻没过,参考了一下官方题解[英文版传送门]=。=而且并没有代码

(此题4秒)嗯~在cf上发表文章会获得贡献值,现在有n个人在cf上发表过文章,第i个人贡献值为 \({t_i}\) ,Limak想让k个人的贡献值相等,为此他可以进行以下两种操作:

1.消耗b时间阅读某人的一篇文章并使他增加5贡献值。

2.消耗c时间阅读某人的一个评论并使他增加1贡献值。

不保证b>c。

请输出Limak消耗的最小时间。

输入两行,第一行为n,k,b,c \((2\, \le \,k\, \le \,n\, \le \,200\,000,\,1\, \le \,b,\,c\, \le \,1000)\) ,第二行为n个整数 \({t_i}( - {10^9} \le {t_i} \le {10^9})\)

输出一行为一个整数,表示最小时间。


一开始我就觉得排个序然后滑动窗口搞一下就可以,然而卡在了可以增加5这个奇怪的地方……题解用了一个很奇怪的做法,把数组排序并使用滑动窗口扫描5遍,每次分别保证使k个人保持相等的贡献值%5等于0,1,2,3,4(当然在满足上述条件下最小),然后5个最小值在取个最小值就可以了。

时间复杂度O(n),空间复杂度O(n)

 

发表评论