tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 高考 >>

NOIP2009提高组复赛题解


1、潜伏者 program spy; var v: array['A'..'Z'] of boolean; p, q: array['A'..'Z'] of char; a, b: string; j: char; i: integer; procedure stop; 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); for i := 1 to length(a) do begin v[a[i]] := true; p[a[i]] := b[i]; q[b[i]] := a[i]; end; for j := 'A' to 'Z' do if not v[j] then stop; for i := 1 to length(a) do begin if p[a[i]] <> b[i] then stop; if q[b[i]] <> a[i] then stop; end; readln(a); for i := 1 to length(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; function gcd(a,b:longint):longint; begin if b=0 then exit(a) else exit(gcd(b,a mod b)); end; begin readln(n); for k:=1 to n do begin tot:=0; readln(a0,a1,b0,b1); for i:=1 to (b1 div a1) do begin x:=i*a1; if b1 mod x=0 then if gcd(a0,x)=a1 then if (b0*x) div (gcd(b0,x))=b1 then begin inc(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] of longint; a0,a1,b0,b1,i,j,k,m,tot,t,n:longint; function gcd(a,b:longint):longint; begin if b=0 then exit(a) else exit(gcd(b,a mod b)); end; procedure dfs(i,sum:longint); var max,j:longint; begin if i>m then begin inc(tot); p[tot]:=sum; exit; end; max:=sum; dfs(i+1,max); for j:=1 to c[i] do begin max:=max*x[i]; dfs(i+1,max); end; end; procedure work(b:longint); var i,p:longint; begin i:=2; p:=b; while i<=sqrt(p) do begin if p mod i=0 then begin inc(m); x[m]:=i; c[m]:=0; repeat

inc(c[m]); p:=p div i; until p mod i<>0; end; inc(i); end; if p<>1 then begin inc(m); x[m]:=p; c[m]:=1; end; dfs(1,1); end; begin readln(n); for i:=1 to n do 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); for j:=1 to tot do if (gcd(p[j],a0)=a1) and ((p[j] div gcd(p[j],b0) * b0)=b1) then inc(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<t4,则 s=t4

若 t3=t4,则 s<=t4 这样,我们或者求出了 s 的范围,要么证明了不存在合法数字。如果 s 存在合法取值,我 们就将 ans 乘上 s 的合法取值个数,否则直接输出 0。 注意:如果循环结束后,a0>1 或 b1>1,那么此时 a0 或 b1 一定是超过我们枚举的数字范 围的质数。这时我们特殊判断一下就行了。我们的时间复杂度是循环质数复杂度+分解因数 复杂度。分解因数最坏是该数为 2 的若干次方,所以复杂度的上限是 log(2000000000), 很小。最慢的点在 0.3 秒以内出解。 程序 3 program son; var i,j,k,l,m,n,p,q,l2,r2,r,s,t,a0,a1,b0,b1,ans:longint; prime:array[0..60000] of longint; need:array[0..60000] of longint; pd:boolean; function pri(x:longint):boolean; var g:longint; begin for g:=2 to trunc(sqrt(x)) do if x mod g=0 then exit(false); exit(true); end; begin p:=1;prime[1]:=2; for i:=3 to 50000 do if pri(i) then begin inc(p); prime[p]:=i; end; read(n); for t:=1 to n do begin read(a0,a1,b0,b1); ans:=1; fillchar(need,sizeof(need),255); q:=p; pd:=true; for i:=1 to p do begin l:=0;r:=0;l2:=0;r2:=0; while a0 mod prime[i]=0 do

begin inc(l);a0:=a0 div prime[i]; end; while a1 mod prime[i]=0 do begin inc(r);a1:=a1 div prime[i]; end; while b0 mod prime[i]=0 do begin inc(l2);b0:=b0 div prime[i]; end; while b1 mod prime[i]=0 do begin inc(r2);b1:=b1 div prime[i]; end; if l>r then need[i]:=r; if l2<r2 then begin if (need[i]>-1)and(need[i]<>r2) then begin pd:=false;break; end; need[i]:=r2; end; if need[i]=-1 then if r2<r then begin pd:=false;break; end else ans:=ans*(r2-r+1); end; if i=p then if a0>1 then begin inc(i);prime[i]:=a0; l:=0;r:=0;l2:=0;r2:=0; while a0 mod prime[i]=0 do begin inc(l);a0:=a0 div prime[i]; end; while a1 mod prime[i]=0 do begin inc(r);a1:=a1 div prime[i]; end;

while b0 mod prime[i]=0 do begin inc(l2);b0:=b0 div prime[i]; end; while b1 mod prime[i]=0 do begin inc(r2);b1:=b1 div prime[i]; end; if l>r then need[i]:=r; if l2<r2 then begin if (need[i]>-1)and(need[i]<>r2) then begin pd:=false; end; need[i]:=r2; end; if need[i]=-1 then if r2<r then begin pd:=false; end else ans:=ans*(r2-r+1); dec(i); end; if i=p then if b1>1 then begin inc(i);prime[i]:=b1; l:=0;r:=0;l2:=0;r2:=0; while a0 mod prime[i]=0 do begin inc(l);a0:=a0 div prime[i]; end; while a1 mod prime[i]=0 do begin inc(r);a1:=a1 div prime[i]; end; while b0 mod prime[i]=0 do begin inc(l2);b0:=b0 div prime[i]; end; while b1 mod prime[i]=0 do begin inc(r2);b1:=b1 div prime[i];

end; if l>r then need[i]:=r; if l2<r2 then begin if (need[i]>-1)and(need[i]<>r2) then begin pd:=false; end; need[i]:=r2; end; if need[i]=-1 then if r2<r then begin pd:=false; end else ans:=ans*(r2-r+1); dec(i); end; if not pd then writeln(0) else writeln(ans); end; end.

程序 4 program son; var p, x, c: array[1..10000] of longint; n, m, t, i, j, k, a0, a1, b0, b1: longint; function gcd(m, n: longint): longint; var r: longint; begin while n <> 0 do begin r := m mod n; m := n; n := r; end; gcd := m; end; procedure dfs(const i: longint; s: longint); var j: longint; begin if i > m then

begin inc(k); p[k] := s; exit; end; dfs(i + 1, s); for j := 1 to c[i] do begin s := s * x[i]; dfs(i + 1, s); end; end; procedure get(b: longint); var i: longint; begin m := 0; i := 2; while i <= sqrt(b) + 1e-6 do begin if b mod i = 0 then begin inc(m); x[m] := i; c[m] := 0; repeat inc(c[m]); b := b div i; until b mod i <> 0; end; inc(i); end; if b <> 1 then 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); for i := 1 to n do begin read(a0, a1, b0, b1); get(b1); t := 0; for j := 1 to k do if (gcd(p[j], a0) = a1) and (p[j] div gcd(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]of longint; f:array[1..maxn]of boolean; seg:array[1..maxm]of data; procedure insert_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; procedure init; var i,j,k,l:longint; begin readln(n,m); fillchar(a,sizeof(a),255); ls:=0; for i:=1 to n do read(v[i]); for i:=1 to m do begin readln(j,k,l); if l=1 then insert_e(j,k,1,2) else insert_e(j,k,3,3); end; end; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure spfa1; 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]; while open<closed do begin inc(open); k:=stack[open mod maxn]; f[k]:=false; i:=a[k]; while i<>-1 do begin if (seg[i].f and 1=1)and(min(c[k],v[seg[i].t])<c[seg[i].t]) then

