Gaewah.Com

祝爸爸节日快乐~

顺便祝天下所有父亲节日快乐。

刚刚才发现，周董的《说好的幸福呢》里的女主角真的挺像《最终幻想7-降临之子》里的完美女神Tifa。无论脸型，发型都有几分神似啊，都是美女：）
　　看过一些Tifa的Cos，真的每一个满意的。如果叫她去的话，估计会大受好评吧（YY中……），难道周董也是FF的Fans？
　　废话不多说了，刚好手上有标清版MV，剪几张来对比下，欣赏美女咯，哈~~

怎么样，还不错吧~~~

上面单数是Tifa，双数是《说好的幸福呢》女主角陈匡怡~

本以为会办的很好，实际上的最终board也与预测中比较类似，十分惊喜，比赛中有来自天大，浙大，武大，川大，华南理工，西电的Final队或牛队来捧场。还有来自母校衡阳八中的那群已经迅速成长的小KIDs们的精彩表演。

美中不足的是，水题扎堆而，陈题一大堆。并且被不少人看出来，直接交了标程，导致比赛有失公允。

但我自认为这不是我的错，至少作为命题组的一员，我已经尽力了。我出的3题，除了最水的F无所谓原创不原创外，另外的H和I都是原创的。但由于种种原因，这两题鲜有人问津，让我很失望。

下面简单说下解法：

 A题：哈希+解模线性方程的数论题，感觉数论相关的难题，如果以前仔细研究过，一般都可以写出来，但如果想在比赛中现场研究一个，还是比较难的。

B题：由于出题时没有很好的沟通，导致B题和H题有很大的相似的地方，不过还是不同的。自认为H应该比B题简单些，事实上B题现场过的人却还多一点。因为B题是动态提问的，而H题的答案摆在那。也因为要动态处理，所以B题需要用到高级数据结构——线段树。解题应尽量往线段树方向想，在线段树上DP

C题：题目意思简洁，解法也简洁，但用某些容易想到的方法却处理起来不太容易，标准解法是二分，这样做的话会省很多事。

D题：本题是一道经典陈题，它在CEOI 99. Ural, POJ 等多个OJ或比赛中出现过，并且本题竟然没有改样例。导致比赛5分钟就有人交标程，后续很多人跟着交，所以这题虽然不简单，通过率与通过速度却很高。用 Sum(i) 表示序列第 1 个至第 i 个数的和, 那么 “a b even” 表示 Sum(a-1) 和 N(b) 同奇偶,”a b odd” 表示 N(a-1) 和 N(b) 不同奇偶. 用并查集, 把两个有关系的点记录下来.

E题：本题也是一道经典有向图的强联通分量。

F题：本题有意让题目意思很纠结，生词很多，背景很长，为的是考察大家的看题情况，事实证明效果很好，在1个小时之内只有3、4支队伍AC，AC人数与AC率远远低于D和E，知道近2个小时的时候大家才开始发现这道水题。当然题目中我没说清楚的是给每个editor的属性，effect和cost是否可能为负数，的确数据里没出现负数，但出现了0，数据范围没说清楚，这是我的失误。最后这题是一道简单的背包题，解法就不详说了。

G题：据出题者说，这是一道水题，事实证明它不是一道水题。解法是简单的枚举搜索+适当的减枝。

H题：和B题类似，也是最大子段和问题的扩展，不过这里扩展成3维的。解法有两种，一种是枚举底面，因为每层的方块权值是一样的，这个问题就转化成最大子段和问题了。另一种是枚举高，每个对应的高和它出现的位置能算出这个高的位置，再根据这个高可以算出一个最大的面积。比赛中天大用的貌似是第2种方法，而其效率貌似更优。

I题：这是我精心准备的一题，可惜比赛中无人通过。看了一下尝试的几个队伍的情况，大家都想把这道动态规划的题优化成线性的问题。事实上由于Y[i]对于每一个i的不确定性，这里并不能用到动态规划的单调性优化。这题是一道单峰极值的问题，标准解法是将题目的动归方程改写成F[i]=min{P[j]+i*Y[j]}+K的形式(0<=j<=i)。再进行优化，在求之前状态最优解中用到平衡二叉树保存之前算出的状态，再维护这棵树。

本套题目内部均有解题报告，但由于制作水题很水，因此暂不对外开放下载，对某题有疑问的可以留言讨论，或索要解题报告。

