2019南大计算机夏令营机考

it2022-05-06  6

第一题

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

最新回复(0)