Random用法 pascal.doc

Random导论 前言——为什么要写此导论 在近几次的模拟赛中，笔者深感学艺不精，能力有限。但是测试数据是有限的，人品的力量是无穷的（有可能是maxlongint,也有可能是maxlongint+1），在模拟赛最后的十几分钟怎甘心坐以待毙？朴素？再朴素这几分钟也写不好吧？就算写完了，能过的点也是极其有限的。与其过那有限的一两个点，不如拼一下自己的RP。随机生成一个答案去赌一下。(类花哥者慎用！否则后果自负！！！)谨以此篇导论献给所有爆过0的OIer。 准备——积攒RP值 关于RP的理论随着信息竞赛的发展已经日趋完善，就不必我在这里多费口舌。详细资料百度一下，你就知道。（推荐：《RP导论》） 要谨记：为人要老实、做好事不要有太强的目的性、有义务性劳动主动参加、捡到东西要上交、在Dota中不要虐队友或电脑、一天感觉太顺是打开扫雷调成高级尝试连点99下不触雷……（额，看到有臭鸡蛋和烂菜叶飞过来了……） 代码——random的基础 笔者是学Pascal的，能力有限，只能提供Pascal的代码了。用C/C++的朋友委屈了，网上自己查一下吧。百度一下，你就知道。 首先，在主程序开头（或在调用的过程里）打上”randomize;”。 这个叫做“埋种子”，相当于系统的初始化，否则你怎么random都是一个数。然后呢，“ans:=random(n)”，ans是你要的答案，random是pascal自带的随机数函数，n是一个参数，是random出来的数的上界（下界是0，包括两端点）。注意n为整形数，random产生的也是整形数。 program ran(input,output); var i,j,n:Longint; begin randomize; n:=10; for i:=1 to 10 do begin j:=random(n); write(j, ); end; end. 大概就是这么个用法。 技巧——实战应用 适合用random题目大家也许都猜得到，就是那些答案输出简单（一个整数、yes或no）；下面看一道真题。 【Description】 题目描述尧尧又饿了，所以决定在家中觅食…… 尧尧的家是一个有N个房间的洞穴（问:为什么是洞穴……答:房价太贵……），由M条双向道路连接着它们，每对房间之间至多有一条道路，这其中有K个房间里存储着一盘生炒鸡，尧尧每吃一盘生炒鸡，体积增加1。 尧尧从他的房间里出发（房间编号为1），他当然希望吃得越多越好，可悲的是，尧尧的家长为了限制他的体重，把每条通道都进行了相应的改造，改造后的通道会有一个体积限制，如果体积严格大于通道的限制，可怜的尧尧会被卡住（卡卡卡卡卡……） 尧尧从他的房间里出发（他的房间里可能也有食物），经过一圈觅食过后（一条通道可以无限次走，只要不被卡住……）再回到他的房间，现在尧尧想知道他最多能吃多少盘生炒鸡得嘞？（话说，尧尧你爱吃生炒鸡么……） 【Input】输入格式 第一行输入N，M，K，之后的K行每行一个数字，代表该洞穴中有生炒鸡，之后的M行每行三个整数，代表双向通道的起点和终点和体积限制 【Output】输出格式 一个数，代表尧尧最多吃到生炒鸡的盘数【样例】 Inputhunger.in 6 7 5 1 2 3 4 5 1 2 3 3 6 2 6 2 10 2 4 1 5 1 1 4 5 1 1 6 1 Outputhunger.out 4 样例说明 其中一种觅食顺序为：4-3-2-1 【数据规模】 1 =N=100 1 = M = 1000 1 = K = 14readln(n,m,k); for i:=1 to k do readln(fry[i]); for i:=1 to m do begin readln(a,b,t); if t=1 then for j:=1 to k do if fry[j]=b then min:=1; end; for i:=1 to k do if fry[i]=1 then begin inc(min); break; end; ans:=random(k); while (ans=k) or (ansmin) do ans:=random(k); writeln(ans); 结果如下： 发现我对random做的优化了吗？必须要确定一个上界和一个下界，否则在茫茫数海中random一个正确答案耗费的RP值可能远远不止maxlongint De。 看另一实例： TSOI排队 TSOI2010的成员在伟大的教练XH的带领下排成了一条直队。 显然，不同的童鞋们身高不一定相同…… 现在，XH想知道，如果找出一些连续的童鞋