ACM网络赛解题报告.docx

1、ACM网络赛解题报告2012.12江西师范大学ACM网络赛解题报告Make by ECJTU_ACM，2012-12-18（比赛已结束，无赛后提交地址）1001、Binomial 组合数，整数快速幂乘 11002、Factorial 大整数 31003、Rayrays 广度优先搜索bfs 61004、这是字符串问题吗？ 字符串简单题 91005、COH 模拟题 111006、Triangle 简单动态规划入门题 131007、GCD 最大公约数 161008、JXNU 最短路Dijkstra，floyd 171009、Qsort sort函数 201010、Tree 完全二叉树的三种遍历 22

2、1001、Binomial 组合数，整数快速幂乘题目：Problem Description来到大学，小KD发现自己已经忘了高中数学知识了小KD遇到了麻烦，请作为编程高手的你来解决。小KD遇到的问题是：有一个多项式(ax + by)k，请求出多项式展开后xn ,ym 项的系数。Input输入数据有多组，每组占一行，每行包含5 个整数，分别为 a ，b ，k ，n ，m，每两个整数之间用一个空格隔开。保证 0k1,000，0n, mk，且n + m = k，0a，b5000。Output对于每组输入数据，输出一行，每行包含一个整数，表示所求的系数，这个系数可能很大，输出对10007 取模后的结果

3、。Sample Input1 1 3 1 2Sample Output3分析：(x+y)3= x3 + 3*x2*y1 + 3*x1*y2 + y3;二项式系数： 1 3 3 1(x+y)4= x4 + 4*x3*y1 + 6*x2*y2 + 4*x1*y3 + y4;二项式系数： 1 4 6 4 1类推(ax+by)3= (ax)3 + 3*(ax)2*(by)1 + 3*(ax)1*(by)2 + (by)3;类推所以题目求的系数是： C(k, m) * an * bm (C(n,m)代表组合数，n个里面取m个，结果对mod=10007取模);组合数可以先预处理保存，C(n, m) = C

4、(n-1, m) + C(n-1, m-1);时间复杂度：O(10002);an,bn可以直接for循环计算，或者用整数快速幂乘。For循环算的时间复杂度：O(1000);整数快速幂乘: O(log1000 = 10);因粘贴不当以下的代码缩进是3格，大家要养成缩进4格的习惯。代码：C+语言:jxnu_1001/ #include #define maxn 1005constintmod=10007;/* 预处理计算组合数，算到1000即可，题目要求取模， 所以边算边取模，不会超过231（越界）*/intcmaxnmaxn;voidInit() c00=1; for(inti=1;imaxn;

5、+i) ci0=1; cii=1; for(intj=1;ji;+j) cij=(ci-1j-1+ci-1j)%mod; /* xk， 整数快速幂乘 ，边乘边取模等价于：int r=1;for(int i=1; i=1; returnr;intmain() inta,b,k,n,m; Init();/ 在所有的询问之前先算好，只算一次； while(scanf(%d%d%d%d%d,&a,&b,&k,&n,&m)!=EOF) printf(%dn,ckm*( (Pow(a,n)*Pow(b,m) )%mod)%mod); / 上面只是理论分析的代码，没有ac，但个人觉得没问题； / 取模要边乘

6、边取； 1002、Factorial 大整数题目：Problem Description现有一个定义新运算：F(x)=x!+(x-1)!。Randy是个很“懒”的程序猿，希望小电脑能帮自己解决这个问题。Input第一行输入正整数N（N10），接下来的N行，每行都有一个正整数x（x1000）。Output与输入相对应地输出运算结果F(x)。Sample Input225Sample Output3144分析：X1000，直接算计算机无法直接保存这么大的数，所以用到大整数（高精度）。代码：C+语言:jxnu_1002/ /*2012-12-15 14:39:21 Accepted 1002 0 M

7、S 260 KB Visual C+*/#include #include constintM=10000;/万进制int最大,如果只用 +,-,M=1000000000intONE=1,1;/大整数 1intZERO=1,0;/大整数 0intcomp(int*a,int*b) if(a0b0)return1; if(a0=1;i-) if(aibi)return1; if(ai=1;i-)printf(%04d,ai); printf(n);voidcopy(int*a,int*b)/a=b，将大整数b拷贝给a; for(inti=0;i=b0)copy(c,a);copy(d,b); e

