Codeforces Beta Round 5 B Center Alignment

题目

源地址:

http://codeforces.com/contest/5/problem/B

理解

题目不难,不过输出上有点问题,因为题目要求左右均匀分布,上一次偏左则下一次需要偏右。 当总长度为偶数的时候,没有太大的问题;但是当总长度为奇数时,则需要考虑到底应该偏左还是偏右的问题。那么就需要两次判断,首先判断总长度,也就是最大长度是不是 偶数,当总长度不是偶数时,则判断这个字符串是不是偶数。使用一个计数变量num来保存是否是否应该偏左,每一次判断完毕之后都自增一次,这样就能实现保持左右均衡。

Read More

Codeforces Beta Round 5 A Chat Server's Outgoing Traffic

题目

源地址:

http://codeforces.com/contest/5/problem/A

理解

很简单的一道水题,实际上就是输出字符串个数和乘上当前聊天室里面的人数的和。 在具体写的时候有几个需要注意的问题: - 输入,老生常谈了= =。空格的处理通常可以用cin.getline(tmp,MAXN)(对char数组)或者是getline(cin,tmp);(对string类)。 - 每次循环的时候,用于保存聊天内容的字符串都必须清空,否则答案会比正确结果大很多。

Read More

UVa 12174 Shuffle

题目

源地址:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=513&page=show_problem&problem=3326

理解

题意真心有点看不懂,原谅我这个没有用过音乐播放器的男人= =。

使用一个音乐播放器,采用随机播放。随机播放的原理时先随机产生一个1~n的排列,然后就按这个排列顺序播放歌曲。播放完这序列的所有歌曲以后,再次随机生成一个1~n的排列,再继续播放。然后,现在给你一个播放历史记录,但是这个记录是不完整的,因为当它开始记录的时候,有些歌可能已经播放过了但是没有记录到。现在给你一段历史记录和播放器中歌的个数,问历史记录中的第一首歌是某个随机列表的第几首,总共有多少可能?

整个算法可以分成两段,首先处理min(s,n)中的部分,这部分出现的歌曲都放入一个sames容器,以bool数组ok[i]来记录从标号i开始的歌曲是不是都不相同。然后依次枚举第一首歌是第x首,先检查前s-x是不是都不相同,然后从x开始,依次判断x,x+s,x+2s等等是不是符合条件。

Read More

UVa 1451 Average

题目

源地址:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4197

理解

这道题被康逗逗怒拿了FB,默默地去看题,结果完全看不出什么头绪。题意扯到了DNA神马的,其实完全不重要。实际上就是给你一个由0和1组成的串,叫你求出一段长度至少为L的连续子序列,使得这个子序列的平均数最小。如果出现多解,则要求取长度小而且起点小的那个序列。 感觉像是一个DP的题目,但是对如何高效地求出这个最优解没有什么思路。后来在题解中看到了一篇论文《浅谈数形结合思想在信息学竞赛中的应用》。首先,我们可以将目标图形化,取每一个数的序号为X上的变量,取0和1为高度,则可以得出任意两点之间的斜率为(sum[j]-sum[i])*1.0/(j-i)。然后开始维护一个曲线,保证这个斜率上的每一段曲线都是斜率最大的。 在一个for循环中,设最后的节点是i,i~(L,n)。然后开始寻找这个曲线中满足>L要求的最大斜率。

Read More

UVa 1606 Amphiphilic Carbon Molecules

题目

源地址:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4481

理解

比赛的时候太紧张,题目都没敢读全= =。 实际上题意还是比较清楚的,给定一个平面,上面有两类点,分别用黑白来表示。现在要求要用一根直线将这个平面分成两半,在直线上面的点全都取走,问,最多能取走多少个点。 具体的方法曾经讲到过,就是扫描线算法:任取一个点为原点,建立极坐标系,其他的点使用极角排序,然后扫描来寻找最大值。 在实现的时候有两个注意点: - atan2的计算误差不可忽略,极角排序的时候要用叉积的方法进行排序,规避精度问题。 - 叉积方法排序之前,需要做一个投射,将这个平面上的点处理到两个象限中去。

Read More

UVa 120 Stacks of Flapjacks

题目

源地址:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=56

理解

特别涨姿势的一道题。 题目不难,只要理解题目中所谓的翻转的意思,很好做。但是我在看题解的过程中,被STL的各种酷炫吓呆,感觉string类真的好好用= =。要是自己用char数组模拟的话,可能会写得各种坑。

默默记录一下: - istringstream iss(str);,专门用于操作string类的一个类,可以这样用for(int tmp; iss>>tmp; que.push_front(tmp));。超酷炫有木有!。! - deque<int>::iterator it 迭代器,方便好用不多说= = - reverse(Max, que.end()); 用于容器中两个元素的交换,超级好用。 - distance(que.begin(), Max) 返回两个迭代器之间的距离,也是相当的赞。

恩- -,好好学STL,大有前途。

Read More

UVa 714 Copying Books

题目

源地址:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=655

理解

比赛的时候读懂了题意,但是没有拿出来敲,因为感觉自己应该是敲不出来的。实际上,这是一道小白书上提到过的题目,也就是最大值最小化问题。 算法竞赛入门经典P151 使用一个pos数组来保存是否在此分段,然后使用二分最小值来确定pos的取值。 实际上我还不是能够非常具体地描述中间二分的过程,不妨在二分的循环当中打印pos数组的值来找一找感觉。

Input:
1
9 3
100 200 300 400 500 600 700 800 900

