特例+寓言式推理=结论

November 22nd, 2007 No Comments »

这是今天李冉老师课上提出的一个类似思维定势的公式,我觉得还是比较有意思的。

(不过顺便说一下,虽然我同意李老师的分析,但我不同意他对易中天下的结论……)

 

特例+寓言式推理=结论

这个公式错误的关键是推理过程——特例的不普遍性,并且寓言式推理的正确性/错误性有待考察;但是由于语言文字的迷惑性……最后的结论就可以很有煽动性而达到套公式者所期望的效果。

三点建议:

A. 培养系统的思维习惯

B. 不要过早的下结论,盲目地进行思想路线分类 (*之前60-70年代思想运动的后遗症)

C. 慎用公式化的思维方法

Wordpress: IIS下的Permalink解决方法

November 20th, 2007 1 Comment »

好神奇的方法啊~ 

充分利用了404重定向... 大体方法就是自己建一个如下的wp-404-handler.php

<!--p <-->$qs = $_SERVER['QUERY_STRING'];
$pos = strrpos($qs, '://');
$pos = strpos($qs, '/', $pos + 4);
$_SERVER['REQUEST_URI'] = substr($qs, $pos);
$_SERVER['PATH_INFO'] = $_SERVER['REQUEST_URI'];
include('index.php');
?&gt;

然后将空间的404错误页面指向wp-404-handler.php, (注意如果可以的话,选择URL转发而非REDIRECT, 否则会有一个Object Moved的response) 然后这个handler就会把请求parse并传给index.php。

另外这个方法也是搜索引擎友好的,所以强烈推荐~

原文连接:http://tech.einaregilsson.com/2007/07/30/pretty-wordpress-permalinks-on-iis/

Excerpt from Forever Knight

November 20th, 2007 No Comments »

Harry wasn’t sure about what he felt, considering.  He had fought in this war since his first year in Hogwarts; he had felt the burden of it since his fourth.  Looking back on it, he now wasn’t sure if he’d been fighting for a cause.  After all these years, having lost so many, he was more familiar with the concept of fighting to survive, and perhaps to prepare himself for the day he could end it all by facing off with Voldemort. Sometimes he worked with a team, and he did everything to ensure their survival, but had he actually stood on the battlefield and felt driven by self-righteous passion?  That this was a fight about good triumphing over evil? 

 

He was surprised to realize that it hadn’t been like that for him.  His motivations certainly hadn’t been driven by selfishness, but “fighting for the side of good” seemed so abstract to him now, having lived the realities of war.  The last eight years of his life had been about getting the guy next to him—on the battlefield—home, preferably alive, or making sure that Ron got to spend the next Christmas with his family, or having Tonks and Remus live so they could raise a family in peace, or getting Hermione back alive so that maybe they could have their happily ever after, dark fairy-tale though it might be.  All these things meant something to him.  These things were comprehensible and real.  In the face of all that, “fighting for the side of good” seemed nothing more than Ministry propaganda. 

 

Harry realized then that the soldiers he’d sent off weren’t looking to him because they saw him as the Boy Who Lived.  They looked at him and saw a bloke who understood exactly what they were fighting for.  He wasn’t like Dumbledore who was a symbol of wisdom, goodness, and strength.  That image, however gloriously inspiring, was inaccessible and distant, almost divine; like Merlin and Morgana.  At any rate, he didn’t want to be like that.  He wanted these soldiers to look at him and see a man who fought with them on the battlefield; someone they could call to for help and expect to pull them up by the hand, physically, should they happen to fall, or find themselves hanging off a cliff, or buried under rubble. He wanted them to see a bloke who had reasons for living, reasons that weren’t so far from theirs. 

 

Those men who shook his hand weren’t just telling him to defeat Voldemort.  They were telling him to get through it alive, because if he survived it, then maybe they would, too. 

 

- Chapter 36: Purpose, Forever Knight, by DeliverMeFromEve

Contest Summary: ACM/ICPC NWERC Regional Contest semilive

November 19th, 2007 No Comments »

做了半天唯一的感觉是好多牛人啊~~虽然这次题目几乎都很简单~

比如我们下面的MSU CrazySEx13居然有时间写完F+提交6次-_- (那题我觉得为了让代码顺利在时限内出解还是有很多优化要做的……peter曾经估计这道题要写300+行)

而coldor他们居然做了三个小时然后扔下两道计算几何跑了-_-我觉得这次的计算几何题还是不错的啊~总算不是纯体力活了~ 虽然F的代码量似乎还很大……

不过我们今天做的似乎就很水-_- 比如A交了3次H传达题意失误导致拍到一半重写J细节未考虑周全之类错误……

 另外写Summary其实还是很有意思的~~~

Continue reading »

ACM/ICPC 2007 Regional Summary: Changchun Site, Nov 2 – Nov 6

November 18th, 2007 No Comments »

Amethyst: Contest Rank: 23rd / ICPC Rank: N/A

题外话:

下火车的第一感觉是长春明显没有想象的冷啊~

不过长春的轻轨建设方式还是有点那个的……某些路段和马路并行+共用红绿灯,总感觉很容易出问题。

然后是吉林大学~几十个亿建成的校园果然不一般~~ 华丽到我们都在YY这是校园还是公园~~~ 不过校园和我们的住宿处就形成了鲜明的对比-_-

