問題
http://community.topcoder.com/stat?c=problem_statement&pm=10724&rd=14149
解き方
Nは５０だが、同じ数字が２度出現すると条件を満たさないので
N=10までであれば全探索可能。
DFSでこれまで出現した数字をカウントし、有効であればカウントしていき
K番目のものが答えになる。
コード
int was[11111111],n,k;
string ret,s;
class ColorfulStrings {
public:
void rec(int at){
if(at==n){
k--;
if(k==0)ret=s;
return;
}
for(char ch='0';ch<='9';ch++){
s+=ch;
int ok=1,p=1;
for(int i=at;i>=0;i--){
p*=s[i]-'0';
if(was[p])ok=0;
was[p]++;
}
if(ok)rec(at+1);
p=1;
for(int i=at;i>=0;i--){
p*=s[i]-'0';
was[p]--;
}
s=s.substr(0,s.size()-1);
}
}
string getKth(int nn, int kk) {
n=nn,k=kk;
if(n>10)return "";
memset(was,0,sizeof(was));
ret="",s="";
rec(0);
return ret;
}
};
string ret,s;
class ColorfulStrings {
public:
void rec(int at){
if(at==n){
k--;
if(k==0)ret=s;
return;
}
for(char ch='0';ch<='9';ch++){
s+=ch;
int ok=1,p=1;
for(int i=at;i>=0;i--){
p*=s[i]-'0';
if(was[p])ok=0;
was[p]++;
}
if(ok)rec(at+1);
p=1;
for(int i=at;i>=0;i--){
p*=s[i]-'0';
was[p]--;
}
s=s.substr(0,s.size()-1);
}
}
string getKth(int nn, int kk) {
n=nn,k=kk;
if(n>10)return "";
memset(was,0,sizeof(was));
ret="",s="";
rec(0);
return ret;
}
};