jzoj C组 2017.1.18 比赛"/>
jzoj C组 2017.1.18 比赛
第一题——电梯里的爱情
题目描述
细心的同事发现，小x最近喜欢乘电梯上上下下，究其原因，也许只有小x自己知道：在电梯里经常可以遇到他心中的女神。
电梯其实是个很暧昧的地方，只有在电梯里，小x才有勇气如此近距离接近女神。可是，他们的谈话也仅仅限于今天天气不错啊，或是你吃了吗之类的。往往在对方微笑点头后就再次陷入难堪的沉默之中。
于是，小x便在陪伴女神的同时，也关注着电梯中显示的楼层数字，并且他注意到电梯每向上运行一层需要6秒钟，向下运行一层需要4秒钟，每开门一次需要5秒（如果有人到达才开门），并且每下一个人需要加1秒。
特别指出，电梯最开始在0层，并且最后必须再回到0层才算一趟任务结束。假设在开始的时候已知电梯内的每个人要去的楼层，你能计算出完成本趟任务需要的总时间吗?
输入
输入第一行为一个正整数 C，表示有 C 组测试数据。
接下来 C 行，每行包含一组数据，每组数据首先是一个正整数 N，表示本次乘坐电梯的人数，然后是 N 个正整数 Ai，分别表示大家要去的楼层。
输出
请计算并输出完成一趟任务需要的时间，每组数据输出占一行。
样例输入
2
4 2 4 3 2
3 10 10 10
样例输出
59
108
数据范围限制
其中，C<=100，N<=15，Ai<=100。
将去每层的人统计出来，然后将去到每层和下人的时间统计出来。最后注意将电梯降到0楼。
代码如下：
var n,i,max,j,l,m,x:longint;a:array[0..100]of longint;
beginassign(input,'service.in');assign(output,'service.out');reset(input);rewrite(output);readln(n);for i:=1 to n dobeginmax:=0;fillchar(a,sizeof(a),#0);read(m);for j:=1 to m do begin read(x); inc(a[x]); end;readln;l:=0;for j:=1 to 100 doif a[j]<>0 then begin max:=max+6*(j-l)+5+a[j]; l:=j; end;max:=max+4*l;writeln(max);end;close(input);close(output);
end.
第二题——最佳裁判
题目描述
过去的2012年对小x来说是很悲催的一年，失恋了12 次，每次都要郁闷1个月。好在小x是个体育迷，在最痛苦的时候，他常常用观看各种体育节目来麻醉自己，比如伦敦奥运会期间，小x就常常在周末邀上一群单身同事聚在自己的蜗居，一边畅饮啤酒，一边吹牛。小x最喜欢看的是跳水，主要原因也是因为这个项目有中国人参加，而且中国队员获胜的几率很大，一般不会再给自己添堵，不然何谈看体育疗情伤呢。跳水项目的一个重要环节就是裁判打分，小x他们有时候会觉得某个裁判不公平，是不是有意在压中国队员的分数。于是每当一个队员跳水完毕，他们几个也像电视上的裁判那样给队员打分，并且规定，谁的分数和最终得分最接近谁就是他们当中的最佳裁判，现场奖励啤酒一杯！其中，最终得分是这样计算的：N 个人打分，去掉一个最高分，去掉一个最低分，然后剩余分数相加，再除以 N-2 即为最终得分。凭借“看体育疗情伤”而练就的专业体育知识，小x几乎每局必胜，这一夜，小x注定要烂醉如泥了......
输入
输入包含多组测试数据。
每组测试数据首先是一个整数 N，表示裁判的人数，然后接着是 N 个实数，表示 N 个裁判的打分 Pi。
N 为 0 时表示结束输入。
输出
请计算并输出最佳裁判的编号，每组数据输出占一行。若有多人并列最佳裁判，只要求输出编号最小的那个。
特别说明：裁判编号按照打分的顺序从 1 开始，依次类推，最后一人编号为 N。
样例输入
5 8.3 9.2 8.7 8.9 9.0
0
样例输出
4
数据范围限制
其中，5 <= N <= 20，0 <= Pi <= 10。
我们先求出将每一个裁判的打分*10（为了避免精度问题）。然后求出最终分数，找出与最终分数相差最小的裁判打分。
代码如下：
var n,i,l:longint;nmax,min,max:real;a:array[1..20]of real;
beginassign(input,'judgers.in');assign(output,'judgers.out');reset(input);rewrite(output);repeatread(n);fillchar(a,sizeof(a),#0);if n=0 then break;max:=0;nmax:=0;min:=maxlongint;for i:=1 to n dobeginread(a[i]);a[i]:=a[i]*10; if a[i]>max then max:=a[i];if a[i]<min then min:=a[i];nmax:=a[i]+nmax;end;readln;l:=0;nmax:=(nmax-max-min)/(n-2);min:=maxlongint;for i:=1 to n doif abs(nmax-a[i])<min thenbeginmin:=abs(nmax-a[i]);l:=i;end;writeln(l);until n=0;close(input);close(output);
end.
第三题——临时工计划
题目描述
俗话说一分钱难倒英雄汉，高中几年下来，小x已经深深明白了这个道理，因此，新年开始存储一年的个人资金已经成了习惯，不过自从大学之后他不好意思再向大人要压岁钱了，只能把唯一的希望放到自己身上。可是由于时间段的特殊性和自己能力的因素，只能找到些零零碎碎的工作，小x想知道怎么安排自己的假期才能获得最多的工资。
已知小x一共有 m 天的假期，每天的编号从 1 到 m，一共有 n 份可以做的工作，每份工作都知道起始时间 s，终止时间 e 和对应的工资 c，每份工作的起始和终止时间以天为单位(即天数编号)，每份工作必须从起始时间做到终止时间才能得到总工资 c，且不能存在时间重叠的工作。比如，第 1 天起始第 2 天结束的工作不能和第 2 天起始，第 4 天结束的工作一起被选定，因为第 2 天小x只能在一个地方工作。
现在，小x想知道怎么安排才能在假期的 m 天内获得最大的工资数（第 m+1 天小x必须返回学校，m 天以后起始或终止的工作是不能完成的）。
输入
第一行是 2 个正整数：假期时间 m 和可做的工作数 n；接下来 n 行分别有 3 个正整数，描述对应的 n 个工作的起始时间 s，终止时间 e，总工资 c。
输出
输出小x可获得的最高工资数。
样例输入
10 5
1 5 100
3 10 10
5 10 100
1 4 2
6 12 266
样例输出
102
数据范围限制
其中，1<=T<=1000，9< m<=100，0< n<=1000，s<=100, e<=100, s<=e，c<=10000。
此题有两种方法，一种是暴搜，一种是dp
①将开始时间排序，然后。。。果断码一个dfs，只有选和不选两种情况，选要判断完成的时间是否小于小X要上学的时间。
②dp，听说有人用dp做对了。dp动态转换方程为if i>=e[j] then f[i]:=max(f[i],f[b[j]-1]+s[j])。
①代码如下：
var i,n,k,max:longint;s,e,c:array[0..1000]of longint;procedure qsort(l,r:longint);
var i,j,mid,m:longint;
beginif l>r then exit;i:=l; j:=r; mid:=s[(l+r) div 2]; m:=e[(l+r) div 2];repeatwhile (s[i]<mid)or(s[i]=mid)and(e[i]<m) do inc(i);while (s[j]>mid)or(s[j]=mid)and(e[j]>m) do dec(j);if i<=j thenbegins[0]:=s[i]; s[i]:=s[j]; s[j]:=s[0];e[0]:=e[i]; e[i]:=e[j]; e[j]:=e[0];c[0]:=c[i]; c[i]:=c[j]; c[j]:=c[0];inc(i);dec(j);end;until i>j;qsort(l,j);qsort(i,r);
end;procedure dfs(l,ans,m:longint);
beginif ans>max then max:=ans;if m>n then exit;if l>k then exit;dfs(l+1,ans,m);if (m<=s[l])and(n>=e[l]) then dfs(l+1,ans+c[l],e[l]+1);
end;beginassign(input,'partime.in');assign(output,'partime.out');reset(input);rewrite(output);readln(n,k);for i:=1 to k dO readln(s[i],e[i],c[i]);qsort(1,k);dfs(1,0,1);write(max);close(input);close(output);
end.②代码如下：
uses math;
vari,j,n,m:longint;b,e,s:array[1..1000] of longint;f:array[0..100] of longint;
beginassign(input,'partime.in');reset(input);assign(output,'partime.out');rewrite(output);read(m,n);for i:=1 to n doread(b[i],e[i],s[i]);for i:=1 to m dobeginf[i]:=f[i-1];for j:=1 to n dobeginif i>=e[j] then f[i]:=max(f[i],f[b[j]-1]+s[j]);end;end;write(f[m]);close(input);close(output);
end.第四题——捉迷藏
题目描述
小x的妈妈生了三个孩子，老大叫大明， 老二叫二明， 老三…， 老三自然就叫小x了。
一天，小x的妈妈带兄弟三人去公园玩耍，公园里面树木很多，有很多地方可以藏身， 于是他们决定玩捉迷藏。经过几轮的猜拳后，第一轮是小x来找其他两个人。现在小x想知道，在规定时间内，自己是否可以找到所有的人，现在他想请你来帮忙计算一下。
为了简单起见，把公园看成是n行m列的矩阵，其中‘S’表示小x，’D’表示大明，‘E’表示二明，‘X’表示障碍物，‘.’表示通路。这里，我们把发现定义为，可以直接看到对方，也就是说两个人在同一行或者同一列，并且中间没有障碍物或者没有其他人就可以看到对方。并且假 设，大明，二明藏好以后就不会再改变位置，小x每个单位时间可以从当前的位置走到相邻的四个位置之一，并且不会走出公园。
输入
测试数据第一行是一个正整数T，表示有T组测试数据。每一组测试数据首先是三个正整数n,m,t，分别表示行数、列数和规定的时间，接下来n行，每行m个上述的字符，并且保证有且只有一个‘S’，一个‘E’，一个‘D’。
输出
每组先输出一行Case c:(c表示当前的组数，从1开始计数)；接下来一行，如果小明可以在规定时间内找到所有的人，则输出最少需要的时间，否则输出-1。
样例输入
3
5 6 3
XXD…
….E.
….X.
….S.
……
5 6 3
XDX…
….E.
……
….S.
……
5 6 8
XXDX..
.XEX..
……
….S.
……
样例输出
Case 1:
-1
Case 2:
3
Case 3:
-1
数据范围限制
其中，T < 200，3 <= n, m <= 100，0 <= t <= 100。
这题先将可以看到大哥和二哥的位置全部标记起来（注意隔人或有障碍物看不到）。然后用bfs枚举每一个位置，如果时间不超过t，而且大哥和二哥都看到了，就输出。
代码如下：
const dx:array[1..4,1..2]of longint=((1,0),(-1,0),(0,1),(0,-1));
var t,i,j,l,n,m,time,k,q1,q2,q3,x,y,x1,x2,y1,y2:longint;p:boolean;c,f:array[1..100,1..100,0..2]of boolean;a:array[0..101,0..101]of char;state:array[1..10000,1..3]of longint;
beginassign(input,'seek.in');assign(output,'seek.out');reset(input);rewrite(output);readln(t);for l:=1 to t dobeginreadln(n,m,k);fillchar(c,sizeof(c),false);fillchar(f,sizeof(f),false);for i:=1 to n dobeginfor j:=1 to m dobeginread(a[i,j]);if a[i,j]='E' thenbeginx1:=i;y1:=j;end;if a[i,j]='D' thenbeginx2:=i;y2:=j;end;if a[i,j]='S' thenbeginq1:=1;q2:=1;state[1,1]:=i;state[1,2]:=j;state[1,3]:=0;a[i,j]:='.';end;end;readln;end;writeln('Case ',l,':');for i:=1 to 2 dobeginx:=x1-1;y:=y1;while a[x,y]='.' dobeginf[x,y,i]:=true;dec(x);end;x:=x1+1;y:=y1;while a[x,y]='.' dobeginf[x,y,i]:=true;inc(x);end;x:=x1;y:=y1-1;while a[x,y]='.' dobeginf[x,y,i]:=true;dec(y);end;x:=x1;y:=y1+1;while a[x,y]='.' dobeginf[x,y,i]:=true;inc(y);end;x1:=x2;y1:=y2;end;for i:=1 to 2 doif f[state[1,1],state[1,2],i]=true then inc(state[1,3],i);if state[1,3]=3 thenbeginwriteln(0);continue;end;p:=false;time:=0;c[state[1,1],state[1,2],state[1,3]]:=true;while (q1<=q2)and(time<k) dobegininc(time);q3:=q2+1;for i:=q1 to q2 dobeginfor j:=1 to 4 dobeginx:=dx[j,1]+state[i,1];y:=dx[j,2]+state[i,2];if (x>0)and(y>0)and(x<=n)and(y<=m)and(a[x,y]='.') thenbeginx2:=state[i,3];if (f[x,y,1]=true)and(1<>x2) then x2:=x2+1;if (f[x,y,2]=true)and(x2<2) then x2:=x2+2;if x2=3 thenbeginp:=true;break;end;if c[x,y,x2]=false thenbegininc(q2);state[q2,1]:=x;state[q2,2]:=y;state[q2,3]:=x2;c[x,y,x2]:=true;end;end;end;if p=true then break;end;if p=true then break;q1:=q3;end;if p then writeln(time) else writeln(-1);end;close(input);close(output);
end.
更多推荐
jzoj C组 2017.1.18 比赛
发布评论