大家喝的是啤酒，这时你入座了……
你给自己倒了杯可乐，这叫低配置。
你给自已倒了杯啤酒，这叫标准配置。
你给自己倒了杯茶水，这茶的颜色还跟啤酒一样，这叫木马。
你给自己倒了杯可乐，还滴了几滴醋，不仅颜色跟啤酒一样，而且不冒热气还有泡泡，这叫超级木马。
你的同事给你倒了杯白酒，这叫推荐配置。
人到齐了，酒席开始了。
你先一个人喝了一小口，这叫单元测试。
你跟旁边的人说哥们咱们随意，这叫交叉测试。
但是他说不行，这杯要干了，这叫压力测试。
于是你说那就大家一起来吧，这叫内部测试。
这个时候boss向全场举杯了，这叫公开测试。
菜过三巡，你就不跟他们客气了。
你向对面的人敬酒，这叫p2p.
你向对面的人敬酒，他回敬你，你又再敬他……，这叫tcp.
你向一桌人挨个敬酒，这叫令牌环。
你说只要是兄弟就干了这杯，这叫广播。
可是你的上司jj听了不高兴了，只有兄弟么，罚酒三杯。这叫炸弹。
可是你的下级mm听了不高兴了，我喝一口，你喝一杯，这叫恶意攻击。
有一个人过来向这桌敬酒，你说不行你先过了我这关，这叫防火墙。
你的小弟们过来敬你酒，这叫一对多。
你是boss，所有人过来敬你酒，这叫服务器。
酒是一样的，可是喝法是不同的。
你喝了一杯，boss喝了一口，这叫c#。
你喝了一杯，mm喝了一口，这叫vb。
你喝了一杯，你大哥喝了半杯，这叫c++。
你喝了半杯，你小弟喝了一杯，这叫汇编。
你喝了一杯，你的搭档也喝了一杯，这叫c。
死就是一念的事，活着却是一辈子的事，所以活着比死更需要勇气 says:
酒是一样的，可是喝酒的人是不同的。
你越喝脸越红，这叫频繁分配释放资源。
你越喝脸越白，这叫资源不释放。
你已经醉了，却说我还能喝，叫做资源额度不足。
你明明能喝，却说我已经醉了，叫做资源保留。
你喝一段时间就上厕所，这叫cache。
酒过三巡，你也该活动活动了。
你一桌一桌的走，这叫轮巡。
你突然看到某一桌的漂亮mm，走了过去，这叫优先级。
你去了坐下来就不打算走了，这叫死循环。
你的老大举杯邀你过去，你只好过去，这叫激活事件。
你向一桌敬酒，他们说不行不行我们都喝白的，于是你也喝白的，这叫本地化。
你向boss敬酒，可是boss被围了起来，你只能站在外圈，这叫排队。
你终于到了内圈，小心翼翼的向前一步，这叫访问临界区。
你拍着boss的肩膀说哥们咱们喝一杯，这叫越界。
你不知喝了几圈了，只会说两个字，干了，这叫udp。
可是还有人拿着酒瓶跑过来说，刚才都没跟你喝，这叫丢包。
喝酒喝到最后的结果都一样
你突然跑向厕所，这叫捕获异常。
你在厕所吐了，反而觉得状态不错，这叫清空内存。
你在台面上吐了，觉得很惭愧，这叫程序异常。
你在boss面前吐了，觉得很害怕，这叫系统崩溃。
你吐到了boss身上，只能索性晕倒了，这叫硬件休克 。

Update:2009-03-27
其实，方案内容也没多少，特别是最重要的一个步骤，也就一条命令。只是为了测试下Nvidia发布了最新版的Linux驱动（180.22），延迟了几天，虽然结果还是不令人满意。
由于，我用的是Ubuntu，这里以Ubuntu为例，各大Linux发行版特性其实是差不多的，解决方法也应该大体一样。
相信，如果一开始就尝试过自己安装Linux的话，一定遇到过两个主要的问题。
如果插人Ubuntu的LiveCD，进行安装，一定会在进X的地方卡住。可能是由于双显卡的原因，Ubuntu无法辨别这是哪块显卡。这就是第一个问题。
出错了要重启，重启提示按”Enter“键继续，这时才发现，原来键盘也是失效的。这就是第２个问题。
这两个问题在之前都是有解决办法的。
双显卡不能识别问题，可以刷3.02版的BIOS解决，而且今天依然推荐用这种，原因后面会说。但今天还是会给出一个不刷BIOS的解决办法。
而键盘失效问题，之前一直没有解决，无奈之下也只有在刷完BIOS，进系统后插个USB键盘。这个问题，其实怎么解决，在国外讨论了好几个月了，没见有人很好的解决，最近在一篇不起眼的帖子的跟帖中，一个低调的牛人用一条命令解决了，感觉真是很讽刺。。。
今天将给出这两个问题的第２种解决办法。以及各种解决办法所遗留下的问题。

