2016.8.15上午纪中初中部NOIP普及组比赛

2016.8.15上午纪中初中部NOIP普及组比赛

链接：https://jzoj.net/junior/#contest/home/1333 这次比赛不怎么好，因为这套题目我并不是很擅长。 可同学们都说很水，于是。。。我在同学的教导之下AK了。 进度： 比赛:100+ 60+ 30+ 10=200 改题:100+100+100+100=AK 一、icow 链接：https://jzoj.net/junior/#contest/show/1333/0 我一看到“权值”二字，就以为会是图论，结果。。。那没有图论这么难。。。 本来理解错题了，后来改一改就对了。 题目简化： 就是输入权值后，把最大的输出，然后平分给其它的，余数送给前面的，清零。 重复t次。 正解： 读入后来个循环i:=1..t，然后用循环找出最大的值。 然后把它清零，按照题目要求分配。。。循环完毕即可。

var n,t,i,j,x,y,m,mx:longint; r:array[0..1000]of longint; {////////////////////reads////////////////////////////////} procedure reads; begin readln(n,t); for i:=1 to n do readln(r[i]); end; {/////////////////////runs&writes///////////////////////////} procedure runs; begin repeat m:=0; mx:=0; for i:=1 to n do begin if (r[i]>m) then begin m:=r[i]; mx:=i; end; end; writeln(mx); dec(t); r[mx]:=0; x:=m div (n-1); y:=m mod (n-1); for i:=1 to n do begin if i=mx then continue; if y>0 then begin inc(r[i],x+1); dec(y); end else inc(r[i],x); end; until t=0; end; {///////////////////////files///////////////////////////////} procedure openfile(s:string); begin assign(input,s+'.in');reset(input); assign(output,s+'.out');rewrite(output); end; procedure closefile; begin close(input); close(output); end; {//////////////////////main program/////////////////////////} begin openfile('icow'); reads; runs; closefile; end.

二、化装晚会 链接：https://jzoj.net/junior/#contest/show/1333/1 这道题好像可以二分。。。我一开始编二分，结果错了。。。 暴搜后六十，当我以为是什么时间超限时，运行时错误立刻让我明白了为什么 数组开小了！！！ 题目简化： 就是在1~n中选两个的和小于或等于s，能有多少方案 正解： 二分是可以的，排序后再二分。 也可以暴力。。数据太水。。。

var n,s,i,j,l,r,mid,bz:longint; a:array[0..20000]of longint; ans:int64; b:boolean; {read&write/} procedure reads; begin readln(n,s); j:=0; for i:=1 to n do begin inc(j); readln(a[j]); if a[j]>=s then dec(j); end; n:=j; end; procedure writes; begin writeln(ans); end; {runs///} procedure runs; procedure qsort(l,r:longint); var i,j,mid:longint; begin i:=l; j:=r; randomize; mid:=a[l+random(r-l)]; repeat while a[j]>mid do dec(j); while a[i]<mid do inc(i); if i<=j then begin a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0]; dec(j); inc(i); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end; begin qsort(1,n); for i:=1 to n-1 do for j:=i+1 to n do if a[i]+a[j]<=s then inc(ans)else break; { for i:=1 to n do begin l:=i+1; r:=n; repeat bz:=mid; mid:=(l+r)div 2; if bz=mid then break; if a[mid]+a[i]>s then r:=mid else begin if a[mid]+a[i]<=s then l:=mid; end; until false; inc(ans,mid-i); end;} end; {//files} procedure openfile(s:string); begin assign(input,s+'.in');reset(input); assign(output,s+'.out');rewrite(output); end; procedure closefile; begin close(input); close(output); end; {main program///} begin openfile('costume'); reads; runs; writes; closefile; end. 类似于合法方案 链接：http://61.142.113.107:8080/oj/problem.php?id=1469

三、奶牛的比赛 链接：https://jzoj.net/junior/#contest/show/1333/2 考试时用拓扑排序算法（我也不知是不是，听别人说的） 结果不知为何答案错误 题目简化： 没什么好简化的，就是排名高一定打得过排名低的， 然后让电脑分析分析有哪个排名能确定 正解: 拓扑排序是可以的，只不过我错了。 还有一种floyed的方法: 设f[i,j]为i和j哪个赢，如果未知就为0，不然就为i或j 如果i<>j并且i打得过k，k打得过j，f[i,j]:=i; 最后循环，如果发现f[i,1..n]中有n-1（即包括自己）个是有关系的 就inc(ans)。

var n,s,i,j,l,r,mid,bz:longint; a:array[0..20000]of longint; ans:int64; b:boolean; {read&write/} procedure reads; begin readln(n,s); j:=0; for i:=1 to n do begin inc(j); readln(a[j]); if a[j]>=s then dec(j); end; n:=j; end; procedure writes; begin writeln(ans); end; {runs///} procedure runs; procedure qsort(l,r:longint); var i,j,mid:longint; begin i:=l; j:=r; randomize; mid:=a[l+random(r-l)]; repeat while a[j]>mid do dec(j); while a[i]<mid do inc(i); if i<=j then begin a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0]; dec(j); inc(i); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end; begin qsort(1,n); for i:=1 to n-1 do for j:=i+1 to n do if a[i]+a[j]<=s then inc(ans)else break; { for i:=1 to n do begin l:=i+1; r:=n; repeat bz:=mid; mid:=(l+r)div 2; if bz=mid then break; if a[mid]+a[i]>s then r:=mid else begin if a[mid]+a[i]<=s then l:=mid; end; until false; inc(ans,mid-i); end;} end; {/files} procedure openfile(s:string); begin assign(input,s+'.in');reset(input); assign(output,s+'.out');rewrite(output); end; procedure closefile; begin close(input); close(output); end; {main program/} begin openfile('costume'); reads; runs; writes; closefile; end.

四、贝茜的晨练计划 链接：https://jzoj.net/junior/#contest/show/1333/3 我一看就知道是DP，可是考试时半天想不出来 于是暴搜10分。 题目简化： 没什么好简化的，每一分钟内可以跑d[i]米或休息到不累。 正解： DP。 设f[i,j]为i分钟时疲劳度为j f[i,0]=f[i-1,0]（f[i,0]的初值，必须在第一和第二重循环之间） f[i,0]=max(f[i,0],f[i-j,j])（i>=j防止负数） f[i,j]=max(f[i,j],f[i-1,j-1]+d[i]);

var f:array[0..10000,0..500]of longint; d:array[1..10000]of longint; n,m,i,j,ans:longint; {///reads&writes} procedure reads; begin readln(n,m); for i:=1 to n do readln(d[i]); end; procedure writes; begin writeln(f[n,0]); end; {/runs//} procedure runs; function max(a,b:longint):longint; begin if a>b then exit(a)else exit(b); end; begin for i:=1 to n do begin f[i,0]:=f[i-1,0]; for j:=1 to m do begin if i>=j then f[i,0]:=max(f[i,0],f[i-j,j]); f[i,j]:=max(f[i,j],f[i-1,j-1]+d[i]); end; end; end; {/files} procedure openfile(s:string); begin assign(input,s+'.in');reset(input); assign(output,s+'.out');rewrite(output); end; procedure closefile; begin close(input); close(output); end; {main program///} begin openfile('cowrun'); reads; runs; writes; closefile; end.

今天心情好，发得比之前多得多，同时我想，我该为自己负责，所以才发了这么多。 只有养成不要敷衍的好习惯，水平必定会上升。 题外话： 1.我想投诉后面的新学生，很吵，吵到没得思考。