题库十九页（刷题者的福利）

斐波那契额数列

拓扑排序

#include<bits/stdc++.h>
using namespace std;
int n,m;				//n:节点数 m:边数 
int cnt[10001];		   //储存节点入度 
int main(){
	
	cin>>n>>m;
	vector<int> g[10001];//节点之间的连接关系 
	vector<int> v;		 //储存序列 (输出)
	queue<int> q;       //储存访问的节点
	
	for(int i=1;i<=m;i++){
		
		int x, y;
		cin >> x >> y;
		cnt[y]++; //节点y的入度增加一
		g[x].push_back(y); 
		
	} 
	//此时已完成输入
	for(int i=1;i<=n;i++){
		//找出入度是0 
		if(cnt[i]==0) q.push(i);
	} 
	
	while(q.size()){
		
		int temp = q.front();
		v.push_back(temp); //记录到v里面
		q.pop();           //访问完队首
		for(int i=0;i<g[temp].size();i++){
			
			int p=g[temp][i];  //和temp相连的点 
			cnt[p]--;		   //p点的入度-1 
			if(cnt[p]==0){
				q.push(p);  //下一次输出 
			}
		} 
		 
	}
	if(v.size()!=n){
		cout<<"has circle";//有圈无法排序 
		return 0;
	}
	
	for(int i=0;i<v.size();i++){
		cout<<v[i]<<" ";
	}
	return 0;
} 

二叉树遍历

# include <bits/stdc++.h>
using namespace std;
vector<int> v[1001];
int n,l,r;

void fun1(int x){//x:当前节点 先序 
	cout<<x<<" ";
	if(v[x][0]) fun1(v[x][0]);//左子节点 
	if(v[x][1]) fun1(v[x][1]);//右子节点 
	
}

void fun2(int x){//中序 
	if(v[x][0]) fun2(v[x][0]);
	cout<<x<<" ";
	if(v[x][1]) fun2(v[x][1]);
}

void fun3(int x){//后序 
	if(v[x][0]) fun3(v[x][0]);
	if(v[x][1]) fun3(v[x][1]);
	cout<<x<<" ";
}
int main()
{	
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>l>>r;
		v[i].push_back(l);
		v[i].push_back(r);
		
	}
	fun1(1);
	cout<<endl;
	fun2(1);
	cout<<endl;
	fun3(1);
	return 0;
}

二叉树的性质：
性质1：第1层最多有多少个节点？ 2^(i-1)
性质2：i层一共有多少个节点？   2^i-1 
性质3：对于任意的二叉树，n0=n2+1
n = n0+n1+n2
n = n1+n2*2+1
n0 = n2+1
性质4：求二叉树的深度 floor(log2(n))+1
性质5：对于完全二叉树
一个节点的编号为i，左子节点编号为2*i，右子节点编号为2*i+1叶子节点的数量为 n-n/2; 

完全背包
# include <bits/stdc++.h>//背包 
using namespace std;
int n,total;
int v[100001],c[100001];
int dp[100001];
int main()
{
	cin>>n>>total;
	for(int i=1;i<=n;i++) cin>>v[i]>>c[i];
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=total;j++){
			if(j>=v[i]){
				dp[j]=max(dp[j],c[i]+dp[j-v[i]]);
			}
		}
	}
	cout<<dp[total];
	return 0;
}

01背包

# include <bits/stdc++.h>//背包 
using namespace std;
int n,total;
int v[100001],c[100001];
int dp[100001];
int main()
{
	cin>>n>>total;
	for(int i=1;i<=n;i++) cin>>v[i]>>c[i];
	
	for(int i=1;i<=n;i++){
		for(int j=total;j>=1;j--){
			if(j>=v[i]){
				dp[j]=max(dp[j],c[i]+dp[j-v[i]]);
			}
		}
	}
	cout<<dp[total];
	return 0;
}

//STL容器2

// vector 动态数组、向量

