被奶死了。

基本解法清清楚楚，因为后缀满足性质，所以搜一发就行了。

一个月前写了Java？没卵用。

bitset优化？没卵用。

位数优化？没卵用。

啊。。。为什么我忽略了这么显然的剪枝呢？

 

4404: [Neerc2015]Binary vs Decimal

Time Limit: 10 Sec  Memory Limit: 512 MB

Submit: 157  Solved: 66

[][][]

Description

一个数A，如果它转成二进制后B。A是B的后缀，这个数就是我们所要的。

现在给出数字N，求第N个这样的数（1 ≤ n ≤ 10000）

Input

 

Output

 

Sample Input

2

Sample Output

10

HINT

 

 

#include 
      
       using namespace std;const int maxl = 180;const int modn = 1e9 + 7;const int maxn = 10500;bitset
       
         xp[maxl];void add(bitset
        
          &a, bitset
         
           b) {    int carry = 0;    for (int i = 0; i < maxl; ++i) {        int t = carry + (int)a.test(i) + (int)b.test(i);        a.set(i, t % 2);        carry = t / 2;    }}struct Node {    Node() { len = 0; }    bool set() {        //cout << len << endl;        s.set(len - 1);        bitset
          
           & c = xp[len-1];        int carry = 0;        for (int i = 0; i < maxl; ++i) {            int t = carry + (int)b.test(i) + (int)c.test(i);            if (i < len && t % 2 != s.test(i))                return false;            b.set(i, t % 2);            carry = t / 2;        }        return true;    }    bitset
           
             s; bitset
            
              b; int len;};queue
             
               q;vector
              
                ans[maxl];int anscnt;void insert_ans(Node &x) { if (!x.s.test(x.len - 1)) return; char res[maxl]; memset(res, 0, sizeof(res)); for (int i = 0; i < x.len; ++i) res[x.len-i-1] = x.s.test(i) + '0'; anscnt++; ans[x.len].push_back(res);}string find_string(int rank) { int tot = 0; for (int i = 0; i < maxl; ++i) { if (tot + ans[i].size() >= rank) { sort(ans[i].begin(), ans[i].end()); return ans[i][rank-tot-1]; } else tot += ans[i].size(); }}int main(){ #ifdef ULTMASTER freopen("a.in", "r", stdin); #endif int N; cin >> N; xp[0].set(0); for (int i = 1; i < maxl; ++i) { xp[i] = (xp[i-1]<<1); add(xp[i], xp[i]<<2); } Node zero; zero.len = 1; Node one = zero; one.set(); q.push(zero); q.push(one); while (!q.empty()) { if (anscnt > N + 200) break; Node u = q.front(); insert_ans(u); q.pop(); u.len++; q.push(u); if (u.set()) q.push(u); } cout << find_string(N) << endl; return 0;}