NOIP提高组复赛题解.docx
- 文档编号:18508173
- 上传时间:2023-08-19
- 格式:DOCX
- 页数:29
- 大小:19.53KB
NOIP提高组复赛题解.docx
《NOIP提高组复赛题解.docx》由会员分享,可在线阅读,更多相关《NOIP提高组复赛题解.docx(29页珍藏版)》请在冰点文库上搜索。
NOIP提高组复赛题解
1、潜伏者
programspy;
var
v:
array['A'..'Z']ofboolean;
p,q:
array['A'..'Z']ofchar;
a,b:
string;
j:
char;
i:
integer;
procedurestop;
begin
writeln('Failed');
close(input);
close(output);
halt;
end;
begin
assign(input,'spy.in');
reset(input);
assign(output,'spy.out');
rewrite(output);
readln(a);
readln(b);
fillchar(v,sizeof(v),0);
fori:
=1tolength(a)do
begin
v[a[i]]:
=true;
p[a[i]]:
=b[i];
q[b[i]]:
=a[i];
end;
forj:
='A'to'Z'do
ifnotv[j]thenstop;
fori:
=1tolength(a)do
begin
ifp[a[i]]<>b[i]thenstop;
ifq[b[i]]<>a[i]thenstop;
end;
readln(a);
fori:
=1tolength(a)do
write(p[a[i]]);
writeln;
close(input);
close(output);
end.
2、Hankson的趣味题
思路1:
根据最大公约数的定义,X必定为最大公约数的倍数,那么我们可以去枚举a1的倍数,然后去验证最大公约数和最小公倍数是否符合条件。
期待分数:
50。
程序1:
var
a0,a1,b0,b1,i,j,n,k,x,tot:
longint;
functiongcd(a,b:
longint):
longint;
begin
ifb=0thenexit(a)elseexit(gcd(b,amodb));
end;
begin
readln(n);
fork:
=1tondo
begin
tot:
=0;
readln(a0,a1,b0,b1);
fori:
=1to(b1diva1)do
begin
x:
=i*a1;
ifb1modx=0then
ifgcd(a0,x)=a1then
if(b0*x)div(gcd(b0,x))=b1thenbegininc(tot);end;
end;
writeln(tot);
end;
end.
思路2:
根据最小公倍数和最大公约数分解质因数指数的特殊关系进行优化。
比如两个数,分解质因数可以得到以下的式子
A=p1^a1+p2^a2+p3^a3……
B=p1^b1+p2^b2+p3^a3……
例如6和21就可以分解成
6=2^1+3^1+5^0+7^0……
21=2^0+3^1+5^0+7^1……
则最大公约数=2^(min(a1,b1))+3^(min(a2,b2))+5^(min(a3,b3))+7^(min(a4,b4))…
最小公倍数=2^(max(a1,b1))+3^(max(a2,b2))+5^(max(a3,b3))+7^(max(a4,b4))…
那么我们可以先将b1分解质因数,在根据最大公约数和最小公倍数在指数上的关系,进行搜索。
期待分数:
100
程序2:
var
p,x,c:
array[0..1000]oflongint;
a0,a1,b0,b1,i,j,k,m,tot,t,n:
longint;
functiongcd(a,b:
longint):
longint;
begin
ifb=0thenexit(a)elseexit(gcd(b,amodb));
end;
proceduredfs(i,sum:
longint);
var
max,j:
longint;
begin
ifi>mthen
begin
inc(tot);
p[tot]:
=sum;
exit;
end;
max:
=sum;
dfs(i+1,max);
forj:
=1toc[i]do
begin
max:
=max*x[i];
dfs(i+1,max);
end;
end;
procedurework(b:
longint);
vari,p:
longint;
begin
i:
=2;
p:
=b;
whilei<=sqrt(p)do
begin
ifpmodi=0then
begin
inc(m);
x[m]:
=i;
c[m]:
=0;
repeat
inc(c[m]);
p:
=pdivi;
untilpmodi<>0;
end;
inc(i);
end;
ifp<>1then
begin
inc(m);
x[m]:
=p;
c[m]:
=1;
end;
dfs(1,1);
end;
begin
readln(n);
fori:
=1tondo
begin
readln(a0,a1,b0,b1);
fillchar(p,sizeof(p),0);
fillchar(x,sizeof(x),0);
fillchar(c,sizeof(c),0);
m:
=0;
tot:
=0;
t:
=0;
work(b1);
forj:
=1tototdo
if(gcd(p[j],a0)=a1)and((p[j]divgcd(p[j],b0)*b0)=b1)theninc(t);
writeln(t);
end;
end.
思路三:
和思路二有异曲同工之妙。
我们可以先预处理trunc(sqrt(2000000000))以内的质数,然后每读入一组数据,初始答案ans=1,然后我们循环质数,看a0、a1、b0、b1里面有多少个该质数因子,并且将这四个数分别消去所有该质数因子。
我们设求出来的该因子个数分别是t1、t2、t3、t4。
如果数据合法,那么t1>=t2,t3<=t4。
根据最大公约数和最小公倍数的定义,我们要求的数所拥有的该质因子个数s必须要同时满足以下限制条件:
若t1>t2,则s=t2
若t1=t2,则s>=t2
若t3 若t3=t4,则s<=t4 这样,我们或者求出了s的范围,要么证明了不存在合法数字。 如果s存在合法取值,我们就将ans乘上s的合法取值个数,否则直接输出0。 注意: 如果循环结束后,a0>1或b1>1,那么此时a0或b1一定是超过我们枚举的数字范围的质数。 这时我们特殊判断一下就行了。 我们的时间复杂度是循环质数复杂度+分解因数复杂度。 分解因数最坏是该数为2的若干次方,所以复杂度的上限是log(2000000000),很小。 最慢的点在0.3秒以内出解。 程序3 programson; vari,j,k,l,m,n,p,q,l2,r2,r,s,t,a0,a1,b0,b1,ans: longint; prime: array[0..60000]oflongint; need: array[0..60000]oflongint; pd: boolean; functionpri(x: longint): boolean; varg: longint; begin forg: =2totrunc(sqrt(x))do ifxmodg=0thenexit(false); exit(true); end; begin p: =1;prime[1]: =2; fori: =3to50000doifpri(i)then begin inc(p); prime[p]: =i; end; read(n); fort: =1tondo begin read(a0,a1,b0,b1); ans: =1; fillchar(need,sizeof(need),255); q: =p; pd: =true; fori: =1topdo begin l: =0;r: =0;l2: =0;r2: =0; whilea0modprime[i]=0do begin inc(l);a0: =a0divprime[i]; end; whilea1modprime[i]=0do begin inc(r);a1: =a1divprime[i]; end; whileb0modprime[i]=0do begin inc(l2);b0: =b0divprime[i]; end; whileb1modprime[i]=0do begin inc(r2);b1: =b1divprime[i]; end; ifl>rthenneed[i]: =r; ifl2 begin if(need[i]>-1)and(need[i]<>r2)then begin pd: =false;break; end; need[i]: =r2; end; ifneed[i]=-1then ifr2 begin pd: =false;break; endelseans: =ans*(r2-r+1); end; ifi=pthen ifa0>1then begin inc(i);prime[i]: =a0; l: =0;r: =0;l2: =0;r2: =0; whilea0modprime[i]=0do begin inc(l);a0: =a0divprime[i]; end; whilea1modprime[i]=0do begin inc(r);a1: =a1divprime[i]; end; whileb0modprime[i]=0do begin inc(l2);b0: =b0divprime[i]; end; whileb1modprime[i]=0do begin inc(r2);b1: =b1divprime[i]; end; ifl>rthenneed[i]: =r; ifl2 begin if(need[i]>-1)and(need[i]<>r2)then begin pd: =false; end; need[i]: =r2; end; ifneed[i]=-1then ifr2 begin pd: =false; endelseans: =ans*(r2-r+1); dec(i); end; ifi=pthen ifb1>1then begin inc(i);prime[i]: =b1; l: =0;r: =0;l2: =0;r2: =0; whilea0modprime[i]=0do begin inc(l);a0: =a0divprime[i]; end; whilea1modprime[i]=0do begin inc(r);a1: =a1divprime[i]; end; whileb0modprime[i]=0do begin inc(l2);b0: =b0divprime[i]; end; whileb1modprime[i]=0do begin inc(r2);b1: =b1divprime[i]; end; ifl>rthenneed[i]: =r; ifl2 begin if(need[i]>-1)and(need[i]<>r2)then begin pd: =false; end; need[i]: =r2; end; ifneed[i]=-1then ifr2 begin pd: =false; endelseans: =ans*(r2-r+1); dec(i); end; ifnotpdthenwriteln(0)elsewriteln(ans); end; end. 程序4 programson; var p,x,c: array[1..10000]oflongint; n,m,t,i,j,k,a0,a1,b0,b1: longint; functiongcd(m,n: longint): longint; var r: longint; begin whilen<>0do begin r: =mmodn; m: =n; n: =r; end; gcd: =m; end; proceduredfs(consti: longint;s: longint); var j: longint; begin ifi>mthen begin inc(k); p[k]: =s; exit; end; dfs(i+1,s); forj: =1toc[i]do begin s: =s*x[i]; dfs(i+1,s); end; end; procedureget(b: longint); var i: longint; begin m: =0; i: =2; whilei<=sqrt(b)+1e-6do begin ifbmodi=0then begin inc(m); x[m]: =i; c[m]: =0; repeat inc(c[m]); b: =bdivi; untilbmodi<>0; end; inc(i); end; ifb<>1then begin inc(m); x[m]: =b; c[m]: =1; end; k: =0; dfs(1,1); end; begin assign(input,'son.in'); reset(input); assign(output,'son.out'); rewrite(output); read(n); fori: =1tondo begin read(a0,a1,b0,b1); get(b1); t: =0; forj: =1tokdo if(gcd(p[j],a0)=a1)and(p[j]divgcd(p[j],b0)*b0=b1)then inc(t); writeln(t); end; close(input); close(output); end. 3、最优贸易 两次SPFA,用a[i]表示从起点开始到i结点能经过的最小值,用b[i]表示从终点延反向边到达i结点能经过的最大值。 Ans=max(b[i]-a[i])。 const maxn=100010; maxm=1000010; type data=record t,f,next: longint; end; var n,m,ls: longint; a,c,d,stack,v: array[0..maxn]oflongint; f: array[1..maxn]ofboolean; seg: array[1..maxm]ofdata; procedureinsert_e(s,t,f1,f2: longint); begin inc(ls); seg[ls].t: =t; seg[ls].f: =f1; seg[ls].next: =a[s]; a[s]: =ls; inc(ls); seg[ls].t: =s; seg[ls].f: =f2; seg[ls].next: =a[t]; a[t]: =ls; end; procedureinit; var i,j,k,l: longint; begin readln(n,m); fillchar(a,sizeof(a),255); ls: =0; fori: =1tondoread(v[i]); fori: =1tomdo begin readln(j,k,l); ifl=1theninsert_e(j,k,1,2) elseinsert_e(j,k,3,3); end; end; functionmax(a,b: longint): longint; begin ifa>bthenexit(a)elseexit(b); end; functionmin(a,b: longint): longint; begin ifa end; procedurespfa1; var i,k,open,closed: longint; begin fillchar(c,sizeof(c),127); fillchar(f,sizeof(f),0); f[1]: =true; open: =0; closed: =1; stack[1]: =1; c[1]: =v[1]; whileopen begin inc(open); k: =stack[openmodmaxn]; f[k]: =false; i: =a[k]; whilei<>-1do begin if(seg[i].fand1=1)and(min(c[k],v[seg[i].t]) begin c[seg[i].t]: =min(c[k],v[seg[i].t]); ifnotf[seg[i].t]then begin f[seg[i].t]: =true; inc(closed); stack[closedmodmaxn]: =seg[i].t; end; end; i: =seg[i].next; end; end; end; procedurespfa2; var i,k,open,closed: longint; begin fillchar(d,sizeof(d),0); fillchar(f,sizeof(f),0); f[n]: =true; open: =0; closed: =1; stack[1]: =n; d[n]: =v[n]; whileopen begin inc(open); k: =stack[openmodmaxn]; f[k]: =false; i: =a[k]; whilei<>-1do begin if(seg[i].fand2=2)and(max(d[k],v[seg[i].t])>d[seg[i].t])then begin d[seg[i].t]: =max(d[k],v[seg[i].t]); ifnotf[seg[i].t]then begin f[seg[i].t]: =true; inc(closed); stack[closedmodmaxn]: =seg[i].t; end; end; i: =seg[i].next; end; end; end; proceduremain; var i,ans: longint; begin spfa1; spfa2; ans: =0; fori: =1tondo ans: =max(ans,d[i]-c[i]); writeln(ans); end; begin assign(input,'trade.in'); reset(input); assign(output,'trade.out'); rewrite(output); init; main; close(input); close(output); end. 程序2: programtrade; const maxn=100005; var e1,e2: array[1..1000010]ofrecord t,next: longint; end; a,b,g1,g2,q: array[1..maxn]oflongint; v: array[1..maxn]ofboolean; n,i,f,r,k,p,s: longint; procedureinit; var m,s,i,j,k,z: longint; procedurelink(consti,j: longint); begin inc(s); withe1[s]do begin t: =j; next: =g1[i]; end; g1[i]: =s; withe2[s]do begin t: =i; next: =g2[j]; end; g2[j]: =s; end; begin read(n,m); fori: =1tondoread(b[i]); fillchar(g1,sizeof(g1),0); fillchar(g2,sizeof(g2),0); s: =0; fork: =1tomdo begin read(i,j,z); link(i,j); ifz=2thenlink(j,i); end; end; begin assign(input,'trade.in'); reset(input); assign(output,'trade.out'); rewrite(output); init; fillchar(v,sizeof(v),0); a[1]: =b[1]; fori: =2tondoa[i]: =100000; f
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- NOIP 提高 复赛 题解