The Sun Also Rises

Algorithm, Mathematica, 计算机科学, C++, photography, GNU/Linux的讨论空间

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  73 随笔 :: 6 文章 :: 169 评论 :: 0 Trackbacks

#

500分的题。。。
由于之前看到过chomp game,(《Game Theory》的练习里有),然后开始试图推公式之类的。。。在wiki上找到rectangle情况先手必胜的证明:

Who wins?

Chomp belongs to the category of impartial 2-player perfect information games.

It turns out that for any rectangular starting position bigger than 1 × 1 the 1st player can win. This can be shown using a strategy-stealing argument: assume that the 2nd player has a winning strategy against any initial 1st player move. Suppose then, that the 1st player takes only the bottom right hand square. By our assumption, the 2nd player has a response to this which will force victory. But if such a winning response exists, the 1st player could have played it as his first move and thus forced victory. The 2nd player therefore cannot have a winning strategy.

Computers can easily calculate winning moves for this game on two-dimensional boards of reasonable size.


很优美的证明。。。只可惜不能提供任何strategy...-_-bbbbbbbb
最后终于悟出来这题规定棋盘3*n, n<=100,所以就100*100*100的dp就行了。。-_-bbbbbbbbbb


p.s. wiki : Chomp Game


p.s. 确实觉得一知半解是一个很容易出错的情况...因为如果完全不知道思维也就没有任何限制了,曾经看到过么...感觉会有点紧张(想要赶紧搞掉的那种感觉) & 试图用记忆中的套路去做...但有时候可能没有关系(例如这个game, 先手必胜的证明并不能提供任何先手如何operate的信息...,如果继续往这个上面想就直接挂了...-_-bbbbbbb)
还有就是有可能会出现类似于"当时为什么不仔细推清楚"之类的念头...这个seems容易解决...

感觉如果是完全陌生的题想法通常容易比较open, 如果感觉这个模型熟悉一般都会试图往熟悉的模型上套...大多数情况下这样确实可以节省时间...但是如果失去了open的思维 + 熟悉的模型无法解决就orz了...


posted @ 2008-02-17 04:15 FreePeter 阅读(990) | 评论 (4)编辑 收藏

基于AJAX的一个在浏览器内的浏览器~~~
好东西。。。可以用来看wiki的articles~~~
and Under GPL~~~~~~~~~

http://gollum.easycp.de/en/
posted @ 2008-02-17 00:15 FreePeter 阅读(528) | 评论 (0)编辑 收藏

[Overview] Arab and North Africa 2007, ANARC2007

Judging Olympia
弱智题
Hide That Number
利用mod11的性质直接算出前面应该补充什么。
Rotating Rings
每层判断是否可行。
A Tale from the Dark Side of the Moon
据说是无聊题
Fermat's Chirstmas Theorem
预处理素数列表 + 直接回答,注意2也是第二类素数
Incidental Points
经典题,枚举一个点,算出其他点相对于它的向量,问题就变成count同样的向量有多少个,sort / hash都可以。。。
Let's Go to the Movies
简单的DP题
The Writer's Club
writer之间求一下传递闭包,然后把所有是某个writer的reader合并起来,可以用32位压int来优化.
Moving Sticks
据说直接搜就可以了。To be written
Johnny Hates Math
经典的DP,用BFS来实现。内存稍微有点紧。


posted @ 2008-02-16 18:24 FreePeter 阅读(1218) | 评论 (3)编辑 收藏

Northwestern Europe (NWERC) 2007 解题报告
Central Europe 2007解题报告
Southeastern Europe 2007解题报告

顺便增加以下这三个页面的PR...~~~
posted @ 2008-02-09 19:54 FreePeter 阅读(1211) | 评论 (1)编辑 收藏

Trouble Loading Firmware 2

If you get the following:

