maxwell杯模拟赛题目和标程

1、Maxwell 杯重庆八中青少年信息学竞赛10 月 22 日题目一览Problem 1 : leader谁是组长问题描述八中信息组需要选一个组长。信息组一共有 n 个人，分别用 1 到 n参与了投票。得票数过半（票数大于 m div 2）的人将被选为组长。，其中 m 个人输入数据将告知这 m 个人分别将票投给了谁，请统计出谁将担任八中信息组的组长。输入数据第一行两个数 n 和m。第二行有 m 个数，这些数都是不超过 n 的正整数，表明这 m 个人的选择。输出数据输出将被选为组长的人。如果没有人的票数过半，请输出- 。输入样例输出样例时间限制各测试点 秒内存限制你的程序将被分配MB 的运行空间数

2、据规模1=n=maxlong 1=m=10000内容快速排序题目名称谁是组长最小花费最小寻找代表元源文件名称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 秒内存限制10M40M10M10M测试点10 个10 个10 个10 个分值100 分100 分100 分100 分Problem 2 : money最小花费问题描述在n 个人中，某些人的之间可以互相转账。这

3、些人之间转账续费各不相同。续费，请问 A 最少需要给定这些人之间转账时需要从转账金额里扣除百分之几使得转账后 B 收到 100 元。输入数据第一行输入两个正整数 n,m，分别表示总人数和可以互相转账的人的对数。以下 m 行每行输入三个正整数 x,y,z，表示标号为 x 的人和标号为 y 的人之间互相转账需要扣除 z%续费 (z100)。最后一行输入两个正整数 A,B。数据保证 A 与 B 之间可以直接或间接地转账。输出数据输出 A 使得 B 到账 100 元最少需要的总费用。精确到小数点后 8 位。输入样例3 31 2 12 3 21 3 31 3输出样例103.07153164时间限制各测试

4、点 1 秒内存限制你的程序将被分配 40MB 的运行空间数据规模1=n=2000内容Dijkstra 最短路算法Problem 3 : harm最小问题描述把儿站在一个 N x N 的方阵中最左上角的格子里。他可以从一个格子走到它右边和下边的格子里。每一个格子都有一个值。他想在受最小的情况下走到方阵的最右下角。输入数据第一行输入一个正整数 n。以下n 行描述该矩阵。矩阵中的数保证是不超过 1000 的正整数。输出数据输出最小值。样例输入3样例输出8数据规模n=1000内容数塔问题型动态规划Problem 4 : unique寻找代表元问题描述八中一共有 n 个社团，分别用 1 到n八中一共有

5、m 个人，分别用 1 到 m参加任何社团。每个人可以参加一个或多个社团，也可以不每个社团都需要选一。希望的人能够成为代表。输入数据第一行输入两个数 n 和 m。以下n 行每行若干个数，这些数都是不超过 m 的正整数。其中第 i 行的数表示社团 i 的全部成员。每行用一个 0 结束。输出数据输出最多的能够成为代表的人数。样例输入4 41 2 01 2 01 2 01 2 3 4 0样例输出3数据范围n,m=200内容二分图最大匹配gary 算法1 3 32 2 23 1 2评测结果参考程序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