ACM网络赛解题报告.docx

ACM网络赛解题报告.docx

《ACM网络赛解题报告.docx》由会员分享，可在线阅读，更多相关《ACM网络赛解题报告.docx（28页珍藏版）》请在冰点文库上搜索。

ACM网络赛解题报告

2012.12江西师范大学ACM网络赛解题报告

MakebyECJTU_ACM，2012-12-18

（比赛已结束，无赛后提交地址）

1001、Binomial组合数，整数快速幂乘1

1002、Factorial大整数3

1003、Rayrays广度优先搜索bfs6

1004、这是字符串问题吗？

字符串简单题9

1005、COH模拟题11

1006、Triangle简单动态规划入门题13

1007、GCD最大公约数16

1008、JXNU最短路Dijkstra，floyd17

1009、Qsortsort函数20

1010、Tree完全二叉树的三种遍历22

1001、Binomial组合数，整数快速幂乘

题目：

ProblemDescription

来到大学，小KD发现自己已经忘了高中数学知识了……小KD遇到了麻烦，请作为编程高手的你来解决。

小KD遇到的问题是：

有一个多项式（ax+by）^k，请求出多项式展开后x^n,y^m项的系数。

Input

输入数据有多组，每组占一行，每行包含5个整数，分别为a，b，k，n，m，每两个整数之间用一个空格隔开。

保证0≤k≤1,000，0≤n,m≤k，且n+m=k，0≤a，b≤5000。

Output

对于每组输入数据，输出一行，每行包含一个整数，表示所求的系数，这个系数可能很大，输出对10007取模后的结果。

SampleInput

11312

SampleOutput

3

分析：

（x+y）^3=x^3+3*x^2*y^1+3*x^1*y^2+y^3;

二项式系数：

1331

（x+y）^4=x^4+4*x^3*y^1+6*x^2*y^2+4*x^1*y^3+y^4;

二项式系数：

14641

类推……

（ax+by）^3=（ax）^3+3*（ax）^2*（by）^1+3*（ax）^1*（by）^2+（by）^3;

类推……

所以题目求的系数是：

C（k,m）*a^n*b^m（C（n,m）代表组合数，n个里面取m个，结果对mod=10007取模）;

组合数可以先预处理保存，C（n,m）=C（n-1,m）+C（n-1,m-1）;

时间复杂度：

O（1000^2）;

a^n,b^n可以直接for循环计算，或者用整数快速幂乘。

For循环算的时间复杂度：

O（1000）;

整数快速幂乘:

O（log1000=10）;

因粘贴不当以下的代码缩进是3格，大家要养成缩进4格的习惯。

代码：

C++语言:

 jxnu_1001

//

#include

#definemaxn1005

const int mod = 10007;

/*预处理计算组合数，算到1000即可，题目要求取模，

 所以边算边取模，不会超过2^31（越界）*/

int c[maxn][maxn];

void Init（）{

  c[0][0]= 1;

  for（int i=1; i

    c[i][0]= 1;

    c[i][i]= 1;

    for（int j=1; j

      c[i][j]= （c[i-1][j-1] + c[i-1][j]）%mod;

  }

}

/*x^k，整数快速幂乘，边乘边取模

等价于：

intr=1;

for（inti=1;i<=k;++i） //时间复杂度：

O（k）;

  r=r*x%mod;

returnr;

*/

int Pow（int x, int k）{

  int r= 1;

  while（k）{

    if（k&1） r= r*x%mod;

    x= x*x%mod;

    k>>= 1;

  }

  return r;

}

int main（）

{

  int a, b, k, n, m;

  Init（）; ///在所有的询问之前先算好，只算一次；

  while（scanf（"%d%d%d%d%d", &a, &b, &k, &n, &m）!

=EOF）{

    printf（"%d\n", c[k][m] * （（ Pow（a, n） * Pow（b, m））%mod ） %mod ）;

    //上面只是理论分析的代码，没有ac，但个人觉得没问题；

    //取模要边乘边取；

  }

}

1002、Factorial大整数

题目：

ProblemDescription

现有一个定义新运算：

F（x）=x!

+（x-1）!

。

Randy是个很“懒”的程序猿，希望小电脑能帮自己解决这个问题。

Input

第一行输入正整数N（N<10），接下来的N行，每行都有一个正整数x（x<1000）。

Output

与输入相对应地输出运算结果F（x）。

SampleInput

2

2

5

SampleOutput

3

144

分析：

X<1000，直接算计算机无法直接保存这么大的数，所以用到大整数（高精度）。

代码：

C++语言:

 jxnu_1002

//

/*2012-12-1514:

39:

21  Accepted  1002  0MS  260KB  VisualC++*/

#include

#include

const int M = 10000; //万进制int最大,如果只用+,-,M=1000000000

int ONE[] = {1, 1}; //大整数1

int ZERO[] = {1, 0}; //大整数0

int comp（int *a, int *b）{

  if （a[0] > b[0]）return 1;

  if （a[0] < b[0]）return -1;

  for （int i = a[0]; i >= 1; i--）{

    if （a[i] > b[i]）return 1;

    if （a[i] < b[i]）return -1;

  }

  return 0;

}

