[TIOJ] 1026. 惡猿果實

題目連結:http://tioj.infor.org/problems/1026
本題因為都是走二的冪次,所以可以用二進位的思考方式想一下,就會發現本題可以先走要走的數字在二進位中位數全填一步(e.g. 11在二進位中表示為1101,故先走二進位為1111的15步),然後再考慮要該往回走幾單位,那必定是全填1的減掉給的數字單位,那我們如果把一個格子改成0則是往回走$2 \times 2^{第幾格}$步,所以把那數除以二並跟原本全填一的數xor後,再看每一格即是答案。
#include <iostream>
#include <bitset>

using std::bitset;

int main() {
    int n;
    scanf("%d",&n);
    int d=32-__builtin_clz(n);
    bitset<32> b;
    for(int i=0;i<d;i++)
      b[i]=1;
    b^=((b.to_ulong()-n)>>1);
    printf("%d\n",d);
    for(int i=0;i<d;i++)
      putchar(b[i]?'+':'-');
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology