maxwell杯模擬賽題目和標(biāo)程

1、Maxwell 杯重慶八中青少年信息學(xué)競賽10 月 22 日題目一覽Problem 1 : leader誰是組長問題描述八中信息組需要選一個組長。信息組一共有 n 個人，分別用 1 到 n參與了投票。得票數(shù)過半（票數(shù)大于 m div 2）的人將被選為組長。，其中 m 個人輸入數(shù)據(jù)將告知這 m 個人分別將票投給了誰，請統(tǒng)計出誰將擔(dān)任八中信息組的組長。輸入數(shù)據(jù)第一行兩個數(shù) n 和m。第二行有 m 個數(shù)，這些數(shù)都是不超過 n 的正整數(shù)，表明這 m 個人的選擇。輸出數(shù)據(jù)輸出將被選為組長的人。如果沒有人的票數(shù)過半，請輸出- 。輸入樣例輸出樣例時間限制各測試點 秒內(nèi)存限制你的程序?qū)⒈环峙銶B 的運行空間數(shù)

2、據(jù)規(guī)模1=n=maxlong 1=m=10000內(nèi)容快速排序題目名稱誰是組長最小花費最小尋找代表元源文件名稱leader.(pas/p)money.(pas/p)harm.(pas/p)unique.(pas/p)輸入文件名leader.oney.inharm.inunique.in輸出文件名leader.outmoney.ourm.outunique.out時間限制1 秒1 秒1 秒1 秒內(nèi)存限制10M40M10M10M測試點10 個10 個10 個10 個分值100 分100 分100 分100 分Problem 2 : money最小花費問題描述在n 個人中，某些人的之間可以互相轉(zhuǎn)賬。這

3、些人之間轉(zhuǎn)賬續(xù)費各不相同。續(xù)費，請問 A 最少需要給定這些人之間轉(zhuǎn)賬時需要從轉(zhuǎn)賬金額里扣除百分之幾使得轉(zhuǎn)賬后 B 收到 100 元。輸入數(shù)據(jù)第一行輸入兩個正整數(shù) n,m，分別表示總?cè)藬?shù)和可以互相轉(zhuǎn)賬的人的對數(shù)。以下 m 行每行輸入三個正整數(shù) x,y,z，表示標(biāo)號為 x 的人和標(biāo)號為 y 的人之間互相轉(zhuǎn)賬需要扣除 z%續(xù)費 (z100)。最后一行輸入兩個正整數(shù) A,B。數(shù)據(jù)保證 A 與 B 之間可以直接或間接地轉(zhuǎn)賬。輸出數(shù)據(jù)輸出 A 使得 B 到賬 100 元最少需要的總費用。精確到小數(shù)點后 8 位。輸入樣例3 31 2 12 3 21 3 31 3輸出樣例103.07153164時間限制各測試

4、點 1 秒內(nèi)存限制你的程序?qū)⒈环峙?40MB 的運行空間數(shù)據(jù)規(guī)模1=n=2000內(nèi)容Dijkstra 最短路算法Problem 3 : harm最小問題描述把兒站在一個 N x N 的方陣中最左上角的格子里。他可以從一個格子走到它右邊和下邊的格子里。每一個格子都有一個值。他想在受最小的情況下走到方陣的最右下角。輸入數(shù)據(jù)第一行輸入一個正整數(shù) n。以下n 行描述該矩陣。矩陣中的數(shù)保證是不超過 1000 的正整數(shù)。輸出數(shù)據(jù)輸出最小值。樣例輸入3樣例輸出8數(shù)據(jù)規(guī)模n=1000內(nèi)容數(shù)塔問題型動態(tài)規(guī)劃Problem 4 : unique尋找代表元問題描述八中一共有 n 個社團(tuán)，分別用 1 到n八中一共有

