3模拟策略课件

1、模拟法,在自然界和日常生活中，许多现象具有不确定的性质，有些问题甚至很难建立数学模型，或者很难用计算机建立递推、递归、枚举、回溯法等算法。在这种情况下，一般采用模拟策略。所谓模拟策略就是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。,模拟形式,随机模拟 题目给定或者隐含某一概率。设计者利用随机函数和取整函数设定某一范围的随机值，将符合概率的随机值作为参数。然后根据这一模拟的数学模型展开算法设计。由于解题过程借助了计算机的伪随机数发生数，其随机的意义要比实际问题中真实的随机变量稍差一些，因此模拟效果有不确定的因素； 过程模拟 题目不给出概率

2、，要求编程者按照题意设计数学模型的各种参数，观察变更这些参数所引起过程状态的变化，由此展开算法设计。模拟效果完全取决于过程模拟的真实性和算法的正确性，不含任何不确定因素。由于过程模拟的结果无二义性，因此竞赛大都采用过程模拟。,模拟法的类型,直叙式模拟,筛选法模拟,构造法模拟,直叙式模拟,直叙式模拟即按照试题要求展开模拟过程。编程者要忠实于原题，认真审题，千万不要疏漏任何条件，精心设计方便模拟的数据结构。“直叙式模拟”的难度取决于模拟对象所包含的动态变化的属性有多少，动态属性愈多，则难度愈大。,花生采摘,鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴

3、着一张小小的纸条：“欢迎免费品尝我种的花生！熊字”。 鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”,我们假定多多在每个单位时间内，可以做下列四件事情中的一件： 1)从路边跳到最靠近路边（即第一行）的某棵花生植株； 2)从一棵植株跳到前后左右与之相邻的另一棵植株； 3)采摘一棵植株下的花生

4、； 4)从最靠近路边（即第一行）的某棵花生植株跳回路边。 现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。 例如在图2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为13, 7, 15, 9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。 【输入文件】输入文件peanuts.in的第一行包括三个整数，M, N和K，用空格隔开；表示花生田的大小为M * N（1M, N20），多多采花生的限定时间为K（0K1000

5、）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i + 1行的第j个整数Pij（0Pij 500）表示花生田里植株(i, j)下花生的数目，0表示该植株下没有花生。 【输出文件】输出文件peanuts.out包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。,解法1:直译模拟,每次在二维数组中找到当前最大值的位置 若最大值为零，则由当前位置直接返回路边；否则判断走至最大值位置后再返回路边的时间是否来得及： 如果来得及，则移动到最大值位置，把该位置的花生数置为零，累加已用时间； 如果来不及，就由当前位置直接返回路边。,设 var t,m,n,k,max

6、,i,j,max1i,max1j,maxi,maxj,total:integer; 多多目前的行程为t；花生田的规模为m*n；多多采花生的限定时间为k ；最近采集花生的位置为（max1i,max1j），准备采集花生的位置为（maxi，maxj），显然两个采集点的距离为 ；多多在限定时间内可采集到的最多花生数为total p:array1.20,1.20of integer; 花生田。其中pi，j为花生田里植株(i, j)下花生的数目 由于多多在相邻元素间移动一步的时间为一个单位，因此除去多多从路边往返数组第一行的2个单位时间，则多多在数组内采集花生的时间不允许超过k-2（k=k-2）个时间单位

7、。 我们首先计算花生数最多的位置（max1i，max1j）和该位置的花生数max，将多多的行程t初始化为max1i。显然，如果花生田里有花生(max0)且采集了花生最多的植株后可返回路边（t+max1i-1k），则采集（max1i，max1j）位置的花生（pmax1i,max1j0；totaltotal+max）。然后计算下一个花生数最多的位置（maxi，maxj），将两个采集点的距离计入t(tt+ )，并将（maxi，maxj）设为下一个采集目标（max1imaxi;max1jmaxj）。 重复上述计算过程，直至花生田里无花生(max=0)或者采集（max1i，max1j）位置的花生后无法返

