Posts match “ UVa ” tag:

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

  1. 选择在凸包上的直线更好
  2. 如何算距离?观察到(对于某一条直线,由于所有点都在直线一侧,所以所有的符号相同),所以预处理后可以求之。
继续阅读

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

思路:微延长每条线段,这样检测区域的封闭性就可以看各个端点之间能否直接相连,最后看原点(怪物位置)能否dfs达到一个坐标很大的点。
注意:若延长后的端点在任意一条线段上则忽略该点。(因为微延长的技巧是为了造成“墙”的效果,且“墙”中间是不能有点的)

继续阅读

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

结论:
证明:


如图所示,作AG//BC交BE延长线于点G,作DH//AB交CF于点H
则有
所以AG:BC=AE:EC=1:2,
AP:PD=AG:BD=3:4
又由于DH:BF=1:3, DH:AF=1:6

所以DR:AR=1:6, DR:DA=1:7

look,7出来了(基本上到这里结论就出来了)
(更详细的证明见http://blog.csdn.net/freezhanacmore/article/details/8171942

继续阅读

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=704
http://codeforces.com/gym/100379

题意很简单,给你两个斐波那契进制数,求二者相加得到的斐波那契进制数。

一位一位地算,每算一位就处理一下。

附:
Zeckendorf's theorem
Fibonacci coding

继续阅读

零、「以牙还牙,以眼还眼」

Codeforces 197A Plate Game
(经典博弈,我们选修课老师在上课时提到过此题)
分析:一开始你放一个盘子在桌子中心,然后对手怎么放,你就关于桌子中心对称地放,只要一开始你能放一个盘子在中心,那么最后你肯定能赢。
此乃「以牙还牙,以眼还眼」。

一、基础知识

一般规则:

  1. i=0为必胜/必败态(视题目而定);
  2. 某个i-(某个数)为必败态的话,i为必胜态 / 若i为必败态,则i+(某个数)为必胜态;
  3. 所有i-(某个数)为必胜态的话,i为必败态 / 若i为必胜态,则i+(某个数)可能为必败态,但是若i+(某个数)只有一个后继,则其必为必败态

技巧:
如果难以看出必胜/必败态,不妨从i=0开始画一棵必胜/必败态的转移树来辅助分析。

一些题目使用记忆化搜索就可以解决。

>> 有最大取子限制的取石子游戏:POJ 2068 Nim
>> 需要一些技巧性讨论的取石子游戏:POJ 1740 A New Stone Game
>> 欧几里得博弈:POJ 2348 Euclid's Game (好题)
>> 弗格森 (Ferguson) 游戏(大白书 P134)
>> Chomp! 游戏(大白书 P134)
>> 约束游戏(大白书 P135)
>> 日历博弈:POJ 1082 Calendar Game

巴什 (Bash) 博奕
HDU 1846 Brave Game
有 n 个石子,两个人轮流取 1~m 个石子。最后取光者得胜。
结论:当 时后手胜,否则先手胜。
分析:以牙还牙。当 时,先手取 x 个,那么后手取 m+1-x 个,最后一定是后手取完;当 时,设 ,一开始先手取 r 个,那么变成前面 的局面,最后先手取完。

>> 威佐夫 (Wythoff) 博奕与 Beatty 定理
>> 斐波那契 (Fibonacci) 博弈与 Zeckendorf 定理

二、Nim

该游戏起源于中国,经当年到美洲打工的华人流传出去。其英文名「NIM」是由广东话「拈」(取物之意)音译而来。

1902 年,L.Bouton 脑洞大开,提出了如下定理,从而彻底地解决了 Nim 问题:

异或和值为零则后手胜,否则先手胜。

而这个定理两句话就能解释明白:

  1. 当异或和值为零时,无论你怎么取,异或和值一定变为非零,对手以牙还牙,使异或和值变为零,如此循环,直至对手取完。故此时先手必败(处于必败态)。
  2. 当异或和值非零时,总能在某一堆中选取若干个石头,使得异或和值为零(可以自己找几个例子算算),则必胜态总能转移到必败态。

一些问题可以转化为 Nim 问题,常用的思路是两个两个分成一组进行思考,注意利用“以牙还牙,以眼还眼”这一技巧。

例题:
UVa 12499 I am Dumb 3
HDU 4315 Climbing the Hill

下面阶梯博弈的变形2也可以用分组的思想做。

阶梯博弈(Staircase Nim)

博弈在一列阶梯上进行,每个阶梯上没有石子或放着若干个石子。两个人进行阶梯博弈,每一步则是将阶梯(不是第一层的阶梯)上的若干个石子移到(某些指定的)低阶的阶梯去,最后没有石子可以移动的人输。

阶梯博弈可以利用游戏的限制转化成Nim解决:由于某个阶梯上的石子移动到不能移动时所需的步数要么是奇数,要么是偶数。对于偶数步,对方用哪些石子走一步你也用哪些石子走一步,从而不影响游戏结果。所以只对奇数阶的石子求Nim就行

例题:HDU 3389 Game

有一些看似与阶梯博弈无关的题,揭开它的面纱后,实际上就是阶梯博弈:

  1. 博弈在一个N个格子的方块上进行,每个方块上至多有一个石子,每次可以选择一个石子向右移动到最近的空位,不能移动石子的人输,如下图所示:

设函数F[i]表示第i个石子移动到不能移动所需要的步数。
然后我们来观察某一次移动,假设图中的2跳到了4的后面,我们可以来观察一下所有石子的F函数有什么变化:


首先对于1及其之前的石子,它们的F函数显然不变。
同样,对于移动后的2之后的石子,它们的F函数也不变。
那么变化的就是2,3,4这三个石子的F值,变化了多少?每一个减少了1
那么,如果我们把这个函数F[]看做台阶的阶数的话,乃是不是觉得有一点熟悉的感觉了~
没错!就是阶梯博弈

·2. POJ 1704 Georgia and Bob
也是一行格子和一些石子,每次可以把一个石子往左移动若干步,但是不能越过石子,谁最后不能移动谁输。
如果将没有石子的格子看做阶梯上的石子,我们会发现移动一个石子实际上是将这个石子左边的格子移到右边去,也就是把高度为i的阶梯上的石子移到下一个阶梯上去(最右边的空白为第一阶),所以还是讨论奇偶性~
(这题也可以用两个两个一组的思路来思考)

三、Grundy值(SG函数)

我们把 Nim 游戏加点限制:每次你只能取a1,a2,a3,...an个石头。
如何转化成 Nim 问题呢?
原来的 Nim 是 a->a' 的转化,现在我们改为 SG(a)->SG(a') 的转化。
Wiki 中给出的例子。

Sprague-Grundy 定理(SG 定理):游戏和的Grundy值等于各游戏Grundy值的异或和。
很多博弈游戏都含有游戏和这一要素,故可用Grundy值很方便的解决。

剪纸博弈
POJ 2311 Cutting Game(代码见下)

继续阅读

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

思路:离线+逆序操作。逆序后删边变连边,用并查集判连通性即可。Q操作用名次树解决,C操作拆为删除和插入两个操作。
顺便附上我的Treap+名次树模板。

继续阅读