8、lsecopy(c,b);copy(d,a); s=c0; t=d0;/c0=d0 cs+1=0; for(i=1;i=M)ci-=M;ci+1+; for(;i=M)ci-=M;ci+1+; elsebreak; if(cs+10)c0=s+1;/处理最后一位/大整数a乘常数b, bM, d=a*bvoidmult(int*a,intb,int*d) intw,i,p; if(b=1)copy(d,a);return; if(b=0) | (a0=1&a1=0) d0=1;d1=0;return; w=a0; p=0;/ for(i=1;i=M)p=di/M;di%=M; elsep=0;

9、if(p)w+;dw=p; d0=w;#define maxn 650intansmaxn;inttempmaxn,temp1maxn;intmain() intn,x; scanf(%d,&n); while(n-) scanf(%d,&x); copy(ans,ONE); for(inti=2;ix;+i) mult(ans,i,temp); copy(ans,temp); mult(ans,x,temp); add(ans,temp,temp1); copy(ans,temp1); /printf(length = %dn, ans0); / 输出位数； PN(ans); 1003、Ra

10、yrays 广度优先搜索bfsProblem Description一天，小KD玩到了这个游戏: YY 出了一个类似的简易的模型游戏规则：每次点击一个小朋友，他和他的周围的小朋友都会改变状态（蹲下的变成了站起来的，站起来的变成了蹲下的）我们将这个抽象成如下图所示的 1*N 的图.对于一个单元格,黑色表示小朋友是站起来的,反之,蹲下的小朋友是是白色的.Source 表示初始状态,Target 表示目标状态.现在小KD有点偷懒,希望作为神牛的你帮小KD算出初始状态到目标状态的最少点击数.Input输入数据有多组。对于每组数据：第一行为 N （N=12）表示小朋友的个数.第二行是初始状态,有 N 个

11、数,每个数不是 0 就是 1.(0 表示小朋友是蹲下的,1 表示小朋友是站起来的)第三行的结构跟第二行类似,表示目标状态.Output对于每组输入数据，输出一个数 X,表示初始状态到目标状态的最少点击数。如果无法到达目标,则请输出BoringSample Input90 1 0 0 0 1 0 0 01 0 1 0 1 0 1 0 0Sample Output2分析：广度优先搜索bfs的经典应用。可以看一看数据结构书上关于bfs的讲解，每个状态可以看成一个点，按题目意思每个点之间或者可以直接转换到达，或者不可直接转换，抽象成图，就是有的点之间有边，有的没有，且边权全部为1（只转换一次）。从源状

12、态出发按bfs的方式遍历，一定可以走一条最短的路径到达目标路径（如果可达的话）。Bfs采用队列（一种数据结构，书上也有）实现。题目给的状态是一个01序列，可以转换成十进制保存，比如n=4， 序列： 0 1 1 0，那么该状态是： 6；比如n=6， 序列： 0 1 0 0 1 1，那么该状态是： 19；我们就可以用数字表示状态了，题目n=12，所以最大212的规模是可以保存的下的。一个数字到另一个数字的转变方式按题目的意思是二进制表示中连续3位数字取反。比如某个数的二进制表示：001101101， 那么这个数的转变方式有:0000101111010101111010101这几种连续位上的01进行

13、取反，从而变成新的数字，取反的方式用异或 就可以:比如上面第3个011，也即001101101011100000变成：010001101就是011变成了100，而其他位上的没变。而011100000的生成，可以用位运算， int d = (17) + (16) + (15);即d= 27 + 26 + 25。见C语言的运算符：代码：C+语言:jxnu_1003/*2012-12-15 15:10:28 Accepted 1003 0 MS 272 KB Visual C+*/#include #include constintN=(112); / 112 1*212;intn;intqueN+

