河工oj（1101-1113）

1101 求组合数（函数专题）

代码

#include<bits/stdc++.h>
using namespace std;

int fact(int n) {
	int res = 1;
	while(n) {
		res *= n--;
	}
	return res;
} 

int main() {
	int m, k;
	cin >> m >> k;
	cout << fact(m)/fact(k)/fact(m-k) << endl;
	return 0;
}

1102 计算退票费（函数专题）

代码

#include<bits/stdc++.h>
using namespace std;

double CancelFee(double p) {
	double fee = p*0.05;
	int f = p*0.05;
	double xs = fee-f;
	if(xs<0.05) xs = 0;
	else if(xs>=0.75) xs = 1;
	else xs = 0.5;
	return xs+1.0*f;
}

int main() {
	double p;
	cin >> p;
	printf("%.1lf\n",CancelFee(p));
	return 0;
}

1103 回文数

代码(stl的compare)

截取前后

#include<bits/stdc++.h>
using namespace std;

bool solve(int n) {
	string s = to_string(n);
	int len = s.size();
	int i = len/2; // 位序 
	string s1 = s.substr(0,i);
	if(len&1) i ++; //中间独子的位序 
	string s2 = s.substr(i,len-i);
	reverse(s2.begin(),s2.end());
	if(s2.compare(s1)==0) return true;
	else return false;
	 
}

int main() {
	int m, n;
	cin >> m >> n;
	for(int i = m; i <= n; i ++) {
		if(solve(i)) cout << i << " ";
	}
	return 0;
}

代码2（双指针算法）

#include<bits/stdc++.h>
using namespace std;

bool solve(int n) {
	string s = to_string(n);
	// 这里判断条件不能是指针相遇（i==j）
	// 应该是相遇或相互错过，因为两位数时，各自加1和减1相当于位置互换，不相遇 
	for(int i = 0, j = s.size()-1; i < j; i++, j --) {
		if(s[i]!=s[j]) return false;
	} 
	return true;
}

int main() {
	int m, n;
	cin >> m >> n;
	for(int i = m; i <= n; i ++) {
		if(solve(i)) cout << i << " ";
	}
	return 0;
}

1104 不确定进制转换

代码

#include<bits/stdc++.h>
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	int flag = 1;
	if(n == 0) {
		cout << 0 << endl;
		return 0;
	}
	if(n<0) {
		flag = -flag;
		n = -n;
	}
	vector<int> a;
	while(n) {
		a.push_back(n%k);
		n /= k;
	}
	if(flag==-1) cout << "-";
	for(int i = a.size()-1; i >= 0; i --) cout << a[i];
	return 0;
}

1105 求最大数（函数的嵌套调用）

代码1

#include<bits/stdc++.h>
using namespace std;

int main () {
	int a, b, c;
	cin >> a >> b >> c;
	if(a<b) swap(a,b);
	if(a<c) swap(a,c);
	if(b<c) swap(b,c);
	cout << a << endl;
	return 0;
}

代码2

#include<bits/stdc++.h>
using namespace std;

int main () {
	vector<int> a;
	for(int i = 0; i < 3; i ++) {
		int x; cin >> x;
		a.push_back(x);
	} 
	sort(a.begin(),a.end());
	cout << a[2] << endl;
	return 0;
}

代码3

#include<bits/stdc++.h>
using namespace std;

int main () {
	int a[3];
	for(int i = 0; i < 3; i ++) cin >> a[i];
	sort(a,a+3);
	cout << a[2] << endl;
	return 0;
}

1106 求n！（递归函数）

代码（非递归）

#include<bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;
	int res = 1;
	while(n) {
		res *= n--;
	} 
	cout << res << endl;
	
	return 0;
}

代码2（递归）

#include<bits/stdc++.h>
using namespace std;

int solve(int n) {
	if(n == 1) return 1;
	return n*solve(n-1);
}

int main() {
	int n;
	cin >> n;
	cout << solve(n) << endl;
	
	return 0;
}

1107 汉诺塔

代码

#include<bits/stdc++.h>
using namespace std;

void Move(int n,char a,char b,char c) {
	if(n == 1) {
		cout << a << "->" << c << endl; 
		return ;
	}
	if(n == 2) {
		cout << a << "->" << b << endl;
		cout << a << "->" << c << endl;
		cout << b << "->" << c << endl;
		return ;
	}
	Move(n-1,a,c,b);
	Move(1,a,b,c);
	Move(n-1,b,a,c);
	return ;
}

