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
1
2
3
4

範例輸出 Sample Output

1
2
3
4
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/*
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

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


e338. 放暑假了!!!!!...可惜要上暑輔...開學後還要模考...
https://blog.yangjerry.tw/2019/08/24/zj-e338/
作者
Jerry Yang
發布於
2019年8月24日
許可協議