tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> IT/计算机 >>

noip2010提高组解题报告


Noip2010
反观 2010 年的提高组题目:第一题机器翻译是一道纯模拟的题目, 第二题乌龟棋 DP 类型 的题目,第三题实际上就是求最大值最小问题,最后一题难度高,自己无法下定义。 1:源代码: var m,n,i,j,k,p,ans,x:longint; a:array[1..100000] of longint; begin readln( m , n ); p:=0; ans:=0; fillchar(a,sizeof(a),0); for i:=1 to n do begin read(x); k:=0; for j:=1 to p do if a[j] = x then begin k:=j; break; end; if k = 0 then begin inc( p ); if p>m then begin for j:=2 to m do a[j-1]:=a[j]; p:=m; end; a[p]:=x; inc( ans ); end; end; writeln( ans ); end. 2:题目中每种卡最多只有 40 张,所以从这里入手。 可以得到动态转移方程 f[i,j,i1,j1]=max( f[i-1,j,i1,j1] , f[I,j-1,i1,j1] ,f[I,j,i1-1,j1] ,f[I,j,i1,j1-1] ) +a[i+2*j+3*i1+4*j1+1] 边界条件:f[0,0,0,0]:=1; 源代码: var

n,m,i,j,i1,j1,x:integer; b:array[1..4] of integer; a:array[1..350] of integer; f:array[-1..40,-1..40,-1..40,-1..40] of integer; function max(x,y:integer):integer; begin if x > y then max:=x else max:=y; end; begin readln( n , m ); for i:=1 to n do read( a[i] ); for i:=1 to m do begin read( x ); inc( b[x] ); end; for i:=0 to b[1] do for j:=0 to b[2] do for i1:=0 to b[3] do for j1:=0 to b[4] do f[i,j,i1,j1]:=max( max(f[i-1,j,i1,j1],f[i,j-1,i1,j1]) , max(f[i,j,i1-1,j1],f[i,j,i1,j1-1]) ) + a[i+2*j+3*i1+4*j1+1]; writeln( f[b[1],b[2],b[3],b[4]] ); end. 3:关押罪犯,这道题我花了很长时间才理解。因为这道题是求最大值最小类型的,所以首先 做的第一件事是排序,接下来可以用并查集或者二分分之做。 算法介绍: 1:并查集 从大到小排序后,我们可以把第一大的两个人放在不同监狱里(也就是不同的 子集中)【我这里首先是把两个数互相记录对放】 , , 当 find(x)= find(y)时,此时两个人都在同一个监狱中,此时 z[i]就是最大值,推出循环, 再输出就可以了, 当 r[x]=0 and r[y]=0 时,我们又可以互相记录对方,根据以后的数值再决定两人放在哪一个 监狱中(不用担心以后不再会出现这两个数,如果不出现,那最好,两人都是共同独立的, 任意放在两个监狱中,都不会于其他人发生冲突) 当 (r[x]=0 and r[y]<>0 ) or (r[x]<>0 and r[y]=0)时,我们又记录数据,此时就可以合并集合了, union( r[x] , y ) union( r[y] ,x ) {就是把该人所共同对立的两人合并在同集合中} 重复以上过程就可以完成。 2:二分 我们也把数据从大到小排序,再用二分取到中间值,把中间值以上的所有数据建 立一个相应的图(也不能说是图,本人比较弱只能讲到这了) ,如果图不成立,则向上取, 否则向下取。 源代码:{并查集} var f:array[1..20000] of longint;

x,y,z:array[1..100000] of longint; r:array[1..20000] of longint; ans1,ans2,i:longint; n,m:longint; procedure init; var i:longint; begin readln(n,m); for i:=1 to m do readln(x[i],y[i],z[i]); for i:=1 to n do f[i]:=i; end; procedure sort(l,r:longint); var i,j,mid,temp:longint; begin i:=l; j:=r; mid:=z[(i+j)>>1]; repeat while z[i]>mid do inc(i); while z[j]<mid do dec(j); if i<=j then begin temp:=z[i];z[i]:=z[j];z[j]:=temp; temp:=x[i];x[i]:=x[j];x[j]:=temp; temp:=y[i];y[i]:=y[j];y[j]:=temp; inc(i); dec(j); end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; function find(x:longint):longint; begin if f[x]=x then exit(x); f[x]:=find(f[x]); exit(f[x]); end;

