UVa 1152 4 Values whose Sum is 0

题目

源地址:

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

理解

题意非常清楚,就是在一个矩阵里面找出四个数,使得他们的和为零。 一开始的想法是DFS,把这个看成一个四层的图,不停搜索就行了。但是DFS写得太搓了,各种姿势挂,后来决定二分暴力乱搞。 思路是这样,把这个矩阵分成左右两份,然后只要一个两层的for循环,就能用两个数组保存下所有可能出现的数字组合的和。有一个小小的技巧是,第二份在保存的时候保存为他们的负数,这样在后面的二分中,只要判断是不是相等就可以了,减少了计算量。 最后感慨一下,一千六百万的数组也能开的出来= =。

Read More

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