int main() {
	int n;
	cin >> n;
	Move(n,'A','B','C');
	
	return 0;
}

代码2（非递归，模拟递归工作栈）

移动结构： a 借助b 移动到 c

#include<bits/stdc++.h>
using namespace std;

// 汉诺塔移动结构 
struct hnoi {
	int num;
	char a;
	char b;
	char c;
};

const int N = 1e5+10;
hnoi h[N]; int hh = 0, tt = 0;

void solve(int n,char a, char b,char c) {
	// 入栈 
	h[tt++] = {n,a,b,c};
	// 栈不空
	while(tt!=hh) {
		auto nn = h[tt-1].num;
		auto aa = h[tt-1].a, bb = h[tt-1].b, cc = h[tt-1].c;
		tt --;
		
		if(nn == 1) {
			cout << aa << "->" << cc << endl;
		}
		else {
			h[tt++] = {nn-1,bb,aa,cc};
			h[tt++] = {1,aa,bb,cc};
			h[tt++] = {nn-1,aa,cc,bb};
		}
	} 
}

int main() {
	int n;
	cin >> n;
	solve(n,'A','B','C');
	
	return 0;
}

1108 最大公约数

代码（函数__gcd(a,b) ）

这里就不想写了，以前写了有笔记。

数论—快速幂，欧几里得及其扩展，逆元，单位元_数论单位元函数-CSDN博客

#include<bits/stdc++.h>
using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	cout << __gcd(a,b) << endl;
	return 0;
}

1109 字符串

代码（搭建递归工作栈和递归结构）

怎么递归写呢？（递归的非递归写法）

跟汉诺塔那样一样写，别忘了条件判断才入栈，逆序入栈.

其实就是三个递归入口，a，b, c. 从a进又不断 a b c 不断深搜路径数

#include<bits/stdc++.h>
using namespace std;

// 字符串递归结构 
struct _str {
	int a;
	int b;
	int c;
	int n;
};

_str str[100000];
int tt;

int solve(int a, int b, int c, int n) {
	if(a+b+c<n) return 0;
	int count = 0;
	str[tt++] = {a,b,c,n}; //入栈 
	// 栈不空 
	while(tt) {
		// 出栈 
		auto A = str[tt-1].a;
		auto B = str[tt-1].b;
		auto C = str[tt-1].c;
		auto num = str[tt-1].n;
		tt --;
		
		if(num == 0) count ++;
		else {
			if(C) str[tt++] = {A,B,C-1,num-1};
			if(B) str[tt++] = {A,B-1,C,num-1};
			if(A) str[tt++] = {A-1,B,C,num-1};
		} 
	}
	return count;
}

int main() {
	int a, b, c, n;
	cin >> a >> b >> c >> n;
	
	int ans = solve(a,b,c,n);
	cout << ans << endl;
	
	return 0;
}

代码2（递归）

#include<bits/stdc++.h>
using namespace std;

int res = 0;

void solve(int a,int b,int c,int n) {
	if(n == 0) res ++;
	if(a>0) solve(a-1,b,c,n-1);
	if(b>0) solve(a,b-1,c,n-1);
	if(c>0) solve(a,b,c-1,n-1);
}

int main() {
	int a, b, c, n;
	cin >> a >> b >> c >> n;
	solve(a,b,c,n);
	cout << res << endl;
	return 0;
}

1110 走台阶

数据保证<=40

代码（递归）

#include<bits/stdc++.h>
using namespace std;
// 需要预定义，因为奇偶相互交替
int odd(int n);
int even(int n); 

// 奇偶替换
// 偶数解个数 
int even(int n) {
	if(n==1) return 0;
	if(n==2) return 1;
	// 走一步到奇数；
	return odd(n-1) + odd(n-2); 
} 
//奇数解个数 
int odd(int n) {
	if(n==1 || n==2) return 1;
	// 走一步到偶数
	return even(n-1) + even(n-2); 
}

int main() {
	int n;
	cin >> n;
	cout << even(n) << endl;
	return 0;
}

代码（非递归）

偶会走到奇数步，奇偶交替

#include<bits/stdc++.h>
using namespace std;
//递归阶梯结构
struct step {
	int n;
	int even;
	int odd;
};

const int N = 1e5+10;
step a[N]; int tt;
int res = 0;