vector<int> vec;//定义
vector<int> vec1(5);// 创建 初始空间为5，元素默认值为0
vector<int> vec2(5,2);//创建 初始空间为5 元素默认值为2
vector<int> vec3(vec2);//创建 其拷贝vec2
int arr[5]={1,2,3,4,5};
vector<int>vec4(arr);//创建 其拷贝数组arr
vector<int>vec5(arr+1,arr+5);//创建 其拷贝数组区间[1,5) 
//vector的常规函数 
vec.push_back(n);//把n添加到vec的最后
vec.front(); //返回vec的第一个元素
vec.pop_back();//删除vec的最后一个元素
vec.erase(iter);//删除iter所在位置元素
vec.clear();//清空 
vec.empty(); //判断是否为空
//set的创建
set<int> set1;//定义 
set<int> set2(set1);//创建set2，其内容拷贝set1 
int arr[5]={1,2,3,4,5}; 
set<int> set4(arr,arr+5);//创建set4,其内容拷贝十足区间[0,5) 
//set的常规函数 
set1.insert(n);//将n添加到set1的最后 
set1.find(n);//返回set1中间值为n的迭代器位置，如果没有返回end()； 
set1.erase(x);//删除值为x的所有元素返回删除数量 
set1.erase(iter);//删除iter所在位置的元素 
set1.erase(left,rigrt);//删除 [left,rigrt)范围内所有元素 
set1.clear();//清空 
set1.empty();//判断是否为空
//迭代器访问(vector)
vector<int>::iterator iter;
for(iter=vec.begin();iter!=vec.end;iter++) cout<<*iter<<" ";
//迭代器访问(set)
set<int>::iterator iter;
for(iter=set.begin();iter!=set.end();iter++) cout<<*iter<<" ";
//利用数组下标直接访问但是需要获取当前vec的长度 
for(int i=0;i<vec.size();i++) cout<<vec[i]<<" "; 
//map
map<string,int> a; //第一个表示key数据类型，第二个表示value数据类型
a["one"] = 1; 
a["tow"] = 2;
a["one"] = 3;
//赋值时，key值作为下标，后面的数据作为对应key的value元素，在map中新添加一对数据
//赋值时，如果key值已经存在，表示将此key值对应的value元素修改为新的数据
cout << a["one"] << endl;
//key值可以作为下标，直接输出对应的元素
cout << a["three"] << endl;
//注意：下标访问不会做下标检查，如上语句不会报错，但打印结果为空，因为下标访问会插入不存在的key，对应的value为默认值
a.insert({"three",3}); //将指定键值对插入到map中，插入元素会自动插入到合适的位置，使整个map有序，默认是按照key从小到大排序
a.erase("one"); //删除指定key值的键值对
cout << a.count("three") << endl; //查询指定key值是否出现
cout << a.empty() << endl; //判断是否为空，非空为0，空为1 
cout << a.size() << endl; //获取map长度

map<string,int>::iterator it = a.begin(); //创建一个map类型迭代器  
for(;it!=a.end();it++){
	cout << it->first << " " << it->second << endl;
} //遍历并输出，因为是类结构体指针，每个键值对通过first访问key，second访问value
return 0;

}

高精度加法

# include <bits/stdc++.h>
using namespace std;
int main()
{
	char s1[10005]={},s2[10005]={};
	int a[10005]={},b[10005]={},c[10005]={};
	cin>>s1>>s2;
	for(int i=strlen(s1)-1,j=0;i<strlen(s1);i--,j++){
		a[j]=s1[i]-'0';
	} 
	for(int i=strlen(s2)-1,j=0;i<strlen(s2);i--,j++){
		b[j]=s2[i]-'0';
	} 
	int len=max(strlen(s1),strlen(s2));
	for(int i=0;i<len;i++){
		c[i]+=a[i]+b[i];
		if(c[i]>=10){
			c[i]-=10;
			c[i+1]+=1;
		}
	}
	if(c[len]!=0) len++;
	for(int i=len-1;i>=0;i--){
		cout<<c[i];
	}
	return 0;
}

高精度减法

