2019南大计算机夏令营机考

第一题

给你一个不超过100位的数n，和一个不超过100的数字k，要求从数n中去掉k个数字，然后使得去掉k个数之后，n最小。

           

#include<iostream>
using namespace std;
int k;
main()
{
	int t;
	cin>>t;
	while(t--)
	{
		string n; //定义字符串n
		cin>>n>>k;
		int len=n.size(); //也可以用n.length()来取字符串n的长度
		while(k--)
			for(int i=0;i<len;i++) //枚举
				if(n[i]>n[i+1]||i==len-1) //删除遇到的第一个递减序列的第一个数字(若整个字符串为非递减序列，则删去末尾的数字)
				{
					n.erase(i,1); //把当前字符从字符串中删除
					break; //不可省略，否则字符串会多删字符
				}
		while(n[0]=='0'&&n[1]) //去掉前缀0，并至少保留1个数字
			n.erase(0,1); //删去当前字符串开头的'0'
		cout<<n<<endl; //输出字符串
	}
}

           

第二题

有B个男孩，G个女孩，要求所有男孩女孩排成一队，连续的男孩个数不可以超过K个，问一共有多少种排法。（结果需要mod 10007）

           

做法1（暴力70分）

#include<iostream>
using namespace std;
int sum=0;
int n=6;
int k=3;
int x=4,y=2;
void DFS(int i,int a,int b,int temp){
	if(a>x||b>y||temp==k)return;
	if(n==i){
		sum++;
		return;
	}
	for(int j=0;j<=1;j++)
	{
		if(j==0)
		{
			DFS(i+1,a+1,b,temp+1);
		}
		else
		{
			DFS(i+1,a,b+1,0);
		}
	}
}
int main()
{
	DFS(0,0,0,0);
	cout<<sum;
	
}

           

做法2（DP100分）

待补
           

第三题

给出一个二叉树的前序遍历序列和后序遍历序列的字符串，问通过这两个序列可以构造多少中不同的二叉树，
    因为树的样子不一样，遍历的序列是可能一样的。比如前序序列:abc，后序序列cba，就有4种不同的树。
           

在这里插入代码片