void solve(int n,int os,int js) {
	a[tt++] = {n,os,js};
	
	while(tt) {
		auto num = a[tt-1].n;
		auto _os = a[tt-1].even;
		auto _js = a[tt-1].odd;
		tt --;
		
		if(_os==1&&num==2) res++;
		if(_js==1&&(num==1||num==2)) res ++;
		else if(num>2) {
			a[tt++] = {num-2,-_os,-_js};
			a[tt++] = {num-1,-_os,-_js};
		}
	}
}

int main() {
	int n;
	cin >> n;
	solve(n,1,-1);
	cout << res << endl;
	return 0;
}

1111 扑克牌

代码（dfs递归）

每张牌选几张，有五种选法。

#include<bits/stdc++.h>
using namespace std;

int res = 0;

void dfs(int n, int k) {
	if(n < 0) return ;
	if(n == 0) {
		res ++; return ;
	}
	for(int i = 0; i <= 4; i ++) {
		if(k<13) 
			dfs(n-i,k+1);
	}
}

int main() {
	dfs(13,0);
	cout << res << endl;
	return 0;
}

代码2（非递归）

#include<bits/stdc++.h>
using namespace std;

int res = 0;
// 选牌组合递归结构 
struct pk {
	int n; //剩余要选牌数 
	int k; // 当前牌号 0-12 
};

const int N = 1e5+10;
pk p[N]; int tt;

void solve(int n, int k) {
	p[tt++] = {n,k};
	while(tt) {
		auto num = p[tt-1].n;
		auto kk = p[tt-1].k;
		tt --;
		if(num<0) continue;
		if(num==0) {
			res ++; continue;
		}
		for(int i = 0; i <= 4&&kk<13; i ++) { // kk<13 牌号 
			p[tt++] = {num-i,kk+1};
		}
	}
}

int main() {
	solve(13,0);
	cout << res << endl;
	return 0;
}

1112 第M个排序

代码1（stl)

排序后第m个，所以next_permutation() , m次

#include<bits/stdc++.h>
using namespace std;

vector<int> a;

int main() {
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i ++) {
		int x; cin >> x;
		a.push_back(x);
	}
	for(int i = 0; i < m; i ++) {
		next_permutation(a.begin(),a.end());
	}
	for(auto x:a) cout << x <<" ";
	return 0;
}

代码2（dfs递归）

path路径存储数组，作为全局变量，dfs深搜每条路径的搜索，会将前面路径覆盖。

#include<bits/stdc++.h>
using namespace std;

int n, m;
int res;
const int N = 1e5+10;
int path[N];
int a[N];
bool vis[N];

void dfs(int u) {
	if(u == n) {
		res ++;
		if(res == m+1) {
			for(int i = 0; i < n; i ++) cout << path[i] << " ";
		}
		return ;
	}
	for(int i = 0; i < n; i ++) {
		if(!vis[i]) {
			path[u] = a[i];
			vis[i] = true;
			dfs(u + 1);
			vis[i] = false;
		}
	}
}

int main() {
	memset(vis,false,sizeof vis);
	cin >> n >> m;
	for(int i = 0; i < n; i ++) cin >> a[i];
	dfs(0);
	return 0;
}

代码3（非递归，递归工作栈搭建）

没想好

1113 按字典序输出所有排列

代码（dfs)

#include<bits/stdc++.h>
using namespace std;

int n, m;
const int N = 1e5+10;
int a[N];
int path[N];
bool vis[N];

void dfs(int u) {
	if(u == m) {
		cout << path[0] ;
		if(m>1) {
			for(int i = 1; i < m; i ++) cout << "," << path[i];
		}
		cout << endl;
	}
	for(int i = 0; i < n; i ++) {
		if(!vis[i]) {
			path[u] = a[i];
			vis[i] = true;
			dfs(u+1);
			vis[i] = false;
		}
	}
}

int main() {
	cin >> n >> m;
	for(int i = 0; i < n; i ++) cin >> a[i];
	dfs(0);
	return 0;
}

代码2（next_permutation() ）

正常实现，取前两个

#include<bits/stdc++.h>
using namespace std;

int n,m;
const int N = 1e5+10;
int a[N];

int fact(int x) {
	int res = 1;
	for(int i = x; i >= 1; i --) res *= i;
	return res;
}

int main() {
	cin >> n >> m;
	for(int i = 0; i < n; i ++) cin >> a[i];
	int num = fact(n-m);
	int flag = 1;
	do {
		if(flag == 1) {
			cout << a[0];
			for(int i = 1; i < m; i ++) cout << "," << a[i];
			cout << endl;
		}
		if(flag == num) flag = 0;
		flag ++;
	} while(next_permutation(a,a+n));
	
	return 0;
}