jzoj C组 2017.1.17 比赛

本文主要是介绍jzoj C组 2017.1.17 比赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一题

题目描述毕业于普通本科的小x一直自称是资深屌丝。谁又能想到，如此不起眼的小x 在历经重重面试环节后，竟然如愿以偿加入了心仪已久的腾讯公司！正所谓野百合也有春天，屌丝也有逆袭的那一天！

  一段时间以后，随着对工作环境以及同事的熟悉，小x逐渐放松下来，在工作间隙，他细细观察了自己的工作环境，发现整个工作室是一个 N 行 M 列的矩形布局，或者是因为屌丝的本性逐步暴露，他还暗自给每个同事在心里进行了魅力值评分（为区别男女，男生一律用负整数表示，女生一律用正整数表示）。现在，小x把所有人的数据记录下来，并且这样定义一个位置的价值：1、一个位置的价值只和其上下左右四个邻居的魅力值有关（对于靠边的位置，只考虑

其存在的邻居）；

 2、一个位置的价值是其邻居的魅力值之和。当然，如果某邻居和该位置主人性别不同，则是加上邻居魅力值的绝对值，否则为加上邻居魅力值的绝对值的相反数；3、对周围所有邻居的数据处理后，最终的得分即为这个位置的最终得分。得分越高的位置越好；

现在，请你能帮助小x计算一下哪里才是最好的位置。
输入

数据的第一行包含 2 个整数 N 和 M，表示工作室的布局是 N 行 M 列；

接下来的 N 行，每行有 M 个整数，分别表示对应位置员工的魅力值Ki，正整数表示女生的魅力值，负整数表示男生的魅力值；

其中，N<=500，M<=500，-500<=Ki<=500。

输出

请计算并输出最佳位置的行列号以及对应的得分。

如果得分最高的位置有多个，则请输出行号最小的那个，行号还相同的话，再比较列号，只输出列号最小的那个即可。

样例输入

2 3

5 -4 3

-6 3 7

样例输出

1 2 11

数据范围限制

N<=500，M<=500，-500<=Ki<=500。

这题伟大而神圣的暴力，求出每个位置的价值，找出最大值就行了。

代码如下：

const dx:array[1..4]of longint=(0,0,-1,1);dy:array[1..4]of longint=(1,-1,0,0);
var   n,m,i,j,k,ans,max,h,l:longint;a:array[0..501,0..501]of longint;
beginassign(input,'reven.in');assign(output,'reven.out');reset(input);rewrite(output);readln(n,m);for i:=1 to n dobeginfor j:=1 to m do read(a[i,j]);readln;end;max:=-maxlongint;for i:=1 to n dofor j:=1 to m dobeginans:=0;for k:=1 to 4 doif (a[i+dx[k],j+dy[k]]<0)and(a[i,j]<0)or(a[i+dx[k],j+dy[k]]>0)and(a[i,j]>0)thenans:=ans-abs(a[i+dx[k],j+dy[k]])elseans:=ans+abs(a[i+dx[k],j+dy[k]]);if ans>max thenbeginmax:=ans;h:=i;l:=j;end;end;write(h,' ',l,' ',max);close(input);close(output);
end.

第二题

题目描述
今天是一年一度的植树节，腾讯幼儿园要求每个老师在班里选出几个小朋友一起去野外种植小树苗，根据学校的整体安排，小x老师的班里要选出 3 个小朋友。

 已知小x的班里共有 n 个孩子，每个孩子有 Bi 个朋友(i 从 1 到 n)，且朋友关系是相互的，如果 a 小朋友和 b 小朋友是朋友，那么 b 小朋友和 a 小朋友也一定是朋友。为了选择的公平性，小x老师会随机抽取 3 个小朋友出来(每个人被抽到的概率相同)，但是他很希望这 3 个小朋友之间的关系完全相同，小x老师想请你帮他算算抽到的 3 个小朋友正好关系相同的概率是多少？PS. 关系相同就是指要么 3 个人互相是朋友，要么 3 个人互相都不是朋友。输入

输入数据第一行是一个整数 T(1<=T<=1000)，表示输入数据的组数；

每组数据的第一行是一正整数 n 表示孩子的总数(2 < n<=1000)，第二行有 n 个数 Bi (i 从1 到n)，分别代表每个小朋友的朋友的个数。

输出

对于每组数据，请输出抽到的 3 个小朋友关系相同的概率，结果保留 3 位小数。

