开学一周

开学一周，不好不坏~~~

总算过来了！~.~

嘎嘎.....

小妹军训也结束了...现在整天在家对着电视~~！

Orz.......

嘎嘎~~~

高一的学生对新的校园总是很好奇的~~！

嗯。。。。

这一周有一件事很丢丑.....

我手机有一个自救功能。。上面说按住“0”健2秒钟自动个设置的号码列表发短信~~！

前天。。。因为上课手机都是调成振动的

晚自习放学了，刚出校门我就改成振动的..嗯了一会，还是真振动的.......

郁闷

........

又按了一次.....好了！~

我骂了句什么破手机~~！！！

然后听着音乐就回家了~~~

刚走了一会，有短信，上面写道：“你什么意思？？”

我....

我毁了一个电话：“什么？你说的我不明白？！什么什么意思？？”

对方：“你刚才发的那短信什么意思？？”

“啊？？”

“没有发啊？”

“怎么会？”

“恩真的没有发。。。。我听歌那！！，短信什么内容？？？”

“上面写的什么‘SOS...我现在醋与危机状态....请给我回个电话.....”

“啊？？？？”

我认识到事情的严重性....因为这条信息是紧急短信..要发的话就是6个人同时接到..........

汗......

我先给老师打了一个电话....关机....还好关机了....我发了几条短信~~！

刚发完，妈妈的电话就来了....哭啊.......

妈妈...我错了.....

没有事...那短信是误发的.....

妈妈...说：“吓死了.....我就是说怕你在晚自习回家的路上出事情.....你先回家。。。。到家在给你打电话（爸妈在外地）......”

很感动......

这次犯下这个错误...我把手机的那个功能关掉了~~~！

嘎嘎.......

以后回想起了真够搞笑的~~~

嗯....

放假了..

还好，这是最后一次了放到1号（囧~~~这也算放假了~~）..因为9.1迎接新生~！

嗯。。。

加油了~~~

没有时间喽~~！


嘎嘎

开学了

奥运会结束了，我门也开学了~~！

奥运会中国的战绩很好...100奖牌，51金牌。创下了新的纪录！

我也要继续努力喽~!

嘎嘎.......

曾经和一个朋友说过开学那天，就是我疯狂的时候~~~

其实啊，何止如此~！

整个暑假。。。某某人都在不停的疯狂！

这样也还好，这正验证了他的那句话~~~

或者升的更高，或者彻底堕落；



或者成就自己，或者毁掉自己。


高三了.......

想起把儿的一篇日记。。。其中有一句话：“也许是上天让我回到OI........”

嘎嘎......没有什么好犹豫的了～！

因为你没有那个资格了～！


Orz....



记得我只愿面朝大海，春暖花开。

Think like an OIer...

Think like an OIer...

1. 与32、95、XP属于同一类事物的是：

A. 61 B. SEX

C. 我 D. Love is Everything

2. 如果48=0，那么84等于什么?

A. :) B. T

C. 000 D. 12:56

3. 下面这些选项中哪一项是一种计算机高级语言？

A. B.

C. D.

4. 下面这些算式中哪一个算出来很可能是负数？

A. 1111+1111 B. 2222+2222

C. 11111+11111 D. 22222+22222

5. (10000000000)2

A. (1024)1 B. (1024)10

C. (1024)100 D. (1024)1000

6. 请选择下列描述中错误的一项：

A. 270400是一个完全平方数 B. 500500是一个三角形数

C. 33550336是一个完全数 D. 以上三项全错

7. 这道题的题目是什么？

A. 关于递归运算的题目 B. 关于线性规划的题目

C. 关于汇编语言的题目 D. 关于周莉莉的一切V

8. 1099511627776B

A. tumor B. tuberculosis

C. aeroacrophobia D. pneumonoultramicroscopicsilicovolcanoconiosis

9. 下面四个选项中有几个是错误的？

A. 1个 B. 2个

C. 3个 D. 4个

10. 以下哪个命令可以列出当前目录下的文件？

A. 楼主 B. 楼上

C. 火星 D. 沙发

11. 请选出下面四个选项中与众不同的一项：

A. 1 B. 2　　　　　　　

C. 3 D. 4

12. 你认为OIer最喜欢下列哪个选项？

A. C B. C

C. C D. C

13. 恐怖份子与战斗机

A. √ B. ×

C. ∴ D. ∵

14. 27乘以6.5等于多少？

A. 92.755 B. 175.6

C. 23.1516 D. -7632.33

15.

16. We use Θ if O( f(n) )=__( f(n) )

A. 劳力士 B. 欧米茄

C. 天梭 D. 斯沃琪

17. 以下哪个选项在英文中出现频率最高？

A. 麦当劳 B. 氧

C. 2.718 D. 函数

18. 打网游为什么经常死机？

A. 经常出现各种人物 B. 经常出现各种宠物

C. 经常出现各种怪物 D. 经常出现各种NPC

19.

A. 123456 B. 234567

C. 345678 D. 456789

20 以下哪个选项正是本题所缺少的？

A. , B. .

C. ? D. !





另附一个回复：


楼层: 15楼 2007-4-30 12:25 ahyangyi 说：

1

选择： D

原因： the answer to Everything is 42, and 42 looks lovelier than 61.

2

选择：B

原因：...其实我更想选A :)

3.选择：全部都是。

原因：约有203,000,000项符合A programming language的查询结果
约有69,500,000项符合B programming language的查询结果
约有105,000,000项符合C programming language的查询结果
约有115,000,000项符合D programming language的查询结果
可见 A语言 > D语言 > C语言 > B语言 :)

4.选择：都不是

原因：都不是“很”可能

5.选择：BCD

6.选择：D

7.选择：A

原因：不认识周莉莉...

8.选择：sesquipedalian.

9.选择：C

10.选择：都不能

11.选择：A

12.选择：A

理由：pascal user不一定喜欢C吧... 反对做B者和丢B者也不会选B... 至于A和D, 当然是A @_@

13.选择：C

14.选择：B

15.选择：[teeth]

16.选择：B

17.选择：C

18.选择：D

19.选择：C（参见12题）

20 选择：D

btw:验证码居然是算式，真伤心，算错了N次...

回复（Matrix67）：天牛驾临，

被华丽地鄙视了……

本游戏试题出自MATRIX67.....再次顶礼膜拜

http://www.matrix67.com/blog/archives/162

notepad++

我不想说什么.....

看看这张图片（我全屏截的）：


图片不清楚，大家可以点击图片看看原图，

建议大家到它官网看一

下！！！

小妹好好

嘎嘎.........

小妹这次回来，变得好好哦！！

记得在很晚的时候（大概深夜2++的时候），我在看书，小妹问我说：“哥，怎么不睡觉？，早点睡吧！” “嗯” 。。我..就说一个字～！

我很郁闷。。。。平时没有那么好啊......要是很早以前........嘎嘎难道我RP暴增～～！！

