学步园

D2 hard   DistinctDigits

选定一个区间[low,high]，将每个数的数字按小到大排序，去掉所有0，构成一个集合。问不同的集合种类。

区间数目相当之大，因此无法从区间各个数来推得答案。考虑到最后一个样例中几近题目最大限度，结果仅为19519，我们可以先搜索集合的种类，然后再逆推是否可组成区间内的数字。

当集合的数字个数小于len(high)大于len(low)时，必然可以得到区间内的某一数字。

当集合的数字个数和high或者low相同时，我们可以继续进行一字符串搜索。

最终最大结果用时1.4s。

#define LL long long<br /> #define MP make_pair<br /> #define PII pair < int, int ><br /> #define VI vector < int ></p> <p>int ans;<br /> int maxSize, minSize;<br /> int low, high;<br /> int used[10];<br /> int ac;<br /> string ls, hs, Set;</p> <p>string itos ( int n )<br /> {<br /> string ret;<br /> while ( n )<br /> ret += ( '0' + n % 10 ), n /= 10;<br /> reverse ( ret.begin (), ret.end () );<br /> return ret;<br /> }</p> <p>int len ( int n )<br /> {<br /> return n ? len ( n / 10 ) + 1 : 0;<br /> }</p> <p>void dfss ( string cur )<br /> {<br /> if ( cur.size () == Set.size () )<br /> ac = 1;<br /> if ( ac )<br /> return;<br /> int len = cur.size ();<br /> for ( int i = 0; i < Set.size (); i ++ ) if ( !used[i] )<br /> {<br /> string temp = cur + Set[i];<br /> if ( temp >= ls.substr ( 0, len + 1 ) && temp <= hs.substr ( 0, len + 1 ) )<br /> {<br /> used[i] = 1;<br /> dfss ( temp );<br /> used[i] = 0;<br /> }<br /> }<br /> }</p> <p>void check ( string s )<br /> {<br /> //cout << s << endl;<br /> if ( s[s.size () - 1] == '0' )<br /> return;<br /> if ( s.size () > minSize && s.size () < maxSize )<br /> {<br /> //cout << s << endl;<br /> ans ++;<br /> return;<br /> }<br /> memset ( used, 0, sizeof ( used ) );<br /> ac = 0;<br /> int h, l;<br /> if ( s.size () == minSize && s.size () == maxSize )<br /> h = high, l = low;<br /> else if ( s.size () == minSize )<br /> {<br /> l = low;<br /> h = 1;<br /> for ( int i = 0; i < s.size (); i ++ )<br /> h *= 10;<br /> h --;<br /> }<br /> else if ( s.size () == maxSize )<br /> {<br /> h = high;<br /> l = 1;<br /> for ( int i = 1; i < s.size (); i ++ )<br /> l *= 10;<br /> }<br /> Set = s, hs = itos ( h ), ls = itos ( l );<br /> dfss ( "" );<br /> if ( ac )<br /> ans ++;<br /> }</p> <p>void dfs ( string s, int n )<br /> {<br /> string str = s + char ( '0' + n );<br /> if ( str.size () > maxSize )<br /> return;<br /> if ( str.size () >= minSize )<br /> check ( str );<br /> dfs ( str, n );<br /> if ( n < 9 )<br /> dfs ( s, n + 1 );<br /> }</p> <p>class DistinctDigits<br /> {<br /> public:<br /> int count(int low, int high)<br /> {<br /> ans = 0;<br /> ::low = low, ::high = high;<br /> maxSize = len ( high ), minSize = len ( low );<br /> dfs ( "", 0 );<br /> return ans;<br /> }<br /> };