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種不同的樹。
           

在這裡插入代碼片