8、回路边（t+max1i-1k）为止。由此得出算法：,readln(m,n,k);读花生田的规模和多多采花生的限定时间 k:=k-2; 计算多多在数组内采集花生的最多时间 max:=0;读花生田的信息。计算花生数最多的位置（max1i，max1j）和该位置的花生数max for i:=1 to m do for j:=1 to n do begin read(pi,j); if pi,jmax then begin max:=pi,j;max1i:=i;max1j:=j；end;then end;for t:=max1i;total:=0; 多多的行程和采集的花生数初始化 while (t+ma

9、x1i-10) do若在限定时间内回到路边且找到花生最多的植株，则采摘它的花生，并累计采摘的花生总数 begin pmax1i,max1j:=0;total:=total+max; max:=0;计算当前花生数最多的位置（maxi，maxj）和该位置的花生数max for i:=1 to m do for j:=1 to n do if pi,jmax then begin max:=pi,j;maxi:=i;maxj:=j；end;then t:=t+1+abs(max1i-maxi)+abs(max1j-maxj);累计行程 max1i:=maxi;max1j:=maxj；从该位置出发，继

10、续采摘花生 end;while writeln(total);输出限定时间内多多采到花生数的最大值 时间复杂度为O (k*n2),解法2:贪心算法,先将花生植株按花生数递减的顺序排列成一维数组，数组元素记录下植株的花生数和位置。按照数组顺序，找出距离之和不超过k-2、且最接近k-2的前若干个元素，将这些元素记录的花生数累加起来，便构成了问题的解。算法的时间复杂度为O (n*log n +k)。,字符串的展开,【问题描述】在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例了：如果在输入的字符串中，含有类似于“d-h”或“4-8”的子串，我们就把它当作一种简写，输出时，用连续递

11、增的字母或数字串替代其中的减号，即，将上面两个子串分别输出为“dcfgh”和“45678”。在本题中，我们通过增加些参数的设置，使字符串的展开更为灵活。具体约定如下： （1)遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号“”，减号两侧同为小写字母或同为数字，且按照AScII码的顺序，减号右边的字符严格大于左边的字符。 (2)参数p1:展开方式。p1=1时，对于字母予串，填充小写字母： p1=2时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。pl=3时，不论是字母r串还足数字子串，都用与要填充的字母个数相同的星号*来填充。 (3)参数p2：填充字符的重复个数。

12、p2=k表示同一个字符要连续填充k个。例如，当p2=3时，子串“d-h”应 展 为“deeefffgggh”。减号两侧的字符小变。,(4)参数p3：是否改为逆序：p3=l表示维持原有顺序，p3=2表示采用逆序输出，注意这时仍然不包括减号两端的字符。例如当p1=1、p2=2、p3=2时，子串“d-h”应扩展为“dggffeeh”。 (5)如果减号右边的子符恰好是左边字符的后继只删除中间的减号，例如：“de”应输出为“de”，“3-4”应输出为“34”。如果减号右边的字符按照ASCLL码的顺序小于或等于左边字符，输出时，要保留中间的减号，例如：“d-d”应输出为“d-d”，“3-l”应输出为“3-

13、l”。 【输入】输入文件expandin包括两行：第l行为用空格隔开的3个正整数，依次表示参数p1，p2，p3;第2行为一行字符串，仅由数字、小写字母和减号“-”组成。行首和行末均无空格。 【输出】输出文件expandout只有一行，为展开后的字符串。 【限制】 40的数据满足：宁符串长度小超过5;100%的数据满足：lp13，lp28，lp32。字符串长度不超过100,试题简述,题目大意：给出一个字符串（串长100），对于串中出现-符号，且-左右两边均为小写字母或数字，且左边的比右边的小，则需要按要求将它展开。 其中有三个展开参数，p1，p2，p3。 p1：展开方式。p1=1时，对于字母子串

14、填充小写字母；p1=2时，对于字母子串填写大写字母；p1=3时，无论是字符串还是数字串都填写*。 p2：填充字符的重复个数。 p3：是否为逆序。,算法,直接模拟。对于每一个-，判断是否需要展开即可。算法复杂度O(L)（L为答案字符串长度）。设 展开后的目标串为ans，长度为tot； 初始串st，string类型;,判别是否需要展开,设-左右的字符分别为ch1和ch2。若ch1和ch2同为数码或同为字母且递增，则需要展开；否则不需要展开。这一判别过程由布尔函数check(ch1,ch2)描述： function check(ch1,ch2:char):boolean;若字符ch1和ch2同数码或

15、同字母且递增，则返回true；否则返回false begin check:=false; if(ch1 in 0.9)and(ch2 in 0.9) or(ch1 in a.z)and(ch2 in a.z) then if ch1ch2 then check:=true end;,展开规则,若相邻的两个同类型且递增的字符ch1和ch2，则需要被展开的中间字符按照序数计算为ord(ch1)+1ord(ch2)-1，其中每个字符被展开p2次，展开的内容由p1决定，顺序由p3决定： ， 其中当展开字母（p1=1,2） 时，p3=,procedure add(ch1,ch2:char);输入相邻的两

