失去色彩的花丛

http://roba.yculblog.com

搬家了，麻烦和我链接的朋友改一下，不好意思。

欢迎光临我的新BLOG：http://roba.yculblog.com ，努力建设中，拉点人气过去先。麻烦加我链接的朋友改一下地址，不好意思。

发现这里越来越让人不能忍受，终于下决心要搬了，可怜好不容易积攒的四千多的访问量……正在把一些我感觉还有价值的文章转过去，可惜的是大家的评论不能加上了。离开之前把各种症状列表如下:

(1)加入或删除一篇文章，提交上去还要再点更新首页，更新RSS……至于到底能不能更新就看你的运气了。

(2)加入或删除一个链接，不知过几天才能放上，这个是不论你怎么点更新也没用的。

(3)新加一个评论，以前的情况是有可能导致这个页面很长一段时间打开时一片空白，现在好像没有这种情况了，但是每条评论前面都给加了一个灰色的人头形状，ms这样的页面很漂亮？

(4)评论里访客的留下的地址如果不是blogchina的就不会显示，有朋友来交换链接，我只能进到管理页面里才能看到，这还是我前几天才发现的，不知blogchina的用户有多少人发现了这个小窍门，可以找我交流一下>_< ~~

(5)最近终于让我下定决心要搬的是，我的BLOG竟然会经常莫名其妙回到几天前的状态~~~新加的文章、链接、评论全部消失，更搞笑的是我的个人图片居然变成了几个星期前的那一张~~~然后我发一篇文章，再更新一次，有时候所有的东东就全回来了，有时候反而到了更以前的状态~~~终于体验了一把时光倒流的感觉~~~

至于其他的像上传的文件类型有限制啊，手拉手拉到姥姥家啊，访问统计莫名其妙啊，也就不多说了，毕竟人家提供免费服务也不容易，想想以前也换过好几次地方了，从blogcn到csdn再到blogchina，这次准备搬到ycul，如果再不行的话，等我有了闲钱，也像BunnyQ他们买个空间爽一把，不再受这窝囊气了。

http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1154

组队以来第二次比赛，这次比较爽的说，一开始狂贴代码（好像有点无耻了~~~）居然做了一段的时间的rank1，汗ing~~~然后我就说，剩下的四题一定要至少再过一道，让别人知道咱们不只会贴代码嘀，还好这个目标后来实现了。

我一直在敲K（在没有模版的情况下用VI敲了二百多行的计算几何，想起来就后怕）wtommy和zxj郁闷在B上好长时间，最大生成树，最小费用流什么的都搬出来了，理论知识我是不大懂哈，仔细一看N只有20，明明硬搜就可以了么~~~开始还想怎么剪枝来着，后来因为情况紧迫（女队都排在我们前面了>_<~~），直接乱搜一通就交上去了，一次AC，大FT~~~

回来继续敲我的K，累得半死终于写完，SAMPLE都不过，郁闷了，这时还剩半小时，时间紧迫只好转到VC开始调试（嘘~~~）跟了两下就发现错在一个结构体没有清空，还是VC好啊~~~改过来过了SAMPLE却WA了，又把几个不确定的地方和精度都调了调，继续WA……还剩不到10分钟，就在我将要放弃，一眼瞟见那个清空的地方sizeof的大小居然写错了，SAMPLE因为数据很小恰巧能过，改过来再交，AC！

我向来都是后两个小时一个题也做不出的，这个一定要好好记录下来，嗯嗯~~

599060 blizzard K Accepted 116K 15MS C++ 4.59K 2005-08-05 17:53:23.0 （注：18:00比赛结束）

这次只是因为RP好，那个错误绝对是无意中发现的，不然的话十分钟去找一个200行的程序的错应该不可能的说，以后还要争取在写程序时少犯低级失误才对饪縍P可不行。还有发现我善于把东西往简单的方向考虑，因为复杂的都不会 >_<~~~上次一道简单的几何题，wt用凸包做了半天，也是后来让我发现了极简单的做法，以后他们两个如果想到什么BT算法一定要经我这简单的头脑过滤一下才行，嘎嘎~~~

给宿舍电脑也装上了linux，以后编程要争取全在Vi里进行,VC的调试功能害死人啊,不管多么隐蔽的错误,跟几下就一清二楚了,现在等于VC换成一个记事本,立刻傻眼,各种莫名其妙的错误,手忙脚乱~~~编程的效率降低N倍啊~~~

Vi设置好了还是非常好用的,作为一个文本编辑器而言的确非常优秀,现在已经有点习惯了,对于在什么地方插上printf有助于发现bug也有了点感觉.今晚上搞定了一个很麻烦的搜索,刚刚比赛过的POJ2325,4K的代码,花了两个小时多一点,对于离开调试器就死了一半的我来说已经很不容易了...还要继续努力...

btw:终于把线段树弄明白了,不容易啊...

Linux的确是一个高手用的系统，不会时越来越郁闷，上手以后就会越来越觉得顺手，以前我第一次装Linux时，VI给我的感觉是难用到了无法忍受的地步，一会能打字，一会又变成了命令，不知道按了什么一行文字就全没了@@最近因形势所迫不得不再次装上，仔细研究之后发现还是很好用的，好多觉得不爽的地方其实都可以配置，好多实用的功能都可以用最快的方式来实现，把从网上查到的有用的东东列个表先：

