The 9th CCPC Harbin B.Memory

$The9thCCPCHarbinB.Memory$

题目大意

给定一个数组，求每一个$Mood(i)$的正负性。
$$Mood(i)=\sum _{j=1}^i{2}^{j-i}\times a_j$$

思路

一道签到题，思路很简单，但是赛时用了完全不同的一种思路。

赛后看了题解，才发现小数不会在后面被消除，这么简单赛时怎么没想到hhh。

跟据式子能够推出：$Mood(i)=Mood(i-1)/2+a_i$。

很容易发现这道题卡浮点数高精，我们可以考虑将所有数转为二进制来写，每次将数字的二进制相加，并且采用进位。

对于负数，我们可以将其二进制下的每一位都看为负就好了。

最后判断其最高位是$-1or0or1$。

标程

const int N = 1e5 + 50; 
vector<int> a(N);
void Solved() { 
    int n; cin >> n;
    int mx = 0;
    for(int i = 1; i <= n; i ++ ) {
        int x; cin >> x;
        bool flag = true;
        if(x < 0) flag = false, x = -x;
        int len = 0;
        while(x) {
            a[len + i] += flag ? (x & 1) : -(x & 1);
            mx = max(mx, len + i);
            int t = 0;
            while(a[i + len + t] >= 2) {
                a[i + len + t + 1] += a[i + len + t] / 2;
                a[i + len + t] %= 2;
                t ++;
                mx = max(mx, i + len + t);
            }
            t = 0;
            while(a[i + len + t] <= -2) {
                a[i + len + t + 1] += a[i + len + t] / 2;
                a[i + len + t] %= 2;
                t ++;
                mx = max(mx, i + len + t);
            }
            x >>= 1; len ++;
        }
        while(mx > 0 && a[mx] == 0) mx --;
        if(mx == 0) cout << '0';
        else cout << (a[mx] < 0 ? '-' : '+');
    }
}