16、个同类型且递增的字符，按要求展开 var i,j,s,e:longint; begin s:=ord(ch1);e:=ord(ch2);计算两个字符的asll码 if p1=3若填写 then begin for i:=s+1 to e-1 do按照字典序，ch1与ch2间的每个中间字符用p2个取代 for j:=1 to p2 do begininc(tot);anstot:=*end; exit end; if p1=2若填充大写字母，则首尾字符取大写字母的asll码 then begin if ch1 in a.z then begin s:=s-32;e:=e-32 end end;

17、if p3=1若正序，则按照字典顺序，ch1至ch2间的每个中间字符重复p2次 then for i:=s+1 to e-1 do for j:=1 to p2 do begin inc(tot);anstot:=chr(i)end else for i:=e-1 downto s+1 do若逆序，则按照字典逆序，ch2至ch1的每个中间字符重复p2次 for j:=1 to p2 do begin inc(tot); anstot:=chr(i) end end;,主程序,readln(p1,p2,p3);读展开方式 readln(st);读初始串 l:=length(st);计算初始串的长

18、度 tot:=1;ans1:=st1;第个字符进入目标串 for i:=2 to l-1 do逐个字符展开 if sti=- then begin if check(sti-1,sti+1)若相邻的两个字符同类型且递增，则按照要求展开；否则第i个字符进入目标串 then add(sti-1,sti+1) else begin inc(tot);anstot:=sti end end else begin inc(tot);anstot:=sti end; 否则第i个字符进入目标串 inc(tot); anstot:=stl最后一个字符进入目标串 for i:=1 to tot do write

19、(ansi);输出展开后的目标串 writeln;,昂贵的聘礼,年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说：“嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要5000金币就行了。”探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。不过探险家没必要用

20、多样东西去换一样东西，因为不会得到更低的价格。探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。另外他要告诉你的是，在这个部落里，等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。他是一个外来人，所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。,为了方便起见，我们把所有的物品从1开始进行编号，酋长的允诺也看作一个物品，并且编号总是1。每个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品Ti和该替代品

21、所对应的“优惠”Vi。如果两人地位等级差距超过了M，就不能“间接交易”。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。 输入文件:M，N（1=N=100），依次表示地位等级差距限制和物品的总数。 按照编号从小到大依次给出了N个物品的描述。每个物品的描述开头是三个非负整数P、L、X（XN），依次表示该物品的价格、主人的地位等级和替代品总数。接下来X行每行包括两个整数T和V，分别表示替代品的编号和“优惠价格”。 输出文件:最少需要的金币数。,数据结构,const maxn=100;物品数上限 type ny=nz;物品的指针变量 nz=array1.maxn,1.2 of l

22、ongint;替代品序列，包括每一个替代品的编号和“优惠价格” nx=record p,x,l:longint; 物品的价格、替代品总数和主人的地位等级 list:ny; 替代品序列 end; var map:array1.maxn of nx;物品序列 can:array1.maxn of boolean;记录与当前客户的等级差距在限制范围内的客户 p,l,x,i,j,m,n，l1:longint;,输入信息,readln(m,n);输入地位等级差距限制和物品总数 readln(map1.p,map1.l,map1.x);读入物品1的价格、主人的地位等级和替代品总数 new(map1.lis

23、t);读入物品1的每个替代品的编号和“优惠价格” for i:=1 to map1.x do readln(map1.listi,1,map1.listi,2); for i:=2 to n do读入物品2物品n的信息 with mapi do begin readln(p,l,x);new(list); for j:=1 to x do readln(listj,1,listj,2); end;,计算最少需要的金币数,递推每一个客户h(1hn) 11寻找每一个与客户h的等级差距在限制范围内的客户i 搜索客户i的每一个可与客户h交易的替代品j,若替代后花钱更少，则记下 pricei=minpr

24、icej+物品j的优惠价，物品i的单价 12若当前方案最佳（price1min），则调整min 最后输出min,procedure solve; var i,j,now,more:longint; price:array1.maxnof longint; pricei为客户i的最少花销 ok:boolean;不存在更便宜的方案标志 min,h:longint; 最少需要的金币数和当前客户 begin min:=maxlongint;最少需要的金币数初始化 for h:=1 to n do begin枚举每一个客户 fillchar(can,sizeof(can),false); for i:=