begin c[seg[i].t]:=min(c[k],v[seg[i].t]); if not f[seg[i].t] then begin f[seg[i].t]:=true; inc(closed); stack[closed mod maxn]:=seg[i].t; end; end; i:=seg[i].next; end; end; end; procedure spfa2; 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]; while open<closed do begin inc(open); k:=stack[open mod maxn]; f[k]:=false; i:=a[k]; while i<>-1 do begin if (seg[i].f and 2=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]); if not f[seg[i].t] then begin f[seg[i].t]:=true; inc(closed); stack[closed mod maxn]:=seg[i].t; end; end; i:=seg[i].next; end;

end; end; procedure main; var i,ans:longint; begin spfa1; spfa2; ans:=0; for i:=1 to n do 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: program trade; const maxn = 100005; var e1, e2: array[1..1000010] of record t, next: longint; end; a, b, g1, g2, q: array[1..maxn] of longint; v: array[1..maxn] of boolean; n, i, f, r, k, p, s: longint; procedure init; var m, s, i, j, k, z: longint; procedure link(const i, j: longint); begin inc(s); with e1[s] do begin

t := j; next := g1[i]; end; g1[i] := s; with e2[s] do begin t := i; next := g2[j]; end; g2[j] := s; end; begin read(n, m); for i := 1 to n do read(b[i]); fillchar(g1, sizeof(g1), 0); fillchar(g2, sizeof(g2), 0); s := 0; for k := 1 to m do begin read(i, j, z); link(i, j); if z = 2 then link(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]; for i := 2 to n do a[i] := 100000; f := 0; r := 1; q[1] := 1; while f <> r do begin if f = maxn then f := 1 else inc(f); k := q[f]; v[k] := false; p := g1[k]; while p <> 0 do begin

