试题、程序及解题报告1000

1、NOIP2005 解题孙慨然第一题：scholar给出 N（1N100）个人的情况，按照 5 条不同的奖学金条件发奖金（可重复得奖），求得到最多奖学金的人是谁，并求总奖学金数。这是一道简单题，没更好或更坏的算法。只需按照实际情况模拟即可，每人判断5 个条件，该发多少发多少就行了。要注意的是每人最多得 15850 元，总数最多 1585000 元，注意长整的使用。#include #define MAXN 100 FILE *fpi,*fpo;char nameMAXN+121; n;main()long s=0,max=0,maxi, money;/*最大人数*/*人名*/i,mark,clm

2、ark,pchar g,w;r;fpi=fopen(scholar.in,r);fpo=fopen(scholar.out,w);fscanf(fpi,%d,&n); for(i=1;i80 & pr0) money+=8000;/*判断各个奖*/if(mark85 & clmark80) money+=4000; if(mark90) money+=2000;if(mark85 & w=Y) money+=1000; if(clmark80 & g=Y) money+=850; s+=money;if(moneymax) max=money; maxi=i;fprf(fpo,%sn%ldn%

3、ldn,namemaxi,max,s); fclose(fpi);fclose(fpo);return(0);第二题：river一个青蛙要过一个宽为 P 米（1P109）的河，他一步能跳 S 到 T 米（1ST10），他不喜欢踩到河里的石子（石子数 M100），给出每个石子的坐标，问最少踩到多少石子能过河。这道题在没看数据规模之前以为是一道简单的 DP，但是数据开到十亿，无论在时间还是空间复杂度都过大，所以就要进行优化了。解一：简单方法：预期得分 30。简单动态规划，fi代表青蛙跳到 i 点时所可能踩到的最少石子数，所以有 fi=minfk+mapi(i-ski-t)，其中 mapi代表 i

4、上是否有石子，有是 1，否则 0。算法复杂度O(n2)。解二：改进方法：预期得分 100。会发现，虽然桥很长，但上面最多只有 100 个石子，想到能否用石子 DP，而应该是的。那能否基于第法？由于石子排布非常的疏，我们还会发现，如果两个石子相隔甚远，那他们中间的 fi大部分将会是同一个数，能否把两个石子的距离缩短，使之还与原来等效？要是行的话怎么缩？同学时做了一个方法能够过全部数据，用的滚动数组，下面列出了他的程序。也写了个程序，和他不尽相同：我令 L=stonei-stonei-1（stonei代表按坐标由小到大顺序排列的石块坐标），当 L 能够被 t 整除时（L%t=0），令 k=t；当

5、L 不能被 t 整除时（L%t!=0），令 k=L%t。然后令 k 为 k+t，最后判断如果 kL，那么 map数组中 stonei和 stonei-1两石头的距离就被等效成为 L（也就是没变）；如果 k=L，那么 map数组中 stonei和 stonei-1两石头的距离就被等效成为 k，可以看出来，这样处理完，两石子最大间距为 2*t，大大的缩短了数组，再按解一进行DP，就可以通过了。：Program River;Varf1, f2 : Text;x, Temp, i, l, s, t, p, q, n : Long; Stone : Array1.100 Of Long;a : Arra

6、y0.9 Ofeger;Procedure Qsort(l, r : Long);Vari, j, x, Temp : Long;Begini := l; j := r; x := Stone(l + r) Shr 1; RepeatWhile Stonei x Do Dec(j); If i j;If j l Then Qsort(l, j); If i = x Then Exit(Stonei); End;End;Function FindStone(x : Long) :Vari : Long; BeginFindStone := False; For i:=1 To n Do Begi

7、nIf Stonei = x Then Exit(True); End;End;Function FindMin(s, t : Long) : Long;Vari, Min : Long;Found :Begin;Min := MaxLong; Found := False; If s = t Then BeginFor i:=s To t Do BeginIf ai 101 Then Found := True;If ai M End;End Else Beginhen Min := ai;For i:=0 To t Do BeginIf ai 101 Then Found := True;

8、If ai MEnd;hen Min := ai;For i:=s To 9 Do BeginIf ai 101 Then Found := True;If ai 10) And (i 10) Then Begin i := i + (Temp - i) Div 10 - 1) * 10;End;p := i Mod 10 - t; q := i Mod 10 - s; If p 0 Then p := p + 10;If q 0 Then q := q + 10; x := FindMin(p, q);If FindStone(i) Then ai Mod 10 := x + 1 Else

