东林离散大作业.doc

《东林离散大作业.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、度数序列Problem:ATimeLimit:1000msMemoryLimit:65536KDescription由握手定理我们知道任意的一个图中，所有顶点的度数之和等于边数的2倍，那么给你一个无向图的度数序列，你能判定它能否构成无向图吗？(10分）Input输入数据有多组，每组第一行有1个数为n(1<=n<=100)，接下来第二行有n个正整数，代表n个度数。Output如果能构成图，则在一行内输出yes，否则输出no。SampleInput41234SampleOutputYes#include

2、m>#includeusingnamespacestd;intmain(){intn;while(scanf("%d",&n)!=-1){ints=0;for(inti=0;i>a;s+=a;}intb=(s&1);if(b==1){cout<<"no"<

3、计算G的边数m.（10分）Input输入数据有多组，每组有2个正整数n和r,分别代表顶点数和面数。Output在一行内输出这个平面图的边数。SampleInput76SampleOutput11#include#includeusingnamespacestd;intmain(){intx,y;while(~scanf("%d%d",&x,&y)){cout<<(x+y-2)<

4、536KDescription设m和t分别是2元正则树t的边数和树叶数，在给定树叶数t的前提下，请你计算边数m？（10分）Input输入数据有多组，每组有1个正整数t,代表正则树t的树叶数。Output在一行内输出边数m。SampleInput10SampleOutput18#include#includeusingnamespacestd;intmain(){intn;while(scanf("%d",&n)!=-1){cout<<2*(n-1)<

5、;}错排Problem:DTimeLimit:1000msMemoryLimit:65536KDescription在n个字母的全排列中，使得每个字母都不在原来位置的排列数是多少？请使用错位排列的递推公式来计算本题。（10分）Input输入数据有多组，每组有1个正整数n(1<=n<=10),代表字母的个数。Output在一行内输出这n个字母都不在原来位置的方法数。SampleInput2SampleOutput1#include#includeusingnamespacestd

6、;intD(intx){if(x==1){return0;}if(x==2){return1;}return(x-1)*(D(x-2)+D(x-1));}intmain(){intn;while(scanf("%d",&n)!=-1){cout<

7、nput输入数据有多组，每组有1个正整数n(1<=n<=10),代表编码的长度。Output在一行内输出n位长的有效码字有多少个？SampleInput1SampleOutput7#include#includeusingnamespacestd;longa[100];intf(intn){if(n==1){return7;}return6*f(n-1)+a[n-1];}intmain(){a[0]=1;for(inti=1;i<20;i++){a[i]=a[i-1]*8;}i

8、ntn;while(scanf("%d",&n)!=-1){cout<