ipw2200: Detected Intel PRO/Wireless 2200BG Network Connection
ipw2200: ipw2200-bss.fw request_firmware failed: Reason -2
ipw2200: Unable to load firmware: -2
ipw2200: failed to register network device
ACPI: PCI interrupt for device 0000:03:03.0 disabled
ipw2200: probe of 0000:03:03.0 failed with error -5

In the latest distribution of Gentoo(kernel>=2.6.23-r3, and udev>=115-r1), everything configuration files are OK now. You may find

    SUBSYSTEM=="firmware", ACTION=="add", RUN+="firmware.sh 

in the file/etc/udev/rules.d/50-udev.rules. Even list ipw2200 in /etc/modules.autoload/kernel-2.6 is unnecessary now.

However, if you compiled the driver into the kernel, you may suffer this problem. One way to solve it is to regenerate the kernel and compile the driver as a module.

Also you may apply this patch : http://ipw2200.sourceforge.net/patches/ipw2200-1.2.2-close_intf.patch

For more informations, visit : http://bugs.gentoo.org/show_bug.cgi?id=202557

If it's not because of this, or you use a relatively old version of kernel, you may read the solutions below.



The reason is very simple (From bugzilla id 202557)
When the ipw2200 driver is built into the kernel (not as a module), it attempts to load firmware from a file on disk while the kernel is initializing, which of course fails because there is no filesystem at this point in time.


The whole article can be found in http://gentoo-wiki.com/HARDWARE_ipw2200
posted @ 2008-02-05 10:24 FreePeter 阅读(431) | 评论 (0)编辑 收藏

注:是昨天的事情了。。。8过没找到哪里可以改发布时间。。。-_-bbbbbbbbbb


早上给小白菜打了个电话。。。
于是他说。。他今天下午正好要和一群人聚。。。
于是把我也push_back()了。。。
我晕。。。这么大的雪。。。恩。。。精神可嘉。。。

于是我就英勇无畏的去了。。。
然后发现他们居然是K歌。。。-_-bbbbbbbbbbbbbbbbbbbbbbbbbb
话说某件事情以后我对K歌都有心理阴影了不是。。。
好吧。。。谁怕谁。。。
然后发现小白菜拖来个(2)班的女生。。。结果我就被萌住了。。。嘿嘿以后对K歌估计就没有心理阴影了~~~~~

发现《美人鱼》唱起来没有想象中的走调~~~
恩。。。进步很大。。。

K完歌大家去吃日本料理。。。
名字叫金田中还是啥的。。。细节不要在意。。。
比较好吃。。。当然有可能是因为小白菜 & zt比较会点。。。
那个煎秋刀鱼相当之好吃啊。。。(话说zt ms在YY上一大盆。。。当然这样的代价可能是我们要留下来刷盘子。。。:P)
生鱼片也不错。。。应该是因为那个芥末不冲。。。我还是很怕芥末的冲味的。。。
(据小白菜说。。。正宗的日本芥末是不冲的。。。中国产的比较冲。。。
那为虾米我在日本吃的时候也这么冲呢。。。难道是中国进口的。。。-_-bbbbbbbbbbbbb)



最后发现wireless配置不成功。。。
我哭。。。为虾米就是load firmware失败呢。。。T_T
freepeter@localhost /sbin $ dmesg | grep ipw2200
ipw2200: Intel(R) PRO/Wireless 2200/2915 Network Driver, 1.2.2kmrq
ipw2200: Copyright(c) 2003-2006 Intel Corporation
ipw2200: Detected Intel PRO/Wireless 2200BG Network Connection
ipw2200: ipw2200-bss.fw request_firmware failed: Reason -2
ipw2200: Unable to load firmware: -2
ipw2200: failed to register network device
ipw2200: probe of 0000:02:03.0 failed with error -5



posted @ 2008-02-03 19:45 FreePeter 阅读(213) | 评论 (0)编辑 收藏

同学是从香港买的V3224AU,因为预装的是繁体的Vista非常之不习惯,然后帮忙装XP.

