东林离散大作业

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

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

3、行内输出这个平面图的边数。 Samp Ie Input 7 6 Samp Ie Output 11 #include #include stdio.h us i ng namespace std; i nt ma i n 0 int x, y ； whi le (scanf (%d%d, 树的边数 Problem:C Time Limit:1000ms Memory Limit:65536K Descr i pt i on 设rn和t分别是2元正则树t的边数和树叶数，在给定树叶数t的前提下，请你计算m? 边数（10分） I nput 输入数据有多组，每组有1个正整数t,代表正则树t的树叶数。

4、Output 在一行内输出边数m。 Samp Ie Input 10 Samp Ie Output 18 #incIude #incIude stdio.h using namespace std; i nt ma i n () ( int n; whi le(scanf (%d, return 0 错排 Problem:D Time Limit:1000ms Memory Limit:65536K Descr i pt i on 在n个字母的全排列中，使得每个字母都不在原来位置的排列数是多少？请使用错位 排列的递推公式来计算本题。(10分) 1 nput 输入数据有多组，每组有1个正整数n(

5、K=n=10),代表字母的个数。 Output 在一行内输出这n个字母都不在原来位置的方法数。 Samp Ie Input 2 Samp Ie Output 1 #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 return 0; return 0; 数字编码 Problem:E Time Limit:1000m

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

7、(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, 方格涂色 Problem:F Time Limit:1000ms Memory Limit:65536K Descr i pt i on 还有偶 一个1*n的方格用红、蓝、绿或橙色四种颜色涂色，如果有偶数个方格被涂成红色, 数个方格被涂成绿色，问有多少种方案？( 15分) 1 nput 输入数据有多组，每组有1个正整数n(1=n=10),代表方格的个数。Output 在一行内输出有多少种方案？ Samp Ie

8、Input 1 Samp Ie Output 2 #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, continue; 1 couta 2*n2 +a n-1 end I ; return 0; 最大公约数-离散数学 Problem:G Time Limit :1000ms Memory Limit:65536K Descr

9、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 16 Samp Ie Output No #incIude #incIude stdio.h us i ng namespace std; i nt ma i n () ( irrt n, m; whi Ie (scanf (%d%d, i f

10、(m n) swap (m, n); for (int i二2; i=n; i+) i f(m% i 二二 0 break; if (flag = fa I se) cout,lno,end I ; e I se coutyesend I ; return 0; 中国剩余定理 Problem:H Time Limit:1000ms Memory Limit:65535K Description根据孙子算经，里面有一个物不知数的问题，现在孙子的问题是：今有物，不知其 数，ml数之剩a1;m2数之剩a2;m3数之剩a3；请用中古剩余定理求解该数是多少，本题要求 最小的正整数解？ 1 nput 输入

11、数据有多组，每组一行，每行6个整数，分别为a1,m1, a2, m2, a3, m3;这里ml, m2, m3是 两两互素的！ Output对于每组数据，请计算该问题的最小正整数解？ Samp Ie Input 2 3 3 5 2 7 Samp Ie Output 23 # 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 i nt M