第二天，我看到我的衣服在外面晾着....恩，很感动～～！

但是我没有说什么！

其实这些都在我的心里哦～！


恩，这次回来小妹的变化真的很大！！

小妹开学上高中了。。。

她真的长大了～！

嘎嘎.......

高兴ing!!!

【春天, 十个海子】

【春天, 十个海子】


春天, 十个海子全都复活
在光明的景色中
嘲笑这一野蛮而悲伤的海子
你这么长久地沉睡到底是为了什么?

春天, 十个海子低低地怒吼
围着你和我跳舞、唱歌
扯乱你的黑头发, 骑上你飞奔而去, 尘土飞扬
你被劈开的疼痛在大地弥漫

在春天, 野蛮而复仇的海子
就剩这一个, 最后一个
这是黑夜的儿子, 沉浸于冬天, 倾心死亡
不能自拔, 热爱着空虚而寒冷的乡村

那里的谷物高高堆起, 遮住了窗子
它们一半而于一家六口人的嘴, 吃和胃
一半用于农业, 他们自己繁殖
大风从东吹到西, 从北刮到南, 无视黑夜和黎明
你所说的曙光究竟是什么意思

关于C和C++的O/I

早有耳闻，C++的不怎么好～～
一直都还不太相信。。
今天倒是亲眼目睹了我的错误～.～

在做RQNOJ的第133题得时候我用C++的I/O做的，80......

看下：

状态: Unaccepted
测评机： Xeond[6]
得分： 80分
提交日期： 2008-8-18 18:26:00
有效耗时： 1860毫秒
测试结果1: 通过本测试点有效耗时63:ms
测试结果2: 通过本测试点有效耗时62:ms
测试结果3: 通过本测试点有效耗时94:ms
测试结果4: 通过本测试点有效耗时109:ms
测试结果5: 通过本测试点有效耗时422:ms
测试结果6: 通过本测试点有效耗时594:ms
测试结果7: 通过本测试点有效耗时469:ms
测试结果8: 选手程序运行超过时限
测试结果9: 选手程序运行超过时限
测试结果10: 通过本测试点有效耗时47:ms

源程序：
#include
using namespace std;
struct Tree
{
long d;
Tree *R,*L;
long sum;
}*T=NULL,*Node=NULL;

void Insert(Tree *&T,Tree *Node)
{
if(T==NULL)
{
T=Node;
T->sum=1;
return;
}
if(Node->d<=T->d)
{
if(Node->d==T->d)
{
T->sum++;
}
else
Insert(T->L,Node);
}
else
Insert(T->R,Node);
}

void Print(Tree *T)
{
if(T==NULL)
return;
Print(T->L);
cout<d<<" "<sum<R);
}
int main()
{
long n,t;
cin>>n;
while(n>0)
{
cin>>t;
Node=new Tree;
Node->d=t;
Node->R=NULL;
Node->L=NULL;
Insert(T,Node);
n--;
}
Print(T);
return 0;
}


而后用C的I/O做的：


状态: Accepted
测评机： Xeond[6]
得分： 100分
提交日期： 2008-8-18 18:37:00
有效耗时： 1217毫秒
测试结果1: 通过本测试点有效耗时62:ms
测试结果2: 通过本测试点有效耗时46:ms
测试结果3: 通过本测试点有效耗时47:ms
测试结果4: 通过本测试点有效耗时63:ms
测试结果5: 通过本测试点有效耗时109:ms
测试结果6: 通过本测试点有效耗时141:ms
测试结果7: 通过本测试点有效耗时125:ms
测试结果8: 通过本测试点有效耗时312:ms
测试结果9: 通过本测试点有效耗时265:ms
测试结果10: 通过本测试点有效耗时47:ms

源程序：

#include
struct Tree
{
long d;
Tree *R,*L;
long sum;
}*T=NULL,*Node=NULL;

void Insert(Tree *&T,Tree *Node)
{
if(T==NULL)
{
T=Node;
T->sum=1;
return;
}
if(Node->d<=T->d)
{
if(Node->d==T->d)
{
T->sum++;
}
else
Insert(T->L,Node);
}
else
Insert(T->R,Node);
}

void Print(Tree *T)
{
if(T==NULL)
return;
Print(T->L);
printf("%ld %ld\n",T->d,T->sum);
Print(T->R);
}
int main()
{
long n,t;
scanf("%ld",&n);
while(n>0)
{
scanf("%ld",&t);
Node=new Tree;
Node->d=t;
Node->R=NULL;
Node->L=NULL;
Insert(T,Node);
n--;
}
Print(T);
return 0;
}


不知道你们注意吗，在用C输出的时候最大耗时是312ms，而C++....我不想再说什么了～～

以后学C++的朋友要注意，最好要用C的O/I。。

终于AC了。。。
有些题目是没什么错，但是要考虑时空的。。


..

刘翔退出比赛

从今天早晨8：00开始我、小妹还有我姨妈一家人就围在电视机前，等待刘翔~！
嗯。。
等了很久，看到要11点五十分才出场....
一家人焦急的等待
期间一直都在议论罗伯斯和刘翔，当然一家人都想刘翔胜出！
11：50小组赛第一枪。。
看着刘翔刚开始做那些滑稽的动作和表情~！
我们只是高兴的笑了.....
而后来，看到刘翔有点不适，一家人都在为刘翔加油鼓劲！
:-)
我们总是认为刘翔怎么都会坚持到最后的~~。~~
没想到，唉...
不管怎样，还是希望刘翔早日康复！！
网上的平论很多，各执其词....！
不想看，也不想参与讨论，正如一个朋友说的：“08奥运最令人震撼的三件事：1.刘翔退出2.斯的枪法3.菲尔普斯夺金。”
唉....
无论如何
都已经过去了！

可以到这里看看：
http://www.beijing2008.cn/news/sports/headlines/athletics/n214558021.shtml

Matrix67:什么是P问题、NP问题和NPC问题

这或许是众多OIer最大的误区之一。

你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题，NPC问题才是。好，行了，基本上这个误解已经被澄清了。下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就可以不看了。接下来你可以看到，把NP问题当成是 NPC问题是一个多大的错误。

还是先用几句话简单说明一下时间复杂度。时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。

容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者：一种是O(1),O(log(n)),O(n^a)等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置；另一种是O(a^n)和O(n!)型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。

