codeforces #389 Div.2

link

http://codeforces.com/contest/752

Solution

A.Santa Claus and a Place in a Class

题目大意:给你一张图,按图上的位置给座位标号,然后输出第k号座位的行列

暴力模拟n^{2}直接过就行了4

首先考虑每一排一定是有2\times m个座位

那么我们可以得到他是在第几排,即col=\left \lceil \frac{k}{2\times m} \right \rceil

有了这个以后我们把前面的所有减掉,即减去k=k-(col-1)\times2\times m

然后我们可以根据剩下的数算出是第几行,即row=\left \lceil \frac{k}{2} \right \rceil

同时判断k是奇数还是偶数,奇数意味着在左边,偶数意味着在右边

这样就是O(1)的正常做法啦


B. Santa Claus and Keyboard Check

题目大意:圣诞老人键盘坏了,有的键可能会和另外一个键混用,他看着他的键盘输入了一串字符,然后他抬头懵了个逼,希望你找出有哪些键混用了,或者是不可能,一个键只可能和一个键混用(可能可以和自己混用)

这题BUG真多QQ图片20160623113051

首先我们扫描一下,如果当前位置的两个字符不一样,就认为是一次混用

然后同时记录一下这个字母的混用情况(即使相同仍然记录

然后就没了,输出的时候不要输出i\;i这种


C. Santa Claus and Robot

题目大意:圣诞老人有个二笔机器人,这个机器人每次都会走最短路去到达一些点,现在圣诞老人忘记这个机器人经过哪些点了,但他还记得这个机器人走的路线,现在让你输出最少有多少个点。

很明显是个贪心,根据题意,起始点一定会放一个关键点

模拟这个串,当前的位置和上一次我放关键点的位置的曼哈顿距离如果小于我花了多少步从上一次关键点位置到当前位置,这个点就一定要放关键点,不然就不满足最短路的原则了。

时间复杂度O(n)


D. Santa Claus and a Palindrome

题目大意:让你从许多串中选一些串组合起来,在组合后是回文串的情况下,要求选的串的价值和最大,你也可以一个都不选

首先,对于一个本身不是回文串的串,考虑它的反串是否存在

存在的话,我们一定要择优匹配,也就意味着我们先对所有串排序

把本身是回文串的拎出来,回头处理

本身不是的,如果可以找到一个串是他的反串,那么就把提出来用掉(他们的价值之和大于0)

这样我们的模型就是形如QQQQQ???????QQQQQQ

现在问号的部分我们要用回文串去填

对于每一个自身是回文串的回文串,他一定只可以和与他一样的回文串匹配

当他们的价值大于0的时候,我们采用他

然后我们选一个没有被用且价值>0的丢到中间去

然后我们发现这么做是错的

为什么呢?因为考虑一个代价为负数的回文串,他如果与一个代价为正的回文串组合,那么等于无形中拉低了群体的颜值QQ图片20160623113042

我们要做的,就是把这个拉低颜值的踢掉,单独要那个价值为正的回文串

也就是在合并的时候记录下最大的负数,答案把它减掉就行了

对于串的存在,一定要用map或者trie啥的去判,单hash会挂test 47


E. Santa Claus and Tangerines

题目大意:给你一些数,每个数可以分裂成x/2,x-x/2,然后可以分裂许多次,你需要选出k个数,最大化你选的数中的最小值。

以下思路来自zqc

考虑从1e7往前扫

对于当前的一个点,可以对x/2,(x+1)/2产生1的贡献

于是不断地累积,只要某一个时刻,扫的和比k大或者等于,我们就要输出当前的i

但是我们这么做会发现多计算了给予贡献的点

那么不妨再打个标记,然后我们减掉即可

时间复杂度O(M)

我自己的二分思路太丑了,还FST了,不想贴出来QQ图片20160623113044


F. Santa Clauses and a Soccer Championship

题目大意:给你树上n对点,要求你选出最少的点,使得每对点的最短路都经过你选出的点

首先考虑对这个字,不妨选树的重心来当做我们选出的点

因为树的重心四周的每一个子树的大小都不会超过整体的\frac{1}{2}

于是一定能在另一边找到匹配的

我们对于每个关键点的子树都缩起来,那么问题就变成了NOIP问题:排队接水

弄一个优先队列来维护即可

时间复杂度O(n\log n)

总结

题目挺水的,没有AK是最大的遗憾,垃圾E题毁我青春

发表评论