第一题

给你一个不超过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种不同的树。 在这里插入代码片