考研机试题（第一天）

• 整数拆分（动态规划）
• 二叉树遍历（数据结构）
• 玛雅人的秘密（BFS）
• 最小邮票数（暴力or动态规划）

题目：

思路说明：可以将n看作背包容量，背包体积为2的n次幂，每个背包可以无限使用，为完全背包问题。
代码：

#include 
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
LL f[N];
LL a[N];
int main (){
    int n; cin >> n;
    for (int i = 1; i <= 20; i ++)
        a[i] = (1 << (i - 1));
    f[0] = 1;
    for (int i = 1; i <= 20; i ++)
    {
        for (int j = a[i]; j <= n; j ++)
        {
            f[j] = (f[j] + f[j - a[i]]) % 1000000000;
        }
    }
    cout << f[n];
    return 0;
}

题目：

思路说明： 先序为中左右，中序为左中右，递归建树，递归遍历即可
代码：

#include 
using namespace std;

string s;
int cnt = 0;
char tree[100000005];
void create (int u){
	char c = s[cnt ++];
	if (c == '#')
		return ;
	tree[u] = c;
	create (u * 2);
	create (u * 2 + 1);
	
}

void mid (int u)
{
	if (tree[u] == 0)	return ;
	mid (u * 2);
	cout << tree[u] << " ";
	mid (u * 2 + 1);
}
int main (){
	while (cin >> s)
	{
		cnt = 0;
		create (1);
		mid (1);
		cout << "n";
	}
	return 0;
}

题目：

思路：　从初始的字符串出发，每一步的拓展为结果为每一个位置和下一个位置交换形成的字符串集合，若存在2012，输出步数即可。
代码：

#include 
using namespace std;

int n;
string s;
void bfs (){
	int cnt = 0;
	queue  q;
	q.push (s);
	while (q.size ()){
		int s = q.size ();
		for (int i = 0; i < s; i ++)
		{
			auto t = q.front ();
			q.pop ();
			if (t.find ("2012") != -1){
				cout << cnt;
				return ;
			}
			for (int i = 0; i < t.size () - 1; i ++){
				string tmp = t;
				swap (t[i], t[i + 1]);
				q.push (t);
				t = tmp;
			}
		}
		cnt ++;
	}
	cout << -1;
	return ;
}
int main (){
	
	cin >> n >> s;
	bfs ();
	return 0;
}

题目：

暴力思路：每个位置有选与不选两种状态，将所有的状态组合枚举出来求最小
代码：

#include 
using namespace std;

int n, m, ans = 1e8;
int p[25];
int flag = 0;

void dfs (int sum, int level, int cnt){
//     cout << "sum = " << sum << "n";
//     cout << "level = " << level << "n";
	if (sum > m) return ;
	if (sum == m)
	{
        ans = min (ans, cnt);
		return ;
	}
	for (int i = level; i <= n; i ++){
		dfs (sum + p[i], i + 1, cnt + 1);
		dfs (sum, i + 1, cnt);
	}
	
}
int main (){
	
	while (cin >> m){
		cin >> n;
		int sum = 0;
		for (int i = 1; i <= n; i ++) {
			cin >> p[i];
			sum += p[i];
		}
		sort (p + 1, p + 1 + n, greater());
		if (sum < m){
			cout << 0 << "n";
			continue;
		}
		dfs (0, 1, 0);
		if (ans == 1e8) cout << 0 << "n";
        else cout << ans << "n";
		
		
	}
	
	return 0;
}

动态规划思路： 将邮票总值看作背包总容量，则此题可看作将背包恰好填满需要的最小背包数量。
代码：

#include 
using namespace std;

const int N = 1e5 + 10;
int dp[N];
int n, m;
int a[N];
int main (){
    while (cin >> m){
        cin >> n;
        for (int i = 1; i <= n; i ++) cin >> a[i];
        for (int i = 1; i <= 100; i ++) dp[i] = N;
        
        for (int i = 1; i <= n; i ++){
            for (int j = m; j >= 0; j --){
                if (j - a[i] >= 0){
                    dp[j] = min (dp[j], dp[j - a[i]] + 1);
                }
            }
        }
        if (dp[m] == N) cout << 0 << "n";
        else cout << dp[m] << "n";
    }
    return 0;
}