a 插入模式
i 改写模式
dd 删除一行
:q 退出
:w 保存
:r 打开
:h xxx 帮助
:set xxx 进行各种配置，对ACMer有用的有

:set cindent  C缩进模式
:set tabstop=xx  TAB的长度
:set shiftwidth=xx 缩进的长度
:set number/nonumber 开启/关闭行号显示
:set filetype=cpp CPP文件类型的语法
:syntex on/off  开启/关闭语法高亮

上面这些可以写在/etc/vimrc里，这样就不用每次都修改了。

另外Vi还可以和gcc有一定程度的“集成”的，我也已经试验成功了。如果在源文件所在目录写好了makefile，可以在vi里直接用命令:make来编译，返回信息会直接显示出来，并且光标会自动跳到出错的行，还可以用命令来在出错的行之间跳转。麻烦的是要作一个makefile，不知道真正比赛的时候有没有闲时间写那个东东，虽然只用两行就行了~~~

还有变量自动完成的功能太cool了，敲入前几个字母，一按Ctrl+N，嘎嘎~~ 还有一个tags功能，也试了试，用ctag命令生成一个什么文件，然后就可以在很多文件中快速找到某个函数，不过这对于很短的ACM程序来说似乎用处不大的说~~~

好多东东是从这个BLOG看到的，推荐一下：

http://blog.csdn.net/mylxiaoyi/

半夜里的UVA比赛，比较郁闷，全是数学题（后来发现这次比赛就叫Abednego's Mathy Contest -__-），想得头疼，大概时差的问题，没有多少中国人参加，所以虽然很菜却排名不低，在我上面的五星红旗只有NealZane（可能还有新注册的被分到外国去了，嘎嘎~~），不管怎样先抓个图yy一下：

睡到了11:50爬起来上PKU，巨郁闷，搞掉了H以后干坐了好几个小时，N道题的TLE，加上头昏昏的还没吃午饭，痛苦啊~~~解题报告已经贴出来了，好好学习学习，至少也得做出一半来，嗯嗯~~~

晚上一直在装LINUX，发现似乎比Windows慢呢，不过感觉还是不错的，用FireFox上UVA，比用IE好看多了。想干什么事，在终端里啪啪啪打上一串命令，很有高手的感觉@@。费了好大劲装上Realplayer，把音箱耳机的音量什么的都调好了，可以听歌了呵呵~~LumaQQ怎么安装还是没太搞明白，如何把FAT分区里的东东mount过去也没弄出来……以后就要用这个东东写代码了，传说中的用记事本写程序的境界……VI好麻烦，gedit感觉还不错，没有调试，呜哇哇~~~

组队了，我感觉应该是很理想的组合，不过我还没想好到底往什么方向发展，几何题一看就恶心，图论一知半解只会硬往上套，搜索题一般还没写就做好TLE的准备~~~皑皑，好像一无是处了，啥也别说了继续努力吧~~

今天他们那里的比赛题，挺有意思的，我本来还想做做试试呢，上来就被一个表达式求值的题堵住了，RE N次，后来发现是一个白痴级错误，郁闷了~~不做了~~都是原创题，好像不是很容易，下面这道应该是比较简单的，就让我想了好久~~也可能是绕弯子了，还请大牛指点。

Hacker on CET
http://acm.fzu.edu.cn/problem.php?pid=1335

我的思路是，有n道题，设ans[n][0]表示符合要求的情况数，ans[n][1]表示有奇数个A或奇数个C的情况，ans[n][2]表示有奇数个A且奇数个C的情况，则递推式为：

ans[n][0] = ans[n-1][0] * 2 + ans[n-1][1]                          (1)
ans[n][1] = ans[n-1][0] * 2 + ans[n-1][1] * 2 + ans[n-1][2] * 2    (2)
ans[n][2] = ans[n-1][1] + ans[n-1][2] * 2                          (3)

但是这题n可到10^9，显然要设法找到一个闭合的形式才行。观察可以发现，ans[n][1] = ans[n][0] + ans[n][2]，而ans[n][0] + ans[n][1] + ans[n][2] = 4^n 即所有可能的情况，所以有

ans[n][0] + ans[n][2] = (4 ^ n) / 2                                (4)

令(1) - (3)得 ans[n][0] - ans[n][2] = (ans[n-1][0] - ans[n-1][2]) * 2

可以看到(ans[n][0] - ans[n][2])是公比为2的等比数列，而ans[1][0] = 2 , ans[1][2] = 0

所以 ans[n][0] - ans[n][2] = 2 ^ n                                 (5)

联立(4)(5)可解得

ans[n][0] = 2^(n-1) * (2^(n-1) + 1)

因为题目只要求输出最后两位，用手算即可求出(2^(n-1) % 100)的循环（我手懒，写个程序找的，hoho~~其实只有20个数），剩下的工作用常数时间即可完成。:)

比赛见这里: http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1151