转到比赛。

练习赛那天我们中午吃完午饭回住处拿东西,但是由于大家都错误估计了从宾馆到赛场的时间(单程耗时近30分钟),我们赶到赛场已经是比赛开始十多分钟之后的事了-_- 自然而然就发生了某件我怀疑让全场都记住我们队的事件-_-bbbbbbbb 这里就不提了 (据说当时声音大到很多人都停止做题去看怎么回事-_-不过之后有个小插曲:我们进场后peter瞬间秒掉一道题,然后我们似乎就变成场上第一个过题的队了……)

 

正式赛。整场比赛做的很郁闷,大体就是刚开始peter看到A可做,但是由于出了一点xxoo的交流问题,导致我自己冲上去拍……交上去RE, peter合作改掉两个bugTLE. 这个时候我们还是O(2^N*NlogN)的暴力枚举,稍微考虑了一下优化成O(2^N), 再交就过了-_- 而这个时候已经80多分钟了。后来的一段时间我在非常天真纯洁地在想F O(MN^2)算法……直到2小时多放弃这个题; 同时Peter证出了E题的枚举可以限制在某个范围之内,然后提交并1Y

这个时候由于我们没有可以写的题,LynnKaye决定写D。然后我转去看题发现H/I均可写; 但这时LynnKayeD的程序效率太低 (而这时场上已经有不少队伍3/4题了) 于是我转去协助D, 同时peter开始打G题的表格。(当然我那时大脑短路没发现D被我们想复杂了。。。 导致莫名其妙计算量多了10-_-bbbbbb)

另外我调D的过程中LynnKayeFO(MNMlogN)的算法一定可以过, 但当时由于我错误估计了最坏情况下复杂度坚决拒绝去写……比赛后却知道judge们的标准做法就是那样-_-bbbbbb 我错了……

 

这一段时间场上发生了很多神奇的事情——

1)主办方提示今天比赛很多的题目看起来可能很难但其实不是这样的,鼓励大家去尝试做题……但我们却没有一个人意识到Judge们的意思是今天很多题是可以水的-_-比如那道xxF题……

2)由于场上过题队数过少裁判宣布放宽A的时限+Rejudge! 然后似乎一次放的时限还不够多,一会儿之后又第二次Rejudge——结果好象就是A无论多暴力的枚举都过了-_-bbbbbbb

3) 据说离比赛结束一个半小时主裁判曾经让大家去做字符串处理题I -_- “字符串处理那题很简单,现在写还肯定来得及.”(不过这句话我没听见……当然听见了我也不会去做的…)

 

总之过了一段时间就封Board了……这时D的程序仍然很慢(5~10组极限数据就足够让程序超时)而我感觉D我们的算法应该不是最优的但又没有什么更好的思路,无奈之下放弃D去写H;期间同时发现Peter G题的打表效率有问题……最后我拍H直到<10min过样例+自己出的数据提交&返回WALynnKaye修改D直到最后发现之前加的某个剪枝有问题,无奈之下删掉所有剪枝后提交居然返回WA而不是TLE-_-

然后比赛结束之后我郁闷的检查H的代码然后在10分钟内发现两个低级错误(当时拍的太急了……)当时有!@#$%^的冲动。。。

 

总体上说 我们的主要失误首先是我和LynnKaye没有尽早把题目完整地读一遍(我个人开始只读了AF, 直到过了A之后才去读其他题目),而这直接导致初期错误的做题顺序;其次Peter的代码能力非常强而这两场比赛都主要在想题。再有一点就是我们最后应该集中精力去攻一道题;我相信D H如果再多一点时间应该都能过的。另外我们还有一点失误就是D的代码备份不够多 (没记错的话我们一共只留了2份……)

 

最后虽然这场比赛的题目比较不爽(暴力+打表 …) THU PKU等队伍仍然出了4~5题……我觉得这也说明了我们队存在的一些问题。

 

暂时到这里。

 

最后惯例,题目分析。

A: 枚举+凸包。朴素做法(O(2^N*NlogN)),优化后的复杂度是O(2^N). 这道题利用凸性质剪枝应该可以做到赛后裁判长说的N=40, 不过后来我没有测试过。

B: 搜索+打表, 当时据Metaphor队说他们的打表程序跑了2个多小时。

C: 首先枚举R-robot的修理方案,然后对于G-robot网络流检查解是否可行。

D: DP+剪枝-_- 比较郁闷的是我们之前一直在想怎么优化算法……最后10分钟决定交了才发现程序是错的-_-bbb

E: 据说给定的数的可分解性与a^2 + 2 * b^2是否为质数有关~具体我不会证,请参阅P大牛blog~ 但是据说这道题数据水到随便限一下边界枚举都能过……

F: 这是我整场比赛最无语的一道题了-_- 据说O(M*N^3)的算法优化一下常数就能过,而出题者的标准做法居然是O(MN*MlogN)! 而我当时一直在想计算量在10^7左右的算法-_-bbbbbb  另外这题的最优做法是最短路树。

G: DP+打表~~~复杂度应该是是O(N^4*logC),不过当时我们打表的方式似乎有问题,导致程序效率很低。

H: 分块处理,或者线段树

I: 模拟题,但是当时由于在网络预赛中已经对JLU命的这种题有点心理阴影而没有做-_-

最后, Scoreboard以及成绩……

Continue reading »