jzoj C组 2017.1.19 比赛

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

第一题——小x的游戏

题目描述

   Tac游戏在一个4*4的方格上进行。起先可能会在16个方格中出现一个标记‘T’，其余的方格是空着的。游戏有两个玩家，小x和小o。小x先开始，然后游戏轮流进行。每一步玩家可以将他的标记放入一个空的方格中。小x的标记是‘X’，小o的标记是‘O’。在一个玩家结束操作后，如果出现一行、一列或者对角线都是该玩家的标记，或者有3个该玩家的标记以及标记‘T’，那么他获得胜利，游戏结束，否则游戏继续，进入另一个玩家的回合。如果所有的方格都被填满，并且没人获得胜利，那么游戏结束，为平局。给出一个4*4的方格，包括‘X’,‘O’,‘T’和‘.’(‘.’表示空的方格)，输出现在游戏的状态，游戏的状态包括：• “X won”（游戏结束，小x获胜）• “O won”（游戏结束，小o获胜）• “Draw”（游戏结束，平局）• “Game has not completed”（游戏还未结束）如果有空格，并且游戏还未结束，你应该打印 “Game has not completed”，即使最后的结果是一定的。

输入

第一行一个整数T，表示测试数据的组数。

每组测试数据包括4行，每行4个字符，如题所述。每组测试数据后会有一行空行。

输出

对于每组测试数据，输出“Case #x: y”，x表示第x组测试数据（组号从1开始），y即上述的状态之一。注意‘O’不是‘0’。

样例输入

6

XXXT

….

OO..

….

XOXT

XXOO

OXOX

XXOO

XOX.

OX..

….

….

OOXX

OXXX

OX.T

O..O

XXXO

..O.

.O..

T…

OXXX

XO..

..O.

…O

样例输出

Case #1: X won

Case #2: Draw

Case #3: Game has not completed

Case #4: O won

Case #5: O won

Case #6: O won

数据范围限制

对于50%的数据：1<=T<=10

对于100%的数据：1<=T<=110

---

每行每列每个对角线都搜一次，如果有满足获胜的方法，就输出。如果没人获胜，就判断这里有没有空格。有就输出Game has  not completed 没有则输出Draw。

---

代码如下：

