題目 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
維持網站題目質量品質也是大家的責任