zkx06111's Blog

CodeForces Round #349

| Comments

昨天晚上打了CF #349的Div 2,只出了ABC。现在来补题辣!
还差几道: 3

A. Pouring Rain

一个圆柱题杯子,底面直径为d,初始水深为h,你每秒可以喝v毫升的水,每秒会下e毫升的雨,问你能不能喝完水,并求出喝完水的时间。

按照题意模拟即可。时间复杂度O(1)
这里是我的代码

B. Coat of Anticubism

告诉你n条边,求出最小的一个长度,使得加入该长度的边之后可以形成一个凸多边形,注意边可以夹角为180度。

好吧,我在写的时候是发现了样例全部都是形成三角形,于是就猜三角形一定最好。

于是就只要按照边的长度排序,如果存在一个分割点使得它以及它之前的和大于等于它后面的和,那么就只要加入一条长度为1的边。如果不存在,就加入一条长度为min{presum[i], sufsum[i+1]}的边。时间复杂度O(nlgn)

为什么这样可以呢?我们来讲讲道理。 啊...我不知道啊...求老司机告知,我现在感觉自己的做法非常没有道理啊...好像随便卡就能卡掉啊...

这里是我的代码

C. Reberland Linguistics

一个单词以这种方式构成:一个长度大于4的字符串,称为词根。然后在后面加一堆长度为2或3的后缀(注意这里的后缀类似于英语构词法里面的后缀,并不是指包含字符串最后一个字符的字串),同时还需要满足同样一个后缀(例如ab)不能被连续加入。

题目题意好琐碎。我在考场上的记录非常悲剧:T9,W6,T20,W4,W4,A,简直酸爽无比。

记忆化搜索,solve(x, l)表示目前处理子串S[0..x-1],上一个加入的后缀长度为l,然后只需要根据题目说的不能连续加的要求把符合要求的字符串放进一个set里面就可以了。用一个数组solved记录某个状态有没有被访问过。

时间复杂度O(nlgn),其中lgn的复杂度来自set。

这里是我的代码

D. World Tour

告诉你一个有向图,要在其中选出4个不同的点(a, b, c, d),使得相邻两个元素之间的最短路之和最大。

结束之后补的。对于每个点,用广搜跑出单源最短路。然后,对于每个点,把其他点分别按照到它的最短路和从它走出的最短路排序。

枚举(b, c),然后分别枚举走到a,从d出发走到的最远的3个点,作为a和d,用来更新答案。

注意判断:点不能相同,并且点与点之间必须要有路。复杂度O(n^2 lgn),其中lg n的复杂度如果用计数排序代替快排就可以没有了。

这里是我的代码

Comments

comments powered by Disqus