样例输入

3 3 3 3 4

样例输出

0.400

数据范围限制

(1<=T<=1000)

(2 < n<=1000)

公式：C(3,n) div 6/（count(每个人朋友的个数*不是朋友的个数） div 2)

代码如下：

var   t,i,n,x,s,j:longint;y:double;a:array[1..1001]of longint;
beginassign(input,'trees.in');assign(output,'trees.out');reset(input);rewrite(output);readln(t);for i:=1 to t dobeginreadln(n);for j:=1 to n do read(a[j]);readln;x:=n*(n-1)*(n-2) div 6;s:=0;for j:=1 to n do inc(s,a[j]*(n-1-a[j]));s:=s div 2;y:=s/x;y:=1-y;writeln(y:0:3);end;close(input);close(output);
end.

第三题

题目描述

  春节将至，小x要去超市购置年货，于是小x去了自己经常去的都尚超市。刚到超市，小x就发现超市门口聚集一堆人。用白云女士的话说就是：“那家伙，那场面，真是人山人海，锣鼓喧天，鞭炮齐呤，红旗招展。那可真是相当的壮观啊！”。好奇的小x走过去，奋力挤过人群，发现超市门口贴了一张通知，内容如下：值此新春佳节来临之际，为了回馈广大顾客的支持和厚爱，特举行春节大酬宾、优惠大放送活动。凡是都尚会员都可用会员积分兑换商品，凡是都尚会员都可免费拿 k 件商品，

blablabla….

  还没看完通知，小x就高兴的要死，因为他就是都尚的会员啊。迫不及待的小x在超市逛了一圈发现超市里有 n 件他想要的商品。小x顺便对这 n 件商品打了分，表示商品的实际价值。小x发现身上带了 v1 的人民币，会员卡里面有 v2 的积分。他想知道他最多能买多大价值的商品。由于小x想要的商品实在太多了，他算了半天头都疼了也没算出来，所以请你这位聪明的程序员来帮帮他吧。

输入

第一行是四个整数 n，v1，v2，k；

然后是 n 行，每行三个整数 a，b，val，分别表示每个商品的价钱，兑换所需积分，实际价值。

其中，1 <= n <= 100，0 <= v1, v2 <= 100，0 <= k <= 5，0 <= a, b, val <= 100。

Ps. 只要钱或者积分满足购买一件商品的要求，那么就可以买下这件商品。

输出

输出能买的最大价值。

样例输入

5 1 6 1

4 3 3

0 3 2 2 3 3

3 3 2

1 0 2

样例输出

数据范围限制

1 <= n <= 100，0 <= v1, v2 <= 100，0 <= k <= 5，0 <= a, b, val <= 100。

设f[i,j,k]为用i元j积分k次免费次数的最大价值，因此推出dp式
if i>=s[x] then f[i,j,k]:=max(f[i,j,k],f[i-s[x],j,k]+m[x]);
if j>=w[x] then f[i,j,k]:=max(f[i,j,k],f[i,j-w[x],k]+m[x]);
if k>=1 then f[i,j,k]:=max(f[i,j,k],f[i,j,k-1]+m[x]);

代码如下：

var n,v1,v2,k,i,ans,min,k1,x,j:longint;s,w,m:array[0..100]of longint;f:array[0..100,0..100,0..5]of longint;function max(x,y:longint):longint;
beginif x>y then exit(x) else exit(y);
end;beginassign(input,'purcha.in');assign(output,'purcha.out');reset(input);rewrite(output);  readln(n,v1,v2,k1);for i:=1 to n do readln(s[i],w[i],m[i]);for x:=1 to n dofor i:=v1 downto 0 dofor j:=v2 downto 0 dofor k:=k1 downto 0 dobeginif i>=s[x] then f[i,j,k]:=max(f[i,j,k],f[i-s[x],j,k]+m[x]);if j>=w[x] then f[i,j,k]:=max(f[i,j,k],f[i,j-w[x],k]+m[x]);if k>=1 then f[i,j,k]:=max(f[i,j,k],f[i,j,k-1]+m[x]);end;write(f[v1,v2,k1]);close(input);close(output);
end.

第四题

题目描述

小x最近喜欢上了一个名为十滴水的游戏。