9、ai Mod 10 := x; End;Wrin(f2, FindMin(0, 9); Close(f2);End.我：#include #define MAXN 100#define MAXS 100000 FILE *fpi,*fpo;long stoneMAXN+1=0; mapMAXS+1=0;long fMAXS+1=0;s,t,m,p=0,q;void qsort(l,r)/*排序石子*/i,j; long x,t; i=l;j=r;x=stone(i+j)/2; dofor(;stoneix;j-); if(i=j)t=stonei; stonei=stonej; stonej=

10、t;i+; j-;while(i=j); if(ir) qsort(i,r);if(lj) qsort(l,j);main() long l,k;i,j,min; fpi=fopen(river.in,r);fpo=fopen(river.out,w);fscanf(fpi,%ld %d %d %d,&l,&s,&t,&m); for(i=1;i=m;i+) fscanf(fpi,%ld,&stonei); qsort(1,m);for(i=1;i=m;i+) l=stonei-stonei-1; if(l%t=0) k=t;else k=l%t; k+=t; if(lk) k=l; p+=k

11、; mapp=1;for(i=1;i=p+t;i+)/*读入石子坐标*/*排序*/*缩短数组，p 为 map 长度*/*动态规划*/mAXN+1;for(j=i-t;j=i-s;j+) if(j0) continue; if(fjmin) min=fj;fi=mapi;mAXN+1;for(i=p+1;i=p+t;i+) if(fimin) min=fi; fprf(fpo,%dn,min);fclose(fpo); fclose(fpi);return(0);/*找最小值*/*输出*/第三题：fireN 个人先按顺序站成一个圈，然后发布（b1,b2,bk）样式令，意思是 b1换到 b2 的位

12、置上，b2 换到 b3 的位置上，bk 换到 b1 的位置上，k 为此命令代价。要求用最小的总命令代价调整这个圈，使之变为目标状态（就是满足所有人的喜好）。如果不能满足则输出“-1”，否则输出最小代价数。先看到 50000 的数据规模，想到它可能连动态规划都不是，只能考虑 O(N)，O(NlogN)，O(N*k)之类的算法。通过思考可发现，令有个特点，他点到名的同学的位置都有变化，而其余的位置并不移动。可以证明，一个由 N 个人组成的队列，发布命令使之变成一个和此队列没有一个同学位置相同的新队列，所用的最少代价为 N（大家可以思考一下）。所以求最小命令代价转变成了求最少与目标位置不同，也就是最

13、多与目标位置相同。而且又可以知道，只要有一个初始状态，就会通过发布命令得到目标状态，所以当且仅当所有人的喜好构不成一个圈时才不能满足每个同学的愿望（输出“-1”）。还要注意，通过输入数据得到的是两个圈，一个正的一个反的。现在把问题简化再反过来，问题转化为：给出一个数字圈，它与一个递增圈和一个递减圈里的数字重合数字最多是几个，用 N 减去这个数即为所求。可以这样算：先推出这个圈，把 reduce数组清零，再顺时针把每个人的依次减去 1，2，N（正向），每个结果存为 t，把 t 当作下标（小于 0 的加上 N），让 reduce0t+；然后顺时针把每个人的依次减去N，N-1，1（反向），每个结果存

14、为 t，把 t 当作下标（小于 0 的加上 N），让 reduce1t+；这样求出 reduce 数组中的最大值为 max，输出N-max 即可。为什么请大家自己思考:-D开始时，读数据时间复杂度为 O(N)，生成圈时间复杂度为 O(N)，减数的时间复杂度为O(2*N)（一正一反），总复杂度约为 O(4*N)，完全受得了，要注意的还是长整问题（使之成为条件反射）。本题应该算动态规划的状态压缩吧，大家如果有更好的算法可以跟我#include 。#define MAXN 50000 FILE *fpi,*fpo;long manMAXN+22;long cercleMAXN+2=0,1; used

15、MAXN+2=0;long reduce2MAXN+2=0; long n,max=0;main()long i,p,q=1,t; fpi=fopen(fire.in,r);fpo=fopen(fire.out,w);fscanf(fpi,%ld,&n);/*最大人数*/*每个人的左右手各连接谁*/*生成圈的顺序*/*状态数组*/for(i=1;i=n;i+) fscanf(fpi,%ld %ld,&mani0,&mani1);p=manq1; for(i=2;i=n+1;i+)if(manq1=p)p=q;/*生成圈*/q=manq0;elseif(manq0!=p) break; p=q;

16、q=manq1;if(usedq) break;else usedq=1; cerclei=q;/*此人三只手*/*此人要拉一个已经拉两手的人*/if(i=n+1) fprf(fpo,-1n); elsefor(i=1;i=n;i+) if(t=cerclei-i)max) max=reduce0t; if(t=cerclei-n+i-1)max) max=reduce1t;fprf(fpo,%ldn,n-max);fclose(fpi); fclose(fpo); return(0);/*构不成圈*/*正圈*/*判断最大值*/*反圈*/*判断最大值*/*输出*/第四题：equal给出一个多项