自然地，人们会想到一个问题：会不会所有的问题都可以找到复杂度为多项式级的算法呢？很遗憾，答案是否定的。有些问题甚至根本不可能找到一个正确的算法来，这称之为“不可解问题”(Undecidable Decision Problem)。The Halting Problem就是一个著名的不可解问题，在我的Blog上有过专门的介绍和证明。再比如，输出从1到n这n个数的全排列。不管你用什么方法，你的复杂度都是阶乘级，因为你总得用阶乘级的时间打印出结果来。有人说，这样的“问题”不是一个“正规”的问题，正规的问题是让程序解决一个问题，输出一个“YES”或“NO”（这被称为判定性问题），或者一个什么什么的最优值（这被称为最优化问题）。那么，根据这个定义，我也能举出一个不大可能会有多项式级算法的问题来：Hamilton回路。问题是这样的：给你一个图，问你能否找到一条经过每个顶点一次且恰好一次（不遗漏也不重复）最后又走回来的路（满足这个条件的路径叫做Hamilton回路）。这个问题现在还没有找到多项式级的算法。事实上，这个问题就是我们后面要说的NPC问题。

下面引入P类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。哪些问题是P类问题呢？通常NOI和NOIP不会出不属于P类问题的题目。我们常见到的一些信息奥赛的题目都是P问题。道理很简单，一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法。

接下来引入NP问题的概念。这个就有点难理解了，或者说容易理解错误。在这里强调（回到我竭力想澄清的误区上），NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。比方说，我RP很好，在程序中需要枚举时，我可以一猜一个准。现在某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图，但怎么也算不出来，于是来问我：你看怎么选条路走得最少？我说，我RP很好，肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线，说就这条吧。那人按我指的这条把权值加起来一看，嘿，神了，路径长度98，比100小。于是答案出来了，存在比100小的路径。别人会问他这题怎么做出来的，他就可以说，因为我找到了一个比100 小的解。在这个题中，找一个解很困难，但验证一个解很容易。验证一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的时间把我猜的路径的长度加出来。那么，只要我RP好，猜得准，我一定能在多项式的时间里解决这个问题。我猜到的方案总是最优的，不满足题意的方案也不会来骗我去选它。这就是NP问题。当然有不是NP问题的问题，即你猜到了解但是没用，因为你不能在多项式的时间里去验证它。

下面我要举的例子是一个经典的例子，它指出了一个目前还没有办法在多项式的时间里验证一个解的问题。很显然，前面所说的Hamilton回路是NP问题，因为验证一条路是否恰好经过了每一个顶点非常容易。但我要把问题换成这样：试问一个图中是否不存在Hamilton回路。这样问题就没法在多项式的时间里进行验证了，因为除非你试过所有的路，否则你不敢断定它“没有Hamilton回路”。

之所以要定义NP问题，是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。相信读者很快明白，信息学中的号称最困难的问题——“NP问题”，实际上是在探讨NP问题与P类问题的关系。

很显然，所有的P类问题都是NP问题。也就是说，能多项式地解决一个问题，必然能多项式地验证一个问题的解——既然正解都出来了，验证任意给定的解也只需要比较一下就可以了。关键是，人们想知道，是否所有的NP问题都是P类问题。我们可以再用集合的观点来说明。如果把所有P类问题归为一个集合P中，把所有 NP问题划进另一个集合NP中，那么，显然有P属于NP。现在，所有对NP问题的研究都集中在一个问题上，即究竟是否有P=NP？通常所谓的“NP问题”，其实就一句话：证明或推翻P=NP。

NP问题一直都是信息学的巅峰。巅峰，意即很引人注目但难以解决。在信息学研究中，这是一个耗费了很多时间和精力也没有解决的终极问题，好比物理学中的大统一和数学中的歌德巴赫猜想等。

目前为止这个问题还“啃不动”。但是，一个总的趋势、一个大方向是有的。人们普遍认为，P=NP不成立，也就是说，多数人相信，存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的，就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题，也即所谓的 NPC问题。C是英文单词“完全”的第一个字母。正是NPC问题的存在，使人们相信P≠NP。下文将花大量篇幅介绍NPC问题，你从中可以体会到NPC问题使P=NP变得多么不可思议。 为了说明NPC问题，我们先引入一个概念——约化(Reducibility，有的资料上叫“归约”)。

简单地说，一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。《算法导论》上举了这么一个例子。比如说，现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以约化为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题，那么我们能找到一个“规则”，按照这个规则把解一元一次方程程序的输入数据变一下，用在解一元二次方程的程序上，两个程序总能得到一样的结果。这个规则即是：两个方程的对应项系数不变，一元二次方程的二次项系数为0。按照这个规则把前一个问题转换成后一个问题，两个问题就等价了。同样地，我们可以说，Hamilton回路可以约化为TSP问题(Travelling Salesman Problem，旅行商问题)：在Hamilton回路问题中，两点相连即这两点距离为0，两点不直接相连则令其距离为1，于是问题转化为在TSP问题中，是否存在一条长为0的路径。Hamilton回路存在当且仅当TSP问题中存在长为0的回路。

“问题A可约化为问题B”有一个重要的直观意义：B的时间复杂度高于或者等于A的时间复杂度。也就是说，问题A不比问题B难。这很容易理解。既然问题A能用问题B来解决，倘若B的时间复杂度比A的时间复杂度还低了，那A的算法就可以改进为B的算法，两者的时间复杂度还是相同。正如解一元二次方程比解一元一次方程难，因为解决前者的方法可以用来解决后者。 很显然，约化具有一项重要的性质：约化具有传递性。如果问题A可约化为问题B，问题B可约化为问题C，则问题A一定可约化为问题C。这个道理非常简单，就不必阐述了。

现在再来说一下约化的标准概念就不难理解了：如果能找到这样一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同，那么我们说，问题A可约化为问题B。 当然，我们所说的“可约化”是指的可“多项式地”约化(Polynomial-time Reducible)，即变换输入的方法是能在多项式的时间里完成的。约化的过程只有用多项式的时间完成才有意义。 好了，从约化的定义中我们看到，一个问题约化为另一个问题，时间复杂度增加了，问题的应用范围也增大了。通过对某些问题的不断约化，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但只能用于很小的一类问题的算法。再回想前面讲的P和NP问题，联想起约化的传递性，自然地，我们会想问，如果不断地约化上去，不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题，那么最后是否有可能找到一个时间复杂度最高，并且能“通吃”所有的 NP问题的这样一个超级NP问题？答案居然是肯定的。也就是说，存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的NPC 问题，也就是NP-完全问题。NPC问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信，NPC问题是最复杂的问题。再次回到全文开头，我们可以看到，人们想表达一个问题不存在多项式的高效算法时应该说它“属于NPC问题”。此时，我的目的终于达到了，我已经把NP问题和NPC问题区别开了。到此为止，本文已经写了近5000字了，我佩服你还能看到这里来，同时也佩服一下自己能写到这里来。 NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。证明一个问题是 NPC问题也很简单。先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它（由约化的传递性，则NPC问题定义的第二条也得以满足；至于第一个NPC问题是怎么来的，下文将介绍），这样就可以说它是NPC问题了。 既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P 了。因此，给NPC找一个多项式算法太不可思议了。因此，前文才说，“正是NPC问题的存在，使人们相信P≠NP”。我们可以就此直观地理解，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。 顺便讲一下NP-Hard问题。NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广）。NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。 不要以为NPC问题是一纸空谈。NPC问题是存在的。确实有这么一个非常具体的问题属于NPC问题。下文即将介绍它。