这里写图片描述游戏是在一个6*6的方格内进行的，每个格子上有一滴水或者没有水滴。水滴分为四个等级1~4。初始时你有十滴水，通过把水加入格子内的水滴，会让水滴升1级。你也可以把水放到空格子内，这样会在这个格子里面产生一个1级的水滴。当水滴等级大于4时则会爆裂为四个小水滴，并向四个方向飞溅。每个飞溅的小水滴碰到其他水滴后会融入其中，使其升一级或者爆裂，以此类推。飞溅的小水滴互不干扰，运动速度相等(1秒可以移动一个格子的距离)。水滴爆裂后就消失掉了。

输入

  包含多组测试数据；对于每组数据，首先是6行，每行有6个整数数字，每个数字的范围为0~4；当数字为0时，表示空格子，当数字为1~4时，表示1~4级的水滴；然后第7行是一个整数m，表示有m个操作；接下来是m行，每行有两个整数x, y ，表示在(x,y)放入一滴水。特别说明：每次都是在全部的水滴静止后才进行下一次操作，也就是说只有在方格内没有任何飞溅的小水滴时才能放入一滴水。其中，1 <= m <= 10，1 <= x, y <= 6。

输出

  对于每组测试数据，请输出m个操作之后6*6方格内水滴的样子，每组数据的输出后面跟着一个空行（PS：最后一组数据也需要跟着一个空行）。

样例输入

0 0 0 4 0 4

0 0 0 0 0 0

1 0 0 4 0 4

0 0 0 0 0 0

0 0 0 1 0 0

1 6

0 0 0 4 0 4

0 2 0 4 0 4

0 0 0 0 0 0

1 6

2 2 0 2 0 3

3 3 0 1 3 1

2 2 2 4 0 4

2 4 4 2 2 3

3 3 2 4 0 1

1 3 4 3 0 1

5 3

3 3

3 2

2 1

6 3

样例输出

0 0 0 0 0 0

2 0 0 0 0 0

0 0 0 0 0 0

0 0 0 2 0 0

0 0 0 0 0 0

0 3 0 0 0 0

0 0 0 0 0 0

0 4 0 2 0 3

0 0 0 4 3 2

0 0 0 0 0 0

0 0 0 0 4 4

0 0 0 0 0 4

4 0 0 0 0 3

数据范围限制

1 <= m <= 10，1 <= x, y <= 6。

每次将这个水滴带进格子，如果这个点大于4，则再向四个方向搜索，遇到第一个水滴后升级或爆裂。如果爆裂就这个点存起来，到层搜完后再搜。一层一层的搜，直到没有水滴的等级大于四。

代码如下：

const dx:array[1..4,1..2]of longint=((-1,0),(0,1),(1,0),(0,-1));
var   i,j,k,x,y,nx,mx,n:longint;x1,x3:array[1..40,1..2]of longint;x2,x4:array[1..40]of longint;f:array[1..6,1..6]of boolean;a:array[1..6,1..6]of longint;
beginassign(input,'drops.in');assign(output,'drops.out');reset(input);rewrite(output); while not eoln dobeginfor i:=1 to 6 dobeginfor j:=1 to 6 do read(a[i,j]);readln;end;readln(n);for i:=1 to n dobeginreadln(x,y);inc(a[x,y]);if a[x,y]=5 thenbeginnx:=4;for j:=1 to 4 dobeginx1[j,1]:=x;x1[j,2]:=y;x2[j]:=j;end;a[x,y]:=0endelse nx:=0;while nx>0 dobeginmx:=0;for j:=1 to nx dobeginx:=x1[j,1]+dx[x2[j],1];y:=x1[j,2]+dx[x2[j],2];if (x<7)and(x>0)and(y<7)and(y>0) thenif a[x,y]>0 thenbegininc(a[x,y]);if a[x,y]>4 then f[x,y]:=true;endelsebegininc(mx);x3[mx,1]:=x;x3[mx,2]:=y;x4[mx]:=x2[j];end;end;for j:=1 to 6 dofor k:=1 to 6 doif f[j,k]=true thenbeginf[j,k]:=false;a[j,k]:=0;for x:=1 to 4 dobeginx3[mx+x,1]:=j;x3[mx+x,2]:=k;x4[mx+x]:=x;end;inc(mx,4);end;nx:=mx;x1:=x3;x2:=x4;end;end;for j:=1 to 6 dobeginfor k:=1 to 6 do write(a[j,k],' ');writeln;end;writeln;end;close(input);close(output);
end.