void PN（int *a）{//输出"%04d"10000进制

  printf（"%d", a[a[0]]）;

  for （int i = a[0] - 1; i >= 1; i--）printf（"%04d", a[i]）;

  printf（"\n"）;

}

void copy（int *a, int *b）{ //a=b，将大整数b拷贝给a;

  for （int i = 0; i<= b[0]; ++i）a[i]= b[i];

}

//大整数a+大整数b，答案保存到c中；

void add（int *a, int *b, int *c） {

  int s, i, t, d[1000];

  if（（b[0]== 1）&&（b[1]== 0））{ copy（c, a）; return; }

  if（（a[0] == 1） && （a[1] == 0））{ copy（c, b）; return; }

  if（a[0] >= b[0]）{ copy（c, a）; copy（d, b）; }

  else{ copy（c, b）; copy（d, a）; }

  s = c[0];

  t = d[0]; //c[0]>=d[0]

  c[s + 1] = 0;

  for （i = 1; i <= t; i++） {

    c[i] += d[i];

    if （c[i]>= M） { c[i]-= M; c[i+1]++; }

  }

  for（;i<= s; i++） {

    if（c[i] >= M）{ c[i]-= M; c[i + 1]++; }

    else break;

  }

  if（c[s + 1]> 0）c[0] = s + 1; //处理最后一位

}

//大整数a乘常数b,b

void mult（int *a, int b, int *d） {

  int w, i, p;

  if （b == 1） { copy（d, a）; return; }

  if （（b==0）||（a[0]==1 && a[1]==0））{

    d[0] = 1; d[1] = 0; return;

  }

  w = a[0];

  p = 0; //

  for（i = 1; i <= w; i++）{

    d[i] = a[i] * b + p;

    if （d[i] >= M）{ p= d[i] / M; d[i]%= M; }

    else p = 0;

  }

  if（p）{ w++; d[w] = p; }

  d[0]= w;

}

#definemaxn650

int ans[maxn];

int temp[maxn], temp1[maxn];

int main（）

{

  int n, x;

  scanf（"%d", &n）;

  while（n--）{

    scanf（"%d", &x）;

    copy（ ans, ONE ）;

    for（int i=2; i

      mult（ ans, i, temp ）;

      copy（ ans, temp ）;

    }

    mult（ ans, x, temp ）;

    add（ ans, temp, temp1 ）;

    copy（ ans, temp1 ）;

    //printf（"length=%d\n",ans[0]）;//输出位数；

    PN（ans）;

  }

}

1003、Rayrays广度优先搜索bfs

ProblemDescription

一天，小KD玩到了这个游戏:

YY出了一个类似的简易的模型……

游戏规则：

每次点击一个小朋友，他和他的周围的小朋友都会改变状态（蹲下的变成了站起来的，站起来的变成了蹲下的）

我们将这个抽象成如下图所示的1*N的图.对于一个单元格,黑色表示小朋友是站起来的,反之,蹲下的小朋友是是白色的.Source表示初始状态,Target表示目标状态.现在小KD有点偷懒,希望作为神牛的你帮小KD算出初始状态到目标状态的最少点击数.

Input

输入数据有多组。

对于每组数据：

第一行为N（N<=12）表示小朋友的个数.

第二行是初始状态,有N个数,每个数不是0就是1.（0表示小朋友是蹲下的,1表示小朋友

是站起来的）

第三行的结构跟第二行类似,表示目标状态.

Output

对于每组输入数据，输出一个数X,表示初始状态到目标状态的最少点击数。

如果无法到达目标,则请输出"Boring"

SampleInput

9

010001000

101010100

SampleOutput

2

分析：

广度优先搜索bfs的经典应用。

可以看一看数据结构书上关于bfs的讲解，每个状态可以看成一个点，按题目意思每个点之间或者可以直接转换到达，或者不可直接转换，抽象成图，就是有的点之间有边，有的没有，且边权全部为1（只转换一次）。

从源状态出发按bfs的方式遍历，一定可以走一条最短的路径到达目标路径（如果可达的话）。

Bfs采用队列（一种数据结构，书上也有）实现。

题目给的状态是一个01序列，可以转换成十进制保存，

比如n=4，序列：

0110，那么该状态是：

6；

比如n=6，序列：

010011，那么该状态是：

19；

我们就可以用数字表示状态了，题目n<=12，所以最大2^12的规模是可以保存的下的。

一个数字到另一个数字的转变方式按题目的意思是二进制表示中连续3位数字取反。

比如某个数的二进制表示：

001101101，那么这个数的转变方式有:

00

001

011

110

101

011

110

101

01

这几种连续位上的01进行取反，从而变成新的数字，

取反的方式用异或^就可以:

比如上面第3个011，也即

001101101

^

011100000

变成：

010001101

就是011变成了100，而其他位上的没变。

而011100000的生成，可以用位运算，intd=（1<<7）+（1<<6）+（1<<5）;

即d=2^7+2^6+2^5。

见C语言的运算符：

代码：

C++语言:

 jxnu_1003

/*2012-12-1515:

10:

28  Accepted  1003  0MS  272KB  VisualC++*/