下文即将介绍逻辑电路问题。这是第一个NPC问题。其它的NPC问题都是由这个问题约化而来的。因此，逻辑电路问题是NPC类问题的“鼻祖”。 逻辑电路问题是指的这样一个问题：给定一个逻辑电路，问是否存在一种输入使输出为True。 什么叫做逻辑电路呢？一个逻辑电路由若干个输入，一个输出，若干“逻辑门”和密密麻麻的线组成。看下面一例，不需要解释你马上就明白了。

这是个较简单的逻辑电路，当输入1、输入2、输入3分别为True、True、False或False、True、False时，输出为True。 有输出无论如何都不可能为True的逻辑电路吗？有。下面就是一个简单的例子。

上面这个逻辑电路中，无论输入是什么，输出都是False。我们就说，这个逻辑电路不存在使输出为True的一组输入。 回到上文，给定一个逻辑电路，问是否存在一种输入使输出为True，这即逻辑电路问题。 逻辑电路问题属于NPC问题。这是有严格证明的。它显然属于NP问题，并且可以直接证明所有的NP问题都可以约化到它（不要以为NP问题有无穷多个将给证明造成不可逾越的困难）。证明过程相当复杂，其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出（想想计算机内部也不过是一些 0和1的运算），因此对于一个NP问题来说，问题转化为了求出满足结果为True的一个输入（即一个可行解）。 有了第一个NPC问题后，一大堆NPC问题就出现了，因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来，Hamilton 回路成了NPC问题，TSP问题也成了NPC问题。现在被证明是NPC问题的有很多，任何一个找到了多项式算法的话所有的NP问题都可以完美解决了。因此说，正是因为NPC问题的存在，P=NP变得难以置信。P=NP问题还有许多有趣的东西，有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的终极目标。现在我们需要做的，至少是不要把概念弄混淆了。

Matrix67原创转载请注明出处

本人对Matrix67顶礼膜拜！！

很强，原来不懂，现在讲的是那么的透彻清晰！！

原帖地址：http://www.matrix67.com/blog/archives/105

留白

一周的留白～！




嘎嘎......只为一个人..........

奥运会项目

哈哈
以前06年在CCTV.COM上看到过
感觉不错
一直也没见到......
TOT...




今天贴出来喽
忽忽

素数与素性测试

今天做了一个素数测试的小程序：

然后想起Matrix67上关于素数的一篇文章，很好所以转载过来和大家分享～～！

我MS写不出来的！！～.～

囧~~~~

一个数是素数（也叫质数），当且仅当它的约数只有两个——1和它本身。规定这两个约数不能相同，因此1不是素数。对素数的研究属于数论范畴，你可以看到许多数学家没事就想出一些符合某种性质的素数并称它为某某某素数。整个数论几乎就围绕着整除和素数之类的词转过去转过来。对于写代码的人来说，素数比想像中的更重要，Google一下BigPrime或者big_prime你总会发现大堆大堆用到了素数常量的程序代码。平时没事时可以记一些素数下来以备急用。我会选一些好记的素数，比如4567, 124567, 3214567, 23456789, 55566677, 1234567894987654321, 11111111111111111111111 (23个1)。我的手机号前10位是个素数。我的网站域名的ASCII码连起来(77 97 116 114 105 120 54 55 46 99 111 109)也是个素数。还有，我的某个MM的八位生日也是一个素数。每次写Hash函数之类的东西需要一个BigPrime常量时我就取她的生日，希望她能给我带来好运。偶尔我叫她素MM，没人知道是啥意思，她自己也不知道。 素数有很多神奇的性质。我写5个在下面供大家欣赏。

素数有很多神奇的性质。我写5个在下面供大家欣赏。

1. 素数的个数无限多（不存在最大的素数）


证明：反证法，假设存在最大的素数P，那么我们可以构造一个新的数2 * 3 * 5 * 7 * ... * P + 1（所有的素数乘起来加1）。显然这个数不能被任一素数整除（所有素数除它都余1），这说明我们找到了一个更大的素数

2. 存在任意长的一段连续数，其中的所有数都是合数（相邻素数之间的间隔任意大）

证明：当0< a <=n时，n!+a能被a整除。长度为n-1的数列n!+2,>

3. 所有大于2的素数都可以唯一地表示成两个平方数之差。


证明：大于2的素数都是奇数。假设这个数是2n+1。由于(n+1)^2=n^2+2n+1，(n+1)^2和n^2就是我们要找的两个平方数。下面证明这个方案是唯一的。如果素数p能表示成a^2-b^2，则p=a^2-b^2=(a+b)(a-b)。由于p是素数，那么只可能a+b=p且a-b=1，这给出了a和b的唯一解。

4. 当n为大于2的整数时，2^n+1和2^n-1两个数中，如果其中一个数是素数，那么另一个数一定是合数。

证明：2^n不能被3整除。如果它被3除余1，那么2^n-1就能被3整除；如果被3除余2，那么2^n+1就能被3整除。总之，2^n+1和2^n-1中至少有一个是合数。

5. 如果p是素数，a是小于p的正整数，那么a^(p-1) mod p = 1。

这个证明就有点麻烦了。 首先我们证明这样一个结论：如果p是一个素数的话，那么对任意一个小于p的正整数a，a, 2a, 3a, ..., (p-1)a除以p的余数正好是一个1到p-1的排列。例如，5是素数，3, 6, 9, 12除以5的余数分别为3, 1, 4, 2，正好就是1到4这四个数。 反证法，假如结论不成立的话，那么就是说有两个小于p的正整数m和n使得na和ma除以p的余数相同。不妨假设n>m，则p可以整除a(n-m)。但p是素数，那么a和n-m中至少有一个含有因子p。这显然是不可能的，因为a和n-m都比p小。 用同余式表述，我们证明了：(p-1)! ≡ a * 2a * 3a * ... * (p-1)a (mod p) 也即：(p-1)! ≡ (p-1)! * a^(p-1) (mod p) 两边同时除以(p-1)!，就得到了我们的最终结论：1 ≡ a^(p-1) (mod p)

