考研机试题 -- DFS、模拟、递推、BFS

全排列（DFS）

https://www.noobdream.com/DreamJudge/Issue/page/1185/

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

const int N = 10;
int visit[N], n;
char path[N];
string s;

void dfs(int u) {
	if(u == n) {
		for(int i = 0; i < n; i ++) {
			cout << path[i];
		}
		cout << endl;
		return;
	}
	
	for(int i = 0; i < n; i ++) {
		if(!visit[i]) {
			visit[i] = 1;
			path[u] = s[i];
			dfs(u + 1);
			visit[i] = 0;
		}
	}
}

int main() {
	cin >> s;
	n = s.length();
	
	dfs(0);
	return 0;
} 

八皇后（DFS）

也可以每次输入b时都执行一次dfs，但那样就慢了；

一个易错点：如果不开 path 数组，直接用 res 数组去记录答案（即19行的代码换成 res[k][u] = i）会出错，原因是回溯时可能不会回溯到 u = 1，此时 k 自增以后导致 res[k][1] 值为 0。

#include <iostream>
using namespace std;

const int N = 20;
int n, col[N], dg[N], udg[N], path[N];
int res[100][100], k = 1;

void dfs(int u) {
	if(u > 8) {
		for(int i = 1; i <= 8; i ++) {
			res[k][i] = path[i];
		}
		k ++;
		return;
	}
	for(int i = 1; i <= 8; i ++) {
		if(!col[i] && !dg[i + u] && !udg[u - i + 8]) {
			col[i] = dg[i + u] = udg[u - i + 8] = 1;
			path[u] = i; //要用path把路径保存下来，注意不能用二维数组，因为u=1时无法记录路径
			dfs(u + 1);
			col[i] = dg[i + u] = udg[u - i + 8] = 0;
		}
	}
}

int main() {
	int n, b; 
	cin >> n;
	dfs(1);
	while(n --) {
		cin >> b;
		for(int i = 1; i <= 8; i ++)
			cout << res[b][i];
		cout << endl; 
	}	
	return 0;	
}

反序输出（模拟）

https://www.noobdream.com/DreamJudge/Issue/page/1155/

#include <iostream>
#include <string>
using namespace std;

int main() {
	string s;
	while(cin >> s) {
		int len = s.length();
		string res;
		for(int i = 0; i < len; i ++)
			res[i] = s[len - 1 - i];	
		for(int i = 0; i < len; i ++)
			cout << res[i];
		cout << endl;
	}
	return 0;
}

库函数：注意algorithm头文件

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	string s;
	while(cin >> s) {
		reverse(s.begin(), s.end());
		cout << s << endl;
	}
	return 0;
}

特殊乘法（模拟）

https://www.noobdream.com/DreamJudge/Issue/page/1168/

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	int res = 0;
	string a, b;
	cin >> a >> b;
	int len_a = a.length();
	int len_b = b.length();
	
	for(int i = 0; i < len_a; i ++) 
		for(int j = 0; j < len_b; j ++) {
			res += (a[i] - '0') * (b[j] - '0');
			
	cout << res;
	return 0;
}

众数（模拟）

https://www.noobdream.com/DreamJudge/Issue/page/1534/

#include <iostream>
using namespace std;

int s[10][10]; //s[i][j]表示从低到高第i位的j数字出现了几次

int main() {
	int n, m, k;
	cin >> n >> m;
	
	while(n --) {
		cin >> k;
		for(int i = 0; i < m; i ++) {
			s[i][k % 10] ++;
			k /= 10;
		}
	}	
	
	int res = 0, max = 0; //res记录众数，max记录最多出现的次数
	
	for(int i = 0; i < m; i ++) {
		for(int j = 0; j < 10; j ++) {
			if(s[i][j] > max) {
				max = s[i][j];
				res = j;
			}
		}
		cout << res << endl;
		res = max = 0;
	}
	return 0;
} 

吃糖果（模拟）

https://www.noobdream.com/DreamJudge/Issue/page/1197/
循环加n模n

#include <iostream>
using namespace std;

const int N = 110;
int a[N], tmp[N]; //a[i]表示第i个学生拥有的糖果数，tmp[i]表示i同学糖果数的一半 

int main() {
	int n, cnt; 
	
	while(cin >> n) {
		if(n == 0) break;
		
		for(int i = 0; i < n; i ++)
			cin >> a[i];
		
		cnt = 0; //cnt为轮次
		
		while(true) {
			//判断所有人的糖果是否一样 
			bool same = true;
			for(int i = 0; i < n; i ++) {
				if(a[i] != a[0])
					same = false; 
			}
			if(same) break;
			
			cnt ++;
			
			//每个人拿出一半糖果 
			for(int i = 0; i < n; i ++) {
				tmp[i] = a[i] / 2; 
				a[i] -= tmp[i];
			}
				
			//分糖果 
			for(int i = 0; i < n; i ++) {
				a[i] = a[i] + tmp[(i - 1 + n) % n]; //i同学拿走i-1同学的一半，加n模n是为了让0号同学能拿走n-1同学的糖果 
				if(a[i] % 2) a[i] ++; //奇数加1 
			} 
			
		} 
		cout << cnt << " " << a[0] << endl;
	}
	return 0;
}

递推数列（递推）

https://www.noobdream.com/DreamJudge/Issue/page/1171/
(a + b) mod p = (a mod p + b mod p) mod p，适用于加减乘法，除法不适用。

#include <iostream>
using namespace std;

const int N = 10e6;
int s[N];

int main() {
	int a, b, p, q, k, res;
	cin >> a >> b >> p >> q >> k;
	
	s[0] = a;
	s[1] = b;
	
	for(int i = 2; i <= k; i ++)
		s[i] = (p * s[i - 1]) % 10000 + (q * s[i - 2]) % 10000 ;
	
	cout << s[k] % 10000 ;
	return 0;
} 

玛雅人的密码（BFS）

https://www.noobdream.com/DreamJudge/Issue/page/1162/

#include <iostream>
#include <string>
#include <cstring>
#include <queue>
#include <unordered_map>
using namespace std;

int n;
string s;

int bfs() {
	queue<string> q;
	unordered_map<string, int> dist;
	dist[s] = 0; 
	q.push(s);
	
	while(!q.empty()) {
		string t = q.front();
		q.pop();
		
		for(int i = 0; i < n; i ++) {
			if(t.substr(i, 4) == "2012")
				return dist[t];
		}
		
		for(int i = 1; i < n; i ++) {
			string r = t;			
			swap(r[i], r[i - 1]);
			if(!dist.count(r)) {
				dist[r] = dist[t] + 1;
				q.push(r);
			}
			
		}
	}
	
	return -1;
}

int main() {
	cin >> n >> s;
	cout << bfs();
	return 0;
}