3.1计数原理

1，抽屉原理：把n-1件东西放入n个抽屉，则至少有一个抽屉是空的

2，加法原理(分类加法计数原理)

3，乘法原理(分步乘法计数原理)

4，容斥原理

利用组合数和杨辉三角形打表计算:

void play_table()
{
    for(int i=0;i<=32;i++)
        for(int j=0;j<=i;j++)
        {
            if(!j||i==j)
              c[i][j]=1;
            else
              c[i][j]=c[i-1][j-1]+c[i-1][j];
        }
    return ;
}

 3.2稳定婚姻问题(Gale-Shapley算法)

https://blog.csdn.net/a854596855/article/details/44631851

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=30;
int couple;//总共多少对
int malelike[maxn][maxn],femalelike[maxn][maxn];
//男士对女士的喜欢程度（按降序排列）和女士对男士的喜欢程度 
int malechoice[maxn],femalechoice[maxn];//男士和女士的选择,男士选择了第几喜欢的 
int malename[maxn],femalename[maxn];//名字的hash,方便打印对应编号的名字 
int main(){
	int T;
	char str[30];
	scanf("%d",&T);
	while(T--)
	{
		queue<int> freemale;//没有配对的男士 
		scanf("%d",&couple);
		for(int i=0;i<couple;i++)
		{
			scanf("%s",str);
			malename[i]=str[0]-'a';
			freemale.push(malename[i]);
		}
		//将名字排序，便于字典序
		sort(malename,malename+couple);
		for(int i=0;i<couple;i++)
		{
			//女士是大写 
			scanf("%s",str);
			femalename[i]=str[0]-'A';
		}
		//男士对女士的印象，按降序排列
		for(int i=0;i<couple;i++)
		{
			scanf("%s",str);
			for(int j=0;j<couple;j++)
			malelike[i][j]=str[j+2]-'A';//他喜欢的是谁 
		}
		//女士对男士的打分，添加虚拟人物，编号为couple，为女士的初始对象
		for(int i=0;i<couple;i++)
		{
			scanf("%s",str);
			for(int j=0;j<couple;j++)
			femalelike[i][str[j+2]-'a']=couple-j;//她喜欢他多少 
			femalelike[i][couple]=0;
		}
		//初始化男士选自己最喜欢的女士，其实还是光棍 
		memset(malechoice,0,sizeof(malechoice));
		//女士先初始一个对象
		for(int i=0;i<couple;i++)
		femalechoice[i]=couple;
		while(!freemale.empty())
		{
			//找出一个未配对的男士，注意不要习惯性的pop
			int male=freemale.front();
			//男士心仪的女士
			int female=malelike[male][malechoice[male]];
			//如果当前的男士比原来的男友更好
			if(femalelike[female][male]>femalelike[female][femalechoice[female]])
			{
				//该男士成功脱单
				freemale.pop();
				//如果有前男友，则把前男友打回光棍,则该光棍只能考虑下一个女士 
				//不要把虚拟的人物加入队列，否则死循环或者错误 
				if(femalechoice[female]!=couple)
				{
					freemale.push(femalechoice[female]);
					malechoice[femalechoice[female]]++;
				}
				//当前男友为这位男士
				femalechoice[female]=male; 
			}
			//如果被该女士拒接，找下一个女士
			else
			malechoice[male]++;
		}
		for(int i=0;i<couple;i++)
		printf("%c %c\n",malename[i]+'a',
		malelike[malename[i]][malechoice[malename[i]]]+'A');
		puts("");
	}
	return 0;
}

3.3组合问题(与元素顺序无关)

存在性(着色法)，计数性(仅仅要求求出种类数：组合数，杨辉三角形，规律性)，构造性问题(纵横图问题)，最优化问题

组合数递推https://baike.sogou.com/v7805885.htm

3.4排列问题(与元素顺序有关)

组合排列问题中，最常出现的是计数问题，计数问题的解题思路一般有以下几种：

1，只取要的：把各种符合条件的情况枚举出来，再利用加法原理求和；

2，先全部取，再减去不要的；

3，先取后排。

选排列，错位排列，圆排列 数学一本通P110