procedure union(x,y:longint); var xx,yy:longint; begin xx:=find(x); yy:=find(y); if xx<>yy then f[xx]:=yy; end; procedure doit; var i,temp1,temp2:longint; begin for i:=1 to m do begin if find(x[i])=find(y[i])then begin writeln(z[i]); exit; end; if (r[x[i]]=0)and(r[y[i]]=0)then begin r[x[i]]:=y[i]; r[y[i]]:=x[i]; continue; end; if r[x[i]]=0 then r[x[i]]:=y[i]; if r[y[i]]=0 then r[y[i]]:=x[i]; union(r[x[i]],y[i]); union(r[y[i]],x[i]); end; writeln(0); end; begin init; sort(1,m); doit; end. 源代码:{二分} var a:array[0..100000,1..3] of longint;

e,h:array[1..200000] of longint; s,color,v:array[1..20000] of longint; n,m,i,es,l,r,mid:longint; procedure addkk(x,y:longint); begin inc(es); h[es]:=s[x]; e[es]:=y; s[x]:=es; end; procedure graph_pre; begin es:=0; fillchar(color,sizeof(color),0); fillchar(h,sizeof(h),0); fillchar(s,sizeof(s),0); end; function bfs(x:longint):boolean; var k,j,w:longint; begin k:=1;j:=1;v[1]:=x;color[x]:=1; while k<=j do begin x:=v[k]; w:=s[x]; while w<>0 do begin if color[e[w]]=0 then begin color[e[w]]:=3-color[x]; inc(j);v[j]:=e[w]; end else if color[e[w]]=color[x] then exit(false); w:=h[w]; end; inc(k); end; exit(true); end; function graph_check:boolean; var i:longint; begin

for i:=1 to n do if color[i]=0 then if not bfs(i) then exit(false); exit(true); end; begin assign(input,'prison.in');reset(input); assign(output,'prison.out');rewrite(output); read(n,m); for i:=1 to m do read(a[i,1],a[i,2],a[i,3]); for i:=1 to m do if a[i,3]>r then r:=a[i,3]; while l<r do begin graph_pre; mid:=(l+r) div 2; for i:=1 to m do if a[i,3]>mid then begin addkk(a[i,1],a[i,2]); addkk(a[i,2],a[i,1]); end; if graph_check then r:=mid else l:=mid+1; end; writeln(l); close(input);close(output); end. 4:引水入城 这道题简直坑爹啊!看了 NOI 专刊上张浩千的题解,我首先无语的是,什么叫 Flood Fill。后来再 NOCOW 上理解了, (哈哈)也就是广搜一张图,也叫种子染色法,还有做 这道题首先要用到一个结论:如果(1,I )能遍历到(n , I )的某些点,那么这个区间一 定是连续的。 (证明可以用反证法证明,详见张浩千的 2010noip 提高组解题报告) 【算法描述】首先枚举第一条边上的每一个点做一次 Flood Fill,判断最后一行的所有点能够 到达,如果不行,那很好,输出 0 和无法安装输水管的城市数。 预判之后,便是计算最少用多少个蓄水站,这个可以用 dp 来做(实际上我根本想不到) ,再 两次用到 Flood Fill,首先从最后一行出发首先是从 1 到 m, 得到 col[i,1] , m 到 1, 从 得到 col[i,2] 这就是第 1 行第 i 个城市建立一个蓄水站,所能达到最后一行的区间,至于 DP 的转移方程 我就写再这里: f[i]=min(f[col[i,1]-1]+1,f[i]) ( i 是指前覆盖前 i 段需要的最少的蓄水站) 源代码:{打的不是很好看} const h:array[1..4,1..2] of longint=((1,0),(-1,0),(0,-1),(0,1)); var col,a:array[0..501,0..501] of longint; f:array[0..500] of longint;

