网易“aazz”题目
#include <iostream>
#include <string>
#include <vector>
using namespace std;
//m个'z'，n个'a' 顺序串
string get_az_string(int n,int m)
{ int i=0;
string p="";
for(;i<m; i)
p=p "z";
for(i=0;i<n; i)
p=p "a";
return p;
}
//n个'a',m个'z'中获取第k个字符，并拼接在jieguo后面
void get_jieguo(int n,int m,int k,string *jieguo)
{
if(n==0 || m==0)
{
*jieguo =(*jieguo) get_az_string(n,m);
return ;
}
int i=0;
//以m个'z'开始的字符串群中，第一个的序号
vector<long long > index_of_z(m 1);
long long start=1;
//计算全排列C(n,n m).C(n,n m-1).....C(n,n)
for(i=m 1;i<=m n; i)
start=start*i;
for(i=1;i<=n; i)
start=start/i;
index_of_z[0]=start;
for(i=1;i<=m; i)
{
start=start*(m-i 1)/(n m-i 1);
index_of_z[i]=start;
}
for(i=1;i<=m; i)
index_of_z[i]=index_of_z[0]-index_of_z[i] 1;
index_of_z[0]=1;
//查到k所在的区间
int index=-1;
for(i=0;i<m; i)
{
if(k>=index_of_z[i] && k<index_of_z[i 1])
{
index=i;
break;
}
}
if(index==-1) //排在最后面
{
*jieguo =(*jieguo) get_az_string(n,m);
}
else
{
if(index==0) //以0个'z'开头，递归查找
{
*jieguo =(*jieguo) "a";
get_jieguo(n-1,m,k,jieguo);
}
else //以index个'z'开头，递归查找
{
*jieguo =(*jieguo) get_az_string(0,index);
get_jieguo(n,m-index,k-index_of_z[index] 1,jieguo);
}
}
return ;
}
//获取C(n,m)，即m中取n个数，n最小为多少时候超过k,-1表示不存在
int get_min(int m,int k)
{
if(k==1)
return 0;
long long count=1;
int jieguo=1;
int mid=m/2;
for(jieguo=1;jieguo<=mid; jieguo)
{
count=count*(m-jieguo 1)/jieguo;
if(count>=k)
return jieguo;
}
return -1;
}
int main()
{
int n,m,k,i,p;
cin>>n>>m>>k;
//求辅助边界
vector<int> max_n(201);
for(i=1;i<=200; i)
max_n[i]=get_min(i,k);
//校验缩小范围
bool exit_jieguo=false;
for(p=0;p<=n; p)
{
if(max_n[p m]!=-1 && p>=max_n[p m])
{
exit_jieguo=true;
break;
}
}
if(!exit_jieguo)
{
cout<<-1;
return 0;
}
//前n-p个全是'a'
string *jieguo=new string;
*jieguo=*jieguo get_az_string(n-p,0);
//递归求结果
get_jieguo(p,m,k,jieguo);
cout<<*jieguo<<endl;
return 0;
}
#笔试题目##网易#
联想公司福利 613人发布
投递淘天集团等公司10个岗位