noip信息竞赛共享2013级辅导第六节第五讲

第五讲基本常识2014.02.291.蚂蚁爬杆最短时间：所有蚂蚁都朝向较近的端点走会比较好。事实上，这种情况下不会发生两只蚂蚁相遇的情况mins=max{min{a[i],L-a[i]}}1<=i<=n事实上：最靠近中点的那只蚂蚁决定最短时间。看看蚂蚁相遇时会发生什么？最长时间：超远端方向爬相遇情况下落的时间？下落时间是：max{max{a[i],L-a[i]},max{a[j],L-a[j]}}QPAa[i]a[j]03109BACa[i]a[j]031096B(AB中点？)PQ交错继续前行031096相遇返回031096时间：max{AC+PC,CB+CQ}=max{3+6,3+4}=9时间：max{AC+CQ,CB+PC}=max{3+4,3+6}=9=max{CB+CQ,AC+PC}事实上，可以知道两只蚂蚁相遇后，当它们保持原样交错而过继续前进也不会有任何问题。可以认为每只蚂蚁都是独立运动的。所以要求最长时间，只要求蚂蚁到竿子端点的最大距离就好了。最长时间的另一种理解：距离端点最近的那只蚂蚁k决定方向和下落时间：等价于所以蚂蚁都朝着蚂蚁k的远端的运行时间=max{a[k],L-a[k]}最长时间：mins=max{max{a[i],L-a[i]}}1<=i<=n这个问题可以说是考察想象力类型问题的经典例子。有很多这样的问题，虽然开始不太明白，但想通之后，最后的程序却是出乎意料地简单。2.进制转换编程将一个十进制整数k转化为二进制数（k<1000000）。样例：输入：19输出：10011进制基数R基本符号二进制20,1八进制80,1,2,3,4,5,6,7十进制100,1,2,3,4,5,6,7,8,9十六进制160,1,2,3,4,5,6,7,8,9,A,B,C,D,E,Fvark,n,i:longint;a:array[1..20]ofinteger;beginreadln(k);n:=0;whilek<>0dobeginn:=n+1;a[n]:=kmod2;k:=kdiv2;end;fori:=ndownto1dowrite(a[i]);writln;end.思考：转换为8进制？转换为16进制？ifa[i]<=9thenwrite(a[i]);ifa[i]=10thenwrite('A');ifa[i]=11thenwrite('B');ifa[i]=12thenwrite('C');ifa[i]=13thenwrite('D');ifa[i]=14thenwrite('E');ifa[i]=15thenwrite('F');casea[i]of10:write('A');11:write('B');12:write('C');13:write('D');14:write('E');15:write('F');end;字符函数：Varc:char;Chr(x):返回ASCII码=x的字符。Ord(c):返回字符c的ASCII码。ifa[i]<=9thenwrite(a[i])elsewrite(chr(a[i]+55));3.砝码称重1克、2克、50克的砝码各10个，问用这些砝码一共能称出多少种重量。输出种数以及每种重量(不包括0)。vara:array[0..530]oflongint;i,j,k,s:integer;beginfori:=0tomaxdoa[i]:=0;fori:=0to10doforj:=0to10dofork:=0to10doa[i+2*j+50*k]:=0;s:=0;fori:=1tomaxdos:=s+a[i];writeln(s);fori:=1tomaxdoifa[i]=1thenwrite(i,'');end.Boolean数据类型：true和false4.素数（1）输入一个正整数k（k<=109），判断是否为素数。（2）输出n(n<=10000000)以内的素数及个数。如20以内的素数有：2,3,5,7,11,13,17,19.筛选法求素数varf:array[1..10000000]ofboolean;n,i,j,sum:longint;beginreadln(n);fori:=1tondof[i]:=true;fori:=2tondoiff[i]=truethenforj:=2tondividof[i*j]:=false;sum:=0;fori:=2tondosum:=sum+ord(f[i]);writeln(sum);end.varf:array[1..10000000]ofboolean;

p:array[1..700000]oflongint;n,m,i,j,k:longint;beginreadln(n);fori:=1tondof[i]:=true;fori:=2tondo//n也可以iff[i]=truethenforj:=2tondividof[i*j]:=false;k:=0;fori:=2tondoiff[i]thenbegink:=k+1;p[k]:=i;end;writeln(k);fori:=1tok-1dowrite(p[i],'');writeln(p[k]);end.5.选择排序算法输入n(n<=1000)个[0，30000]的数，按照从小到大的顺序输出。如：输入：824623164191299184106277输出：64106184191231246277299排序过程初始数据：[24623164191299184106277]第一趟排序后：64[231246191299184106277]第二趟排序后：64106[246191299184231277]第三趟排序后：64106184[191299246231277]第四趟排序后：64106184191[299246231277]第五趟排序后：64106184191231[246299277]第六趟排序后：64106184191231246[299277]第七趟排序后：64106184191231246277299选择排序算法的实现：选择排序算法基本思想：每一趟从待排序的数据元素中选出最小的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。对待排序的序列a[1],a[2],……a[n]进行n-1遍处理：第1遍处理是从a[1],a[2],……a[n]中选择最小的放在a[1]位置；第2遍处理是从a[2],a[3],……a[n]中选择最小的放在a[2]位置；

……第i遍处理是从a[i],a[i+1],……a[n]中找最小的元素与a[i]交换，这样经过第i遍处理后，a[i]是所有的中的第i小。即前i个数就已经排好序了。n-1遍处理后，剩下的最后一个一定是最大的，不需要再处理了，排序结束。//从第1

到第n个中找最小的放在第1

位置k:=1;forj:=2tondo//找最小的位置kifa[j]<a[k]thenk:=j;tem:=a[1];a[1]:=a[k];a[k]:=tem;//交换

第1趟//从第2

到第n个中找最小的放在第2

位置k:=2;forj:=3tondo//找最小的位置kifa[j]<a[k]thenk:=j;tem:=a[2];a[2]:=a[k];a[k]:=tem;//交换

第2趟//从第i

到第n个中找最小的放在第i

位置k:=i;forj:=i+1tondo//找最小的位置kifa[j]<a[k]thenk:=j;tem:=a[i];a[i]:=a[k];a[k]:=tem;//交换

i=n-1趟结束第i趟fori:=1ton-1dobegin

k:=i;forj:=i+1tondo//找最小的数的位置kifa[j]<a[k]thenk:=j;

ifi<>kthen//a[i]和a[k]交换begint:=a[k];a[k]:=a[i];a[i]:=t;end;end;选择排序算法描述：输入n(n<=1000)个[0，30000]的数，按照从小到大的顺序输出。如：输入：824623164191299184106277输出：64106184191231246277299另外一种方法：还可以两两交换：fori:=1ton-1doforj:=i+1tondoifa[j]<a[i]thenbegintem:=a[i];a[i]:=a[j];a[j]:=tem;end;【例5】最大三角形（加强版）有n(<=1000)根木棍，已知他们的长度(<=10000)，现在从中选出3根2木棍组成周长尽可能长的三角形。请计算出最大周长，如果无法组成三角形输出”no”.输入第一行：n第二行:n根木棍的长度。如：输入：5234510输出：12（选345）【数据范围限制】范围限制：n<1000。方法1:3层枚举3条边。方法2