c562 - Puyu 愛數論
題目描述
題目給定一個函數 F(N)，並提供幾個範例值。要求讀取多個數字 N，並輸出對應的 F(N) 值。觀察範例可以發現，F(N) 實際上是計算 N 的十進位表示中，數字 8 出現的次數乘以 2，再加上數字 9、6、0 出現的次數總和。
解題思路
題目要求計算一個函數 F(N) 的值，該函數的計算方式是基於輸入數字 N 的十進位表示。程式碼直接讀取輸入數字的每一個字元，並根據字元的數值來更新答案。如果字元是 '8'，則答案加 2；如果字元是 '9'、'6' 或 '0'，則答案加 1。當讀取到換行符或 EOF 時，輸出當前答案並重置答案。
複雜度分析
- 時間複雜度: O(N)，其中 N 是輸入數字的位數。因為程式碼需要遍歷輸入數字的每一個字元。
- 空間複雜度: O(1)，程式碼只使用了幾個整數變數來儲存答案和臨時值，空間使用量不隨輸入大小變化。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
inline void write(int x) {
if(x==0){putchar_unlocked('0');return;}
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
int ans=0;
char a;
while(a=getchar_unlocked()){
if(a<'0'){
if(a==-1)break;
write(ans);
putchar_unlocked('\n');
ans=0;
}
else if(a=='8')
ans+=2;
else if(a=='9'||a=='6'||a=='0')
++ans;
}
}