with e1[p] do if a[t] > a[k] then begin a[t] := a[k]; if a[t] > b[t] then a[t] := b[t]; if not v[t] then begin if r = maxn then r := 1 else inc(r); q[r] := t; v[t] := true; end; end; p := e1[p].next; end; end; s := 0; fillchar(v, sizeof(v), 0); f := 1; r := 1; q[1] := n; v[n] := true; if s < b[n] - a[n] then s := b[n] - a[n]; while f <= r do begin p := g2[q[f]]; while p <> 0 do begin with e2[p] do if not v[t] then begin v[t] := true; if s < b[t] - a[t] then s := b[t] - a[t]; inc(r); q[r] := t; end; p := e2[p].next; end; inc(f); end; writeln(s); close(input); close(output); end.

4、靶形数独 program d_1; var usei,usej,usex:array[0..10,0..10] of boolean; usep:array[0..100] of boolean; maxi,a:array[0..10,0..10] of longint; t,s,max,tot,i,j,k,n,m,p:longint; x,y:array[0..100] of longint; function solve(i,J:longint):longint; var s,s1:longint; begin if (i<=j) then s:=i else s:=j; if (10-i<=10-j) then s1:=10-i else s1:=10-j; if (s=1) or (s1=1) then begin solve:=6; exit;end; if (s=2) or (s1=2) then begin solve:=7; exit;end; if (s=3) or (s1=3) then begin solve:=8; exit;end; if (s=4) or (s1=4) then begin solve:=9; exit;end; if (s=5) or (s1=5) then begin solve:=10;exit;end; end; function pr(i,j:longint):longint; begin pr:=(i-1) div 3*3+(j-1) div 3+1; end; procedure tryit(pp,now:longint); var t,min,w,j:longint; begin if pp=s+1 then begin if now>max then begin max:=now; maxi:=a; end end else begin t:=0; min:=999999; for i:=1 to s do if (a[x[i],y[i]]=0) and (not(usep[i])) then begin w:=0; for j:=1 to 9 do if (usei[x[i],j]) and (usej[y[i],j]) and (usex[pr(x[i],y[i]),j]) then begin