#include

#include

const int N= （1<<12）;  ///1<<12<==>1*2^12;

int n;

int que[N+10];

int step[N+10];   //同步记录步数（转换了多少次）；

bool vis[N+10];  //标记是否在队列里；

int bfs（int st, int ed）{

  if（st==ed） return 0;

  memset（vis, 0, sizeof（vis））; //初始化；

  int h= 0, t= 0;

  que[t]= st;

  step[t++]= 0;

  vis[st]= 1;

  while（h!

=t）{

    int u= que[h++];  //取队头元素；

    for（int i=0; i

      int d= 0;

      if（ i !

= 0 ） d |= （1<<（i-1））;

      if（ i !

= n-1 ） d |= （1<<（i+1））;

      d |= （1<

      int c= u^d;

      if（ c==ed ） return step[h-1]+1;

      if（ !

vis[c] ）{

        vis[c]= 1;

        que[t]= c; //加入队尾；

        step[t++]= step[h-1]+1;

      }

    }

  }

  return -1; //队列已空，还未到达终态，返回-1；

}

int main（）

{

  while（scanf（"%d", &n）!

=EOF）{

    int begin, end;

    scanf（"%d", &begin）;

    for（int t, i=2; i<=n; ++i）{

      scanf（"%d", &t）;

      begin= （begin<<1） + t; ///begin<<1<==>begin*2;

    }

    scanf（"%d", &end）;

    for（int t, i=2; i<=n; ++i）{

      scanf（"%d", &t）;

      end= （end<<1） + t;

    }

    //printf（"%d%d\n",begin,end）;

    int ans= bfs（begin, end）;

    if（ -1 == ans ） puts（"Boring"）;

    else printf（"%d\n", ans）;

  }

}

1004、这是字符串问题吗？

字符串简单题

ProblemDescription

对于每一个英文字符串，计算出每一个字母出现的次数（不区分大小写），并按字母表顺序递增输出每个字母的个数。

Input

可输入多组字符串（字符串长度小于150），当输入“END”（不包含引号）时结束程序。

Output

每组字符串有K行输出，每行包括字母（大写）和它的出现次数，字母与次数后均空一格。

输出以单独一行“OVER”（不包括引号）结束。

SampleInput

AbCd

RandyRen

END

SampleOutput

A1

B1

C1

D1

OVER

A1

D1

E1

N2

R2

Y1

OVER

分析：

我是先把所有的小写字符转换成了大写字符。

再统计，仔细看看下面的代码吧。

代码：

C++语言:

 jxnu_1004

/*2012-12-1515:

16:

10  Accepted  1004  0MS  252KB  VisualC++*/

#include

#include

#definemaxn155

char ch[maxn];

int main（）{

  while（ scanf（"%s", ch）!

=EOF ）{

    if（ strcmp（ ch, "END" ） == 0 ） break;

    for（int i=0; ch[i]; ++i）

      ch[i] = ch[i]<='Z' ?

 ch[i] :

 ch[i]-32;

    int cnt[26];

    memset（ cnt, 0, sizeof（cnt））;

    for（int i=0; ch[i]; ++i）

      cnt[ ch[i]-'A' ]++;

    for（int i=0; i<26; ++i）

      if（ cnt[i]>0 ）

        printf（"%c%d \n", i+'A', cnt[i]）;

    puts（"OVER"）;

  }

}

1005、COH模拟题

ProblemDescription

每天晚上，某霄汉童鞋都会来找小KD讨论CompanyofHeroes（COH），并要周六和小KD去网吧战COH。

小KD表示这样会荒废大量的时间，于是决定当30号且为周六才会和某霄汉童鞋去网吧约战COH……

期末将至，没复习好高数的小KD希望知道他在2013年前到底浪费了多少个周六的时间。

这里定义约战COH那天不仅是30号还是星期六【一个条件没有达到那个月都不会进行COH大战，因为星期六要放假……】。

于是他找到了编程高手——你。

Input

输入数据有多组，每组占一行，每行仅有一个数，N。

表示小KD是从N年的12月31日24:

00（也就是第二年的第一天）开始和某霄汉童鞋去网吧约战COH的。

【保证1582<=N<=2013】（HINT：

2012年12月31日是星期一）

Output

对于每组输入数据，输出一行，每行输出仅有一个数，M。

表示小KD一共荒废了多少个周六的日子（以天为单位）。

SampleInput

2010

SampleOutput

3

题目在我做的时候不是这样子，没写2012年12月31日是星期一，

我以为是从计算的那一天起是星期一，即第N+1年的1月1日是星期二。

所以下面的代码没有ac，因为是从第N+1年的1月1日是星期二开始算起的，仅供参考。

C++语言:

 jxnu_1005

#include

using namespace std;

bool Is_year（int year）{

  return （year%400==0）||（year%4==0 && year%100!

=0）;

}

int main（）{

  int n;

  while（scanf（"%d", &n）!

=EOF）{

    if（n==2012 ||n==2013 ）{

      puts（"0"）;

      continue;

    }

    int year= n+1, month=1, day= 1, m= 2;

    int cnt= 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） ）{