链接:http://codeforces.com/contest/1013
A:n堆贝壳,第一天每一堆有ai个,现在可以拿走也可以移动任意个,然后给出第二天每一堆的贝壳的数量,问有没有可能。
两天的贝壳求和,如果不等就不可能。
1 |
|
B:给n个数ai,以及一个数x,现在允许x和ai进行与(&)操作后替换ai,问最少操作多少次,n个数中出现两个相同的数字。
由于和x进行与操作后的结果再和x进行操作的结果不会变,因此每一个数至多和x与1次。考虑到结果只可能是-1 0 1 2,因此存下与操作后的数字结果,讨论一下就行。
1 |
|
C:给2n个数字,让你用这2n个数字构成n个二维平面上的点,要求是构造一个平行于坐标轴的、包括所有点的矩形,并且矩形面积最小(面积可以为0)。
很容易想到的是对a进行排序,之后将2n个数分为x坐标和y坐标两个集合,然后依次结合构成点。画图后发现答案就是两个集合的极差乘积,我们希望让这两个集合的极差尽可能小,因此每次从两个集合中拿出最小的放到对方的集合里,这里滑动窗口模拟一下就可以了。
1 |
|
D:要向一个n×m的矩阵里画叉,并且当三个叉构成如下图所示的操作:
当到左图的情况时,会如右图:①的位置会补上(也就是构成了一个矩形)。
现在给你一个n×m的矩阵,以及一些画了叉的位置,问你最少需要手动画多少个叉,能够利用上述操作将整个矩阵填满。
考虑一个叉都不画的情况,最少需要画n+m-1(就是画一个十字)就能利用上述操作将矩阵填满。
再来考虑这个操作的实质:比方说现在有了(x1,y1)、(x1,y2)、(x2,y1)三个点,那么第四个点(x2,y2)实际上是没有贡献的,如下图:
转换成森林上,希望把坐标这个森林连成一片,问最少要加多少条边。这样我们读入数据的时候,x和y连起来(为了区别x和y,y+n来做分层),当他们的父亲不一样的时候,说明这个连接是必须有的,记一次数。之后用n+m-1减掉这个必要的计数就行了。
1 |
|
v1.5.2