25、1 to n do标记每一个与客户h的等级差距在限制范围内的客户 if (mapi.l-maph.l=0) and (mapi.l-maph.l=m) then cani:=true; for i:=1 to n do pricei:=mapi.p;初始时直接购买,repeat ok:=true; for i:=1 to n do枚举每一个与客户h的等级差距在限制范围内的客户 if cani then for j:=1 to mapi.x do begin枚举物品i的每一个替代品，记下其编号和“优惠价格” now:=mapi.listj,1; more:=mapi.listj,2; if （c

26、annow）and(pricenow+morepricei) 若第j个替代品可与客户h交易且间接交易后花钱更少，则采取该交易方案 then begin ok:=false;pricei:=pricenow+more;end; end;for until ok; if price1min then min:=price1;若目前方案的花钱最少，则记下 end;for writeln(min);输出最少需要的金币数 end;,DAM语言,有个机器执行一种DASM语言。该机器有一个栈，初始时栈里只有一个元素x，随着DAM语言程序的执行，栈里的元素会发生变化。DAM语言有四种指令： D指令：把栈顶元素

27、复制一次加到栈顶 A指令：把栈顶元素取出，加到新的栈顶元素中。 M指令：把栈顶元素取出，乘到新的栈顶元素中。 如果执行A或M指令的时候栈内只有一个元素，则机器会发出错误信息。如果程序无误，那么执行完毕以后，栈顶元素应该是x的多项式，例如，程序DADDMA的执行情况为（栈内元素按照从底到顶的顺序从左至右排列，用逗号隔开）： x x， x 2x 2x， 2x 2x， 2x， 2x 2x， 4x2 4x2+2x 给出一段DAM程序，求出执行完毕后栈顶元素。 输入:输入仅一行，包含一个不空的字符串s，长度不超过12，代表一段DAM程序。输入程序保证合法且不会导致错误。 输出:仅输出一行，即栈顶多项式。

28、须按照习惯写法降幂输出，即：等于1的系数不要打印，系数为0的项不打印，第一项不打印正号。一次方不打印1。,模拟需要注意的问题,用数组来表示多项式(由于指令不超过12条，而D指令和A，M指令总数应该相等，因此最多有6条M指令(DMDMDMDMDMDM)，因此次数上限为26=64),避免链表。 系数采用extended类型(指令形式为DAMDMDMDMDM)系数最大可能为232),避免高精度。,$n+ var degree ： array1 . 20 of integer； 存储系数个数的栈 co ： array1 . 20， 0 . 64 of extended；存储多项式的栈 tmp ： ar

29、ray0 . 64 of extended；系数序列 I， j， d， a， b， top ： integer； 栈顶指针为top s ： string； Dam程序 first ： boolean； begin top 1； 栈顶指针初始化 fillchar(co， sizeof(co)， 0)； 存储多项式的栈清零 degree1 1；初始时栈里只有一个元素x co1， 1 1； read(s)；输入Dam程序 for I 1 to length(s) do依次执行Dam程序中的每一条命令 case sI of D： begin 把栈顶元素复制一次加到栈顶 inc(top)；degreet

30、op degreetop 1； for j 0 to degreetop do cotop， j cotop 1， j； end； D ,A： begin 把栈顶元素取出，加到新的栈顶元素中 dec(top)； if degreetop 0 then begin if first then first false else write(+)； if abs(cotop， I 1.0) 1e-6 then write(cotop， I ： 0 ： 0)； write(x)； if I 1 then write(， I)； end；then writeln； end.main,跳远,在水平面上整齐

