UVa 11078 Open Credit System

题意

给出一个整数组成的序列,求两个整数A和B,其中A在数列的位置在B前面,令A-B最大,输出这个最大值。

思路

利用问题的单调性优化的典型例子。

暴力是O(n^2)的,显然无法通过。注意到A始终在B的前面,而且一定是A-B,也就是说对于每一个B,只要找到在它前面最大的A就可以了,不妨考虑随着B逐渐后移的同时,维护前面A的最大值,这样做的复杂度是O(n)的,很完美地解决了这个问题。

这种思想经常会被用在其他问题中作为一个需要优化的环节。

代码

 

 

LA3177 Beijing Guards

题意

可以参见LRJ白书第一章例题16.

有n个人,围个圈,每个人想要一定数量的礼物,注意每个人所持礼物不可以重样,两个相邻的人所持的礼物也不能重样,问你至少要准备多少种不同的礼物,才能符合要求?

思路

大概是个构造题综合二分答案。

首先要想到对n的分类讨论:

  • 如果n是偶数,那么你只需要准备两套不同配置的礼物,按照ABABABABAB这样循环下去就可以满足要求了,因此答案是max{r_i+r_((i+1)%n)}
  • 如果n是奇数,情况就比较复杂。我们可以先反向思考,如果给定有r种礼物,如何才能构造合适的礼物配置满足题设要求?白书里面给了这样一种方法:令编号为奇数的尽量选取靠前的种类,编号为偶数的尽量选取靠后的种类,即把r种礼物分成两半(即前、后两组),对于每一个人维护他按照上面策略进行选取的前组后组中元素数量,最后检查第一个人和最后一个人是否相容即可。这样我们就有了二分答案的检查方法了。

代码

 

UVa 11520 Fill the Square

题意

填充一个NxN网格,使得每个格子的字母与其相邻的字母均不相同。输出字典序最小的填充方案。

思路

注意到解的空间非常大,因此只要每一次从’a’~’z’枚举并检查当前格子就可以了。这样也可以保证字典序最小,因为每一次的填充是从最小的字母开始尝试的。

代码

 

UVa 10795 A Different Task

题意

可以参考LRJ大礼包白书第一章例题11

和汉诺塔游戏一样的规则,区别是这个问题会给出多达60个圆盘每一个最开始在哪根柱子上,要你求出从这个局势开始到终盘(00n)最少要移动多少次。

思路

大概是个。。。构造题?

思路比较复杂,而且还涉及传统汉诺塔问题的结论(把一根有k个盘子的堆移到一个空柱子上,需要((2^k)-1)步)。

具体的思路可以参考白书P27.

代码

Codeforces 573C Bear and Drawing

题意

你要在两条平行直线之间画一棵有n个节点的树,树必须是可平面的(意思就是不能有两条链发生相交的情况)。给出你若干个连边(他们已经组成一棵树),问你是否可能画出符合要求的树。

思路

通过小数据找规律,可以要想把一棵树的安排在两条平行直线上,这棵树需要满足以下几个条件:

  • 首先我们在树上找到一条主链
  • 凡是在主链上的点,它的度数没有限制
  • 与主链直接相连的点,它的度数最大为3
  • 剩下的点,度数最大为2

知道了这些,接下来就是实现的问题了。这里有一种很聪明的实现方法。

  • 首先,统计所有节点的度数。
  • 在每一个叶子节点都发动一次DFS,在DFS过程中若遇到的一切度数小于等于2的点,进入,并做删除标记,否则返回。这一步的目的是清除掉所有叶子节点所属的链(不能直接修改度数,否则会导致删掉整棵树)。
  • 重新统计每个节点的度数,因为刚才只是做标记,没有改变度数。
  • 接下来对于所有曾经为3度现在为1度的点打删除标记,这种点是与主链直接相连的点。
  • 重新统计每个点的度数。
  • 现在每个节点的度数都理应小于3了,因为我们刚才去掉了叶子节点所在的链,如果这棵树正确,一定会删到主链上。接下来又去掉了曾经3度删完1度的节点,这相当于完全去掉了支链。这个时候整棵树理应只剩一条链了,不可能再有度数大于2的节点了。

如果理解有困难,不妨尝试画图帮助理解。

代码

 

UVa 11384 Help is needed for Dexter

题意

请参考LRJ白书第一章例题10

思路

试验小数据,找规律。

代码

 

UVa 11464 Even Parity

题意

请参考LRJ白书第一章例题7.

思路

大概是个带有机智成分的枚举。

为什么这么说,因为这道题的关键思路点就是发现只要知道第一行,就可以构造出整个数表,这样我们只要枚举第一行就可以解决问题,复杂度直接降低了一次幂。

代码

 

 

UVA 10881 Piotr's Ants

题意

请参考LRJ白书第一章例题5

思路

两个蚂蚁相遇会马上调换方向,从视觉上看其实相当于擦身而过(虽然两只蚂蚁的身份并没有交换)。就像在物理中,两个质量相等的小球发生完全弹性碰撞,交换速度。这里是本题第一个思路点。

无论在任何时候,第i只蚂蚁永远是第i只蚂蚁,因为上面也说了,只是视觉上的擦身,实际上蚂蚁又各自回去了。这是第二个思路点。在这个地方还有一个问题,那就是可能会以为仅仅是位置关系保持原来的顺序,其实方向关系也是保持原来的顺序的,这样就可以解决蚂蚁的最终状态的判定问题。

这样我们就有了解法:首先利用擦身而过的想法,求出最终所有蚂蚁的分布。然后利用标号守恒的想法,把终止状态和起始状态对应。

代码

 

LA 3708 Graveyard

题意

请参考LRJ白书第一章例题4.

思路

大概是构造题。

跟白书不太一样的解法,贪心地把两种方案的一个顶点对在一起,然后逐个检查,取两种方案的最小角度差,加在一起,就是答案。

代码

 

UVa 11300 Spreading the Wealth

题意

请参考LRJ白第一章例题3

思路

大概是个构造题。

解决的方法是把整个题转化成一个方程组,令每个人手里的初始金币数量为Ai(已知),送出数量Xi,受付数量Yi,最终每个人金币数量M(已知),这样得到由若干形如Ai-Xi+Yi=M方程组成的方程组,当所有方程形式一样时,考虑逐个联立消去未知量,最终得到了关于X1和Xi的若干等式(注意到Xi和Yi+1的相等关系),我们的目标是令Xi之和最小,我们把所有Xi加在一起,就得到了一个仅关于X1的和式。

这个和式的形式可以几何表示是求数轴上一个点,使得其与若干已知点距离之和最短,这个问题的解取在中位数,这样本问题就可以解决了。(中位数是解的想法在白书上有详细的证明,使用反证法)

综合来看,本体需要适当转化,数学变形,数形结合。

代码

 

Scroll to top