可惜最后这个定理最初不是我证明的。这是大数学家Fermat证明的，叫做Fermat小定理(Fermat's Little Theorem)。Euler对这个定理进行了推广，叫做Euler定理。Euler一生的定理太多了，为了和其它的“Euler定理”区别开来，有些地方叫做Fermat小定理的Euler推广。Euler定理中需要用一个函数f(m)，它表示小于m的正整数中有多少个数和m互素（两个数只有公约数1称为互素）。为了方便，我们通常用记号φ(m)来表示这个函数（称作Euler函数）。Euler指出，如果a和m互素，那么a^φ(m) ≡ 1 (mod m)。可以看到，当m为素数时，φ(m)就等于m-1（所有小于m的正整数都与m互素），因此它是Fermat小定理的推广。定理的证明和Fermat小定理几乎相同，只是要考虑的式子变成了所有与m互素的数的乘积：m_1 * m_2 ... m_φ(m) ≡ (a * m_1)(a * m_2) ... (a * m_φ(m)) (mod m)。我为什么要顺便说一下Euler定理呢？因为下面一句话可以增加我网站的PV：这个定理出现在了The Hundred Greatest Theorems里。

谈到Fermat小定理，数学历史上有很多误解。很长一段时间里，人们都认为Fermat小定理的逆命题是正确的，并且有人亲自验证了a=2, p<300的所有情况。国外甚至流传着一种说法，认为中国在孔子时代就证明了这样的定理：如果n整除2^(n-1)-1，则n就是素数。后来某个英国学者进行考证后才发现那是因为他们翻译中国古文时出了错。1819年有人发现了fermat小定理逆命题的第一个反例：虽然2的340次方除以341余1，但341=11*31。后来，人们又发现了561, a="2时Fermat小定理的逆命题不成立。虽然这样的数不多，但不能忽视它们的存在。于是，人们把所有能整除2^(n-1)-1的合数n叫做伪素数(pseudoprime)，意思就是告诉人们这个素数是假的。

不满足2^(n-1) mod n = 1的n一定不是素数；如果满足的话则多半是素数。这样，一个比试除法效率更高的素性判断方法出现了：制作一张伪素数表，记录某个范围内的所有伪素数，那么所有满足2^(n-1) mod n = 1且不在伪素数表中的n就是素数。之所以这种方法更快，是因为我们可以使用二分法快速计算2^(n-1) mod n 的值，这在计算机的帮助下变得非常容易；在计算机中也可以用二分查找有序数列、Hash表开散列、构建Trie树等方法使得查找伪素数表效率更高。

有人自然会关心这样一个问题：伪素数的个数到底有多少？换句话说，如果我只计算2^(n-1) mod n的值，事先不准备伪素数表，那么素性判断出错的概率有多少？研究这个问题是很有价值的，毕竟我们是OIer，不可能背一个长度上千的常量数组带上考场。统计表明，在前10亿个自然数中共有50847534个素数，而满足2^(n-1) mod n = 1的合数n有5597个。这样算下来，算法出错的可能性约为0.00011。这个概率太高了，如果想免去建立伪素数表的工作，我们需要改进素性判断的算法。

最简单的想法就是，我们刚才只考虑了a=2的情况。对于式子a^(n-1) mod n，取不同的a可能导致不同的结果。一个合数可能在a=2时通过了测试，但a=3时的计算结果却排除了素数的可能。于是，人们扩展了伪素数的定义，称满足a^(n-1) mod n = 1的合数n叫做以a为底的伪素数(pseudoprime to base a)。前10亿个自然数中同时以2和3为底的伪素数只有1272个，这个数目不到刚才的1/4。这告诉我们如果同时验证a=2和a=3两种情况，算法出错的概率降到了0.000025。容易想到，选择用来测试的a越多，算法越准确。通常我们的做法是，随机选择若干个小于待测数的正整数作为底数a进行若干次测试，只要有一次没有通过测试就立即把这个数扔回合数的世界。这就是Fermat素性测试。

人们自然会想，如果考虑了所有小于n的底数a，出错的概率是否就可以降到0呢？没想到的是，居然就有这样的合数，它可以通过所有a的测试（这个说法不准确，详见我在地核楼层的回复）。Carmichael第一个发现这样极端的伪素数，他把它们称作Carmichael数。你一定会以为这样的数一定很大。错。第一个Carmichael数小得惊人，仅仅是一个三位数，561。前10亿个自然数中Carmichael数也有600个之多。Carmichael数的存在说明，我们还需要继续加强素性判断的算法。

Miller和Rabin两个人的工作让Fermat素性测试迈出了革命性的一步，建立了传说中的Miller-Rabin素性测试算法。新的测试基于下面的定理：如果p是素数，x是小于p的正整数，且x^2 mod p = 1，那么要么x=1，要么x=p-1。这是显然的，因为x^2 mod p = 1相当于p能整除x^2-1，也即p能整除(x+1)(x-1)。由于p是素数，那么只可能是x-1能被p整除(此时x=1)或x+1能被p整除(此时x=p-1)。

我们下面来演示一下上面的定理如何应用在Fermat素性测试上。前面说过341可以通过以2为底的Fermat测试，因为2^340 mod 341=1。如果341真是素数的话，那么2^170 mod 341只可能是1或340；当算得2^170 mod 341确实等于1时，我们可以继续查看2^85除以341的结果。我们发现，2^85 mod 341=32，这一结果摘掉了341头上的素数皇冠，面具后面真实的嘴脸显现了出来，想假扮素数和我的素MM交往的企图暴露了出来。

这就是Miller-Rabin素性测试的方法。不断地提取指数n-1中的因子2，把n-1表示成d*2^r（其中d是一个奇数）。那么我们需要计算的东西就变成了a的d*2^r次方除以n的余数。于是，a^(d * 2^(r-1))要么等于1，要么等于n-1。如果a^(d * 2^(r-1))等于1，定理继续适用于a^(d * 2^(r-2))，这样不断开方开下去，直到对于某个i满足a^(d * 2^i) mod n = n-1或者最后指数中的2用完了得到的a^d mod n=1或n-1。这样，Fermat小定理加强为如下形式：

尽可能提取因子2，把n-1表示成d*2^r，如果n是一个素数，那么或者a^d mod n=1，或者存在某个i使得a^(d*2^i) mod n=n-1 ( 0<=i

Miller-Rabin素性测试同样是不确定算法，我们把可以通过以a为底的Miller-Rabin测试的合数称作以a为底的强伪素数(strong pseudoprime)。第一个以2为底的强伪素数为2047。第一个以2和3为底的强伪素数则大到1 373 653。

Miller-Rabin算法的代码也非常简单：计算d和r的值（可以用位运算加速），然后二分计算a^d mod n的值，最后把它平方r次。程序的代码比想像中的更简单，我写一份放在下边。虽然我已经转C了，但我相信还有很多人看不懂C语言。我再写一次Pascal吧。函数IsPrime返回对于特定的底数a，n是否是能通过测试。如果函数返回False，那说明n不是素数；如果函数返回True，那么n极有可能是素数。

注意这个代码的数据范围限制在longint，你很可能需要把它们改成int64或高精度计算。

对于大数的素性判断，目前Miller-Rabin算法应用最广泛。一般底数仍然是随机选取，但当待测数不太大时，选择测试底数就有一些技巧了。比如，如果被测数小于4 759 123 141，那么只需要测试三个底数2, 7和61就足够了。当然，你测试的越多，正确的范围肯定也越大。如果你每次都用前7个素数(2, 3, 5, 7, 11, 13和17)进行测试，所有不超过341 550 071 728 320的数都是正确的。如果选用2, 3, 7, 61和24251作为底数，那么10^16内唯一的强伪素数为46 856 248 255 981。这样的一些结论使得Miller-Rabin算法在OI中非常实用。通常认为，Miller-Rabin素性测试的正确率可以令人接受，随机选取k个底数进行测试算法的失误率大概为4^(-k)。

Miller-Rabin算法是一个RP算法。RP是时间复杂度的一种，主要针对判定性问题。一个算法是RP算法表明它可以在多项式的时间里完成，对于答案为否定的情形能够准确做出判断，但同时它也有可能把对的判成错的（错误概率不能超过1/2）。RP算法是基于随机化的，因此多次运行该算法可以降低错误率。还有其它的素性测试算法也是概率型的，比如Solovay-Strassen算法。另外一些素性测试算法则需要预先知道一些辅助信息（比如n-1的质因子），或者需要待测数满足一些条件（比如待测数必须是2^n-1的形式）。前几年AKS算法轰动世界，它是第一个多项式的、确定的、无需其它条件的素性判断算法。当时一篇论文发表出来，题目就叫PRIMES is in P，然后整个世界都疯了，我们班有几个MM那天还来了初潮。算法主要基于下面的事实：n是一个素数当且仅当(x-a)^n≡(x^n-a) (mod n)。注意这个x是多项式中的未知数，等式两边各是一个多项式。举个例子来说，当a=1时命题等价于如下结论：当n是素数时，杨辉三角的第n+1行除两头的1以外其它的数都能被n整除。

Matrix67原创转贴请注明出处

原帖地址：http://www.matrix67.com/blog/archives/234

08奥运开幕

今天看开奥运开幕式还有一些坡折，

先在机房里，网速慢的实在是受不了！郁闷，以前怎么会那么快？

还光纤来，郁闷，老师急了说：“走到保卫科看电视去”，于是我跟着就去了！

到地方一看，人还真不少，里一层，外一层！

我站在最外层，看了一会，感觉挺壮观的，但是人太多！

于是我又回到机房，总共5个人去了3个，还有2个人在机房！

胖子在看他那不知道什么的小说！



我先看了一会，然后在老师那看QQ直播！~

总算还可以，至少不卡了，我一个人在前面看........

后来就郁闷了————》入场！

.........

囧~~~~

最后象征性的：
中国加油，奥运加油！

七夕&&RP<-∞

今天，我RP 已降到极限~~~~~~~~~
...........................................................................
......................................
.................
.........
.....
.
..........................................................................
..................
..................................
...........................

早上起来，很想吐~~
但是又吐不出来，走到一家超市买了一大瓶水............
喝一口，吐出来，喝一口，吐出来.............
一直吐到学校，路上很多人用异样的眼光看者我，但我却没有任何感觉~~~~~~......
到学校5：30。。。。。。。。。
没开门，转了三圈，找到一同学.......拿到钥匙！~~~
又转了两圈6：00了开门了，我进来.............
纪录下来我有史以来RP最底的时刻....
-----------------------------------------------------------------------


今天七夕~~...............
当然RP低到这个地步七夕是一个原因 ，但是主要的不是这个原因~！





吼啊！~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
RP<-∞

RP开始减减

今天晚上7：00接到鹏坡的电话。。。

请假

.........


我：“老师，我同学叫我请他吃饭，要不讲课我先走了。”....
老师：“讲，怎么不讲？？！............你那同学的事可重要？？”.
我：“............”
老师：“那你去吧，别喝酒啊！喝醉了别打架！打架时有事给我打电话！”
我：“好！..........我走了”


......................



在广场坐了一会，然后到她家............


.................................................



............................





RP---------------------------------

seastar

今天更换了我的MSN:xuzhenhe@msn.com

取名：海星~~~~~~！

....

NOI2008

今年的NOI试题

“AMD”杯


第二十五届全国信息学奥林匹克竞赛



NOI 2008


第一试


浙江绍兴
第 25届全国信息学奥林匹克竞赛第一试假面舞会 party

假面舞会


【问题描述】

一年一度的假面舞会又开始了，栋栋也兴致勃勃的参加了今年的舞会。

今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择
一个自己喜欢的面具。每个面具都有一个编号，主办方会把此编号告诉拿该面具
的人。

为了使舞会更有神秘感，主办方把面具分为 k (k≥3)类，并使用特殊的技术将
每个面具的编号标在了面具上，只有戴第 i类面具的人才能看到戴第 i+1类面具
的人的编号，戴第 k类面具的人能看到戴第 1类面具的人的编号。

参加舞会的人并不知道有多少类面具，但是栋栋对此却特别好奇，他想自己
算出有多少类面具，于是他开始在人群中收集信息。

栋栋收集的信息都是戴第几号面具的人看到了第几号面具的编号。如戴第 2
号面具的人看到了第 5号面具的编号。栋栋自己也会看到一些编号，他也会根据
自己的面具编号把信息补充进去。

由于并不是每个人都能记住自己所看到的全部编号，因此，栋栋收集的信息
不能保证其完整性。现在请你计算，按照栋栋目前得到的信息，至多和至少有多
少类面具。由于主办方已经声明了 k≥3，所以你必须将这条信息也考虑进去。

【输入格式】

输入文件 party.in第一行包含两个整数 n, m，用一个空格分隔，n表示主办
方总共准备了多少个面具，m表示栋栋收集了多少条信息。

接下来 m行，每行为两个用空格分开的整数 a, b，表示戴第 a号面具的人看
到了第 b号面具的编号。相同的数对 a, b在输入文件中可能出现多次。

【输出格式】

输出文件 party.out包含两个数，第一个数为最大可能的面具类数，第二个数
为最小可能的面具类数。如果无法将所有的面具分为至少 3类，使得这些信息都
满足，则认为栋栋收集的信息有错误，输出两个-1。

【输入样例一】


6 5
1 2
2 3
3 4
4 1
3 5


【输出样例一】


4 4

【输入样例二】


3 3
1 2
2 1
2 3


【输出样例二】


-1 -1

【数据规模和约定】


50%的数据，满足 n ≤ 300, m ≤ 1000；
100%的数据，满足 n ≤ 100000, m ≤ 1000000。


“AMD”杯


浙江绍兴
第 25届全国信息学奥林匹克竞赛第一试设计路线 design

设计路线


【问题描述】

Z国坐落于遥远而又神奇的东方半岛上，在小 Z的统治时代公路成为这里主
要的交通手段。Z国共有 n座城市，一些城市之间由双向的公路所连接。非常神
奇的是 Z国的每个城市所处的经度都不相同，并且最多只和一个位于它东边的
城市直接通过公路相连。Z国的首都是 Z国政治经济文化旅游的中心，每天都有
成千上万的人从 Z国的其他城市涌向首都。

为了使 Z国的交通更加便利顺畅，小 Z决定在 Z国的公路系统中确定若干条
规划路线，将其中的公路全部改建为铁路。

我们定义每条规划路线为一个长度大于 1的城市序列，每个城市在该序列中
最多出现一次，序列中相邻的城市之间由公路直接相连(待改建为铁路)。并且，
每个城市最多只能出现在一条规划路线中，也就是说，任意两条规划路线不能有
公共部分。

当然在一般情况下是不可能将所有的公路修建为铁路的，因此从有些城市出
发去往首都依然需要通过乘坐长途汽车，而长途汽车只往返于公路连接的相邻的
城市之间，因此从某个城市出发可能需要不断地换乘长途汽车和火车才能到达首
都。

我们定义一个城市的“不便利值”为从它出发到首都需要乘坐的长途汽车的
次数，而 Z国的交通系统的“不便利值”为所有城市的不便利值的最大值，很明
显首都的“不便利值”为 0。小 Z想知道如何确定规划路线修建铁路使得 Z国的
交通系统的“不便利值”最小，以及有多少种不同的规划路线的选择方案使得“不
便利值”达到最小。当然方案总数可能非常大，小 Z只关心这个天文数字 mod Q
后的值。

注意：规划路线 1-2-3和规划路线 3-2-1是等价的，即将一条规划路线翻转
依然认为是等价的。两个方案不同当且仅当其中一个方案中存在一条规划路线不
属于另一个方案。

【输入格式】

输入文件 design.in第一行包含三个正整数 N、M、Q，其中 N表示城市个数，
M表示公路总数，N个城市从 1~N编号，其中编号为 1的是首都。Q表示上文
提到的设计路线的方法总数的模数。接下来 M行，每行两个不同的正数 ai、bi (1≤
ai , bi ≤
N)表示有一条公路连接城市 ai和城市 bi。输入数据保证一条公路只出现
一次。

【输出格式】

输出文件 design.out应包含两行。第一行为一个整数，表示最小的“不便利
值”。第二行为一个整数，表示使“不便利值”达到最小时不同的设计路线的方
法总数 mod Q的值。
如果某个城市无法到达首都，则输出两行-1。

【输入样例】


5 4 100
1 2
4 5
1 3
4 1

【输出样例】


1
10

【样例说明】

以下样例中是 10种设计路线的方法：

(1) 4-5
(2) 1-4-5
(3) 4-5, 1-2
(4) 4-5, 1-3
(5) 4-5, 2-1-3
(6) 2-1-4-5
(7) 3-1-4-5
(8) 1-4
(9) 2-1-4
(10) 3-1-4

【数据规模和约定】

对于 20%的数据，满足 N,M ≤ 10。
对于 50%的数据，满足 N,M ≤ 200。
对于 60%的数据，满足 N,M ≤ 5000。
对于 100%的数据，满足 1 ≤
N,M ≤ 100000，1 ≤
Q ≤ 120000000。

【评分方式】

每个测试点单独评分。对于每个测试点，第一行错则该测试点得零分，否则
若第二行错则该测试点得到 40%的分数。如果两问都答对，该测试点得到 100%
的分数。


“AMD”杯


浙江绍兴
第 25届全国信息学奥林匹克竞赛第一试志愿者招募 employee

志愿者招募


【问题描述】

申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的
主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志
愿者。经过估算，这个项目需要 N天才能完成，其中第 i天至少需要 Ai个人。
布布通过了解得知，一共有 M类志愿者可以招募。其中第 i类可以从第 Si天工
作到第 Ti天，招募费用是每人 Ci元。新官上任三把火，为了出色地完成自己的
工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是
布布找到了你，希望你帮他设计一种最优的招募方案。

【输入格式】

输入文件 employee.in的第一行包含两个整数 N, M，表示完成项目的天数和

可以招募的志愿者的种类。
接下来的一行中包含 N个非负整数，表示每天至少需要的志愿者人数。
接下来的 M行中每行包含三个整数 Si, Ti, Ci，含义如上文所述。为了方便起

见，我们可以认为每类志愿者的数量都是无限多的。

【输出格式】

输入文件 employee.out中仅包含一个整数，表示你所设计的最优方案的总费
用。

【输入样例】

3 3
2 3 4
1 2 2
2 3 5
3 3 2


【输出样例】

14


【样例说明】

招募 3名第一类志愿者和 4名第三类志愿者。

【数据规模和约定】

30%的数据中，1 ≤
N, M ≤ 10，1 ≤
Ai ≤ 10；

100%的数据中，1 ≤
N ≤ 1000，1 ≤
M ≤ 10000，题目中其他所涉及的数据均
不超过 231-1。


NOI 2008


第二试


竞赛时间：2008年7月31日上午 8:00-13:00

题目名称奥运物流糖果雨赛程安排
目录 trans candy match
可执行文件名 trans candy match
输入文件名 trans.in candy.in match1.in~match10.in
输出文件名 trans.out candy.out match1.out~match10.out
每个测试点时限
1s 2s N/A
内存限制
128M 128M N/A
测试点数目
10 10 10
每个测试点分值
10 10 10
是否有部分分无无有
题目类型传统传统提交答案

提交源程序须加后缀

对于
Pascal语言 trans.pas candy.pas N/A
对于
C 语言 trans.c candy.c N/A
对于
C++ 语言 trans.cpp candy.cpp N/A

注意：最终测试时，所有编译命令均不打开任何优化开关


“AMD”杯


浙江绍兴
第 25届全国信息学奥林匹克竞赛第二试奥运物流 trans

奥运物流


【问题描述】

2008北京奥运会即将开幕，举国上下都在为这一盛事做好准备。为了高效率、
成功地举办奥运会，对物流系统进行规划是必不可少的。

物流系统由若干物流基站组成，以 1…N进行编号。每个物流基站 i都有且
仅有一个后继基站 Si，而可以有多个前驱基站。基站 i中需要继续运输的物资都
将被运往后继基站 Si，显然一个物流基站的后继基站不能是其本身。编号为 1的
物流基站称为控制基站，从任何物流基站都可将物资运往控制基站。注意控制基
站也有后继基站，以便在需要时进行物资的流通。在物流系统中，高可靠性与低

成本是主要设计目。对于基站 i，我们定义其“可靠性”R()i如下：

设物流基站 i有 w个前驱基站PP1,,..P，

2w 即这些基站以 i为后继基站，则基

站 i的可靠性 R(i)满足下式：

R()i=
Ck (

i+Σ(w) RP j)

j=1

其中 Ci和 k都是常实数且恒为正，且有 k小于 1。

整个系统的可靠性与控制基站的可靠性正相关，我们的目标是通过修改物流
系统，即更改某些基站的后继基站，使得控制基站的可靠性 R(1)尽量大。但由于
经费限制，最多只能修改 m个基站的后继基站，并且，控制基站的后继基站不
可被修改。因而我们所面临的问题就是，如何修改不超过 m个基站的后继，使
得控制基站的可靠性 R(1)最大化。

【输入格式】

输入文件 trans.in第一行包含两个整数与一个实数，N, m, k。其中 N表示基
站数目，m表示最多可修改的后继基站数目，k分别为可靠性定义中的常数。

第二行包含 N个整数，分别是 S1, S2…SN，即每一个基站的后继基站编号。

第三行包含 N个正实数，分别是 C1, C2…CN，为可靠性定义中的常数。

【输出格式】

输出文件 trans.out仅包含一个实数，为可得到的最大 R(1)。精确到小数点两
位。

【输入样例】


4 1 0.5
2 3 1 3
10.0 10.0 10.0 10.0
【输出样例】


30.00

【样例说明】

原有物流系统如左图所示，4个物流基站的可靠性依次为 22.8571，21.4286，

25.7143，10。
最优方案为将 2号基站的后继基站改为 1号，如右图所示。此时 4个基站
的可靠性依次为 30，25，15，10。

【数据规模和约定】

本题的数据，具有如下分布：

测试数据编号 N M
1 ≤ 6 ≤ 6
2 ≤ 12 ≤ 12
3 ≤ 60 0
4 ≤ 60 1
5 ≤ 60 N-2
6~10 ≤ 60 ≤ 60

对于所有的数据，满足 m ≤
N ≤ 60，Ci ≤ 106，0.3 ≤
k < k =" 1，2，3）分别表示事件的类型，分别对应三种事件：插入事件，" di =" -1)或向右(Di" di =" -1或" pi =" Ri" n =" 2k)个同学报名参加，因此第一轮后就会有" n="8时比赛的赛程表" a="1)。于是小" 2k =" n。" i =" 0.00。" p1="1-0.8="0.2," p2="0.8-0.528="0.272," p3="0.528。" 3 =" 2.328。"> our_ans，得 12分。

如果 your_ans < our_ans*d，得 1分。

否则得分为：

.
your _ ans .
our _ ans *d .

*8 +
2

..

.
our _ ans .
our _ ans *d .

【提示】

“数学期望”

数学期望是随机变量最基本的数字特征之一。它反映随机变量平均取值的大
小，又称期望或均值。它是简单算术平均的一种推广。例如某城市有 10万个家
庭，没有孩子的家庭有 1000 个，有一个孩子的家庭有 9万个，有两个孩子的家
庭有 6000个，有 3个孩子的家庭有 3000个，则该城市中任一个家庭中孩子的数
目是一个随机变量，它可取值 0，1，2，3，其中取 0的概率为 0.01，取 1的概
率为 0.9，取 2的概率为 0.06，取 3的概率为 0.03，它的数学期望为 0×0.01＋1×0.9

＋2×0.06＋3×0.03等于 1.11，即此城市一个家庭平均有小孩 1.11个。
本题中期望值的计算：假设小 Z在第一轮被打败的概率为 P1，第一轮胜利且
在第二轮被打败的概率为 P2, 前两轮胜利且在第三轮被打败的概率为 P3……，
那么小 Z的期望奖金为：

P1 * a1 + P2 * a2 + …+ Pk+1 * ak+1

【特别提示】

请妥善保存输入文件*.in和你的输出*.out，及时备份，以免误删。

今天昏昏的爬格子，然后接到一电话

今天，学校里依然放着那首歌（DYCADR）。

心情不太好。。。。

没心情做题目！

从早晨开始一直做在P前爬啊爬（进度条），看着看着，今天一天就这样看过了80%。。。

没劲.........

ORZ....

看者别人的BLOG虽然在不停的换，但是不知道上面写的什么。。。。

郁闷..

到了晚上8：45的时侯，我接到一个电话，我听见那收悉的声音........

本能的说：你在那？

而对方说让我过去。。。。。。

呵呵

然后就直接给老师请假过去....~~~~：（（

还算有点收获：至少，她明白了我要表达的意思........

...................

在广场，我们坐到11：30.....

话不多但是我很开心，因为我没有躲避着她~~~

这样我就对自己很满意了！

期间，她说了一些很感人的话。。。

可是我不知道怎么回答她······

或许是不愿意说罢了！

哎~~！

都过去了..

再说也没意思了....

记得一同学说：感情不必拿来感慨！

...............

其实我想对她说的话一直都没说：

...................................................................................

虽然我们在一起不可能了，但我很感谢你，

感谢你以前对我的好，还有不好。

我不知道你怎么想，但是都无所谓 .........

：））
期间她也说过一些话，虽然我很感动，
但是我却不知道怎么回答她。。。...................................
到家里已经很晚了（12：00）
，，，，，，，
哥还没睡，
我进到屋里说：“哥，我回来了！”，
但是我看到他的表情..............（讥笑，嘲讽），我彻底无语！
说了句我睡觉了就走了~~~~~~~~~~~~~~~~~~~~~~
`0..........................

没有RP

所谓RP，就是人品吧。（至少我是这样理解的）。。。

很郁闷，估计.......不对啊，我又没有犯错误啊！

今天放假第一天，我昨天叫晋福今天来找我，一起出去玩。

后来我们来到我学校机房！

由于昨天放假前我最喜欢的一台P坏掉了！（伤心啊。。。搞笑，讲一下配置:

搞笑吧！我都受不了了！

天天我就对着这样的P！！

：（

:-)

今天我们到学校来后老师来了！

前面说了几句话，我都没什么！

可是.....后来。。。

他说：以后不要再带人来了！

我同学：日，当我不存在！草............

我心里说：好！怎么一点面子都不给我留！

昏倒

.........

郁闷a

！

今天下午，我没有带人来，可是又遇到好久没有见过的表弟。。。。。。。。。。。

昏倒............

就在这时..

老师又来了！

昏死..............】

今天高一的报名~~~~

学校有了一点变化：N年不管放一次流行歌曲，这两天 天天放！还有以后下课不用铃声了，用广播！没劲外面的学校早就有了！

日，竟然放《第一次爱的人》 ，难受！

草。。没有一点RP——》说我自己。。。。。

不写了！！！！！！！！！！

...............

放假了

今天~~~~
放假了！
因为奥运会！
忽忽...........放到25号！高兴，好久没有放过那么长的假期了！
习习！这两天都糊涂了！为了弄一个网站~~！
丝丝还没有弄好！
我想只有等到高三毕业了！哎.......
到时候一定好好弄一个！
今天遇到一个小女生，丝丝16岁比我小一岁！她的网站弄的都比我的强！郁闷！
我一定要加油努力！好好学着做网站！！！
今天放假，我想也没什么时间去玩的！
没意思~~~！
还得学习，高三了吗！！
我想看看奥运会也没有什么可以弄的了！
:((
忽忽......
Orz.........