5、m 個人，分別用 1 到 m參加任何社團(tuán)。每個人可以參加一個或多個社團(tuán)，也可以不每個社團(tuán)都需要選一。希望的人能夠成為代表。輸入數(shù)據(jù)第一行輸入兩個數(shù) n 和 m。以下n 行每行若干個數(shù)，這些數(shù)都是不超過 m 的正整數(shù)。其中第 i 行的數(shù)表示社團(tuán) i 的全部成員。每行用一個 0 結(jié)束。輸出數(shù)據(jù)輸出最多的能夠成為代表的人數(shù)。樣例輸入4 41 2 01 2 01 2 01 2 3 4 0樣例輸出3數(shù)據(jù)范圍n,m=200內(nèi)容二分圖最大匹配gary 算法1 3 32 2 23 1 2評測結(jié)果參考程序programvarleader;a:array0.10001of long n,m:long;proced

6、ure re var;i:long begin;readln(n,m);for i:=1 to m do read(ai);end;procedure swap(var t1,t2:long var);t3:long begint3:=t1; t1:=t2; t2:=t3;end;wangyuAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAT390simonAAAWAWWWAWAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA350supermanAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAWWWWWWWW320rogerAAAAAA

7、AAAAAAAAAAAAWWAAAAAAAAAAAAAWWWWWWW310盧雙龍AWAWWBBBBBAAAAAAAAWWAAAAAAAAAAAAAAAAAAAA300LYAAAAAAAAAABBAAAAAAWWAAAAAAAAAAAAAWWWWWWW290kenAAAAAAAAAA-AAAAAAAAAAAAAWWWWWWA240llxWAWWAWWWAWWWWWWWWWWWAAAAAAAAAAAAAAAAAAAA230sparkWAAAAAAAAAAAAAAAAAAAMMMMMMMMMMAWATTTTTTT210gujoeAAAAAAAAAABBBBBBBBBBAAAAAAAAAAWWWWWW

8、WWWW200007AAAAAWAWAWTTTTTTTTTTAAAAAAAAAA-170 xcjzjAAAAAWAWAWWWWWWWWWWWAAAAAAAAAA?170shadowMMMMMMMMMMWWWWWWWWWWAAAAAAAAAAAAAWWWWWWW130zsABBBBBBBBBWWWWWWWWWWMMMMMMMMMMAAAWWWAWWW50kirkYYYYYYYYYY?0任廣元WWWWWWWWWWBBBBBBMMMMMMMMM?0procedure sort(l,r:long); vari,j,mid:long begini:=l;j:=r; mid:=a(i+j)div 2; r

9、epeatwhile aimid do dec(j); if ij;if lj then sort(l,j); if im divend;f aiai-1then2 then exit(apre)elsepre:=i;beginassign(input,leader.in); reset(input); assign(output,leader.out); rewrite(output);re;sort(1,m);wrin(solve); close(input); close(output);gram money;varmap:array1.2000,1.2000of dist

10、:array1.2000of real; hash:array1.2000ofreal;n,a,b:long;procedure re var;i,j,m,x,y,z:long;beginreadln(n,m);for i:=1 to n do for j:=1 to n domapi,j:=1e10;for i:=1 to m do beginreadln(x,y,z); mapx,y:=100/(100-z);mapy,x:=100/(100-z); end;readln(a,b); end;procedure solve; vari,j,minj:long min:real;begin;

11、for i:=1 to n do disti:=1e10;distb:=100; hashb:=true; minj:=b;for i:=1 to n-1 do beginfor j:=1 to n doif noshj and (distminj*mapminj,jdistj)thendistj:=distminj*mapminj,j;min:=1e10;for j:=1 to n doif no beginshj and (distjmin)thenmin:=distj; minj:=j;end;hashminj:=true; end;end;procedure writep; begin

12、wri end;n(dista:0:8);beginassign(input,money.in); reset(input); assign(output,money.out); rewrite(output);re; solve; writep;close(input); close(output);gram harm;varmap:array0.1000,0.1000of long f:array0.1000,0.1000of long;n:long;function min(a,b:long beginif a0 then connecti,x:=true else break;until false; end;function check(t: vari: eger; beginfor i:=1 to l2 beginusedi:=true; if (mi=0) or beginmi:=t; exit(true);end; end;check:=false; end;eger):;f not usedi andconnectt,ithencheck(mi) then=main=vari: begineger;assign(inp