给一个MxN的Grid Graph,结点是编号的,如图:
1-3-5-7-9
| | | | |
2-4-6-8-10
问有多少种方法去去掉一些边,使它形成一些连通分支.两种方案是相同的当且仅当连通分支集合是相同的,即连通分支内的边应当全部保留.
比如
1-3
| |
2-4
可以划分成12种:
[1 3] [1 3] [1-3] [1-3] [1 3] [1 3] [1-3] [1 3] [1 3] [1-3] [1 3] [1-3]
[ ] [| ] [ ] [| ] [ ] [| ] [ ] [ |] [| |] [ |] [ |] [| |]
[2 4] [2 4] [2 4] [2 4] [2-4] [2-4] [2-4] [2 4] [2 4] [2 4] [2-4] [2-4]
......
|
给一个有向图，每条边有颜色，每个顶点出边的颜色都不同。让你选择一个终点和一个颜色序列，使得无论从哪个点出发把颜色序列走完都能到终点。所谓“走”颜色序列就是如果当前点有一条边和序列中的当前颜色相同，那么沿着那条边走到下一个点，否则停在这个点。然后当前颜色往后移。要求颜色序列尽可能短。
windy教主给了一个很强的方法，是这样：每个点放一个人，位置集合作为状态，然后枚举颜色，每个人同步的进行移动。BFS就能找到最短序列。虽然状态看上去有2^30那么多，但是实际的结点并没有那么多（我的程序开了5*10^6)。
这题还可以有一个变化，就是如果当前颜色匹配，那么当前颜色不往后移，最后必须要停下才算结束。那么就要与处理出next[u][k]，就是在结点u，用颜色k进行移动，最后会停在哪里？很类似http://acm.tju.edu.cn/toj/contest/showp68_J.html. 依然要处理环的情况。
回到原问题，上面的算法并不是能很快的算出所有的数据。原因是答案可能会高达>20，BFS会扩展相当多的结点。比如下面这......
|
ural1542被rejudge(AC->MLE)了。就是上一次ural比赛的A题，给出前缀让输出频率前10的匹配字符串。原来用的trie确实很占内存。其实有更简单的做法，就是对所有串排字典序。然后维护一棵线段树，结点表示[i...j]的前10个字符串。更新的时候归并即可。对于给定的前缀，用二分找到最左边的和最右边匹配前缀，然后在线段树中查询一下就搞定。
一开始竟把二分写错了。。。......
|
今天去把头发剪了，又剪回短发了，因为现在的长度非常的inefficient。
男子蓄发需要勇气，把长发剪掉更需要勇气，下了很大的决心才去的。
看着自己的头发大把大把的被削下来（真的是削的，不是剪的），非常的心疼。我们汉族祖先3000年来如此珍视自己的头发，不忍伤其分毫，不是没有道理的。头发也是身体的一部分啊。造物主让人类的头发可以自发的长到很长，有他的理由，任何人不要妄自浅薄的去揣测。
所以，男子蓄发，天经地义，所谓“只有女人才留长发”纯属无稽之谈，还有“留长发的男子都是艺术家”，更是扯淡。男子汉气度不是靠头发长短表现的，和搞不搞艺术也没有必然联系。Albus Dumbledore就留着飘逸的银色长发，而他是整个HP里面最气宇轩昂的一位。至于长发和气质的关系，则和留发者本人的条件有关，不能一概而论，而且也不要以头发在awkward phase的情况来做评价。男子留发的一大困难就是要度过很长的awkward phase，这是一段头发很难看的阶段（女人也有这个阶段，不过她们可以将头发扎成辫子；男子扎短辫太feminine，不可取，烫发和找美发师修剪都是可行的解决办法，但是如果真的要留到很长，这是与终极目标背道而驰的）。当头发留到一定长度，重量协调以后，才能修得飘逸的长发，这时男子就可以将头发扎起来。所以你见到的大多数长发男子基本上都在awkward phase，中国人中我还没见过的真正的长发男子，除了在古装片里面，不过那个貌似是假发。外国人倒是有不少，在西安比赛的时候，街道上都见到过。Eryx也是。
......
|
|
呼唤人品 |
2007-4-19 星期四(Thursday) 晴 |
昨晚SRM345，有米，本来形势一片大好--最后10秒成功的完成第4个Challenge，而且CHA的是第二名，我顺利的升到房间第二（第一是俄罗斯猛牛andrewsta，和target分到一个房间没什么好说的了）。当时高兴得叫了一声。可惜高兴得太早了，ST瞬间就完成了，而我的500竟然fail了。打开一看，当场抓狂，本来应该是sort(B,B+t)，我写成了sort(V,V+t)，相当于没有排序。到手的米金就这样飞了。
简单分析一下题目：
250：很繁的一个题。要讨论点在4个区间还有坐标轴的情况。我讨论了半小时，还讨论错了，重交了一次。其实更简单的做法是枚举从原点出发两步以内的走法，再看从当前点能否沿沿曼哈顿路径直接到终点，这样不容易错，缺点是基本失去了在这个题上Challenge的机会。
500：博弈题。数一下初始奇数堆的个数，如果是奇数，那么可以看成胜状态，否则是负状态。胜状态和负状态总是在走了一步后相互转化。负状态没有办法吃掉当前为偶数的那些堆，因为对手可以在你下手的那个偶数堆响应。它唯一能吃掉的是初始数目为一的那些堆。所以一开始两边首先......
|
校内赛终于办完了， 写个回忆录。
题目从第三周就开始征集了，我也陆续写了几个题的题面，分别是Erdos Number，Erdos' Travel，Tom's Travel, A Simple Game，Armageddon和The Heroes。不过后来Armageddon报废了，此乃后话。
第四周开始和WCM碰头讨论题目。这时stone，Well和彪哥的题目也过来了。stone的题目我大概知道是Stern-Brocot树和Burnside定理，很自然的作为了决赛题。彪哥的两个题我看了后都很喜欢，尤其是那道数学题，于是也决定放到决赛。Well的第一题Playground读了以后觉得似曾相识，WCM告诉我Well的标程是匹配。想了很久发现确实可以转化到最小覆盖，不过有个地方我没想明白，就是为什么最小覆盖中不会存在一条边的两个点都被选择，以为是最小覆盖的什么性质，决定下来再翻翻书想想。他另一道Is Greedy OK?是判断最少硬币的贪心法是否正确，给了一个很强的方法，与硬币的面值无关，看了看那个结论，没有细想，只是觉得这么难的题当然要放到决......
|
昨天晚上和stone做了场老印的比赛.其中那个Dinners Problem有着很有趣的结论.题目是这样说的:
给M把椅子围成一个圈,N个人1...N分别确定自己的初始位置并且轮流去坐那个位置.如果他的位置被占,那么他顺时针找一把空的椅子坐上去.要求他们不同的初始选择序列的个数,满足他们入座后1...K坐满,K+1和M为空,其它椅子不作要求.M,N和K都很大.
考虑1...K的那些位置.选择K个人来坐,显然他们不可能全挤在2...K,故必有一个人的初始选择是1.同理,剩下K-1不可能全挤在3...K,他们必有一人选择{1,2}.这样确定了每个人的选择后,全排列这些选择最后的入座情况也满足要求.所以这K个人的初始选择数是
{1} x {1,2} x {1,2,3} x ... x {1,2,...,K}
产生的每个K元组再做全排列,这样一共有多少个不同的K元组?
推广一下,令f(s,n)表示
{1,2,...,s} x {1,2,...,s+1} x ... x {1,2,...,s+n-1}
产生的每个n元组再做全排列......
|
昨天晚上和stone做了场老印的比赛.其中那个Dinners Problem有着很有趣的结论.题目是这样说的:
给M把椅子围成一个圈,N个人分别确定自己的初始位置并且轮流去坐那个位置.如果他的位置被占,那么他顺时针找一把空的椅子坐上去.要求N个人初始选择的个数,满足他们入座后1...K坐满,K+1和M为空,其它椅子不作要求.M,N和K都很大.
考虑1...K的那些位置.选择K个人来坐,显然他们不可能全挤在2...K,故必有一个人的初始选择是1.同理,剩下K-1不可能全挤在3...K,他们必有一人选择{1,2}.这样确定了每个人的选择后,全排列这些选择最后的入座情况也满足要求.所以这K个人的初始选择数是
{1} x {1,2} x {1,2,3} x ... x {1,2,...,K}
产生的每个K元组再做全排列,这样一共有多少个不同的K元组?
推广一下,令f(s,n)表示
{1,2,...,s} x {1,2,...,s+1} x ... x {1,2,...,s+n-1}
......
|
Silbermond - Symphonie
http://www2.nkfust.edu.tw/~u9433007/symphonie.mp3
YouTube的backstage版(清音更好听)
http://www.youtube.com/watch?v=EXuFUUMMOAY&NR
歌词
Strophe 1:
Sag mir was ist bloß um uns geschehn
Du scheinst mir auf einmal völlig fremd zu sein
Warum geht’s mir nich mehr gut
Wenn ich in deinen Armen liege
Ist es egal geworden was mit uns passiert
Wo willst du hin ich kann dich kaum noch sehn
......
|
|
点名 :-) |
2006-12-24 星期日(Sunday) 晴 |
竟然被goodhorsezxj点名了.希望借这个机会能够攒一点RP,一扫今年的颓气 ~~
规则：
一、被点到名字的要在自己的博客上写下答案，并且将这几个题目传到其他七个
人，还要到这七个人的博客上留言通知对方“你被点名了”。
二、这七个人要在博客上注明是在哪接到的题目，并且再将题目传给其他七个人，
让游戏继续下去，不得回传，被点名的人将得到大家的祝福，并且所有美丽的愿望
都会在不久以后得以实现。
1. 2006你最开心的事是什么？
UESTC校内赛，北京和成电的朋友相聚，西安拿了块金牌，生日和招娣MM吃蛋糕，还有一件事是不能讲的，怕被某人看到了挨揍~~
2. 2006年最难过的事是什么？
衰的事情就不要提了吧，不过现在都不郁闷了，呵呵
3. 2006冬天最大的心愿是什么？
把RP攒高点
4. 最大的愿......
|
|
|
|