c:array[0..500,1..2] of longint; d:array[0..500000] of record x,y:longint;end; n,m,i,j,color:longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure Judge; var i,j:longint; procedure bfs(x,y:integer); var i,t,f:longint; begin t:=1;f:=1;d[t].x:=x;d[t].y:=y;col[x,y]:=color; repeat for i:=1 to 4 do if col[d[f].x+h[i,1],d[f].y+h[i,2]]=0 then if a[d[f].x+h[i,1],d[f].y+h[i,2]]<a[d[f].x,d[f].y] then begin inc(t); d[t].x:=d[f].x+h[i,1]; d[t].y:=d[f].y+h[i,2]; col[d[t].x,d[t].y]:=color; end; inc(f); until f>t; end; begin for i:=0 to n+1 do begin a[i,0]:=maxlongint; a[i,m+1]:=maxlongint; end; for i:=0 to m+1 do begin a[0,i]:=maxlongint; a[n+1,i]:=maxlongint; end; for color:=1 to m do bfs(1,color); j:=0; for i:=1 to m do if col[n,i]=0 then inc(j); if j>0 then begin writeln(0); writeln(j); halt; end; end; procedure floodfill; procedure bfs(x,y:integer); var i,t,f:longint; begin t:=1;f:=1;d[t].x:=x;d[t].y:=y;col[x,y]:=color; repeat for i:=1 to 4 do if col[d[f].x+h[i,1],d[f].y+h[i,2]]=0 then if a[d[f].x+h[i,1],d[f].y+h[i,2]]>a[d[f].x,d[f].y] then begin inc(t); d[t].x:=d[f].x+h[i,1]; d[t].y:=d[f].y+h[i,2]; col[d[t].x,d[t].y]:=color;

end; inc(f); until f>t; end; var i,j:longint; begin for i:=0 to n+1 do begin a[i,0]:=0; a[i,m+1]:=0; end; for i:=0 to m+1 do begin a[0,i]:=0; a[n+1,i]:=0; end; fillchar(col,sizeof(col),0); for color:=1 to m do if col[n,color]=0 then bfs(n,color); for i:=1 to m do c[i,1]:=col[1,i]; fillchar(col,sizeof(col),0); for color:=m downto 1 do if col[n,color]=0 then bfs(n,color); for i:=1 to m do c[i,2]:=col[1,i]; end; procedure DP; var i,j:longint; begin f[0]:=0; for i:=1 to m do begin f[i]:=maxint; for j:=1 to m do if (c[j,2]>=i)and(c[j,1]<=i) then f[i]:=min(f[i],f[c[j,1]-1]+1); end; writeln(1); writeln(f[m]); end; BEGIN read(n,m); for i:=1 to n do for j:=1 to m do read(a[i,j]); judge; floodfill; DP; END.


推荐相关:

NOIP2010提高组解题报告

noip2010提高组解题报告 11页 免费 NOIP2011提高组复赛试题与... 13页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈...


NOIP2010提高组C++

欢迎访问 NOI 网站 CCF NOIP2010 初赛 提高组 C++ 2 7.关于拓扑排序,下面说法正确的是( )。 A. 所有连通的有向图都可以实现拓扑排序 B. 对同一个图而言,...


NOIP2010提高组解题报告2

Noip2010提高组试题 10页 免费 NOIP2010提高组解题报告 6页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...


2010noip提高组解题报告

noip2010提高组解题报告 11页 免费 NOIP2011 提高组 试题 Day... 4页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进...


NOIP2010解题报告

解题报告 11页 免费 NOIP2010普及组个人解题... 9页 免费 全国信息学奥林匹克联赛... 6页 免费 NOIP2010提高组解题报告... 2页 免费 NOIP2010年提高组结题...


NOIP2010普及组解题报告

NOIP2010普及组解题报告_调查/报告_表格/模板_应用文书。NOIP2010 普及组解题报告时间:2011-09-14 10:39:27 来源:网络 作者:网络 首先前两题可以说非常水,第三...


NOIP2010年提高组结题报告

题目:[NOIP2010]关押罪犯 问题编号:600 题目描述 S 城现有两座监狱,一共关押...noip2009提高组解题报告... 10页 1下载券 NOIP2011提高组解题报告... 9页 ...


NOIP2010解题报告(附代码)

NOIP2010解题报告 3页 免费 NOIP2010提高组解题报告... 2页 免费 NOIP2010解题报告 15页 1下载券喜欢此文档的还喜欢 NOIP2010提高组解题报告 6页 免费 noip2010...


Noip2010提高组 第1题 translate 机器翻译

Noip2010 提高组 第 1 题 translate 机器翻译 【题意分析】 现在要翻译一段...NOIP2010年提高组结题报... 9页 免费 NOIP2010提高组解题报告... 2页 ...


NOIP2009提高组解题报告

xnhua2011贡献于2010-10-20 0.0分 (0人评价)暂无用户评价 我要评价 ...NOIP2009提高组解题报告NOIP2009提高组解题报告隐藏>> NOIp 2009 解题报告 November...

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