noip2009普及组复赛解题报告
多项式输出
问题转述：
给出一个一元多项式各项的次数和系数，按照规定的格式要求输出该多项式。
分析：
普及组的水题。多项式大家应该很熟悉，输出的时候注意一下几点即可：
1. 最高次项为正的话开头无加号。
2. 系数为0不输出。
3. 一次项输出x，并非x^1。
4. 非常数项系数为1或-1时直接输出正负号，但是常数项需要输出该数字。
其中除第三项外其它均可在样例中检查出错误，但是若没想到第三点那么就只能得到50分了。
程序：
var i,k,n:longint;
begin
assign(input,'poly.in');reset(input);
assign(output,'poly.out');rewrite(output);
readln(n);
for i:=n downto 0 do
begin
read(k);
if k=0 then continue;
if (k>0) and (in) then write('+');
if i=0 then write(k)
else if (abs(k)1) then write(k) else if k=-1 then write('-');
if i0 then
if i=1 then write('x')
else write('x^',i);
end;
writeln;
close(input);
close(output);
end.
2009-11-28 12:03 回复
自杀猫
0位粉丝
3楼
分数线划定
问题转述：
给出录取人数及所有面试者成绩，考号。求出分数线和实际录取人数，并按成绩降序，若成绩相同则考号升序的规则输出录取人考号与成绩。
分析：
双关键字排序。由于n在5000左右，为了确保不TLE所以需要使用快排等nlogn的排序。之后将指针指向计划录取的最后一名，并滑动至与其相同分数的最后一人。则指针之前为实际录取的面试者。
程序：
type arr=array[1..2] of longint;
var i,j,n,m:longint;
a:array[1..5001] of arr;
procedure swap(var a,b:arr);
var c:arr;
begin
c:=a;a:=b;b:=c;
end;
procedure qsort(l,r:longint);
var i,j,temp1,temp2:longint;
begin
i:=l;j:=r;temp1:=random(r-l+1)+l;
temp2:=a[temp1,2];temp1:=a[temp1,1];
repeat
while (a[i,1]>temp1) or ((a[i,1]=temp1) and (a[i,2]<temp2)) do inc(i);
while (a[j,1]temp2)) do dec(j);
if i<=j then
begin
swap(a[i],a[j]);
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;
begin
randomize;
assign(input,'score.in');reset(input);
assign(output,'score.out');rewrite(output);
readln(n,m);
m:=trunc(m*1.5);
for i:=1 to n do readln(a[i,2],a[i,1]);
a[n+1,1]:=0;
qsort(1,n);
i:=m;
while a[i+1,1]=a[i,1] do inc(i);
writeln(a[i,1],' ',i);
for j:=1 to i do
writeln(a[j,2],' ',a[j,1]);
close(input);close(output);
end.
2009-11-28 12:04 回复
自杀猫
0位粉丝
4楼
细胞分裂
问题转述：
给出m1，m2以及若干个个si，求si^a mod m1^m2=0中a的最小值。若无解，输出-1。
分析：
数学题。由于m1<=30000,m2<=10000，根本无法直接计算，所以需要通过数学分析得出答案。如果一个数能够整除另一个数，那么这个数因数分解后一定有另一个数所有的元素，且每个元素个数均大于等于另一个数相同元素的个数。因此我们可以先对m1进行因数分解，并将对应元素的个数乘以m2。之后读入每个数，判断该数因数分解后是否有m1中所有的元素。如果有的话，则计算该细胞最大的分裂次数，即对应m1种元素个数/si中元素个数后向上取整。最后更新答案即可。
注意因数分解中1比较特殊，所以要单独判断一下。
程序：
type arr=array[1..30000,1..2] of longint;
var ans,g,i,k,n,m1,m2,total:longint;
a:arr;
procedure factorization(k:longint;var a:arr;var link:longint);
var i:longint;
begin
i:=1;
link:=0;
repeat
inc(i);
if k mod i=0 then
begin
inc(link);
a[link,1]:=i;
a[link,2]:=0;
while k mod i=0 do
begin
inc(a[link,2]);
k:=k div i;
end;
end;
until k=1;
end;
procedure main;
var i,z,max:longint;
begin
max:=-1;
read(k);
for i:=1 to total do
begin
if k mod a[i,1]0 then exit;
z:=0;
while k mod a[i,1]=0 do
begin
inc(z);
k:=k div a[i,1];
end;
if (a[i,2]+z-1) div z>max then max:=(a[i,2]+z-1) div z;
end;
if max<ans then ans:=max;
end;
begin
assign(input,'cell.in');reset(input);
assign(output,'cell.out');rewrite(output);
ans:=maxlongint;
readln(n);
readln(m1,m2);
if m1=1 then begin writeln(0);close(input);close(output);halt;end;
factorization(m1,a,total);
for i:=1 to total do a[i,2]:=a[i,2]*m2;
for i:=1 to n do
main;
if ans=maxlongint then writeln(-1) else writeln(ans);
close(input);
close(output);
end.
2009-11-28 12:05 回复
自杀猫
0位粉丝
5楼
道路游戏
问题转述：
有一条环形路，路上有n个点，第i个点和第i+1个点有边相连（第n个点与第1个点有边相连）。每个点都可以花费不同的代价生产一个机器人，且机器人可以顺时针走不多于p步（每走一步消耗一单位时间），并捡起此时路上的金币。最多只能有一个机器人存在于路上。不同的时间每条路上金币数不同。求最后能够得到的最大金币数。（即捡起的金币数减去生产机器人需要的金币数）。
分析：
题目描述极其恶心，整理好思绪之后便应该能想出本题是动态规划。由于高达1000的m，n，所以只能设计时间复杂度为O(mn)的动规。此类问题的动规模型比较好想，即：
其中f[i,j]为i时间在j点上得到的最大金币数。Coin[i,j]为i时间j号路得金币数。Cost[k]代表在k点购买机器人花费的金币数。其中1<=k<=n。step[i,j]代表f[i,j]的状态时机器人已经走的步数。past[j]为j之前的点。即past[i]=i-1(2<=i<=n) past[1]=n。
注意这个动规是三维的，但是因为上一阶段的最优值是不变的，所以我们只需要在计算本阶段的最优值之后顺便保存一个最大的，作为下一阶段的上一阶段最优值即可。
程序：
var i,j,k,n,m,p,pastmax,nowmax:longint;
coin,f,step:array[0..1000,0..1000] of longint;
cost,past:array[1..1000] of longint;
begin
assign(input,'game.in');reset(input);
assign(output,'game.out');rewrite(output);
filldword(step,sizeof(step) shr 2,maxlongint);
readln(n,m,p);
for i:=2 to n do
past[i]:=i-1;
past[1]:=n;
for i:=1 to n do
for j:=1 to m do
read(coin[j,i]);
for i:=1 to n do read(cost[i]);
pastmax:=0;
for i:=1 to m do
begin
nowmax:=-maxlongint;
for j:=1 to n do
begin
if step[i-1,past[j]]<p then
begin
if pastmax-cost[past[j]]>f[i-1,past[j]]
then begin step[i,j]:=1;f[i,j]:=pastmax-cost[past[j]]+coin[i,past[j]];end
else begin step[i,j]:=step[i-1,past[j]]+1;f[i,j]:=f[i-1,past[j]]+coin[i,past[j]];end;
end
else begin step[i,j]:=1;f[i,j]:=pastmax-cost[past[j]]+coin[i,past[j]];end;
if f[i,j]>nowmax then nowmax:=f[i,j];
end;
pastmax:=nowmax;
end;
writeln(nowmax);
close(input);
close(output);
end.
Problem 1: poly 多项式输出
【分析】
简单的字符串处理题目，注意处理系数为-1,1,0的项，以及多项式的一次项不需给出次数（注意：样例中并没有带一次项的数据）.故而只需分类讨论n,2..n-1,1,0项即可.
Problem 2: score 分数线划定
【分析】
本题和NOIP 2007的奖学金思路一致，同样是简单的排序题目.考虑到n<=5000，故而直接使用冒泡排序即可.当然，为了保险起见使用快速排序也未尝不可.
Problem 3: cell 细胞分裂
【分析】
仔细读题后可以发现，本题的实质就是求 中t的最小值.这样一来，我们可以直接使用高精度算法来枚举t的最小值.但高精度算法却不能处理任何细胞都不满足要求的情况.故而，我们需要进行简单的数学分析.
通过观察得知，如果i细胞可以满足情况时，那么 有的质因数， 也一定有.反之，若 有的质因数，没有，则i细胞不能满足情况.而 的充要条件就是 中质因数的次数大于等于 中相同的质因数的次数.至此，题意分析完毕.
接下来，我简单的说一下算法的实现过程：
（1） 构造一个1..30000的质数表，来分解质因数.
（2） 注意 的特殊情况，此时任何 都能整除 ，故而直接输出0.
（3） 分解 ，建立一个m数组储存分解结果.
（4） 分解 ,然后递增t，直到 .这里有个优化，其实分解 时只需处理 中有的质因数，同样，枚举t的时候也只需处理 中有的质因数.此外，还需要设置一个变量处理 中的质因数>30000的情况，一种较为简单的方法是对比每次 的值，连续两次相等则退出.
（5） 输出最终结果.
第四题我也不知道。
Problem 1: poly 多项式输出
【分析】
简单的字符串处理题目，注意处理系数为-1,1,0的项，以及多项式的一次项不需给出次数（注意：样例中并没有带一次项的数据）.故而只需分类讨论n,2..n-1,1,0项即可.
【程序】
var
n,i,j:integer;
a:array[1..100] of integer;
begin
readln(n);
for i:=n downto 0 do read(a[i]);//读入
if abs(a[n])=1 then //处理n次项
if a[n]<0 then write('-x^',n)
else write('x^',n)
else
write(a[n],'x^',n);
for i:=n-1 downto 2 do //处理2..n-1次项
if a[i]<>0 then
if abs(a[i])=1 then //讨论系数为1的情况
if a[i]<0 then write('-x^',i)
else write('+x^',i);
else
if a[i]<0 then write(a[i],'x^',i)
else write('+',a[i],'x^',i);
if a[1]<>0 then //处理1次项
if abs(a[1])=1 then //讨论系数为1的情况
if a[1]<0 then write('-x')
else write('+x');
else
if a[1]<0 then write(a[1],'x')
else write('+',a[1],'x');
if a[0]<>0 then //处理0次项
if a[0]<0 then write(a[0])
else write('+',a[0]);
writeln;
end.
Problem 2: score 分数线划定
【分析】
本题和NOIP 2007的奖学金思路一致，同样是简单的排序题目.考虑到n<=5000，故而直接使用冒泡排序即可.当然，为了保险起见使用快速排序也未尝不可.
【程序】
var
n,m,i,j,p,p_:integer;//p:分数线;p_:进入面试人数;
k,s:array[1..5000] of integer;
procedure swap(var x,y:integer); //交换
var tmp:integer;
begin
tmp:=x;
x:=y;
y:=tmp;
end;
begin
readln(n,m);
for i:=1 to n do read(k[i],s[i]);
for i:=1 to n-1 do //冒泡排序（成绩降序，编号升序）
for j:=i+1 to n do
if (s[i]<s[j]) or ((s[i]=s[j]) and (k[i]>k[j])) then
{【交换条件】i的分数小于j的分数 或者 i,j分数相等，i的编号小于j的编号}
begin
swap(s[i],s[j]);
swap(k[i],k[j]);
end;
p:=trunc(m*1.5); //进入面试人数
p_:=s[p]; //分数线
while (s[p+1]=p_) do inc(p); //最终确定进入面试人数
writeln(p_,' ',p);
for i:=1 to p do writeln(k[i],' ',s[i]);
end.
Problem 3: cell 细胞分裂
【分析】
仔细读题后可以发现，本题的实质就是求 中t的最小值.这样一来，我们可以直接使用高精度算法来枚举t的最小值.但高精度算法却不能处理任何细胞都不满足要求的情况.故而，我们需要进行简单的数学分析.
首先分析样例：
样例1
样例2
2
3
1
0
0
1
列成表格后可以得到：
，
列成表格后可以得到：
2
3
5
3
1
0
1
1
1
2
1
0
通过观察得知，如果i细胞可以满足情况时，那么 有的质因数， 也一定有.反之，若 有的质因数，没有，则i细胞不能满足情况.而 的充要条件就是 中质因数的次数大于等于 中相同的质因数的次数.至此，题意分析完毕.
接下来，我简单的说一下算法的实现过程：
（1） 构造一个1..30000的质数表，来分解质因数.
（2） 注意 的特殊情况，此时任何 都能整除 ，故而直接输出0.
（3） 分解 ，建立一个m数组储存分解结果.
（4） 分解 ,然后递增t，直到 .这里有个优化，其实分解 时只需处理 中有的质因数，同样，枚举t的时候也只需处理 中有的质因数.此外，还需要设置一个变量处理 中的质因数>30000的情况，一种较为简单的方法是对比每次 的值，连续两次相等则退出.
（5） 输出最终结果.
【程序】
type
prime=array[1..3250] of word;
var
n,m1,m2,t,min,time,last,i,j:longint;
//t:30000以内的质数个数
//min:最短时间
//last:监视当前s[i]值，防止死循环
si:array[1..10000] of prime; //si[i]的质因数个数
s:array [1..10000] of longint;
p:array [1..3250] of 1..30000;//30000以内的质数表
m:prime;//m1^m2的质因数个数
flag:boolean;
function ok(x:integer):boolean;//判断s[x]与m1^m2是否含有相同质因数
begin
ok:=true;
for j:=1 to t do
if (m[j]<>0) and (si[x][j]=0) then exit(false);
end;
function ok(x,y:integer):boolean;//判断s[x]^y是否整除m1^m2
begin
ok:=true;
for j:=1 to t do
if (m[j]<>0) and (si[x][j]*y<m[j]) then exit(false);
end;
begin
fillchar(m,sizeof(m),0);
fillchar(si,sizeof(si),0);
readln(n);readln(m1,m2);
for i:=1 to n do read(s[i]);
p[1]:=2;p[2]:=3;t:=2;//用试除法构造30000以内质数表
for i:=4 to 30000 do
begin
flag:=true;
for j:=2 to trunc(sqrt(i))+1 do
if i mod j = 0 then
begin flag:=false;break;end;
if flag then
begin
inc(t);
p[t]:=i;
end;
end;
if m1=1 then //处理m1为1的特殊情况
begin
writeln(0);
halt;
end;
while m1<>1 do //分解m1^m2
for i:=1 to t do
if m1 mod p[i] = 0 then
begin
inc(m[i]);
m1:=m1 div p[i];
end;
for i:=1 to t do m[i]:=m[i]*m2;
flag:=false;min:=65535;
for i:=1 to n do
begin
time:=1;last:=0;
if s[i]=1 then continue;
while s[i]<>1 do //分解si[i]
begin
for j:=1 to t do
if (m[j] <> 0) and (s[i] mod p[j] = 0) then
begin
inc (si[i][j]);
s[i]:=s[i] div p[j];
end;
if last=s[i] then break;
last:=s[i];
end;
if ok(i) then //判断是否可以整除
begin
flag:=true;
while not ok(i,time) do inc(time);//递增time，直到整除为止
if time<min then min:=time;//计算最短时间
end;
end;
if flag then writeln(min) else writeln(-1);
end.
瞿虹治糜： 普及组:多项式输出问题转述:给出一个一元多项式各项的次数和系数,按照规定的格式要求输出该多项式.分析:普及组的水题.多项式大家应该很熟悉,输出的时候注意一下几点即可:1. 最高次项为正的话开头无加号.2. 系数为0不输出....
岳塘区19518174679： noip2009复赛请问已知x,a0的最大公约数为a1;x,b0的最小公倍数为b1,求x的可行个数的算法是怎样的?其数学思想是怎样的? - ？
瞿虹治糜：[答案] 现计算一个50000以内的素数表. 然后逐个搜索每个素因数,计算符合条件的个数Pi,最后将Pi乘起来. program no2; var a0,a1,b0,b1,t1,t2,q1,q2,bjless,bjmore:longint; sum,i,j,x1,x2:longint; a:array[0..10000] of longint; kq,n:longint; function ok(s:longint):...
岳塘区19518174679： 求2009noip复赛第一题潜伏者答案和详细讲解~~~ - ？
瞿虹治糜： 这种题目完全不要分类的——属于裸模拟题目.题目读懂了就行了.中心思想两步走:1、建立词典2、翻译这两步中任何一步出现错误都直接输出＂Failed＂然后细化到代码实践上:1、把第1、2行完整读入到两个字符串类型中2、建立2个数组...
岳塘区19518174679： NOIP2010普及组复赛(Pascal语言)第三、第四题解题报告及源代码? - ？
瞿虹治糜： typepos=recordd1,d2:qword;end; vara:array[1..100000]of pos;x1,x2,y1,y2,x,y:integer;n,i:longint;ans,max:qword; function f(k:longint):longint; vari:longint; beginf:=k;for i:=k+1 to n doif a[i].d2>=a[f].d2 then f:=i; end; procedure qsort(l,r:...
岳塘区19518174679： 谁能告诉我noip2009普及组的细胞分裂的解题思路??? - ？
瞿虹治糜： 总的来说就算是 分解质因数 由于m1<=30000,m2<=10000,根本无法直接计算,所以需要 通过数学分析得出答案.如果一个数能够整除另一个数,那么这个数因数分解后一定有另一个数所有的元素,且每个元素个数均大于等于另一个数相同元素的个数.因此我们可以先对m1进行因数分解,并将对应元素的个数乘以m2.之后读入每个数,判断该数因数分解后是否有m1中所有的元素.如果有的话,则计算该细胞最大的分裂次数,即对应m1种元素个数/si中元素个数后向上取整.最后更新答案即可.注意因数分解中1比较特殊,所以要单独判断一下.
岳塘区19518174679： noip2008复赛题目求noip2008普及组复赛解题报告 ？
瞿虹治糜： 全国信息学奥林匹克联赛(NOIP2008)复赛普及组一.题目概览中文题目名称 ISBN号码 排座椅 传球游戏 立体图英文题目名称 isbn seat ball drawing可执行文件名 isbn ...
岳塘区19518174679： 2008年noip普及组复赛题解 - ？
瞿虹治糜： 第一题:很水的送分题,可能对于刚刚接触OI的选手来说,处理字符串是一个难点,不妨用整体读入,用st-'0'[fly]的方法即可求出该位数字(C++写法,PASCAL有些忘记见谅,希望有人能够补充上).最后注意'X'即可获得满分 第二题:贪心....
岳塘区19518174679： noip2009普及组初赛讲解答案？
瞿虹治糜： NOIP2009初赛普及组(C语言、PASCAL语言)参考答案与评分标准 一、单项选择题:(每题1.5分) 1.D2.B3.A4.A5.B 6.D7.C8.B9.C10.D 11.C12.C13.B14.D15.D 16.B17.D18.A19.C20.B 二、问题求解:(共2题,每空5分,共计10分) 1.70 ...
岳塘区19518174679： NOIP竞赛 普及组Pascal的复赛如何准备,第一第二题怎么拿分 - ？
瞿虹治糜： 近几年的复赛题都比较简单,普及组前两题基本都是模拟算法.只要有扎实的功底,这些题都很容易拿分.1准备复赛可以做一下历年的复赛试题,并及时查缺补漏和总结.把近几年题目做熟也很利于第一二题拿分2做题时首先要弄清题意,如果...
岳塘区19518174679： NOIP2009普及组初赛三题4题 - ？
瞿虹治糜： 原题目确实有错误,标准答案为NPOI 附:关于NOIP2009初赛普及组Pascal语言一道题目的问题与阅卷处理意见 经查,NOIP2009 初赛普及组(Pascal版本)第四大题(阅读程序写结果)第4小题题 目中存在一处数据输入格式的错误:该题提供...
