学步园

D1D2的250p都是水题，特别纯净的那种。

D1 500p HexatridecimalSum

高精度模板上吧！

D1 1000p IncreasingLists

花了半个下午搞定。首先搜索最长不下降序列划分逗号，然后贪心。贪心时注意：只要某一位被预置，并且与之前的string在该位不同，那么就可以对后面的数位置0.还有一些细节，比如开头不能为0。

string ans;</p> <p>class IncreasingLists<br /> {<br /> int lst[30];<br /> string str[30], m;<br /> void print ( int n )<br /> {<br /> for ( int i = 0; i < n; i ++ )<br /> printf ( "%d ", lst[i] );<br /> printf ( "/n" );<br /> }<br /> void check ( int num )<br /> {<br /> //print ( num );<br /> string temp = "";<br /> string last, cur;<br /> int len = 0;<br /> for ( int i = 0; i < num; i ++ )<br /> {<br /> if ( i )<br /> temp += ',';<br /> cur.resize ( lst[i], ' ' );<br /> if ( lst[i] > len )<br /> {<br /> len = lst[i];<br /> cur[0] = str[i][0] == '?' ? '1' : str[i][0];<br /> for ( int j = 1; j < len; j ++ )<br /> {<br /> cur[j] = str[i][j] == '?' ? '0' : str[i][j];<br /> }<br /> }<br /> else if ( lst[i] == len )<br /> {<br /> int pos, j;<br /> for ( pos = 0; pos < len; pos ++ )<br /> {<br /> if ( str[i][pos] != '?' && str[i][pos] != last[pos] )<br /> break;<br /> }<br /> for ( j = pos; j < len; j ++ )<br /> cur[j] = str[i][j] == '?' ? '0' : str[i][j];<br /> int less = 1;<br /> if ( pos < len && cur[pos] > last[pos] )<br /> less = 0;<br /> for ( j = pos - 1; j >= 0; j -- )<br /> {<br /> if ( str[i][j] != '?' )<br /> {<br /> cur[j] = str[i][j];<br /> }<br /> else<br /> {<br /> if ( less )<br /> {<br /> cur[j] = last[j] + 1;<br /> if ( cur[j] > '9' )<br /> cur[j] = '0', less = 1;<br /> else<br /> less = 0;<br /> }<br /> else<br /> cur[j] = last[j];<br /> }<br /> }<br /> if ( less )<br /> return;<br /> }<br /> if ( cur[0] == '0' )<br /> return;<br /> last = cur;<br /> temp += cur;<br /> }<br /> if ( ans.size () == 0 || temp < ans )<br /> ans = temp;<br /> }</p> <p> void dfs ( int last, int cur, int len, int num, string sub )<br /> {<br /> if ( m.size () - last - 1 < len )<br /> return;<br /> if ( cur == m.size () )<br /> {<br /> int tlen = cur - last - 1;<br /> if ( tlen >= len )<br /> {<br /> lst[num] = tlen;<br /> str[num ++] = sub;<br /> //print ( num );<br /> check ( num );<br /> }<br /> return;<br /> }<br /> int tlen = cur - last - 1;<br /> if ( m[cur] == ',' )<br /> {<br /> if ( tlen >= len )<br /> {<br /> lst[num] = tlen;<br /> str[num] = sub;<br /> dfs ( cur, cur + 1, tlen, num + 1, "" );<br /> }<br /> return;<br /> }<br /> if ( m[cur] >= '0' && m[cur] <= '9' )<br /> {<br /> dfs ( last, cur + 1, len, num, sub + m[cur] );<br /> return;<br /> }<br /> if ( tlen >= len )<br /> {<br /> lst[num] = tlen;<br /> str[num] = sub;<br /> dfs ( cur, cur + 1, tlen, num + 1, "" );<br /> }<br /> dfs ( last, cur + 1, len, num, sub + m[cur] );<br /> } </p> <p>public:<br /> string makeIncreasingList(string mask)<br /> {<br /> m = mask;<br /> ans = "";<br /> dfs ( -1, 0, 1, 0, "" );<br /> if ( ans.size () == 0 )<br /> return "impossible";<br /> else<br /> return ans;<br /> }<br /> }