OK，废话不多说了，进入正题。
以Ubuntu为例的解决步骤：
1、了解你所要装的Linux系统，学习通常如何安装，并决定好你要装那个盘，划分好分区，这些内容不出现在本方案中。
2、插入Ubuntu的LiveCD。
3、选择你习惯的语言，将选择条停留在“用而不改变计算机的任何内容”处，并按F6，打开其他选项（P.S顺便说下，我感觉这句翻译很扯，我就是想用LiveCD安装系统，啥叫不改变计算机的内容）
4、屏幕下方将出现　“引导选项 …… quiet splash –”　省略前面的，那一部分都不要动。
5、最重要的一步，解决键盘无法响应问题：在引导选项的”–”前添加“i8042.nomux=1 i8042.noloop=1″语句，并回车。
6、貌似添加后，LiveCD的启动速度会比通常情况下慢，但是不用担心，时间不是问题，键盘能用才是最重要的!
7、等待，等待……漫长的等待过后，不同BIOS版本的用户应该会出现不同的情况。3.02版BIOS用户请跳至第9步
8.1、安装前，BIOS版本号在1.08~1.16之间的用户：
到此，系统应该会报一个错误，如果安装的系统想使用Nvidia的9600MGT显卡，请先进入windows xp将BIOS刷成3.02版，重复以上步骤后跳至直接跳到第9步继续阅读。如果想不改变其他系统中双显卡切换功能，并不介意Ubuntu中使用 Intel的集成显卡，则继续：
8.2、待系统报错完毕，按Ctrl+Alt+F1进入终端
8.3、输入”sudo vi /etc/X11/xorg.conf”
8.4、将光标移动到Section “Device”　附近
8.5、在键盘上按下i键（vim这个软件不按i键是不能编辑文件的）
8.6、在Section “Device”和EndSection之间添加一行　BusID    “PCI:0:2:0″
8.7、将Driver后面引号的内容改成intel，如果没有Driver这一项就添加一行Driver   ”intel”
8.8、按Esc键
8.9、输入　”:wq”　并回车（冒号是必须的）
8.10、输入命令”sudo /etc/init.d/gdm restart”
8.11、如果顺利的话，这次应该可以进入LiveCD了。
9、如果是3.02版的用于，这次应该也是顺利进入LiveCD了。
10、按正常步骤安装Ubuntu（或其他版本Linux）
11、重启
12、由于上面的键盘补丁是临时的，这里要重新修正下键盘问题。
13、在选择系统的那个地方，先不要进去，下面有提示，按e键修改启动参数，改第２项　kernel什么的。。。
14、同样在最后面加入 i8042.nomux=1 i8042.noloop=1
15、进系统。
16、BIOS版本如果不是3.02的用户可能又一次会报错了。重复8.1-8.11，这次应该可以正常的进系统了。
17、刚刚的键盘补丁依然是临时的，进系统后来个一劳永逸的方法。
18、进终端输入”sudo cp /boot/grub/menu.lst /boot/grub/menu.lst.backup”（这个是备份用的）
19、输入”sudo gedit /boot/grub/menu.lst”
20、感慨下，图形化的界面真好，终于摆脱vim了。。。
21、找到下面title                Ubuntu 8.10, kernel 2.6.27-14-generic（这里版本号可能不一样）下的kernel的最后面加入 i8042.nomux=1 i8042.noloop=1
22、愿意的话把每个kernel后面都加也行，反正你要进的那个版本的kernel要加才能跳过键盘的错误。
23、保存退出。
24、3.02版的用户可以去找NV的驱动了。至此应该问题都解决了。