17、式，在备选中选择与之等价的多项式。考的是编译技术，用通常的方法把多项式转变为一棵二叉树：运算符为各个非叶节点，优先级越低越靠近根节点；叶结点是数值或变量a。如图：将样例(a-1)2+4*a 转化成：再通过加（plus）、减（也是 plus）、乘（mult）、乘方（sqre）运算函数，把字符串转变为自定义类型：expr（表达式型）。一个 expr 类型的数据包含：maxtime：最高次数，coei：i 次项系数，它可以表示任何一个多项式。最后比较每个备选同（expr 类型数据相同）的输出。具体操作看注释，题目没，把与给出多项式含义相技巧，就是麻烦。有的同学用往里代数的方法出解，也可以过，但个人觉

18、得并没有省事多少。#include #define MAXT 100 FILE *fpi,*fpo;char cequal2751=0; struct nodemaxtime;long coeMAXT+1;equal27=0;typedef struct node expr; n;/*最高次数*/*字符串型的表达式*/*定义 expr 类型*/*最高次*/*i 次向系数*/*备选expr 型的表达式*/*备选数*/left(i;k,x)/*根据右括号位置找相应的左括号位置*/for(i=1;i0;) x-;if(cequalkx=) i+;if(cequalkx=() i-;return(x)

19、;find(i;k,x,y,char ch1,char ch2)/*找 ch1 或 ch2 运算符*/1aa42-*+for(i=y;i=x;i-)if(cequalki=ch1 | cequalki=ch2) return(i); if(cequalki=) i=left(k,i);return(0);/*找到喽！*/*跳过括号*/*没找到*/void plus(expr q1,expr q2,expr *bak, i,lng;t)/*多项式加（减）法*/if(q1.maxtimeq2.maxtime) lng=q1.maxtime; else lng=q2.maxtime;for(i=0;

20、i=lng;i+) (*bak).coei=q1.coei+t*q2.coei;while(*bak).coelng=0) lng-; (*bak).maxtime=lng;void mult(expr q1,expr q2,expr *bak) i,j;for(i=0;i=q1.maxtime;i+) for(j=0;j=q2.maxtime;j+)(*bak).coei+j+=q1.coei*q2.coej; (*bak).maxtime=q1.maxtime+q2.maxtime;void sqre(expr q1,expr q2,expr *bak) i;expr q3,z=0; (*

21、bak).coe0=1;for(i=1;i=q2.coe0;i+) q3=z; mult(*bak),q1,&q3); (*bak)=q3;/*多项式乘法*/*多项式乘方*/*清零*/*不断相乘*/void comput(l,i;k,x,y,expr *bak)/*递归调用的 comput 函数*/*把 x 到 y 的字符串表示为 expr 型返回*/expr q1=0,q2=0; if(cequalky=) & left(k,y)=x)comput(k,x+1,y-1,bak); return;/*如果式子被括号，返回括号内式子*/if(l=find(k,x,y,+,-)=0) l=find(k,x,y,*,*); if(l=0) l=find(k,x,y,);if(l=0)if(cequalkx=a)/*找优先级最低的运算符*/*没有运算符（叶节点）*/*当为变量 a 时*/(*bak).maxtime=1;(*bak).coe1=1; return;for(i=x;i=y;i+) (*bak).coe0*=10; (*bak).c