- 首页
- 教学资源
- 课后总结
- 教学研讨
- 备课资源
NOIP2009普及组解题报告
作者:张恩权 发表时间:2016年9月28日 浏览量:8 分享到空间
NOIP2009普及组解题报告
一、 多项式输出
题目大意:给出一元n次多项式的各项系数,按规则输出多项式。
本题属于比较简单的模拟类题目,但是细节比较繁琐,考虑不周容易丢分。
首先,要找到系数非0的最高次项,然后从它开始判断处理。
while a[n]=0 do dec(n);
对于剩余下来的每一项,要考虑一下几个部分:要不要这一项、符号、系数、x、指数。
要不要这一项:
a[i]=0 continue 进入下一次循环
符号:
a[i]>0且( i≠k ) 输出“+”
a[i]<0 输出“-”
系数:
abs(a[i]) ≠ 1 或者 ( i = 0 ) 输出abs(a[i])
x:
i > 0 输出“x”
指数:
i >1 输出“^”和i
(因为题目中提到an≠0,也就是说不需要考虑所有系数全为0的情况)
参考程序:
program poly;
const maxn=100;
var
a:array[0..maxn] of longint;
n,i:longint;
begin
assign(input,'poly.in'); reset(input);
assign(output,'poly.out'); rewrite(output);
readln(n);
for i:= n downto 0 do
read(a[i]);
readln;
while (a[n]=0 ) do dec(n);
for i:= n downto 0 do
begin
if a[i]=0 then continue;
if (a[i]>0 ) and (i<>n) then write('+');
if (a[i]<0) then write('-');
if (abs(a[i])<> 1) or (i=0) then write(abs(a[i]));
if (i>0) then write('x');
if (i>1) then write('^',i);
end;
writeln;
close(input); close(output);
end.
二、 分数线划定
本题主要考查选手双关键字的排序,一般对于多关键字排序,我所采用的方法是定义一个记录,再写一个比较函数。
本题中一个选手有两项信息报名号和笔试成绩。
Student = record num,score end;
比较函数cmp(a,b:student),如果排序后a应该在b前面则返回-1,如果a应该在b后面则返回1,如果a和b完全一样则返回0,可通过如下方法实现:
function cmp(a,b:student):integer;
begin
if a.score>b.score then exit(-1);
if a.score<b.score then exit(1);
if a.num<b.num then exit(-1);//程序执行到此处,必然有a.score=b.score
if a.num>b.num then exit(1);
exit(0);//程序执行到此处,必然有a.score=b.score a.num=b.num
end;
有了这个比较函数,就不需要在排序算法里写很长的条件表达式。利用比较函数的快排算法见参考程序。
排完序后,计算出m=trunc( m*1.5), 但考虑到第m个人的分数可能和后面的分数相等,所以还需要将m后移,直到第m个人的分数不等于第m+1个人的分数(或者m=n即m已经是最后一人)。
参考程序:
program score;
const
maxn=5000;
type
student = record
num,score:longint;
end;
var
s:array[1..maxn] of student;
n,m,i,k:longint;
function cmp(a,b:student):integer; //比较函数
begin
if a.score>b.score then exit(-1);
if a.score<b.score then exit(1);
if a.num<b.num then exit(-1);
if a.num>b.num then exit(1);
exit(0);
end;
procedure qsort(m,n:longint); //快排
var
i,j:longint;
k,t:student; // 中间值和交换的辅助变量都为记录类型student
begin
i:=m; j:=n; k:=s[(m+n) div 2];
repeat
while cmp(s[i],k)<0 do inc(i);
while cmp(s[j],k)>0 do dec(j); //与普通快排差异仅此而已
if (i<=j) then
begin
t:=s[i]; s[i]:=s[j]; s[j]:=t; inc(i); dec(j);
end;
until i>j;
if (m<j) then qsort(m,j);
if (i<n) then qsort(i,n);
end;
begin
assign(input,'score.in'); reset(input);
assign(output,'score.out'); rewrite(output);
readln(n,m);
for i:=1 to n do
with s[i] do
readln(num,score);
qsort(1,n);
m:= trunc( m*1.5);
k:=s[m].score;
while (s[m].score=k) and (m<=n) do inc(m); //将m后移
dec(m);
writeln(k,' ',m);
for i:= 1 to m do
with s[i] do
writeln(num,' ',score);
close(input); close(output);
end.
三、 细胞分裂
题目大意:给定数列s1…sn和两个整数m1、m2,求一个最小的x使得某个si满足。根据数论的知识我们可以得出这么一个结论:任意一个大于1的整数可以表示成若个素数的积。
a=××…×
b=××…×
(p1…pn均为素数)
例如:18= 21×32×50×70×……
如果a mod b =0,那么必然有a1≥b1,a2≥b2,…,an≥bn。
我们可以先求出m1的素因子表ss[i]和该素因子使用的次数num[i],该列表的长度len<log2 m1(为什么?最坏情况每个素数只用1次且每个素数均≥2)。
对于的素因子列表又会是什么样?完全等同于m1的素因子表,仅仅只是每个素因子使用次数变成了num[i] ×m2。
对于某个s[i],如果它不能整除m1的素因子表中的任何一个,s[i]的任何次方也必然不能整除m1,当然更不能整除。
如果s[i]x能整除,如何求出这个最小的x。
对于的素因子表ss[i]和使用次数num[i], 假设s[i]中包含ss[i]的个数为ci(这个可以在log2s[i]的时间内求出),为了使s[i]x能整除,必然要满足ci×x ≥ num[i]。
例如:
m1=24,m2=2,s[1]=30,s[2]=12; (这个数据不同于试题样例)
m1的素因子表为:
ss[i] |
2 |
3 |
num[i] |
3 |
1 |
的素因子表为:
ss[i] |
2 |
3 |
num[i] |
6 |
2 |
对于s[1]=30, 其包含素因子2的数量为1,为了满足s[1]x mod =0,x至少为6;其包含素因子3的数量为1,为了满足s[1]x mod =0,x至少为2。所以对于s[1],x应该为6。
对于s[1]=12, 其包含素因子2的数量为2,为了满足s[1]x mod =0,x至少为3;其包含素因子3的数量为1,为了满足s[1]x mod =0,x至少为2。所以对于s[1],x应该为3。
所以最终答案为3。
参考程序:
program cell;
const
maxn=20;
var
n,m1,m2,si,i,j,k,ans,t,len,x,c:longint;
ss,num,a:array[1..maxn] of longint;
flag:boolean;
begin
assign(input,'cell.in'); reset(input);
assign(output,'cell.out'); rewrite(output);
readln(n);
readln(m1,m2);
fillchar(num,sizeof(num),0);
len:=0; k:=2;
while (m1>1) do //求m1的素因子表
begin
if m1 mod k =0 then
begin
inc(len); ss[len]:=k;
while (m1 mod k = 0 ) do
begin
inc(num[len]);
m1:= m1 div k;
end;
end;
inc(k);
end;
for i:= 1 to len do // 的素因子表仅是m1素因子表中各数量乘m2
num[i]:=num[i]*m2;
ans:=maxlongint;
for i :=1 to n do
begin
read(k);
flag:=true; // flag记录k中包不包含m1的所有素因子,
t:=0; // t记录对于kx mod =0的最小x
for j:= 1 to len do
begin
if k mod ss[j]<>0 then // k中如不含的某个素因子,直接跳出
begin
flag:=false; break;
end;
c:=0;//c记录k中包含的素因子ss[j]的数量
while ( k mod ss[j]= 0) do
begin
inc(c); k:= k div ss[j];
end;
x:=num[j] div c; if (x*c <num[j])then inc(x);
//x记录对于ss[j],最小的x满足kx mod ss[j] =0
if (x>t) then t:=x;
end;
if flag and (t<ans) then ans:=t;
end;
if ans= maxlongint then
writeln('-1')
else writeln(ans);
close(input); close(output);
end.
四、 道路游戏
本题是一道动态规划题目,可以按照时间来划分阶段,记f(i)表示前i时刻可以取得的最多金币,则f(i)= max{ f(x)- cost(k) + sum(k,x+1,i) | i-p≤x<i,1≤i≤m,0≤k<n } ,意思就是枚举中间点x,x+1时刻在路k买车(即机器人),一直让它跑到i时刻能获得金币sum(k,x+1,i),用f(x)-cost(k)+sum(k,x+1,i)更新f[i]。
(为了程序方便,将工厂和路的编号转换为从0开始,即0~n-1),cost(k)表示在k号工厂购买车的价格,sum(k,x+1,i)表示在k号工厂买车从x+1时刻到i时刻能获得的金币。首先要与处理出sum[i,j],sum[i,j]表示第1时刻从i号路出发,到j时刻能获得的金币sum[i,j]=sum[i,j-1]+money[i, (i+j-1) mod n](sum[i,0]=0,其中money[x,y]表示第y时刻在x号路能获得的金币),那么sum(k,x+1,i)=sum[(x+1-(i-1) + n*n) mod n , i]-sum[(x+1-(i-1) + n*n) mod n , x],如此一来,便把环形路变成了直线路。
总的时间复杂度为O(nmp),只能通过90%的数据。如何进一步优化?
f(x)-cost(k)+sum(k,x+1,i) = f(x)-cost(k)+sum(k,1,i)-sum(k,1,x);
对于f(i),在新车在x时刻从路k出发,sum(k,1,i)是一个固定值,记函数val(x) = f(x) - cost(k) - sum(k,1,x),那么在i时刻,假设在新位置再买车,可以产生一个新的val(i)=f(i-1)-cost(k’)-sum(k’,1,i-1)。假设前面产生val是一个降序的,那么我们可以val(i)插入到里面,形成一个新的降序序列,同时记录val(i)产生的时刻time(i),:
val(1)>val(2)>…>val(j)>val(i)>val(j+1)>…
我们可以发现,val(i)之后的val( )不可能比val(i)产生更优的解,也就是说val(i)之后的val( )就不再需要了,那么在插入val(i)时就可以直接删除val(i)之后的val( )和它的time( ),如此一来,time( )必然构成了一个升序序列。如果val(1)产生的时刻time(1)如果能满足p的限制,那么f(i)的最优解必然由val(1)产生(这里只考虑从一条路出发),否则往后枚举,最早满足p限制的val(j)就是使产生f(i)最优解的val( )。
可以为每条路设两个单调队列,val()用来维护f(x) - cost(k) - sum(k,1,x) , time( )用来维护val(i)产生的时刻。结合二分查找,总时间复杂度为O(nmlog2p)
参考程序:
program game;
const
maxn=1000;
type
eque= record//队列
val:array[0..maxn] of longint;// f(x) - cost(k) - sum(k,1,x)的值
time:array[0..maxn] of longint;//对应val产生的时刻
h,r:longint;//队列头指针和尾指针
end;
var
pos,sum,money:array[0..maxn,0..maxn] of longint;//pos[i,j]表示从1时刻从i号路出发,j时刻所在的路
f,cost:array[0..maxn] of longint;
fact:array[0..maxn] of eque;//为每条路添加的队列
n,m,p,i,j,k:longint;
function findval(h,r,k,c:longint):longint;//在fact[c].val的h~r区间内查找k
var
mid:longint;
begin
while h<=r do
begin
mid:=(h+r) div 2;
if fact[c].val[mid]=k then exit(mid);
if fact[c].val[mid]>k then
h:=mid+1
else r:=mid-1;
end;
exit(h);
end;
function findtime(h,r,k,c:longint):longint;// 在fact[c].time的h~r区间内查找k
var
mid:longint;
begin
while h<=r do
begin
mid:=(h+r) div 2;
if fact[c].time[mid] =k then exit(mid);
if fact[c].time[mid]>k then
r:=mid-1
else h:=mid+1;
end;
exit(h);
end;
begin
assign(input,'game.in');reset(input);
assign(output,'game.out');rewrite(output);
readln(n,m,p);
for i:=0 to n-1 do
begin
for j:= 1 to m do
read(money[i,j]);
readln;
end;
for i:= 0 to n-1 do
read(cost[i]);
readln;
fillchar(sum,sizeof(sum),0);
for i:=0 to n-1 do//预处理sum和pos
for j:= 1 to m do
begin
sum[i,j]:= sum[i,j-1]+money[(i+j-1) mod n ,j];
pos[i,j]:=(i+j-1) mod n;
end;
for i:= 0 to n-1 do//处理第1时刻
with fact[i] do
begin
h:=0; r:=0; val[0]:=-cost[i];
time[0]:=1;
if val[0]+sum[i,1]>f[1] then f[1]:=val[0]+sum[i,1];
end;
for i:= 2 to m do
begin
for j:= 0 to n-1 do
begin
with fact[j] do
begin
k:= f[i-1]- sum[j,i-1]-cost[pos[j,i]];
r:=findval(h,r,k,j);
val[r]:=k; time[r]:=i; //维护递减队列val
h:=findtime(h,r, i-p+1, j);
//因为有p的限制,在递增队列time中寻找第一个i-time[h]<p的元素
if val[h]+sum[j,i]>f[i] then f[i]:=val[h]+sum[j,i];//用队列头元素更新f[i]
end;
end;
end;
writeln(f[m]);
close(input);close(output);
end.