下面说下可能出现的问题：
1、3.02版BIOS的用户应该很清楚，这个版本的集成显卡应该处于屏蔽状态，在设备控制器里都找不到。
2、用NV驱动的话，键盘的”\”和”|”这个键会出问题变成”<”和”>”，（就是有明基键盘装了两个这个键的，有一个是没问题的，原来那个多的键是干这事的，强！）
2、1.08~1.16版的用户，经研究发现，在Ubuntu下，虽然只能使用intel的显卡，但Nvidia的9600MGT并没有关闭，处于放电状态，导致待机时间并不长。这也是为什么依然推荐刷BIOS再装Linux的原因。XP下同样放电……
3、不知道是不是我系统的intel驱动的问题，反正intel驱动正常加载后，再按ctrl+alt+f1就看不到任何字了，出现黑色屏幕和绿色的块。当然如果善于盲打还是没问题的，虽然很痛苦的说。
4、我已经多次尝试，在不把集成显卡屏蔽的情况下去装nv驱动，去进系统，情况如下：
我通过修改xorg.conf，让ubuntu去认我的9600MGT，它的确能认出这是一块nvidia的显卡，
接着，它提示初始化错误。
接着，我查错误报告。
它提示，nvidia显卡在读写/dev/nvidia0这个文件时出现I/O错误。
接着……我不敢继续了，因为/dev/nvidia0是硬件里的东西了，继续下去，担心显卡不保阿，这方面完全没有经验，那位牛人有兴趣研究研究把。
5、至于明基为什么不让xp也支持双显卡切换，通过查阅大量国外网友的留言，我明白了，这绝对不是明基做到的。在是Nvidia的问题。
目前使用Hybrid Graphic技术的笔记本并不多，大致也就这几种：
Sony Vaio Z-series (intel/nvidia)
Fujitsu Siemens Amilo XI 3650 (intel/nvidia)
BenQ Joybook S42 (intel/nvidia)
ASUS N10J (intel/nvidia)
Dell Studio XPS 13 (nvidia/nvidia)
MSI EX630 (nvidia/nvidia)
Lenovo ThinkPad T500 (intel/ati)
Lenovo ThinkPad T400 (intel/ati)
ASUS M51Ta (intel/ati)
Fujitsu-Siemens Amilo Sa 3650 (intel/ati)
MSI PX211 12” (intel/ati)
HP Pavilion tx2500 (intel/ati)
可以很直观的看出，与Nvidia相关的机型就6款，而intel显卡和nvidia的双显卡切换的只有４款，其中我知道sony的那款是有一个实体按键的切换的，问题相对小点。华硕的不清楚。富士通的那款则用的是和明基一样的显卡。
而就这么两三款机器，还是非人气产品，让Nvidia花很大精力来满足我们，给我们开发驱动，我觉得不止有点难，相当难。
特别是在nvnews.com那个网站，看到nv的客服（可能是吧，我猜的）说“我们（NVIDIA）暂时没有给Linux支持Hybrid Graphic的计划“我就知道了让Linux支持双显卡的摇摇无期，不知道在我机器退休的那天看得到不？
以后，NV肯定还是会发布支持物理特效的Hybrid Graphic的最新驱动，到时候肯定还得刷回版本号为1系列的BIOS。
到时候，只能一边用着集成显卡，一边拿独立显卡费电了。我们的声音这么小我们又能干什么呢？
特别是有国外玩家提到“NVIDIA是世界上最后一家发布显卡而没有公布相关文档的公司“这种情况下，连网友修改版都难以看到了。只有无奈。

感谢感谢，感谢读完。
本人语言表达能力有限，还有以上情况没有一一测试，有遇到不一样的，希望跟帖说明，我会跟踪修订的。
里面也有很多我不明白的，甚至可能有说错的，希望高手能指正

本文首发于本友会，和网址为我名字点COM的博客

=============================================

预告帖

经过近5个月的研究（我是国庆买的哦！），我终于将S42装Linux的一系列问题接近完美的解决了：包括键盘、触摸板失效问题、图形显卡进XWindows失败问题接近完美的解决了。
之所以是接近，是因为还遗留了一些驱动问题，这个在xp下也是没有解决的，比如双显卡切换，目前看来是很难解决了，除非NV大发慈悲，开发个Linux版的双显卡切换……（不太可能恶）

但还是可以将就用了。
至少可以配置出键盘、触摸版正常访问。
可以选择使用集成显卡还是独立显卡进Linux（和xp下一样，不刷BIOS就用Inter的，刷了就可以用Nvidia的）

真是很好很开心阿。。

由于我准备发布一份详细的解决方案，目前各种方法及可能出现的情况都在整理中。
其实，我也只是Linux的非常非常初级的用户，各位Linux大牛们就莫见笑，也莫指责了。并且我目前用的是Ubuntu系统，对于其他的发行版，各种命令可能不一样，但原理是一样的，就只能借鉴不能照搬了。相信一般用户都能解决吧。。

我希望我来发贴的时候，不要太让我伤心哦。大家顶我。。。

　　三个月不上校内，不上CB，不上本友会，不上魅族，不上易码，不上维基，每天6点半起床，我受刺激了，事者Q287855269!

poj1961 - 求给定串的自我匹配的pre值（通常的讲义里是next数组表示）就可以了。当前前缀长度i-pre[i]的值能被i整除就说明符合题意。

poj2406 - 貌似1961的简化版，就是求1961前缀为整个串的时候的情况。

poj2752 - 长度为n的整个串肯定既是前缀也是后缀，pre[n]肯定也符合题意，那么pre[n]那个串的pre[pre[n]]也是。。。这么一直递归下去直到0

欢迎来到扯蛋的WordPress。这是您的第一次试扯蛋。您可以修改或者把它删除，然后开始正式扯蛋！
aaa

等宽字体
aaaa
bbbb
cccc
a:=b;
b:=c;
c:=a;

用Pascal来扯蛋就是：

1
2
3
4
5

begin
while true do begin
writeln("hello 扯蛋!");
end;
end.

1
2
3
4
5
6

#include <iostream>
using namespace std;
int main(){
    cout<<"hello world!"<<endl;
    return 0;
}