inc(w); if w>=min then break; end; if w<min then begin min:=w; t:=i; end; end; if min=0 then exit; usep[t]:=true; for j:=1 to 9 do if (usei[x[t],j]) and (usej[y[t],j]) and (usex[pr(x[t],y[t]),j]) then begin usei[x[t],j]:=false; usej[y[t],j]:=false; usex[pr(x[t],y[t]),j]:=false; a[x[t],y[t]]:=j; tryit(pp+1,now+solve(x[t],y[t])*j); a[x[t],y[t]]:=0; usei[x[t],j]:=true; usej[y[t],j]:=true; usex[pr(x[t],y[t]),j]:=true; end; usep[t]:=false; end; end; begin assign(input,'sudoku.in'); assign(output,'sudoku.out'); reset(input); rewrite(output); fillchar(usei,sizeof(usei),true); fillchar(usej,sizeof(usej),true); fillchar(usex,sizeof(usex),true); tot:=0; max:=0; s:=0; for i:=1 to 9 do begin for j:=1 to 9 do begin read(a[i,j]); if a[i,j]<>0 then begin

usei[i,a[i,j]]:=false; usej[j,a[i,j]]:=false; usex[pr(i,j),a[i,j]]:=false; t:=solve(i,j); tot:=tot+t*a[i,j]; end; if (a[i,j]=0) then begin inc(s); x[s]:=i; y[s]:=j; end; end; readln; end; fillchar(usep,sizeof(usep),false); tryit(1,tot); if max=0 then writeln('-1') else writeln(max); close(input); close(output); end.


推荐相关:

NOIP2009提高组C++初赛试题与答案

NOIP2009提高组C++初赛试题与答案_学科竞赛_高中教育_教育专区。2009 第十五届...写在试卷纸上一律无效 一. 单项选择题 (共 10 题,每题 1.5 分,共计 15 ...


NOIP2008提高组解题报告

NOIP2009提高组解题报告 16页 免费 NOIP2009提高组复赛题解 12页 1下载券 NOIP2000-2009提高组解题... 47页 2下载券 noip2010提高组解题报告 11页 免费 NOIP...


NOIP2009提高组解题报告

NOIP2009提高组复赛题解 12页 1财富值 NOIP2008提高组解题报告 13页 免费 noip2009提高组解题报告(C... 10页 1财富值如要投诉违规内容,请到百度文库投诉中心;...


NOIP2009提高组初赛试题及答案

NOIP2009提高组初赛试题及答案_学科竞赛_初中教育_教育专区。第十五届全国青少年...写在试卷纸上一律无效 一. 单项选择题 (共 10 题,每题 1.5 分,共计 15 ...


NOIP2009初赛试题及参考答案和解析(提高组)C++

在参加 NOI 系列竞赛过程中,下面哪些行为是被严格禁止的: A) 携带书写工具,...NOIP2009 初赛 提高组 C++ 3 三.问题求解(共 2 题,每空 5 分,共计 10 ...


NOIP2008提高组前三题解题报告

NOIP2009提高组复赛题解 12页 1下载券 NOIP2008 提高组 复赛试... 6页 免费...NOIP2008 提高组前三题解题报告 [日期:2008-11-18] 来源: 作者:张恩权 [...


NOIP2009初赛试题解析(提高组)

NOIP2009初赛试题解析(提高组)NOIP2009初赛试题解析(...写在试卷纸上一律无效 ○○ 每题有且仅有一个...10、全国信息学奥林匹克的官方网站为参与信息学竞赛...


2007noip提高组复赛

NOIP2008提高组复赛 4页 1下载券 NOIP2009提高组复赛题解 12页 1下载券 提高...第1页 共6页 全国信息学奥林匹克联赛(NOIP2007)复赛 提高组 1.统计数字 . ...


NOIP2009提高组(p语言)

全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资 ...NOIP2009提高组-标程 8页 免费 06年提高组C语言试卷 9页 免费喜欢...


(NOIP2009)复赛模拟试题(一)

noip2009复赛试题 5页 1下载券 NOIP2009提高组复赛题解 12页 1下载券 NOIP2009...题目来源:金陵中学 2005-2006 年第二学期信息学奥林匹克竞赛训练题 金华一中...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com