#include<bits/stdc++.h>
using namespace std;
int a[100000],b[100000],c[100000];
int main(){
	string s1,s2;
	cin>>s1>>s2;
	int len=s1.size(),len1=s2.size();
	if(len<len1||(len==len1&&s1<s2)) {
		swap(s1,s2);
		swap(len,len1);
		cout<<'-';
	}
	for(int i=0;i<len;i++) a[len-1-i]=s1[i]-48;
	for(int i=0;i<len1;i++) b[len1-1-i]=s2[i]-48;
	for(int i=0;i<len;i++){
		if(a[i]-b[i]<0){
			a[i+1]-=1;
			a[i]+=10;
		}
		c[i]=a[i]-b[i];
	}
	while(len>1&&c[len-1]==0) len--;
	for(int i=len-1;i>=0;i--) cout<<c[i];
	return 0;
}

广度优先搜索

using namespace std;
const int N=1e6+1;//创建一个常量
bool vis[N];//标记点是否被走过 
int n,k;
struct node{
	int x;
	int time;   //位置和时间 
};
int fx[3]={1,-1};//三个方向 
void bfs(){
	//1.首元素入队 
	node head={n,0};
	queue<node> q;
	q.push(head);
	vis[n]=1;
	//2.进入循环
	while(q.size()){
		//2.1获取首元素
		head=q.front();
		fx[2]=head.x;
		//2.2遍历三个方向
		for(int i=0;i<=2;i++){
			int xx=head.x+fx[i];
			if(xx==k){
				cout<<head.time+1;
				return ;
			}
			if((0<=xx&&xx<=100000)&&!vis[xx]){
				node tmp={xx,head.time+1};
				q.push(tmp);
				vis[xx] = 1;
			}
		} 
		q.pop();
	} 
} 
int main(){
	cin>>n>>k;	
	bfs();
	return 0;
} 
```

传 送 门

OJ

B站

洛谷

CSDN

百度~优先搜索~

队列加栈操作

//stack<int> sta;//创建一个栈
//sta.push(a);//入栈
//int a=sta.top();//返回栈顶元素
//sta.pop();//出栈
//sta.empty();//判断栈是否为空   1为空，0为非空
//sta.clear();//清空

//queue<int> que;//创建一个队列
//que.push(a);//入队
//int a=que.front();//返回队头元素
//que.pop();//出队
//que.empty();//判断队列是否为空   1为空，0为非空
//que.clear();//清空

二分查找模板

#include<bits/stdc++.h>
using namespace std;
int main(){
  int erfen(int c[],int b,int g){
  	int tou=0,wei=b-1;
  	while(tou<=wei){
  		int mid=(tou+wei)/2;
  		if(c[mid]>=g){
  			wei=mid-1;
  		}else if(c[mid]<g){
  			tou=mid+1;
  		}
  	}
  	if(c[tou]==g){
  		return tou+1;
}
	return -1;	
}

Copy

快速排序模板

#include <bits/stdc++.h>
using namespace std;
/*
对n个数进行排序 
*/
const int N=1e5+5;
int a[N];//原数组 
int n;
void fast_sort(int left,int right){
	//基本情况，递归边界 
	if(left>=right){
		 return;
	}
	//交换枢纽元，一般选中间值
	int mid=(left+right)/2;
	//交换枢纽元和最右边的值 
	swap(a[mid],a[right]);
	int i=left,j=right-1;
	while(i<=j){//区间没有交错，还有元素处理
		//i往右移动，直到找到比枢纽元大的数 
		while(a[i]<a[right]){
			i++;
		}
		//j往左移动，直到找到比枢纽元小的数 
		while(a[j]>a[right]){
			j--;
		}
		if(i<=j){
			swap(a[i],a[j]);
			i++;
			j--;
		}
	}
	//交换枢纽元和i交换 
	swap(a[right],a[i]);
	
	//对左右区间进一步划分 
	fast_sort(left,i-1);//左 
	fast_sort(i+1,right);//右 
}

int main(){
	//先输入一个n,再输入n个数 
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	fast_sort(1,n);
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}

三、Windows CMD命令大全

1. gpedit.msc-----组策略
2. sndrec32-------录音机
3. Nslookup-------IP地址侦测器 ，是一个 监测网络中 DNS 服务器是否能正确实现域名解析的命令行工具。 它在 Windows NT/2000/XP 中均可使用 , 但在 Windows 98 中却没有集成这一个工具。
4. explorer-------打开资源管理器
5. logoff---------注销命令
6. shutdown-------60秒倒计时关机命令
7. lusrmgr.msc----本机用户和组
8. services.msc---本地服务设置
9. oobe/msoobe /a----检查XP是否激活
10. notepad--------打开记事本
11. cleanmgr-------垃圾整理
12. net start messenger----开始信使服务
13. compmgmt.msc---计算机管理
14. net stop messenger-----停止信使服务
15. conf-----------启动netmeeting
16. dvdplay--------DVD播放器
17. charmap--------启动字符映射表
18. diskmgmt.msc---磁盘管理实用程序
19. calc-----------启动计算器
20. dfrg.msc-------磁盘碎片整理程序
21. chkdsk.exe-----Chkdsk磁盘检查
22. devmgmt.msc--- 设备管理器
23. regsvr32 /u *.dll----停止dll文件运行
24. drwtsn32------ 系统医生
25. rononce -p----15秒关机
26. dxdiag---------检查DirectX信息
27. regedt32-------注册表编辑器
28. Msconfig.exe---系统配置实用程序
29. rsop.msc-------组策略结果集
30. mem.exe--------显示内存使用情况
31. regedit.exe----注册表
32. winchat--------XP自带局域网聊天
33. progman--------程序管理器
34. winmsd---------系统信息
35. perfmon.msc----计算机性能监测程序
36. winver---------检查Windows版本
37. sfc /scannow-----扫描错误并复原
38. taskmgr-----任务管理器(2000/xp/2003
39. wmimgmt.msc----打开windows管理体系结构(WMI)
40. wupdmgr--------windows更新程序
41. wscript--------windows脚本宿主设置
42. write----------写字板
43. wiaacmgr-------扫描仪和照相机向导
44. winchat--------XP自带局域网聊天
45. mplayer2-------简易widnows media player
46. mspaint--------画图板
47. mstsc----------远程桌面连接
48. magnify--------放大镜实用程序
49. mmc------------打开控制台
50. mobsync--------同步命令
51. iexpress-------木马捆绑工具，系统自带
52. fsmgmt.msc-----共享文件夹管理器
53. utilman--------辅助工具管理器
54. dcomcnfg-------打开系统组件服务
55. ddeshare-------打开DDE共享设置
56. osk------------打开屏幕键盘
57. odbcad32-------ODBC数据源管理器
58. oobe/msoobe /a----检查XP是否激活
59. ntbackup-------系统备份和还原
60. narrator-------屏幕“讲述人”
61. ntmsmgr.msc----移动存储管理器
62. ntmsoprq.msc---移动存储管理员操作请求
63. netstat -an----(TC)命令检查接口
64. syncapp--------创建一个公文包
65. sysedit--------系统配置编辑器
66. sigverif-------文件签名验证程序
67. ciadv.msc------索引服务程序
68. shrpubw--------创建共享文件夹
69. secpol.msc-----本地安全策略
70. syskey---------系统加密，一旦加密就不能解开，保护windows xp系统的双重密码
71. services.msc---本地服务设置
72. Sndvol32-------音量控制程序
73. sfc.exe--------系统文件检查器
74. sfc /scannow---windows文件保护
75. ciadv.msc------索引服务程序
76. tourstart------xp简介(安装完成后出现的漫游xp程序)
77. taskmgr--------任务管理器
78. eventvwr-------事件查看器
79. eudcedit-------造字程序
80. compmgmt.msc---计算机管理
81. packager-------对象包装程序
82. perfmon.msc----计算机性能监测程序
83. charmap--------启动字符映射表
84. cliconfg-------SQL SERVER 客户端网络实用程序
85. Clipbrd--------剪贴板查看器
86. conf-----------启动netmeeting
87. certmgr.msc----证书管理实用程序
88. regsvr32 /u *.dll----停止dll文件运行
89. regsvr32 /u zipfldr.dll------取消ZIP支持
90. cmd.exe--------CMD命令提示符哪里有什么胭脂想象，不过是虚晃一梦罢了，梦醒了，什么都没有了

下面有东西（一定要看）

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

| 

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|


\   |    /

\  |  /

  \ /


都说了别看