Output:
0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 1 0 0
0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 1 0
0 0 0 0 1 0 1 1 0
0 1 0 0 1 0 1 1 0
0 1 0 0 1 0 1 1 0
0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 1 0
0 0 1 0 0 1 0 1 0
0 0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 1 0
0 0 1 0 0 1 0 1 0
0 0 1 0 0 1 0 1 0
0 0 0 0 0 0 1 0 0
0 0 0 0 1 0 1 0 0
0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 1 0 0
0 0 0 0 1 0 1 0 0
0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 1 0 0
0 0 0 0 1 0 1 0 0
0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 1 0
0 0 1 0 0 1 0 1 0
0 0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 1 0
0 0 1 0 0 1 0 1 0
0 0 1 0 0 1 0 1 0
0 0 0 0 0 0 1 0 0
0 0 0 0 1 0 1 0 0
0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 1 0 0
0 0 0 0 1 0 1 0 0
0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 1 0 0
0 0 0 0 1 0 1 0 0
0 0 0 0 1 0 1 0 0

100 200 300 400 500 / 600 700 / 800 900

除去最后一行是答案,不去考虑之外,我们可以看到这是一个在中央取值,然后不断向右靠拢的过程。

Read More

UVa 11134 Fabled Rooks

题目

源地址:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2075

理解

比赛的时候没有写出来。其实很容易可以看出来,这个题目可以变成两个子题目,也就是X和Y方向并没有直接的关系,完全可以看成在X方向是不重叠摆放和在Y方向是不重叠摆放的问题。 一开始的想法是只要对它进行排序,然后逐个判断是否符合题意就OK,但是后来发现这样并不能解决问题。后来看了题解,决定采用优先队列来维护可以选择的区间。也就是每次都在区间[l,r]中选取l最小且r最小的区间,然后设一个变量maxx保存一下当前已经摆放到了什么位置。要是存在一个l<maxx,那么则需要将这个l修改为maxx,并且重新放入队列中。这样,就能保证后面的棋子都不会和前面已经摆好的重叠。

Read More

13级个人赛第一场

比赛地址 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=61737#overview 比赛总结 这次比赛打得还行- -,最近生活比较规律,连带着人也变得机智很多,暴力乱搞加开脑洞,过了很多题。但是,也从侧面暴露出编码能力不强,算法功底不扎实的缺点。接下来还是要好好训练,多多刷题。跟队友多交流,相互促进,不停地PUSH自己。 分题讲解 A题(STL,模拟) 比赛的时候真的看不懂题意= =,太弱了。赛后看的题解大涨姿势,学会了好多神奇的技巧。 只要理解了翻转的过程,题目并不是很难。 http://xuanwo.org/2014/11/04/UVa-120-Stacks-of-Flapjacks/ B题(构造) 超想像CLJ一样来一句傻逼题。 开脑洞过了题之后还没反应过来= =,当时的唯一想法是卧槽,这么逗的题怎么没人过? 然后吐槽了范神带歪了榜= =,导致前面很多水题大家都没做出来。 http://xuanwo.org/2014/11/05/UVa-1605-Building-for-UN/ C题(暴力) 乱搞,开了一个一千六百万的数组二分过了。 不知道是谁告诉我只要学会暴力就能区域赛拿银来着= =。 http://xuanwo.org/2014/11/05/UVa-1152-4-Values-whose-Sum-is-0/ D题(贪心) 把问题想得太复杂,其实X和Y方向根本就没有关系,完全可以分开考虑。 http://xuanwo.org/2014/11/04/UVa-11134-Fabled-Rooks/ E题(贪心) 大胆地喊一句:傻逼题。 想了半天的还差点开始敲网络流模板的我更加傻逼= =。 http://xuanwo.org/2014/11/05/UVa-11054-Wine-trading-in-Gergovia/ F题(几何) 扫描线算法,当年土豪学长跟我们说过,但是打比赛的时候完全没有印象。 也跟读题能力有关系,看到题目长,题意复杂就不敢下手,太弱了,要加强。 http://xuanwo.org/2014/11/04/UVa-1606-Amphiphilic-Carbon-Molecules/ G题(模拟) 一开始以为是神奇的数据结构,实际上不用那么复杂。 http://xuanwo.org/2014/11/05/UVa-11572-Unique-Snowflakes/ H题(二分,乱搞) 感觉是最长上升子序列演变过来的题目。 http://xuanwo.org/2014/11/05/UVa-1471-Defense-Lines/ I题(几何) 赛后看了大神的论文,数形结合是厉害啊= =。 http://xuanwo.org/2014/11/04/UVa-1451-Average/ J题(贪心) 小白书上的最大值最小化问题。 http://xuanwo.org/2014/11/04/UVa-714-Copying-Books/ K题(水题) 傻逼题——我还WA了一发。。。 http://xuanwo.org/2014/11/05/UVa-10954-Add-All/ L题(分治) 貌似是第一次接触分治,这种把大问题分解为多个小问题的思想需要掌握。 http://xuanwo.org/2014/11/05/UVa-12627-Erratic-Expansion/ M题(模拟,剪枝) 很多人过的题,但是我没想出来怎么敲。 http://xuanwo.org/2014/11/06/UVa-11093-Just-Finish-it-up/ N题 O题(模拟) 跟G题有点像,同样是另外开一个数组用来保存第一次出现的位置,这个技巧感觉很有用。 http://xuanwo.org/2014/11/04/UVa-12174-Shuffle/ 更新日志 2014年11月5日 完成部分题解。

Read More