14、10;intstepN+10;/ 同步记录步数（转换了多少次）；boolvisN+10;/ 标记是否在队列里；intbfs(intst,inted) if(st=ed)return0; memset(vis,0,sizeof(vis);/ 初始化； inth=0,t=0; quet=st; stept+=0; visst=1; while(h!=t) intu=queh+;/ 取队头元素； for(inti=0;in;+i) intd=0; if(i!=0)d|=(1(i-1); if(i!=n-1)d|=(1(i+1); d|=(1i); intc=ud; if(c=ed)returnste

15、ph-1+1; if(!visc) visc=1; quet=c; / 加入队尾； stept+=steph-1+1; return-1; / 队列已空，还未到达终态，返回-1；intmain() while(scanf(%d,&n)!=EOF) intbegin,end; scanf(%d,&begin); for(intt,i=2;i=n;+i) scanf(%d,&t); begin=(begin1)+t; / begin1 begin*2; scanf(%d,&end); for(intt,i=2;i=n;+i) scanf(%d,&t); end=(end1)+t; /printf(

16、%d %dn, begin, end); intans=bfs(begin,end); if(-1=ans)puts(Boring); elseprintf(%dn,ans); 1004、这是字符串问题吗？ 字符串简单题Problem Description对于每一个英文字符串，计算出每一个字母出现的次数（不区分大小写），并按字母表顺序递增输出每个字母的个数。Input可输入多组字符串（字符串长度小于150），当输入“END”（不包含引号）时结束程序。Output每组字符串有K行输出，每行包括字母（大写）和它的出现次数，字母与次数后均空一格。输出以单独一行“OVER”（不包括引号）结束。Sam

17、ple InputAbCdRandyRenENDSample OutputA 1 B 1 C 1 D 1 OVERA 1 D 1 E 1 N 2 R 2 Y 1 OVER分析：我是先把所有的小写字符转换成了大写字符。再统计，仔细看看下面的代码吧。代码：C+语言:jxnu_1004/*2012-12-15 15:16:10 Accepted 1004 0 MS 252 KB Visual C+*/#include #include #define maxn 155charchmaxn;intmain() while(scanf(%s,ch)!=EOF) if(strcmp(ch,END)=0)b

18、reak; for(inti=0;chi;+i) chi=chi=Z?chi:chi-32; intcnt26; memset(cnt,0,sizeof(cnt) ); for(inti=0;chi;+i) cntchi-A+; for(inti=0;i0) printf(%c %dn,i+A,cnti); puts(OVER); 1005、COH 模拟题Problem Description每天晚上，某霄汉童鞋都会来找小KD讨论Company of Heroes（COH），并要周六和小KD去网吧战COH。小KD表示这样会荒废大量的时间，于是决定当30号且为周六才会和某霄汉童鞋去网吧约战COH

19、期末将至，没复习好高数的小KD希望知道他在2013年前到底浪费了多少个周六的时间。这里定义约战COH那天不仅是 30 号还是星期六【一个条件没有达到那个月都不会进行COH大战，因为星期六要放假】。于是他找到了编程高手你。Input输入数据有多组，每组占一行，每行仅有一个数，N。表示小KD是从 N 年的 12 月 31 日 24:00（也就是第二年的第一天）开始和某霄汉童鞋去网吧约战COH的。【保证1582=N=2013】（HINT：2012年12月31日是星期一）Output对于每组输入数据，输出一行，每行输出仅有一个数，M。表示小KD一共荒废了多少个周六的日子（以天为单位）。Sample I

20、nput2010Sample Output3题目在我做的时候不是这样子，没写2012年12月31日是星期一，我以为是从计算的那一天起是星期一，即第N+1年的1月1日是星期二。所以下面的代码没有ac， 因为是从第N+1年的1月1日是星期二开始算起的，仅供参考。C+语言:jxnu_1005#include usingnamespacestd;boolIs_year(intyear) return(year%400=0) | (year%4=0&year%100!=0);intmain() intn; while(scanf(%d,&n)!=EOF) if( n=2012| n=2013) puts(0); continue; intyear=n+1,month=1,day=1,m=2; intcnt=0; while(1) day+; m+; if(day=30&m=6)cnt+; if(m=8)m=1; if(year=2012&month=12&day=31)break; if(month=2) if(day=28) if(!Is_year(year)