东林离散大作业(20210426141221)

1、度数序列Problem:ATime Limit:1000msMemory Limit:65536KDescr i pt ion由握手定理我们知道任意的一个图中，所有顶点的度数之和等于边数的2倍，那么给你一个 无向图的度数序列，你能判定它能否构成无向图吗？ (10分)I nput输入数据有多组，每组第一行有1个数为n(K=n=100),接下来第二行有n个正整数，代 表n个度数。Output如果能构成图，则在一行内输出yes,否则输出no。Samp Ie Input412 3 4Samp Ie OutputYes#incIude #includeus i ng namespace std;i nt

2、 ma i n () int n;whi le(scanf (%d, &n) !=-1) int s = 0;for (int i二0; in; i+) irrt a;c i na;s +二 a;)i nt b 二(s&1);if (b = 1) coutnoendI; e I se coutyesXend I ;平面图Problem:Time Limit:1000msMemory Limit:65536KDescr i pt i onOutput已知n阶连通平面图G有r个面，请计算G的边数m.(10分)Input 输入数据有多组，每组有2个正整数n和r,分别代表顶点数和面数。 在一行内输出这

3、个平面图的边数。Samp Ie Input7 6Samp Ie Output11#include #include stdio.hus i ng namespace std;i nt ma i n 0 int x, y ；whi le (scanf (%d%d, &x, &y) cout (x+y-2) end I ;树的边数Problem:CTime Limit:1000msMemory Limit:65536KDescr i pt i on设rn和t分别是2元正则树t的边数和树叶数，在给定树叶数t的前提下，请你计算m? 边数（10分）I nput输入数据有多组，每组有1个正整数t,代表正则

4、树t的树叶数。Output在一行内输出边数m。Samp Ie Input10Samp Ie Output18#incIude #incIude stdio.husing namespace std;i nt ma i n ()(int n;whi le(scanf (%d, &n) !=-1) cout2* (n1) end I ;return 0错排Problem:DTime Limit:1000msMemory Limit:65536KDescr i pt i on在n个字母的全排列中，使得每个字母都不在原来位置的排列数是多少？请使用错位 排列的递推公式来计算本题。(10分)1 nput输

5、入数据有多组，每组有1个正整数n(K=n=10),代表字母的个数。Output在一行内输出这n个字母都不在原来位置的方法数。Samp Ie Input2Samp Ie Output1#include #include us i ng namespace std; int D(int x) if (x 二二 1) return 0;if (x = 2) return 1 ;return (x - 1)* (D (x2) + D (x 1);i nt ma i n ()int n;whi le(scanf&n) !=-1) coutD (n) end I ;return 0;return 0;数字

6、编码Problem:ETime Limit:1000msMemory Limit:65536KDescription 一个编码系统用八进制数字对信息编码，一个码字是有效的当且仅当含有偶数个长的有效码字有多少个？( 15分)7，求D位I nput输入数据有多组，每组有1个正整数n(1=n=10),代表编码的长度。Output在一行内输出n位长的有效码字有多少个？Samp Ie Input1Samp Ie Output7#incIude #inelude stdio.hus i ng namespace std;I ong a 100;int f (int n) if(n = 1) return

7、7;return 6*f(n-1)+anT;i nt ma i n ()a0二 1；for (int i=1; i20; i+)ai二 ai-1*8;int n;whi le(scanf (%d, &n) !=-1) coutf (n) end I ;方格涂色Problem:FTime Limit:1000msMemory Limit:65536KDescr i pt i on还有偶一个1*n的方格用红、蓝、绿或橙色四种颜色涂色，如果有偶数个方格被涂成红色, 数个方格被涂成绿色，问有多少种方案？( 15分)1 nput输入数据有多组，每组有1个正整数n(1=n=10),代表方格的个数。Outp

8、ut在一行内输出有多少种方案？Samp Ie Input1Samp Ie Output2 #include #incIudestdio. h using namespace std; Iong a100;I ong b100;i nt ma i n ()a0二 1；b0二 1;for (int i=1; i20; i+) ai二 ai-1 * 2;int n;whi le(scanf (%d, &n) !二T) if (n = 0) cout1endI ; continue;1 couta 2*n2 +a n-1 end I ;return 0;最大公约数-离散数学Problem:GTime

9、Limit :1000msMemory Limit:65536KDescr i ption已知用辗转相除法可以计算2个数的最大公约数，2个数互素的条件是2个数的最大公因子是1,现在的问题是让你判断2个数是否是互素的？( 15分)Input输入数据有多组，每组有2个正整数a, b(1=a,b=1000000) Output如果这2个数互素，在一行内输出yes,否则输出no.Samp Ie Input 10 11 10 16Samp Ie OutputNo#incIude #incIude stdio.hus i ng namespace std;i nt ma i n ()(irrt n, m;

10、 whi Ie (scanf (%d%d, &n, &m) !=-1)Ibool flag = true;i f (m n)swap (m, n);for (int i二2; i=n; i+) i f(m% i 二二 0 & n%i 二二 0) flag 二 false;break;if (flag = fa I se) cout,lno,end I ; e I se coutyesend I ; return 0;中国剩余定理Problem:HTime Limit:1000msMemory Limit:65535KDescription根据孙子算经，里面有一个物不知数的问题，现在孙子的问题是

11、：今有物，不知其 数，ml数之剩a1;m2数之剩a2;m3数之剩a3；请用中古剩余定理求解该数是多少，本题要求 最小的正整数解？1 nput输入数据有多组，每组一行，每行6个整数，分别为a1,m1, a2, m2, a3, m3;这里ml, m2, m3是 两两互素的！Output对于每组数据，请计算该问题的最小正整数解？Samp Ie Input2 3 3 5 2 7Samp Ie Output23# i ncIude#include us i ng namespace std;int f i ndM_(i nt M, i nt m) for (int i 二0; i100; i+) if (M*iT)%m 二二 0) return i ;i nt ma i n () int a1, a2, a3;int nd, m2, m3; while Cscanf (%d%d%d%d%d%dnf &a1, &m1, &a2, &m2, &a3, &m3)i nt M1 = m2