第一題——小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早寫博客。

轉載于:https://www.cnblogs.com/Comfortable/p/8412443.html

總結

以上是生活随笔為你收集整理的jzoj C组 2017.1.19 比赛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。