e338. 放暑假了!!!!!...可惜要上暑輔...開學後還要模考...

題目 Problem

題目連結：https://zerojudge.tw/ShowProblem?problemid=e338

敘述 Description

段考後的延平:

https://drive.google.com/file/d/1j4qESZGdI0jQW6uuxcSb7tfNsq_SB_vl/view?usp=sharing

XD

輸入 Input

一行一個非負整數n(n<2^31)

輸出 Output

輸出此整數在二進位中1的個數

範例輸入 Sample Input

1
2
3
4

範例輸出 Sample Output

1
1
2
1

提示 Hint

__builtin_popcount()夠快嗎?

2018/8/9 調整時限

題解 Solution

我覺得作者想考$O(1)$算法
但不幸的還是壓到了一般輸入
這題就算單純用 scanf / printf 還是不會過

分兩個大方向去 AC 這題

1. 讀取模板

參考這篇文：https://vincent97198.blogspot.com/2019/06/iozerojudge.html

我只是稍微改了個 EOF 而已（EOF 被定義為 -1，但是本題數入範圍可以暫時不管這東西XD）。

getchar_unlocked() 不是標準的函式，比起 getchar() 少做了很多事（詳情自己去 Google），但不要隨便使用在大型專案上。

putchar_unlocked() 亦同上。

2. 演算法

參考這篇文：https://www.geeksforgeeks.org/count-set-bits-in-an-integer/

第四點就是先把 Bit 個數建表，然後 4 個 4 個讀取加起來

不過總複雜度也不是$O(1)$，嚴格來說似乎是$O(\log_{16}{N})$

程式碼 Accepted Code

/*
    Author: Jerry Yang C.H. (tico88612)
    Date: 2019/8/18
*/
#include <cstdio>
#include <cctype>

inline int redi()
{
    int ret = 0, f = 0;
    char ch = getchar_unlocked();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = 1;
        if(ch == EOF)
            return EOF;
        ch = getchar_unlocked();
    }
    while (isdigit(ch))
    {
        ret = ret * 10 + ch - 48;
        ch = getchar_unlocked();
    }
    return f ? -ret : ret;
}
inline void print(int x)
{
    if (x < 0)
    {
        putchar_unlocked('-');
        x = -x;
    }
    int y = 10, len = 1;
    while (y <= x)
    {
        y *= 10;
        len++;
    }
    while (len--)
    {
        y /= 10;
        putchar_unlocked(x / y + 48);
        x %= y;
    }
}
int num_to_bits[16] = {0, 1, 1, 2, 1, 2, 2, 3,
                       1, 2, 2, 3, 2, 3, 3, 4};
unsigned int countSetBitsRec(unsigned int num)
{
    if (0 == num)
        return num_to_bits[0];
    nibble = num & 0xf;
    return num_to_bits[nibble] +
           countSetBitsRec(num >> 4);
}

/********** Good Luck :) **********/
int main()
{
    int n;
    while((n = redi()) != EOF){
        print(countSetBitsRec(n));
        putchar_unlocked('\n');
    }
    return 0;
}

後記 Afterword

這個 Submission 是壓秒過的
排行上的應該也是建表過的（吧？）
記憶體都比我大很多（我的 100 KB，排行上的大多都 1 MB 以上）

前陣子的 ZeroJudge 常常出現有的沒的 IO 題
但這類的 IO 優化題也可能改天換個主機 Rejudge，搞不好全都 TLE 或全都 AC
也不是說這種題目不好，畢竟幾乎每個人都可以在上面出題，題目多樣性很夠 XD

維持網站題目質量品質也是大家的責任