var  n,i,j,k,l:longint;w:boolean;a:array[1..4,1..4]of char;b:array['A'..'Z']of longint;procedure pdd2(x:longint);
var   i:longint;
beginfor i:=1 to 4 do if a[i,x-i+1]='.' then exit else inc(b[a[i,x-i+1]]);if b['X']=4 then begin l:=1; writeln('X won'); exit; end;if b['O']=4 then begin l:=2; writeln('O won'); exit; end;if (b['X']=3)and(b['T']=1) then begin l:=1; writeln('X won'); exit; end;if (b['O']=3)and(b['T']=1) then begin l:=2; writeln('O won'); exit; end;
end;procedure pdd1(x:longint);
var   i:longint;
beginfor i:=1 to 4 do if a[i,x+i-1]='.' then exit else inc(b[a[i,x+i-1]]);if b['X']=4 then begin l:=1; writeln('X won'); exit; end;if b['O']=4 then begin l:=2; writeln('O won'); exit; end;if (b['X']=3)and(b['T']=1) then begin l:=1; writeln('X won'); exit; end;if (b['O']=3)and(b['T']=1) then begin l:=2; writeln('O won'); exit; end;
end;procedure pdl(x:longint);
var   i:longint;
beginfor i:=1 to 4 do if a[i,x]='.' then exit else inc(b[a[i,x]]);if b['X']=4 then begin l:=1; writeln('X won'); exit; end;if b['O']=4 then begin l:=2; writeln('O won'); exit; end;if (b['X']=3)and(b['T']=1) then begin l:=1; writeln('X won'); exit; end;if (b['O']=3)and(b['T']=1) then begin l:=2; writeln('O won'); exit; end;
end;procedure pdh(x:longint);
var   i:longint;
beginfor i:=1 to 4 do if a[x,i]='.' then exit else inc(b[a[x,i]]);if b['X']=4 then begin l:=1; writeln('X won'); exit; end;if b['O']=4 then begin l:=2; writeln('O won'); exit; end;if (b['X']=3)and(b['T']=1) then begin l:=1; writeln('X won'); exit; end;if (b['O']=3)and(b['T']=1) then begin l:=2; writeln('O won'); exit; end;
end;beginassign(input,'game.in');assign(output,'game.out');reset(input);rewrite(output);readln(n);for i:=1 to n dobeginl:=0;w:=false;for j:=1 to 4 dobeginfor k:=1 to 4 dobeginread(a[j,k]);if a[j,k]='.' then w:=true;end;readln;end;readln;write('Case #',i,': ');for j:=1 to 4 dobeginfillchar(b,sizeof(b),#0);pdh(j);if l<>0 then break;end;if l<>0 then continue;for j:=1 to 4 dobeginfillchar(b,sizeof(b),#0);pdl(j);if l<>0 then break;end;if l<>0 then continue;fillchar(b,sizeof(b),#0);pdd1(1);if l<>0 then continue;fillchar(b,sizeof(b),#0);pdd2(4);if l<>0 then continue;fillchar(b,sizeof(b),#0);if w=true then writeln('Game has not completed') else writeln('Draw');end;close(input);close(output);
end.

第二题——小x的三角形

题目描述

   小x和小o在一起研究各种图形的性质。小x发明了一个问题：一个完全无向图有n个顶点，选择m条边得到它们，并将剩余的n*(n-1）div 2-m条边给小o。小x和小o喜欢图中的三角形，他们想知道他们得到的边所形成的图共形成了多少个三角形。图的顶点从1到n编号。

输入

   第一行包含两个用空格隔开的整数n和m，分别表示顶点数和小x选取的边数。接下来m行每行两个整数ai，bi，表示小x选取的第i条边连接顶点ai，bi，数据保证小x得到的图和初始的完全图无重边和自环。

输出

输出一行一个整数，小x和小o得到的图所包含三角形的总数。

样例输入

input1:

5 5

1 2

1 3

2 3

2 4

3 4

input2:

5 3

1 2

2 3

1 3

样例输出

output1:

3

output2:

4

数据范围限制

【数据范围】

对于20%的数据 1<=n<=20

对于60%的数据 1<=n<=100

对于100%的数据 1<=n<=20000, 0<=m<=10^6，m<=n(n-1)/2，1<=ai,bi<=n，ai≠bi

提示

【样例解释】

第一个样例，小x得到的图有两个三角形：(1,2,3)和(2,3,4)，小o有一个三角形(1,4,5)，所以总数是3。

第二个样例，小x的图只有一个三角形(1,2,3)，小o的图有3个三角形(1,4,5),(2,4,5)和(3,4,5)，所以总数是4。

---

公式为：C(3,n)-(每个点与点联通和不连通的乘积) div 2

---

代码如下：

var   t,i,n,j,z,m:longint;x,s:int64; a:array[1..20000]of longint;
beginassign(input,'triangles.in');assign(output,'triangles.out');reset(input);rewrite(output);readln(m,n);for j:=1 to n dobeginreadln(x,z);a[x]:=a[x]+1;a[z]:=a[z]+1;end;x:=m*(m-1)*(m-2) div 6;s:=0;for j:=1 to m do inc(s,a[j]*(m-1-a[j]));s:=s div 2;x:=x-s;writeln(x);close(input);close(output);
end.

第三题——eko

题目描述

     小x最近终于不用干搬砖的活了，他成为了一名光荣的伐木工人。但伐木工人也不好当，他每天必须至少砍下M米的木材。但小x对此感到毫无压力，因为小y最近给他买了一台崭新的伐木机，可以像野火一样将森林摧毁。但这台伐木机实在太大了，它一次只能将一整排树木一起砍倒。伐木机是这样工作的：小x设计一个参数H，然后伐木机将一排N个树木砍倒，然后得到每棵树高于H的部分。比如，有4棵树，高度分别为20,15,10,17米，而小x将H设为了15米。这样，他从第一棵得到了5m的木材，第四棵得到了2m的木材，一共是7m。当然，如果一棵树的高度不大于H，那么就不会被砍倒，也就不会留下木材。小x是个环保主义者，他希望H尽可能大，这样他砍倒的树木可以尽可能少。当然，前提是小x能至少得到M米木材。

输入

第一行两个整数N，M，代表有N棵树，小x每天至少砍M米木材。

第二行N个整数Ai,代表每棵树的高度。

输出

一行一个整数，代表所要求的最大高度。

样例输入

4 7

20 15 10 17

样例输出

15

数据范围限制

对于30%的数据:1 ≤ N ≤1 000

对于100%的数据:

1 ≤ N ≤1 000 000

1 ≤ M ≤ 2 000 000 000

1 ≤ Ai ≤ 1 000 000 000

---

二分答案，求出最高的高度为r，进行二分。

---

代码如下：

var i,l,r,k,n,m,x,mid:longint;ans,nmax:int64;a:array[0..1000000] of longint;function max(x,y:longint):longint;
beginif x>y then exit(x) else exit(y);
end;beginassign(input,'eko.in');assign(output,'eko.out');reset(input);rewrite(output);readln(n,m);for i:=1 to n dobeginread(a[i]);r:=max(a[i],r);end;l:=1;while l<=r dobeginmid:=(r+l) div 2;for i:=1 to n do if a[i]>mid then inc(nmax,a[i]-mid);if nmax>=m thenbeginans:=mid;l:=mid+1;endelse r:=mid-1;nmax:=0;end;writeln(ans);close(input);close(output);
end.

第四题——math

题目描述

 小x正在做他的数学作业，可是作业实在太难了。题目是这样的：

1.给定一个含有N个数的数列V。

2.你可以从数列中恰好移除K个数,定义移除后的数列为V’。

3.定义M为V’中任意两个数的差的最大值，m为V’中任意两个数的差的最小值。

4.请你选择删去的K个数，使得M+m最小。

 小x的数学十分之差，于是他只能向你求助了。

输入

第一行两个整数N和K。

第二行N个整数Vi。

输出

一行一个整数，为最小的M+m的和。

样例输入

5 2

-3 -2 3 8 6

样例输出

7

数据范围限制

对于60%的数据：3 ≤ N ≤ 2 000

对于100%的数据：

3 ≤ N ≤ 200 000

1 ≤ K ≤ N - 2

-5 000 000 ≤Vi ≤ 5 000 000

提示

【样例解释】

删去-3和-2，得到V’={3,6,8}，M=5,m=2,M+m=7。

---

现将n个数进行快排，因为只能从前和后面删数，枚举前面删数的个数，求出删这几个数，的差的最小值加差的最大值。

---

代码如下：

var  n,k,i,z,j,min,max,l:longint;a,b:array[0..200000]of longint;procedure qsort(l,r:longint);
var  i,j,mid:longint;
beginif l>r then exit;i:=l; j:=r; mid:=a[(i+j) div 2];repeatwhile a[i]<mid do inc(i);while a[j]>mid do dec(j);if i<=j thenbegina[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0];inc(i);dec(j);end;until i>j;qsort(l,j);qsort(i,r);
end;beginassign(input,'math.in');assign(output,'math.out');reset(input);rewrite(output);readln(n,k);for i:=1 to n do read(a[i]);qsort(1,n);for i:=1 to n-1 do b[i]:=a[i+1]-a[i];min:=maxlongint;for i:=1 to k+1 dobeginz:=n-k+i-1;if l<i thenbeginmax:=maxlongint;for j:=i to z-1 doif b[j]<max thenbeginl:=j;max:=b[j];end;endelseif b[z-1]<b[l] then l:=z-1;if b[l]+a[z]-a[i]<min then min:=b[l]+a[z]-a[i];end;write(min);close(input);close(output);
end.

由于今天的题比较水，早AK早写博客。

这篇关于jzoj C组 2017.1.19 比赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---