东林离散大作业

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

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

2、am>#includeusingnamespacestd;intmain(){intn;while(scanf("%d",&n)!=-l){ints=0;for(inti=0;ivn;i++){inta;cin»a;s+=a;}intb=(s&l);if(b==1){cout«Hnotvendl;}else{cout«,,yes,,«endl;}平面图Problem:BTimeLimit:1000msMemoryLimit:65536KDescription已知n阶连通平面图G有r个面，请计算G

3、的边数m.(10分)Input输入数据有多组，每组有2个正整数n和r,分别代表顶点数和面数。Output在一行内输出这个平面图的边数。SampleInput76SampleOutput11#inelude#ineludeusingnamespacestd;intmain(){intx,y;while(~scanf("%d%d“,&x,&y)){cout«(x+y-2)«endl;树的边数Problem:CTimeLimit:1000msMemoryLimit:65536KDe

4、scription设m和t分别是2元正则树t的边数和树叶数,在给定树叶数t的前提下,请你计算边数m?(10分)Input输入数据有多组，每组有1个止整数t,代表正则树t的树叶数。Output在一行内输出边数m。SampleInput10SampleOutput18#inelude#ineludeusingnamespacestd;intmain(){intn;while(scanf(“％d“，&n)!=-l){cout«2*(n-l)«endl;}return0;错排Prob

5、lem:DTimeLimit:1000msMemoryLimit:65536KDescription在n个字母的全排列屮，使得每个字母都不在原来位置的排列数是多少？请使用错位排列的递推公式來计算本题。(10分)Input输入数据有多组，每组有1个正整数n(lv=代表字母的个数。Output在一行内输出这n个字母都不在原来位置的方法数。SampleInput2SampleOutput1#inelude#ineludeusingnamespacestd;intD(intx){if

6、(x==1){return0;}if(x==2){return1;}return(x-l)*(D(x-2)+D(x-1));}intmain(){intn;while(scanf("%dH/&n)!=-l){cout«D(n)«endl;}数字编码Problem:ETimeLimit:1000msMemoryLimit:65536KDescription一个编码系统用八进制数字对信息编码，一个码字是有效的当且仅当含有偶数个7,求n位长的有效码字有多少个？(15分)Input输入数据有多组，每组有1个止整数n(lv

7、=代表编码的长度。Output在一行内输出n位长的有效码字有多少个？SampleInput1SampleOutput7#inelude#ineludeusingnamespacestd;longa[100];intf(intn){if(n二二1){return7;}return6*f(n-l)+a[n-l];}intmain(){a[0]=1；for(inti=l;i<20;i++){a[i]=a[i-l]*8;}intn;while(scanf("%d"z&n)!=-l){

8、cout«f(n)«endl;}方格涂色Problem:FTimeLimit:1000msMemoryLimit:65536KDescription一个計n的方格用红、蓝、绿或橙色四种颜色涂色，如果有偶数个方格被涂成红色，还有偶数个方格被涂成绿色，问有多少种方案？(15分)Input输入数据有多组，每组有1个正整数n(l<=n<=10),K表方格的个数。Output在一行