睡得太晚了，一睁眼已经12:10，抹了把脸过来正赶上比赛开始。一开始的时候决策出现重大失误，先盯上了H题，大概是还没怎么睡醒，觉得这题挺容易的，就是一个欧拉路嘛。用二分搜索来插入点，求了一下各点的度就往上交，结果返回个CE（不祥之兆，预示着灾难的开始）发现在交的时候可能碰了一下回退键，结果把一个分号删了，ft~~再交，WA了，再仔细看看发现题目中没说stick可不可以换方向，又写了一个不能换方向的有向图欧拉路，还是WA，然后又加了几个特殊情况的判断，像没有棍子的情况，只有一根的情况，棍子两端同色的情况，还是WA，这时候已经发现这题有点诡异了，五十多submit居然没人AC，只好暂时放弃去做别的。

这时候已经过了一个小时多一点，做别的时候还在一直想这个题，以至于最简单的D居然错了4次，没有想到上次的烟头可以留到下一次的，一开始总以为是数据范围的问题，把高精除高精都搬出来了 >_<~~~ 后来的A和C也是糊里糊涂过了，改了一个白痴错误做掉C以后，脑袋清醒一点了，能把很BT的G题敲出来说明我的思维已经基本恢复正常，其实没过这题的只是因为不清楚规则而己，我WA了一次是以为王只能走四个方向的，多亏后来问了wtommy一句后改过来了。B题列了一个方程发现不可能解出来的，又看到有人说二分，写了一个居然一次AC了，这题的rp还不错~~

剩下三道题过的最多的就是H了，又开始WAing~~这次想到了要先判连通的，不过这题的点太多了，直接用邻接矩阵显然不行，我想到了一个用并查集的方法，自以为很巧妙了呢，还是WA~~~一直WA到比赛结束~~~彻底无语了~~~结束后找到数据才发现居然如此BT，只能说是rpwt了……开始的一小时和最后的一小时都花在H上，各种错误都出现了~~~因为把时间都浪费在H上了，E和F根本没有看，不知道是怎么样的题。

总的来说还是经验不足，一开始选择失误，WA了多次之后非常慌乱，还导致别的题无谓的出错，我在做5题的里面排名很靠后，就因为罚时太多了，另外对数据的BT程度认识不够，我一直以为空输入是怎么也不可能的，所以虽然加了特殊处理也没有特别留意，没有想到居然就在这里出了问题，最后的时候我把所有不确定因素的所有组合情况几乎都试过了，就是没有想到把这个空输入的Impossible改一下。另外这题我的算法还是有问题，用了4S多才过，比赛的时候这题的时限好像是3S的，感觉开始插入的时候用二叉排序树可以快一些~~~

和那些大牛的差距还是很大，努力ing~~~

刚敲掉了一个被我称作“体力活儿”的题。做的比较郁闷，死活都是WA，实在挺不住了找来数据一看，狂ft~~~发现自己对题目的理解能力超过了出题者（某大大语录），好几个我认为有疑问加了特殊处理的地方，标准输出里居然管都不管，把我的程序删掉一堆东西，AC了 -___-||

以后要少做这种题了，只作消遣时用。说实话这样的剩下的也实在不多了，ZOJ上我可以确保能AC只是懒得去打代码的题，满打满算二十道吧，不知道以后还能不能多发现一些，按照过来人的说法，以后似乎就应该是拼IQ了。

翻去年此时的帖子，好像那时候组队前的这个阶段大家都在狂切简单题，今年的进度要早一些，估计大家手上都没什么简单题了吧（相对于各自的水平来说）呵呵~~感觉还是看书比较重要，发现每看懂一点东西，总能相应地切下几道题来，一些以前觉得根本没法下手的题也能做了，挺不错的。其实现在还是知识不够，可能高手看来是理所当然的思路，因为我们以前没接触过，就会感觉非常困难，比如前些天比赛的Cows那题。

总之还是要多看多学，同时多做一些需要思考的题，还要克服依赖forum的毛病，不过做难题的时候已经很难找到相关的讨论了，这对我来说也是好事。前两天遇到一个二叉树序列的问题，LeeMars的解题报告都被我搜出来了（这位小老虎的解题报告之详尽完备大家都是知道的哈）努力克制着自己没去看，想了一个用Catalan序列逐渐逼近的算法，做了三四个小时被我搞出来了，然后再去看那份解题报告，发现他的思路几乎是完全一样的，hoho~~~ LeeMars大牛说这题让他想了一个月，可见干拼IQ的话我也不怵谁~~~ （先别拍我，让我yy一下）

据说在一套题库里，每个人的做题数目会有一个极限的，就算是这样，再给我一年时间，我要把我的ZOJ极限顶到800以上~~~希望一年后我看到这句话时不会很郁闷，睡觉去了，下午还有比赛呢~~~

摘要：偶们软件学院(hehe~~)有人新开的论坛上水版的一篇文章，挺有意思的题目，虽然有几个以前见过，我费了不少劲写了份解答，随便也贴在这里了，有几个没有解决的问题还请高人指教。其实组合数学很多都是这种游戏性质的东东的……　查看全文