POJ 1023 The Fun Number System

Bertha 。 2022-10-08 02:27 20阅读 0赞

**题目大意**

10的二进制
    8 4 2 1
    1 0 1 0
    
    现在给每一个位置一个权重 
    如果是ppnn
    那么就是，10就可以表示为
    8 4 -2 -1
    1 1  1  0

**思路梳理**

如果要表示的这个数n是奇数（无论正负），那么最后一个位置一定是1
    8 4 -2 -1
    - -  -  1
    接着就需要看
    
    8 4 -2 以及每一个位置了
    
    其实相当于给n/2在以下数列中找
    4 2 -1 也可以确定一个位置
    
    但是在 8 4 -2 -1 的时候最后一个位置填了1 比实际的数字少了2 所以需要在原来的数字加上2
    也就是说
    需要 8 4 -2 0 表示出来n+2
    也就是 4 2 -1 表示出来 (n+2)/2
    
    注意需要补全不足k位前面的0

**代码如下**

#include <iostream>
    #include <algorithm>
    #include <string>
    #include <string.h>
    #include <cstring>
    #include <queue>
    #include <map>
    //#include <unordered_map>
    #include <set>
    //#include <unordered_set>
    #include <stack>
    #include <math.h>
    #include <limits.h>
    #include <stdio.h>
    #include <vector>
    #include <bitset>
    #include <deque>
    #include <functional>
    #include <ctype.h>
    #include <sstream>
    
    using namespace std;
    #pragma warning(disable:4996)
    
    const double eps = 1e-6;
    typedef long long ll;
    #define debug(x) cout<<#x<<": "<<(x)<<endl;
    #define lfeq(a,b) (abs((a)-(b)) < eps)
    
    int mod = 1e9 + 7;
    int inf = 0x3f3f3f3f;
    const double pi = acos(-1.0);
    
    template <typename T> void inline read(T& x) { 
        int f = 1; x = 0; char s = getchar();
        while (s < '0' || s > '9') {  if (s == '-') f = -1; s = getchar(); }
        while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
        x *= f;
    }
    
    template <typename T> void print(T x) { 
        if (x < 0) {  putchar('-'); print(x); return; }
        if (x >= 10) print(x / 10);
        putchar((x % 10) + '0');
    }
    
    bool sol() { 
    
        ll k,n;
        //read(k);
        cin >> k;
        string p;
        cin >> p;
        //read(n);
        cin >> n;
        //debug(n)
        int i = p.size() - 1;
        deque<int> bit;
        do { 
            //debug(n & 1)
            bit.push_front(n & 1);
            if ((n & 1)) { 
                if (p[i] == 'n') { 
                    n += 2;
                }
                else { 
                    ;
                }
            }
            n >>= 1;
            --i;
        } while (n != 0 && i>=0);
    
        //debug(n)
        if (n) { 
            cout << "Impossible" << endl;
            return true;
        }
    
        while (bit.size()<k) { 
            bit.push_front(0);
        }
        deque<int>::iterator it;
        for (it = bit.begin();it!=bit.end();++it) { 
            cout << *it;
        }
        cout << endl;
    
        return true;
    }
    
    
    int main() { 
    
        //freopen("../in1.txt", "r", stdin);
    
        int t;
        cin >> t;
        for (int i = 0; i < t; ++i) { 
            sol();
        }
        return 0;
    }

![在这里插入图片描述][20210619192123846.png]

[20210619192123846.png]: /images/20221005/588336c851b44d66923c9b9deb7995f3.png