【NEFU離散】2020年離散數學大作業

找19lxy學長借的賬號，這些題大部分可以在學校OJ直接找到對應題目的，你們點擊鏈接即可，
考慮到各位可能不怎么會C++，所以離散作業使用純C語言進行解題.

題目

大多數是根據離散數學的公式來寫程式，如果你知道基礎公式的話就比較簡單，但是OJ上寫程式難度可能比銳格上大，因為沒法套資料吧呵呵，如果你沒玩過林大oj建議熟悉熟悉，
比賽在OJ比賽第四頁

后面題目OJ上開了歷年題目可以直接進去交

度數序列

題目鏈接

思路
可以看一下書本P135的例6.3
根據握手定理：所有頂點度數之和為邊數兩倍，
那么有推論，奇度頂點的個數一定是偶數的，
代碼

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){
	int n;
	while(~scanf("%d",&n)){
		int cnt=0;
		for(int i=1,x;i<=n;i++){
			scanf("%d",&x);
			if(x&1)cnt++;
		}
		if(cnt&1)puts("no");
		else puts("yes");
	}
	return 0;
}

平面圖

題目鏈接

思路
書本P159定理6.16
設G為任意的連通的平面圖，則n-m+r=2，其中n為頂點數，m為邊數，r為面數滿足
n ? m + r = 2 n-m+r=2 n?m+r=2
代碼

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){
	int n,r;
	while(~scanf("%d%d",&n,&r)){
		printf("%d\n",n+r-2);
	}
	return 0;
}

樹的邊數

題目鏈接

思路
2元正則樹：T的每個分支點恰有2個兒子
其實想想最特殊的情況，2元完全正則樹嘛（可以先看后面的一道題目）
可以發現 m = 2 ( t ? 1 ) m=2(t-1) m=2(t?1)

代碼

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){
	int t;
	while(~scanf("%d",&t)){
		printf("%d\n",2*(t-1));
	}
	return 0;
}

錯排/錯位排列

題目鏈接

思路
錯排公式：要么用遞推式，要么用近似值
代碼
D [ n ] = ( i n t ) ( n ! e + 0.5 ) D[n]=(int)(\frac {n!} e+0.5) D[n]=(int)(en!?+0.5)

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define e 2.718281828459
int main(){
	int n;
	while(~scanf("%d",&n)){
		int fac=1;
		for(int i=1;i<=n;i++)fac*=i;
		int ans=(int)(fac/e+0.5);
		printf("%d\n",ans);
	}
	return 0;
}

D [ n ] = ( n ? 1 ) ( D [ n ? 2 ] + D [ n ? 1 ] ) D[n]=(n-1)(D[n-2]+D[n-1]) D[n]=(n?1)(D[n?2]+D[n?1])
D [ 1 ] = 0 , D [ 2 ] = 1 D[1]=0,D[2]=1 D[1]=0,D[2]=1

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int D[15];
int main(){
	int n;
	D[1]=0,D[2]=1;
	for(int i=3;i<=10;i++)D[i]=(i-1)*(D[i-1]+D[i-2]);
	while(~scanf("%d",&n)){
		printf("%d\n",D[n]);
	}
	return 0;
}

數字編碼

題目鏈接

思路
書上P218例10.3
代碼
遞推
a [ n ] = 6 ? a [ n ? 1 ] + 8 n ? 1 a[n]=6*a[n-1]+8^{n-1} a[n]=6?a[n?1]+8n?1
a [ 1 ] = 7 a[1]=7 a[1]=7

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int a[15];
int main(){
	int n;
	a[1]=7;
	for(int i=2;i<=10;i++)a[i]=6*a[i-1]+pow(8,i-1);
	while(~scanf("%d",&n)){
		printf("%d\n",a[n]);
	}
	return 0;
}

非遞推式
a [ n ] = 6 n + 8 n 2 a[n]=\frac {6^n+8^n}2 a[n]=26n+8n?
注意，如果用pow的話要轉int，不然直接printf(%d)為輸出0的

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int main(){
	int n;
	while(~scanf("%d",&n)){
		printf("%d\n",(int)(pow(6,n)+pow(8,n))/2);
	}
	return 0;
}

最大公約數-離散數學

題目鏈接

思路
x與y互素就是 g c d ( x , y ) = 1 gcd(x,y)=1 gcd(x,y)=1
代碼

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
int main(){
	int x,y;
	while(~scanf("%d%d",&x,&y)){
		if(gcd(x,y)==1)puts("yes");
		else puts("no");
	}
	return 0;
}

接下來cy老師開始亂殺了嗚嗚嗚
下面的題目去這個比賽里面做

非降路徑

題目鏈接（沒開放）

思路
反手一個走迷宮DP統計方案數呵呵（如果你開心的話）
好吧，還是直接用書上P199公式吧
a n s = C c ? a + d ? b c ? a ans=C_{c-a+d-b}^{c-a} ans=Cc?a+d?bc?a?
本質是求組合數，資料非常友好，但是你直接階乘會溢位的，所以我們求組合數要用遞推式

代碼

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int C[30][30];
int main(){

	for(int i=0;i<=24;i++)
		for(int j=0;j<=i;j++)
			if(!j)C[i][j]=1;
			else C[i][j]=C[i-1][j-1]+C[i-1][j];
			
	int a,b,c,d;	
	scanf("%d%d%d%d",&a,&b,&c,&d);
	int m=c-a+d-b,n=c-a;
	printf("%d\n",C[m][n]);
	return 0;
}

2元完全正則樹

題目鏈接（沒開放）

思路
P178概念題目啦
知道啥是2元完全正則樹即可
概念拆分：
r元樹：T的每個分支點至多有r個兒子
r元正則樹：T的每個分支點恰好有r個兒子
r元完全正則樹：T是r元正則樹，且所有樹葉的層數均為樹高
樹的層數：樹根到任意一點的通路長度
樹的高：最大層數

可以發現，對于樹高為h的2元完全正則樹
頂 點 數 = 2 h + 1 ? 1 頂點數=2^{h+1}-1 頂點數=2h+1?1
邊 數 = 0 + 2 + 4 + 8 + 16 … … 邊數=0+2+4+8+16…… 邊數=0+2+4+8+16……
樹 葉 = 2 h 樹葉=2^h 樹葉=2h

如果求2的次方，可以采用位移運算
代碼

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int main(){
	int h;
	scanf("%d",&h);
	int edge=0;
	for(int i=1;i<=h;i++)edge+=1<<(i);
	printf("%d %d %d",(1<<(h+1))-1,edge,1<<h);
	return 0;
}

計算連通分支數

題目鏈接（未開放）

思路
書P159推論
G是具有k（k>=2）個連通分支的平面圖，則 n ? m + r = k + 1 n-m+r=k+1 n?m+r=k+1

代碼

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){
	int n,m,r;
	scanf("%d%d%d",&n,&m,&r);
	printf("%d",n-m+r-1);
	return 0;
}

求懸掛頂點

題目鏈接（未開放）

思路
根據握手定理：所有頂點度數之和為邊數兩倍
懸掛頂點度數為1，
設有x個懸掛頂點
2 m = （ 2 + 3 + 4 + 5 + 6 ） t + x 2m=（2+3+4+5+6）t+x 2m=（2+3+4+5+6）t+x
x = 2 m ? 20 t x=2m-20t x=2m?20t
代碼

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){
	int m,t;
	scanf("%d%d",&m,&t);
	printf("%d",2*m-20*t);
}