SRM464 Div1 Easy(250), Div2 Medium(500) ColorfulStrings
全探索。n≦50とあるが各桁の数字は全て異なるのでcolorfulな文字列の個数はそれほど多くない。
#include <string> #include <set> using namespace std; class ColorfulStrings { string BT( int n, int k, string s, int *c ); bool check( string s ); public: string getKth( int n, int k ); }; string ColorfulStrings::getKth( int n, int k ) { int c = 0; return BT( n, k, "", &c ); } string ColorfulStrings::BT( int n, int k, string s, int *c ) { if ( ! check(s) ) return ""; if ( (int)s.length() == n ) return ++*c==k ? s : ""; string r; for ( char i='0'; i<='9'; i++ ) r = max( r, BT(n,k,s+i,c) ); return r; } bool ColorfulStrings::check( string s ) { int l = (int)s.length(); set<int> p; for ( int i=1; i<=l; i++ ) for ( int j=0; j+i<=l; j++ ) { int t = 1; for ( int k=j; k<j+i; k++ ) t *= s[k] - '0'; if ( p.count( t ) > 0 ) return false; p.insert( t ); } return true; }