31、的放着n个正三角形，相邻两个三角形的底边之间无空隙， 如左图所示。一个小孩子想站在某个三角形i的顶端，跳到三角形j的顶端上(ij)。他总是朝着斜向45度的方向起跳，且初始水平速度v不超过一个给定值v0。在跳跃过程中，由于受到重力作用（忽略空气阻力），小孩子将沿着抛物线行进，水平运动方程为x = x0 + vt，竖直运动方程为y = y0 + vt 0.5gt2，运动轨迹是一条上凸的抛物线。取g=10.0，(x0， y0)是起跳点坐标。 请编程求出他从每个位置起跳能到达的最远三角形的编号。注意：跳跃过程中不许碰到非起点和终点的其他三角形。 输入:第一行为两个正整数n，v0(3n10， 1v010

32、0)，表示三角形的个数和最大水平初速度。第二行有n个正整数li(1li20)，表示从左到右各个三角形的边长。 输出:输出仅一行，包括n-1个数，表示从三角形1，2，3n-1的顶点出发能到达的最右的三角形编号。如果从某三角形出发无法达到任何三角形，相应的数为0。,状态：起跳点i和i点后的点j。每个状态元素的取值范围：1in-1，i+1jn 约束条件的分析：判断小孩能否从i点跳到j点的方法如下： 设起点和终点间的水平距离为l、垂直距离为h。则由物理知识（已在题目中给出）有：t = l / v;h = vt 5t2 = l 5*(l/v)2 。 因此，v = sqrt(5*l*l/ (l-h)。当然

33、，这个v不一定符合要求，它需要满足两个条件: 它不能大于极限速度v0，即必须有v v0 跳跃过程中不得碰到其他三角形。 如何判断顶点k是否在抛物线下呢？我们可以算出到达时间t0 = dx / v（其中dx为起点到顶点k的水平坐标增量），然后算出该时刻的竖直坐标增量vt0 0.5t02。如果此增量大于起点到顶点k的竖直坐标增量，则抛物线在上方。只有起点和终点之间任何一个三角形的顶点不在抛物线下方，则跳远不能完成。 我们在枚举过程中不断将小孩所能跳到的点j调整为best。 枚举结束后，best即为试题要求的最远点。,var len ： array1 . 20 of longint； x， y ：

34、array1 . 20 of double；三角形顶端顶点的坐标序列 l， h， t， v， v0 ： double； ok ： boolean；跳跃成功标志 i， j， k， n， best ： integer； begin read(n， v0)；输入三角形的个数和最大水平初速度 for i1 to n do read(leni)；入从左到右各个三角形的边长 x1len1 / 2；计算每一个三角形顶端顶点的坐标 y1len1 * sqrt(3) / 2； for i2 to n do begin xixi - 1+leni - 1/2+leni/2； yileni*sqrt(3)/2； e

35、nd；for,for i 1 to n - 1 do依次计算每一个三角形所能到达的最远点 begin best 0；从三角形i出发能到达的最右的三角形编号初始化 for j i + 1 to n do依次枚举右方的每一个三角形 begin l xj - xi；计算三角形i与三角形j的两个顶端顶点的水平距离和垂直距离 h yj - yi； if l v0 then break；若大于极限速度v0，则无法从三角形i起跳 oktrue； for ki+1 to j-1 do判断跳跃过程中是否碰到其他三角形 begin t(xk - xi)/v；计算到达三角形k的时间,if (v * t - 5 *

36、t * t) - (yk - yi) 1e-6 then begin如果该时刻的竖直坐标增量大于起点到顶点k的竖直坐标增量，则抛物线在上方 ok false； break； end；then end；for if ok then best j 若跳远成功，则三角形j为目前三角形i所能到达的最远点，否则跳远不能完成 else break； end；for write(best， )；输出从三角形i的顶点出发所能到达的最右的三角形编号） end；for writeln； end.main,作业调度方案,我们现在要利用m台机器加工n个工件，每个工件都有m道工序，每道工序都在不同的指定的机器上完成。每

37、个工件的每道工序都有指定的加工时间。每个工件的每个工序称为一个操作，我们用记号j-k表示一个操作，其中j为1到n中的某个数字，为工件号；k为1到m中的某个数字，为工序号，例如2-4表示第2个工件第4道工序的这个操作。在本题中，我们还给定对于各操作的一个安排顺序。例如，当n=3，m=2时，“1-1，1-2，2-1，3-1，3-2，2-2”就是一个给定的安排顺序，即先安排第1个工件的第1个工序，再安排第1个工件的第2个工序，然后再安排第2个工件的第1个工序，等等。一方面，每个操作的安排都要满足以下的两个约束条件。 (1) 对同一个工件，每道工序必须在它前面的工序完成后才能开始； (2) 同一时刻每

38、一台机器至多只能加工一个工件。,则对于安排顺序“1 1 2 3 3 2”，下图中的两个实施方案都是正确的。但所需要的总时间分别是10与12。,另一方面，在安排后面的操作时，不能改动前面已安排的操作的工作状态。由于同一工件都是按工序的顺序安排的，因此，只按原顺序给出工件号，仍可得到同样的安排顺序，于是，在输入数据中，我们将这个安排顺序简写为“1 1 2 3 3 2”。还要注意，“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时，有可能排在后面的某个操作比前面的某个操作先完成。例如，取n=3,m=2，已知数据如下：,当一个操作插入到某台机器的某个空档时（机器

39、上最后的尚未安排操作的部分也可以看作一个空档），可以靠前插入，也可以靠后或居中插入。为了使问题简单一些，我们约定：在保证约束条件（1）（2）的条件下，尽量靠前插入。并且，我们还约定，如果有多个空档可以插入，就在保证约束条件（1）（2）的条件下，插入到最前面的一个空档。于是，在这些约定下，上例中的方案一是正确的，而方案二是不正确的。 显然，在这些约定下，对于给定的安排顺序，符合该安排顺序的实施方案是唯一的，请你计算出该方案完成全部任务所需的总时间。 【输入文件】输入文件jsp.in 的第1行为两个正整数，用一个空格隔开： m n（其中m（20）表示机器数，n（20）表示工件数） 第2行：个用空格

40、隔开的数，为给定的安排顺序。 接下来的2n行，每行都是用空格隔开的m个正整数，每个数不超过20。其中前n行依次表示每个工件的每个工序所使用的机器号，第1个数为第1个工序的机器号，第2个数为第2个工序机器号，等等。后n行依次表示每个工件的每个工序的加工时间。可以保证，以上各数据都是正确的，不必检验。 【输出文件】输出文件jsp.out只有一个正整数，为最少的加工时间。,题目大意,有N个工件和M台机器，每个工件都必须要经过这M道工序。每个工件对不同机器需要不同时间处理。每个工件有一个工序的操作先后顺序，下一个工序必须再前面的工序都完成后才能开始。每台机器同一时间只能对一个工件进行一道工序。给出一个

41、安排顺序，对于当前给出的工件，将它插入到工作方案中适合的位置（需要满足该工件对工序的操作顺序，以及机器的使用规定）。求出将所有工件加工完所需要的最短时间。,直译模拟,由于每个工件的每个工序使用的机器号和加工时间给定，因此安排顺序给出后，所用时间也就唯一确定，所以直接模拟即可得到答案。 难点：找出当前机器i开始加工的时间 方法：用所有时间的部分和进行优化。,计算每台机器加工时间的情况,设tti,j=1，表明机器i在时刻j被使用;tti,j=0，表明机器i在时刻j未使用; sumi,j机器i在j时间前使用的时间和，即sumi,j= ； 显然，机器i开始加工的时间j为加工前后使用的时间和为0的位置，

42、即当 sumi,j+加工当前工件工序的时间=sumi,j 时，表明机器i可以从j时刻开始加工当前工件，因为该期间没有其它工件使用该机器。这样顺序查找一遍所有时间点，即可找出机器i开始加工的时间。,递推安排顺序i,1、第i个顺序加工的工件pp已知；如果能够知道工件pp的工序，则使用的机器号已知。因此需要计算每个工件的当前工序 2、从工件pp的上一个工序的结束时间开始，计算加工pp工件当前工序的开始时间，因此需要计算每个工件当前工序的结束时间； 3、加工期间，该机器标志被使用，因此需要计算tt； 4、从加工开始至末尾时间，调整使用的时间和，因此需要计算sum； 5、最少加工时间是所有安排顺序的结束

43、时间的最大值。,按照安排顺序递推完成所有工件加工的最短时间,1、初始时，假设每一个工件从工序1开始加工； for i:=1 to m*n do递推安排顺序 begin 2、取出第i个顺序加工的工件pp、pp工件当前工序ss、使用的机器号aa、上一个工序的结束时间edpp； 3、从edpp时刻开始，计算机器aa开始进工pp工件当前工序的时 间j； 4、设置加工期间机器aa被使用，累计机器aa使用的时间和； 5、设置工件pp完成本工序的结束时间edpp，调整最少加工时间； 6、枚举机器aa完成工件pp的当前工序后的每一个可能时间jj，计算使用的时间和； 7、pp工件进入下一个工序； end; in

44、c(ans),数据结构,const maxt=8000;时间数的上限 maxn=20;工件和工序数的上限 inf=jsp.in;outf=jsp.out; var a,t:array1.maxn,1.maxnof longint; 工件i的j工序所使用的机器号为ai,j，加工时间为ti,j p:array1.maxn*maxnof longint;在安排顺序i中加工的工件号为pi st,ed:array1.maxnof longint; 工件i的当前工序为sti；上一个工序的结束时间为edi sum,tt:array1.maxn,-1.maxtof longint; sumI,j机器i在j时间

45、前使用的时间和；tti,j=1，表明机器i在时刻j被使用， tti,j=0，表明机器i在时刻j未使用 n,m,ans:longint; 工件数为n，机器数为m，最少加工时间为ans,输入信息,procedure init; var i,j:longint; begin assign(input,inf);reset(input);文件读准备 readln(m,n);输入机器数和工件数 for i:=1 to m*n do read(pi);输入每个安排顺序中被加工的工件号 for i:=1 to n do输入每个工件的每个工序所使用的机器号 for j:=1 to m do read(ai,j

46、); for i:=1 to n do输入每个工件的每个工序的加工时间 for j:=1 to m do read(ti,j); close(input) end;,计算最少加工时间ans,procedure main; var i,pp,aa,ss,j,jj:longint; Begin 1、初始时假设每一个工件从工序1开始加工 for i:=1 to n do sti:=1； for i:=1 to m*n do递推安排顺序 begin 2、取出第i个顺序加工的工件pp、pp工件当前工序所使用的机器号aa、pp工件的当前工序ss和上一个工序的结束时间 pp:=pi;aa:=app,stpp

47、;ss:=stpp;j:=edpp； 3、计算机器aa开始进行工件pp当前工序的时间j while(sumaaj+tpp,ss-1-sumaaj-10)do inc(j);,4、设置加工期间机器aa被使用，累计机器aa使用的时间和 for jj:=j to j+tpp,ss-1 do begin ttaajj:=1;sumaajj:=sumaajj-1+1；end； 5、计算工件pp完成本工序的结束时间，调整最少加工时间 edpp:=j+tpp,ss;ans:=max(ans,j+tpp,ss-1); 6、枚举机器aa完成工件pp的ss工序后的每一个可能时间jj，计算使用的时间和 for jj

48、:=j+tpp,ss to maxt do sumaajj:=sumaajj-1+ttaajj； inc(stpp);7、计算pp工件的下一个工序 end; inc(ans) end;,筛选法模拟,模拟过程中可能产生的所有解组成一个筛。筛选法模拟即先从题意中找出约束条件，然后将筛中的每一个可能解放到约束条件的过滤器上，一次一次地将不符合条件的解过滤掉，最后沉淀在筛中的即为问题的解。“筛选法模拟”的结构和思路简明、清晰，但带有盲目性，因此时间效率并不一定令人满意。“筛选法模拟”的关键是找准约束条件，任何错误和疏漏都会导致模拟失败。,蒙特卡洛法,计算定积分 其中ab，0f(x)d， 输入： a b

49、 d a0a1ak(表示f(x)=ak*xk+a1*x+a0),产生n(足够大)个均匀分布在长方形a b c d上的随机数点(xi，yi)。其中 xi均匀分布在区间a，b上的随机数，即xi=a+(b-a)*random(1)； yi均匀分布在区间0，d上的随机数，即yi=d*random(1)； n个随机数点组成一个筛。约束条件的过滤器是某点(xi，yi)是否落在曲边梯形a e f b外。如果是（yif(xi)），则该点从筛中过滤掉。 最后有m个随机数点留在筛中（这些随机数点落在曲边梯形a e f b内）。曲边梯形a e f b的面积应该为m和n的比值乘以长方形a b c d的面积,funct

50、ion f(x)：real；计算f(x) begin f(x)akxk+ak-1kk-1+a1x+a0； end；f function amoncar (a， b， d， n)：real；计算 begin randomize； m0； for i1 to n do begin xa+(b-a)*random(1)；产生ki yd*random(1)；产生yi if yf(x) then mm+1；若(xi，yI)落入曲边梯形内，则累计其点数 end；for amoncarm/n*(b-a)*d；返回曲边梯形面积 end；amoncar 在主程序中，输入随机点的个数n和a，b，d，然后通过调用函

51、数amoncar (a，b，d，n)计算和输出定积分的值。注意，n愈大，定积分的值愈精确，但速度愈慢。,self-number,对任意一个正整数n，定义d(n)为n加上其每一位上的数字，比如d(75) = 75 + 7 + 5 = 87。并且称n是d(n)的一个generator。一个正整数，如果没有任何generator，就说这个数是一个self-number。给出一列数s1，s2，sK，问范围1, N内第s1，s2，sK大的self-number分别是什么。 输入： n k(1 N 107,1 K 5000) s1，s2，sK 输出：范围1, N内第s1，s2，sK大的self-numbe

52、r,如果一个数x不能通过d(n)方式算得出，那么称之为Self-number。如1、3、5、7、9都是Self-number。,用筛数方法产生1, N中的所有self-number,在一张一维的布尔表中，从小到大将每个数n的d(n)都标记为不可能是self-number，那么未被标记的一定就是self-number了。 布尔表的容量：因为d(n) n（各位数的和）并不会很大：最大也不过9*lgn=81。,计算d(n)的时间复杂度,原时间复杂度为O(NlgN)：因为每次计算d(n)时侯分离其每一位的时间复杂度是O(lgN)。本题中N高达107，因此这个O(lgN)的因子不可以忽略。 优化 首先预

53、处理，开一个subi数组，记录i的每一位之和，但是这里i的范围不用太大，只要在O(sqrt(n)=104就可以了。这样计算d(n)的时侯，就可以将n的各位和分成低4位和高3位来计算，而每次计算不过是调用subi，这样计算d(n)的时间复杂度就降到了O(1)。 综上，本题的时间复杂度就是O(sqrt(n)lgN + N + Mlog2M)，其中Mlog2M是在输出的时侯需要对si进行排序。,设筛data，其中datai 将数i的d(i)标记为不可能是self-number。筛长为1000。 data筛的指针为now ； self-number序列为request，其中request i. req

54、uest 为si，request i. number为si的输入顺序，request i. answer为顺序为si的self-number数。self-number序列的指针为p； self-number的个数为total。,初始化,read(N , K); for i := 1 to K do输入s1，s2，sK ，记下输入顺序 begin read(requesti.request);读si requesti.number := i;记下si的输入顺序 end; qk_sort(1 , K)；按照s1，s2，sK 递增顺序排列request 计算sub0sub10000，其中subi为整

55、数i的各位数的和；,fillchar(data , sizeof(data) , 0);初始时筛满，即所有数可能是self-number数 now := 1; total := 0; p := 1; data筛的指针、 self-number的个数、 self-number序列的指针初始化 for i := 1 to N do顺序搜索1, N内第s1，s2，sK大的self-number begin if not datanow then若now在筛中 begin inc(total);累计self-number的个数 while (p Limit do dec(tmp , Limit);将d

56、i限制在1000范围内 datatmp := true; datanow := false; 在data筛中保留第now个元素，去掉第di个元素 if now = Limit循环右移data筛的指针now then now := 1 else inc(now); end;,输出self-number,for i := 1 to K do按照输入要求记下各个self-number数 outarrrequesti.number := requesti.answer; 输出1.n中self-number的个数 total; 输出outarr1 outarrk；,构造法模拟,构造法模拟需要完整精确地构

57、造出反映问题本质的数学模型，根据该模型设计状态变化的参数，计算模拟结果。由于数学模型建立了客观事物间准确的运算关系，因此其效率一般比较高。“构造法模拟”的关键是找到数学模型。问题是，能产生正确结果的数学模型并不是唯一的，从不同的思维角度看问题，可以得出不同的数学模型，而模拟效率和编程复杂度往往因数学模型而异。即便有数学模型，但解该模型的准确方法是否有现成算法、编程复杂度如何，这些都是我们要考虑的问题。,守望者的逃离,【问题描述】恶魔猎手尤迫安野心勃勃.他背叛了暗夜精灵，率深藏在海底的那加企图叛变：守望者在与尤迪安的交锋中遭遇了围杀.被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施

58、咒，这座岛很快就会沉下去，到那时，刀上的所有人都会遇难：守望者的跑步速度，为17m/s， 以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。 现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位。且每次活动的持续时间为整数秒。距离的单位为米(m)。 【输入】输入文件escape.in仅一行，包括空格隔开的三个非负整数M，S，T。 【输出】 输出文件escape.out包含两行: 第1行为字符串Yes或No (区分大小写)，即守望者是否能逃离荒岛。 第2行包含一个整数，第一行为Yes (区分大小写）时表示守望着逃离荒岛的最短时间 第一行为No (区分大小写) 时表示守望者能走的最远距离。,如果守望者尚未逃出荒岛且荒岛未沉没（(nows)and(tT）)，则应采用尽可能使用魔法的贪心策略,守望者的魔法值足以施展闪烁法术（p10），则使用1秒闪烁法术：p=p-10;now=now+60;t=t