装驱动的时候找到了这里,但装好驱动以后系统ms有各种各样的诡异问题。。。
其中包括无法正常关机(-_-bbb,虽然我在XP下还是碰到过些的,但刚装好系统2天就这样还真没碰见过。。。-_-bbbbbbb)
容易死机(这个问题在后来重装withSP2XP后非常明显,因此怀疑是双核本本和XP的兼容性问题)
因为不确定是否是驱动的小不兼容问题,然后就先凑合着。
(后来发现似乎只要是AU/TU系的驱动都可以通用,因为都是通用的驱动,比如nForce, GeForce Go, etc, 而且HP官方的XP驱动下载AU和TU的不同机型的驱动指向相同的链接似乎也证明了这一点

最近浏览了下论坛的帖子发现确实HP对XP的驱动支持不完美。。。(打死HP...-_-bbbb,有vista了好歹也照顾下向后兼容。。。)
所以建议还是做vista & XP双启动~
总的说来本本还是很容易出兼容性问题的,如果厂商不支持。。。诶。。。
要不是别人的本本我考虑直接装个gentoo玩玩~~~。。。



我现在的装法:
1. 一套OEM版的简体中文vista & HP OEM版的XP with SP2
如何制作双系统见这篇帖子
2. 驱动是老大发布的最新驱动
3. 关于双核的安装,我的安装顺序是
AMD官方驱动 -> 微软KB924441补丁(ms是双核和ACPI的no respond补丁) -> AMD加速补丁
这三个东西那张光盘上都有。
至于还有一个微软KB896256补丁,官方介绍是
Install this update to fix a situation where your Windows-based systemthat supports processor power management features, and is equipped withmultiple processors, may experience decreased performance.
简称就是accerlate的。。。你看AMD不是有官方的补丁了么。。。而且这个补丁传说中还要手动编辑注册表打开,一定有JQ。。。于是我就不装了。。。

效果暂时似乎还不错,先用一段时间再看看如何。。。




欢迎大家交流想法 & 方法 & 拍砖~
p.s. 今天在一个人的QQ空间上看到一个HP OEM & 集成驱动版的XP
http://191182924.qzone.qq.com/
不知道有没有人试过呢?


posted @ 2008-02-03 19:38 FreePeter 阅读(514) | 评论 (0)编辑 收藏

http://linux.oneandoneis2.org/LNW.htm

关于这段话

Something to bear in mind, however, is that "training wheels" are often available as "optional extras" for Linux software: They might not be obvious, but frequently they're available.

Take mplayer. You use it to play a video file by typing mplayer filename in a terminal. You fastforward & rewind using the arrow keys and the PageUp & PageDown keys. This is not overly "user-friendly". However, if you instead type gmplayer filename, you'll get the graphical frontend, with all its nice, friendly , familiar buttons.

Take ripping a CD to MP3 (or Ogg): Using the command-line, you need to use cdparanoia to rip the files to disc. Then you need an encoder. . . It's a hassle, even if you know exactly how to use the packages (imho). So download & install something like Grip. This is an easy-to-use graphical frontend that uses cdparanoia and encoders behind-the-scenes to make it really easy to rip CDs, and even has CDDB support to name the files automatically for you. 

The same goes for ripping DVDs: The number of options to pass to transcode is a bit of a nightmare. But using dvd::rip to talk to transcode for you makes the whole thing a simple, GUI-based process which anybody can do.

So to avoid #5b issues: Remember that "training wheels" tend to be bolt-on extras in Linux, rather than being automatically supplied with the main product. And sometimes, "training wheels" just can't be part of the design.



关于trainning wheels的问题。。。我个人比较赞同毛大牛的观点
i.e. 我们要先最naive地走一遍,了解它究竟是如何工作的,then 我们可以使用各种辅助工具。
我以为,没有必要每次重新发明一个轮子,但我个人比较倾向于先了解一下轮子是怎么做出来的。。。然后当然不会自己造轮子,而是使用最好用的轮子~~~我相信这无论是对我使用轮子还是在需要的时候对轮子做出点小变动都是及其有帮助的。

这篇文章还没来得及看:

Computer Science Education: Where Are the Software Engineers of Tomorrow?
我个人觉得这年头framework封装的太好了。。。大多数人都可以很快的学会如何快速的用这些轮子、引擎做成一个汽车。但绝大多数人不知道轮子、引擎的制作原理了。。。
恩。。。学习还是C++好啊~~~用起来显然是Java...
Lisp & C++ & Qt & Python...


posted @ 2008-02-01 01:04 FreePeter 阅读(334) | 评论 (2)编辑 收藏

最近看GTD & ZTD很热。。。
有些东西很value...但有些东西。。。有点郁闷。。。
而且我一向觉得这种东西应该是因人而异的。。。不能完全实践某一个。。。
于是考虑YY一个PPTD...~~~

0. PPTD是会随时修正 / 改变的。。。(i.e. open的,会吸收任何我认为对我好的东西)
另外遵循CCPL协议(就是本blog的协议。。。)

以上都可算作废话。。。

---------------------------------------------------------------------------------------------------

1. 关于事情处理的问题。
我个人比较赞同简约话生活(但不简单),因此我大体比较赞同的方式是 专门时间段时间规划 + 忘掉时间表(seems from Lunarmony)。
比较赞同那个MIT(Most Important Things)原则。。。也就是有一些事情是安置好要做的,这些事情不多。排一个较高priority~

然后问题就是。。。别的事情怎么办?
原则上可以排一个相对优先级,然后挑重要的作。
但是实践中发现。。。试图挑的过程中会罗列大量的事情。。。然后feeling stress || 都想作完的感觉 || 反复思考先作哪件事好呢?。。。
虽然我告诉自己反复思考毫无益处。。。但是。。。-_-bbbbbbbbbbb

确实我觉得有些东西不是思考的。。。如果告诉自己,我应该基于什么原则选择事情。。。然后打分。。。挑最重要的。。。我觉得MITs这样还不错。。。如果所有的事情都这样...人毕竟不是操作系统。。。-_-bbbbbbbbbb

我记得2年前的我实践过一个方式叫做“拒绝思考 / follow your heart”
简称就是想到一件事情,然后觉得差不多,就去作,别的就懒得管了。。。然后等到下一个切换点再选别的事情去做。
现在觉得这个方法还是挺不错的,因为其实跳出来的第一件事情往往是你认为比较重要的。。。当然你要有专门的时间来考虑一下哪些事情比较重要。。。~~~
MITs已经被专门 done了。。。
主要的问题(也是我后来drop掉的原因)是有一些事情(如果跳不出来)会一直不去作,简称进程会饿死。。。-_-bbbbbbbbbbbbb
还有就是不知道要做什么事情的时候。。。恩。。。



posted @ 2008-01-29 01:03 FreePeter 阅读(307) | 评论 (0)编辑 收藏

cppblog提供随笔 & 文章2中post方式。
于是按照我的理解,随笔就是比较敏捷 & 快速发布 & 不成熟 & 试验性质的东东(例如关于某道题的一些想法 & 大体思路)
文章是比较summary的东东。
所以解题报告什么的还是丢到文章(article )里去吧。

唯一的问题是。。。
测试了一下发现如果直接订阅我的blog RSS, 文章是不会显示出来的。。。
没什么大问题。。。不行手动通过随笔发文章的link.


posted @ 2008-01-29 00:40 FreePeter 阅读(350) | 评论 (0)编辑 收藏

仅列出标题
共8页: 1 2 3 4 5 6 7 8 
Creative Commons License
This site is licensed under a Creative Commons Attribution-Share Alike 2.5 China Mainland License. 本站采用创作共用版权协议, 要求署名、相同方式共享. 转载本站内容必须也遵循“署名-相同方式共享”的创作共用协议. This site is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.