e378: 撞來撞去

2019-09-07

內容

現在地板上有兩個立方體和一面垂直於地板的牆壁

離牆壁較遠的立方體以等速撞上另一個立方體,使其撞上牆壁並以原路徑反彈

假設沒有摩擦力且所有碰撞均為完美彈性碰撞(也就是沒有能量散失)

且離牆壁較遠的立方體的質量是離牆壁較近的立方體的 10^x 倍

給你 x,請求出總共會碰撞幾次

輸入

每一行一個非負偶數 x(x<923)

0

輸出

總共會碰撞幾次

3

解題思路

假設較遠的立方體為 a ，較近的為 b，在沒有能量溢散，a 的質量正好為 10^x 且 x 為偶數的的情況下 (也就是題意)，立方 b 的總碰撞次數加起來剛好會是 Floor(π * 10^{x / 2}) 次。

所以建好一個 pi 陣列，從第 0 項輸出至第 x/2 項即為答案。

具體請參考 3B1B (英語中字) 或佑來了 (中文)。

完整程式碼

AC (2ms, 104KB)

#include <stdio.h>

int n;
char tmp, pi[1005] = "31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201989";

int main()
{
    while (scanf(" %d", &n) == 1)
    {
        n >>= 1;
        tmp = pi[n + 1];
        pi[n + 1] = '\0';
        puts(pi);
        pi[n + 1] = tmp;
    }
    return 0;
}

模板庫
[模板] 字串賦值

[模板] 字串賦值

2019-08-30

模板

setInt()

inline char* setInt(register char buffer[], register int src, const char suffix)
{
    static char tmp[13];
    register char* st = tmp + 12;
    register unsigned int div;
    *st = 0;
    if (src < 0)
    {
        src = ~src + 1;
        *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        while (src = div)
            * (--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        *(--st) = '-';
    }
    else
    {
        do
        {
            *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        } while (src = div);
    }
    while (*buffer++ = *st++)
        ;
    *buffer++ = suffix;
    return buffer;
}

setUInt()

inline char* setUInt(register char buffer[], register unsigned int src, const char suffix)
{
    static char tmp[11];
    register char* st = tmp + 10;
    register unsigned int div;
    *st = 0;
    do
    {
        *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
    } while (src = div);
    while (*buffer++ = *st++)
        ;
    *buffer++ = suffix;
    return buffer;
}

setLongLong()

inline char* setLongLong(register char buffer[], register long long src, const char suffix)
{
    static char tmp[22];
    register char * st = tmp + 21;
    register unsigned long long div;
    *st = 0;
    if (src < 0)
    {
        src = ~src + 1;
        *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        while (src = div)
            * (--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        *(--st) = '-';
    }
    else
    {
        do
        {
            *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        } while (src = div);
    }
    while (*buffer++ = *st++)
        ;
    *buffer++ = suffix;
    return buffer;
}

setULongLong()

inline char* setULongLong(register char buffer[], register unsigned long long src, const char suffix)
{
    static char tmp[22];
    register char *st = tmp + 21;
    register unsigned long long div;
    *st = 0;
    do
    {
        *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
    } while (src = div);
    while (*buffer++ = *st++)
        ;
    *buffer++ = suffix;
    return buffer;
}

概述

本組模板為整數轉字串模板，使用此模板取代 sprintf() 可以大幅將整數打印到字串的時間，此外本模板內建指針偏移，可以節省使用 strlen() 偏移指針的開銷。

參數

buffer

本字串用來接收字串化後的數值。

src

本參數為要輸出的整數

suffix

本參數為串接在整數後面的一個後綴字元，若無後墜請輸入 0 (或 '\0')

返回值

該函數返回最後一個格式化數字的下一位元指標，如果含有後綴則在後綴的下一位。

實例

#include <stdio.h>

inline char* setUInt(register char buffer[], register unsigned int src, const char suffix)
{
    static char tmp[11];
    register char* st = tmp + 10;
    register unsigned int div;
    *st = 0;
    do
    {
        *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
    } while (src = div);
    while (*buffer++ = *st++)
        ;
    *buffer++ = suffix;
    return buffer;
}

inline char* setInt(register char buffer[], register int src, const char suffix)
{
    static char tmp[13];
    register char* st = tmp + 12;
    register unsigned int div;
    *st = 0;
    if (src < 0)
    {
        src = ~src + 1;
        *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        while (src = div)
            * (--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        *(--st) = '-';
    }
    else
    {
        do
        {
            *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        } while (src = div);
    }
    while (*buffer++ = *st++)
        ;
    *buffer++ = suffix;
    return buffer;
}

char input[10000], * st = input;

int main()
{
    unsigned long long v = 1LL << 31;
    st = setInt(st, 2147483647, ' ');
    st = setInt(st, v, '\n');
    st = setInt(st, -2147483647, ' ');
    puts(input);
    return 0;
}

編譯運行結果

2147483647 -2147483648
-2147483647

注意事項

在 32 位元架構下的編譯器，由於不需要做右移處理所以 int 的速度一般會比 short 來的更快 (或至少一樣快)，所以在記憶體空間足夠的請況下，保持使用 int 是比較好的選擇。

更新紀錄

2019-9-6

將轉正移至單獨一行避免 ZJ 編譯器出錯
整數轉字元用 '|' 取代 '+' 提升效率
buffer 改成靜態減少宣告時間

模板庫
[模板] 字串取值

[模板] 字串取值

2019-08-27

模板

getInt()

inline char* getInt(register char buffer[], register int* dst)
{
    while (*buffer < '-')
        if (!*buffer++) return NULL;
    if (*buffer == '-')
    {
        *dst = *++buffer ^ '0';
        while (*++buffer >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (*buffer ^ '0');
        *dst = ~*dst + 1;
    }
    else
    {
        *dst = *buffer ^ '0';
        while (*++buffer >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (*buffer ^ '0');
    }
    return buffer;
}

getUInt()

inline char* getUInt(register char buffer[],register unsigned int* dst)
{
    while (*buffer < '0')
        if (!*buffer++) return NULL;
    *dst = *buffer ^ '0';
    while (*++buffer >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (*buffer ^ '0');
    return buffer;
}

getLongLong()

inline char* getLongLong(register char buffer[],register long long* dst)
{
    while (*buffer < '-')
        if (!*buffer++) return NULL;
    if (*buffer == '-')
    {
        *dst = *++buffer ^ '0';
        while (*++buffer >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (*buffer ^ '0');
        *dst = ~*dst + 1;
    }
    else
    {
        *dst = *buffer ^ '0';
        while (*++buffer >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (*buffer ^ '0');
    }
    return buffer;
}

getULongLong()

inline char* getULongLong(register char buffer[],register unsigned long long* dst)
{
    while (*buffer < '0')
        if (!*buffer++) return NULL;
    *dst = *buffer ^ '0';
    while (*++buffer >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (*buffer ^ '0');
    return buffer;
}

getDouble()

inline char* getDouble(register char buffer[],register double* dst)
{
    register char nag;
    while (*buffer < '-')
        if (!*buffer++) return NULL;
    if (*buffer == '-')
        nag = 1, *dst = *++buffer ^ '0';
    else
        nag = 0, *dst = *buffer ^ '0';
    while (*++buffer >= '0')
        * dst = *dst * 10 + (*buffer ^ '0');
    if (*buffer == '.')
    {
        register double m = 1;
        while (*++buffer >= '0')
            * dst += (*buffer ^ '0') * (m *= 0.1);
    }
    if (nag)* dst = -*dst;
    return buffer;
}

概述

本組模板為字串轉數字模板，使用此模板取代 sscanf() 可以大幅減少從字串取得數組的時間，此外本模板內建指針偏移，可以節省使用 strlen() 偏移指針的開銷。

參數

buffer

本參數為來源字串。

dst

本參數用來接收格式化後的數值。

返回值

該函數返回最後一個格式化數字的下一位元指標，如果過濾字元時檢索到空字元 ('\0')，則返回一個空指標。

實例

#include <stdio.h>

inline char* getInt(char buffer[], int* dst)
{
    while (*buffer < '-')
        if (!*buffer++) return NULL;
    if (*buffer == '-')
    {
        *dst = *++buffer ^ '0';
        while (*++buffer >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (*buffer ^ '0');
        *dst = ~*dst + 1;
    }
    else
    {
        *dst = *buffer ^ '0';
        while (*++buffer >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (*buffer ^ '0');
    }
    return buffer;
}

int main()
{
    char input[1000] = "123 20 0 -17", * st = input;
    int val;
    while (st = getInt(&val, st))
    {
        printf("%d\n", val);
    }
    return 0;
}

編譯運行結果

123
20
0
-17

注意事項

為了加快速度，過濾字元時使用 (ch < '0' (有號為'-'))、判斷數字使用 (ch >= '0') 作為字元判斷依據如果字串中包含不符合條件的字元請自行修改判斷式或採用以下嚴格判斷的方式避免錯誤。

有號

(((ch = readChar()) < '0' || ch > '9') && ch != '-')

無號

((ch = readChar()) < '0' || ch > '9')

判斷數字

((ch = readChar()) >= '0' && ch <= '9')
如果情況允許，使用整數型態模擬浮點運算，因為整數型態運算速度遠高於浮點，且不會有失真問題。

更新紀錄

2019-9-6

傳入參數改為 register

模板庫
[模板] 輸出優化

[模板] 輸出優化

2019-08-30

模板

putInt()

inline void putInt(register int src, const char suffix)
{
    static char tmp[13];
    register unsigned int div;
    char* st = tmp + 11;
    *st = suffix, * (st + 1) = '\0';
    if (src < 0)
    {
        src = ~src + 1;
        *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        while (src = div)
            * (--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        *(--st) = '-';
    }
    else
    {
        do
        {
            *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        } while (src = div);
    }
    fputs(st, stdout);
}

putUInt()

inline void putUInt(register unsigned int src, const char suffix)
{
    static char tmp[12];
    register unsigned int div;
    char* st = tmp + 10;
    *st = suffix, * (st + 1) = '\0';
    do
    {
        *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
    } while (src = div);
    fputs(st, stdout);
}

putLongLong()

inline void putLongLong(register long long src, const char suffix)
{
    static char tmp[22];
    register unsigned long long div;
    char* st = tmp + 20;
    *st = suffix, * (st + 1) = '\0';
    if (src < 0)
    {
        src = ~src + 1;
        *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        while (src = div)
            * (--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        *(--st) = '-';
    }
    else
    {
        do
        {
            *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        } while (src = div);
    }
    fputs(st, stdout);
}

putULongLong()

inline void putULongLong(register unsigned long long src, const char suffix)
{
    static char tmp[22];
    register unsigned long long div;
    char* st = tmp + 20;
    *st = suffix, * (st + 1) = '\0';
    do
    {
        *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
    } while (src = div);
    fputs(st, stdout);
}

概述

本組模板為輸出優化模板，使用此模板取代 printf() 可以大幅印出資料的時間。

參數

src

本參數為要輸出的整數

suffix

本參數為串接在整數後面的一個後墜字元，若無後墜請輸入 0 (或 '\0')

返回值

本函式無返回值

實例

#include <stdio.h>

inline void putInt(register int src, const char suffix)
{
    static char tmp[13];
    register unsigned int div;
    char* st = tmp + 11;
    *st = suffix, * (st + 1) = '\0';
    if (src < 0)
    {
        src = ~src + 1;
        *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        while (src = div)
            * (--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        *(--st) = '-';
    }
    else
    {
        do
        {
            *(--st) = (src - ((div = src / 10) << 3) - (div << 1)) | '0';
        } while (src = div);
    }
    fputs(st, stdout);
}

int main()
{
    int min = 1 << 31;
    putInt(30, ' ');
    putInt(2147483647, '\n');
    putInt(min, '\0');
    return 0;
}

編譯運行結果

30 2147483647
-2147483648

注意事項

在 32 位元架構下的編譯器，由於不需要做右移處理所以 int 的速度一般會比 short 來的更快 (或至少一樣快)，所以在記憶體空間足夠的請況下，保持使用 int 是比較好的選擇。
如果要追求更高的效率請自行宣告緩衝區並使用字串賦值串接做批次輸出。

更新紀錄

2019-9-6

將轉正移至單獨一行避免 ZJ 編譯器出錯
整數轉字元用 '|' 取代 '+' 提升效率
buffer 改成靜態減少宣告時間

模板庫
[模板] 輸入優化

[模板] 輸入優化

2019-08-27

模板

readChar()

#define BUFSIZ 1048576

inline char readChar()
{
    static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
    if (now == end)
    {
        if (end < buffer + BUFSIZ)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
        now = buffer;
    }
    return *now++;
}

readInt()

inline char readInt(register int* dst)
{
    register char ch;
    while ((ch = readChar()) < '-')
        if (ch == EOF) return 0;
    if (ch == '-')
    {
        *dst = readChar() ^ '0';
        while ((ch = readChar()) >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
        *dst = ~*dst + 1;
    }
    else
    {
        *dst = ch ^ '0';
        while ((ch = readChar()) >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    }
    return 1;
}

readUInt()

inline char readUInt(register unsigned int* dst)
{
    register char ch;
    while ((ch = readChar()) < '0')
        if (ch == EOF) return 0;
    *dst = ch ^ '0';
    while ((ch = readChar()) >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    return 1;
}

readLongLong()

inline char readLongLong(register long long* dst)
{
    register char ch;
    while ((ch = readChar()) < '-')
        if (ch == EOF) return 0;
    if (ch == '-')
    {
        *dst = readChar() ^ '0';
        while ((ch = readChar()) >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
        *dst = ~*dst + 1;
    }
    else
    {
        *dst = ch ^ '0';
        while ((ch = readChar()) >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    }
    return 1;
}

readULongLong()

inline char readULongLong(register unsigned long long* dst)
{
    register char ch;
    while ((ch = readChar()) < '0')
        if (ch == EOF) return 0;
    *dst = ch ^ '0';
    while ((ch = readChar()) >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    return 1;
}

readDouble()

inline int readDouble(register double* dst)
{
    register char ch, nag;
    while (((ch = readChar()) < '-'))
        if (ch == EOF) return 0;
    if (ch == '-')
        nag = 1, *dst = readChar() ^ '0';
    else
        nag = 0, *dst = ch ^ '0';
    while ((ch = readChar()) >= '0')
        * dst = *dst * 10 + (ch ^ '0');
    if (ch == '.')
    {
        register double m = 1;
        while ((ch = readChar()) >= '0')
            * dst += (ch ^ '0') * (m *= 0.1);
    }
    if (nag)* dst = -*dst;
    return 1;
}

概述

本組模板為輸入優化模板，使用此模板取代 scanf() 可以大幅減少從資料流取得數組的時間，本組模板所有函式皆需要透過 readChar() 完成，請在使用時一併引入。

參數

BUFSIZ

此巨集用來定義緩衝區大小。

dst

本參數用來接收格式化後的數值。

返回值

若讀取到字元 -1 (EOF) 回傳 0，否則回傳 1。

實例

#include <stdio.h>
#define BUFSIZ 1048576

inline char readChar()
{
    static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
    if (now == end)
    {
        if (end < buffer + BUFSIZ)
            return EOF;
        end = buffer + fread(buffer, 1, BUFSIZ, stdin);
        now = buffer;
    }
    return *now++;
}

inline char readInt(register int* dst)
{
    register char ch;
    while ((ch = readChar()) < '-')
        if (ch == EOF) return 0;
    if (ch == '-')
    {
        *dst = readChar() ^ '0';
        while ((ch = readChar()) >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
        *dst = ~*dst + 1;
    }
    else
    {
        *dst = ch ^ '0';
        while ((ch = readChar()) >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    }
    return 1;
}

int main()
{
    int val;
    while (readInt(&val))
    {
        printf("%d\n", val);
    }
    return 0;
}

注意事項

在 32 位元架構下的編譯器，由於不需要做右移處理所以 int 的速度一般會比 short 來的更快 (或至少一樣快)，所以在記憶體空間足夠的請況下，保持使用 int 是比較好的選擇。
為了加快速度，過濾字元時使用 (ch < '0' (有號為'-'))、判斷數字使用 (ch >= '0') 作為字元判斷依據如果字串中包含不符合條件的字元請自行修改判斷式或採用以下嚴格判斷的方式避免錯誤。

有號

(((ch = readChar()) < '0' || ch > '9') && ch != '-')

無號

((ch = readChar()) < '0' || ch > '9')

判斷數字

((ch = readChar()) >= '0' && ch <= '9')
如果情況允許，使用整數型態模擬浮點運算，因為整數型態運算速度遠高於浮點，且不會有失真問題。

更新紀錄

2019-9-6

傳入參數改為 register

e357: 遞迴函數練習

2019-09-06

內容

定義一個函數 F(x)，

若 x = 1, 則 F(x) = 1
若 x 為偶數，則 F(x) = F(x/2)

其餘狀況，F(x) = F(x - 1) + F(x + 1)

輸入

輸入只有一行，其中包含一個正整數 x (1 <= x <= 2000000)。

6

輸出

輸出只有一行，其中包含一個正整數 F(x)。

2

解題思路

簡單的遞迴，依照題目實作即可。

完整程式碼

AC (2ms, 120KB)

#include <stdio.h>

int F(int x)
{
    if (x & 1)
        return x == 1 ? 1 : F(x - 1) + F(x + 1);
    else
        return F(x / 2);
}

int main()
{
    int n;
    scanf(" %d", &n);
    printf("%d", F(n));
    return 0;
}

e351: And 運算

2019-09-06

內容

給你兩個整數 a,b

求 a 到 b 之間所有整數(含)進行 and 運算的結果

輸入

每一行兩個非負整數 a,b(a,b<2^64)

12 15
2 3
8 13
17 23
11 15

輸出

答案

12
2
8
16
8

解題思路

很困難也很簡單的一題，重點在「進位」，二進制在進位之後原本的 1 都會變成 0，像是
0111₍₂₎ 進位後就會變成 1000₍₂₎，而題目是使用 AND 運算，當某位元出現過 0 之後不管之後出現幾次 1 都不會變回 1，因此當範圍內有任一 8 或其倍數(?????000₍₂₎) 時代表答案的最後 3 位必為 0 ，同理能套用在所有 2 的乘冪或其倍數。(如下表)

數	二進制
2	??????0
4	?????00
8	????000
16	???0000
32	??00000
64	?000000

而既然二的冪次或其倍數一定是最多 0 的，那在 a ~ b 中最大的二的冪次或其倍數就會是答案了，所以接下來的目標就是求出範圍內最大的二的冪次或其倍數，這時候就要用到下式

n = n & (n - 1);

這個式子可以把任一數的最後一位 1 變成 0 ，像是

11000₍₂₎ & 10111₍₂₎ = 10000₍₂₎
11100₍₂₎ & 11011₍₂₎ = 11000₍₂₎
11010₍₂₎ & 11001₍₂₎ = 11000₍₂₎
11001₍₂₎ & 11000₍₂₎ = 11000₍₂₎

具體原理是因為借位會讓最小位的 1 變成 0，讓比最小位 1 還小的 0 變成 1 ，但 0 和 1 經過位元 AND 運算後又都會變回 0 ，所以就能達成將最小位的 1 改為 0 的效果。

用這個式子不斷的移除 b 的最小位 1 ，直到 b <= a ，這時候的 b 就會是範圍內最大 2 的冪次的倍數，也就是答案了。

注意本題中輸入的 a 有可能比 b 還大，所以要先判斷兩數大小。

完整程式碼

AC (14ms, 1.1MB)

#include <stdio.h>
#define BUFSIZ 1048576
#define SWAP(x, y) (x)^=((y)^=((x)^=(y)))

inline char readChar()
{
    static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
    if (now == end)
    {
        if (end < buffer + BUFSIZ)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
        now = buffer;
    }
    return *now++;
}

inline char readULongLong(unsigned long long* dst)
{
    register char ch;
    while ((ch = readChar()) < '0')
        if (ch == EOF) return 0;
    *dst = ch ^ '0';
    while ((ch = readChar()) >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    return 1;
}

inline void putULongLong(register unsigned long long src, const char suffix)
{
    register unsigned long long div;
    char tmp[22], * st = tmp + 20;
    *st = suffix, * (st + 1) = 0;
    do
    {
        *(--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
    } while (src = div);
    fputs(st , stdout);
}

int main()
{
    unsigned long long f, t;
    while (readULongLong(&f), readULongLong(&t))
    {
        if (t < f) SWAP(t, f);
        while (f < t)
            t &= (t - 1);
        putULongLong(t, '\n');
    }
    return 0;
}

e346: 區間和練習

2019-09-06

內容

給定一個長度為 n 的整數序列 A，請回答 q 筆詢問。每筆詢問會問其中一段連續區間的總和為何。

輸入

輸入的第一行有一個整數 n (1 <= n <= 200000)，代表 A 序列的長度。

第二行有 n 個整數以空白分隔，依序表示 A 序列中的數字，其中數字的絕對值不會超過 10^9。

第三行有一個整數 q (1 <= n <= 200000)，代表詢問的數量。

接下來有 q 行，每行有兩個個數字 l, r，表示詢問為序列 A 中第 l 個數字到第 r 個數字的總和。

5
1 2 3 4 5
3
1 3
2 4
3 5

輸出

輸出 q 行，每行有一個整數表示該次詢問的答案。

6
9
12

解題思路

由於計算 list[a] ~ list[b] 的範圍時是連續不中斷的相加，所以在建立陣列時用相加的方式，每一項都是輸入值加上前面的所有元素之和，之後輸出時只要計算 list[b] - list[a-1] 就能得到 list[a] ~ list[b] 的和了。

本題不做輸入優化也可以。

完整程式碼

AC (33ms, 2.6MB)

#include <stdio.h>
#define BUFSIZ 1048576

long long list[200010];

inline char readChar()
{
    static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
    if (now == end)
    {
        if (end < buffer + BUFSIZ)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
        now = buffer;
    }
    return *now++;
}

char readInt(int* dst)
{
    register char ch;
    while ((ch = readChar()) < '-')
        if (ch == EOF) return 0;
    if (ch == '-')
    {
        *dst = readChar() ^ '0';
        while ((ch = readChar()) >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
        *dst = ~*dst + 1;
    }
    else
    {
        *dst = ch ^ '0';
        while ((ch = readChar()) >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    }
    return 1;
}

inline void putLongLong(register long long src, const char suffix)
{
    register unsigned long long div;
    char buffer[22], * st = buffer + 20;
    *st = suffix, * (st + 1) = 0;
    if (src < 0)
    {
        src = ~src + 1;
        *(--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
        while (src = div)
            * (--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
        *(--st) = '-';
    }
    else
    {
        do
        {
            *(--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
        } while (src = div);
    }
    fputs(st, stdout);
}

int main()
{
    int n, f, t;
    readInt(&n);
    for (int i = 1; i <= n; i++)
        readInt(&t), list[i] = list[i - 1] + t;
    readInt(&n);
    while (n--)
    {
        readInt(&f), readInt(&t);
        putLongLong(list[t] - list[f - 1], '\n');
    }
    return 0;
}

e345: Add Digits - 面試題

2019-09-05

內容

給一個正整數 n，將所有位數相加總和，如果總和不是個位數，重複相加步驟直到總和為個位數。

e.g. 345 => 3 + 4 + 5 = 12，12 => 1 + 2 = 3

疑？？怎麼覺得好像很眼熟？？好像寫過？？

那你知道如何不用 Loop/Recursion 來算出解答嗎？

輸入

每一行有一個數字 n，0 <= n <= 2147483647

EOF 結束

0
123
456

輸出

輸出該數字對應到的解答

0
6
6

解題思路

數學題，題目說不用迴圈或遞迴也能解代表有一定的規律，所以先列出前面幾項

數	相加和 1	相加和 2
0	0	N/A
1	1	N/A
2	2	N/A
3	3	N/A
4	4	N/A
5	5	N/A
6	6	N/A
7	7	N/A
8	8	N/A
9	9	N/A
10	1	N/A
11	2	N/A
…	…	…
16	7	N/A
17	8	N/A
18	9	N/A
19	10	1
20	2	N/A
21	3	N/A
…	…	…
26	8	N/A
27	9	N/A
28	10	1
29	11	2
30	3	N/A

然後就會由於相加和超過 9 時，會再觸發一次相加直到和變成個位數，而這個動作會讓數的最終合保持在 “1~9” 9 個數字做循環，所以可以用和 9 取餘來表示其規律。

但因為 9 和 9 取餘是 0 ，而題目要求的是 9，所以先將原數減去一取餘完再加回來變成

ans = (n-1) % 9 + 1

來處理數字為 9 的倍數時的例外情況，但這時候又產生另一個問題，當 n 為 0 時會變成 -1 和 9 取餘，所以在取餘前先判斷是否為 0 變成

ans = n != 0 ? (n - 1) % 9 + 1 : 0

然後每次都按公式輸出答案即可，另外在 C 中 -1 % 9 得到的解會是 -1，再加上 1 之後剛好會變回 0，所以不做判斷也可以，只是感覺不太好。

完整程式碼

AC (2ms, 104KB)

#include <stdio.h>

int main()
{
    int n;
    while (scanf(" %d", &n) == 1)
    {
        printf("%d\n", n ? (n - 1) % 9 + 1 : 0);
    }
    return 0;
}

e343: BMI 計算

2019-09-05

內容

「身體質量指數」這個概念，是由 19 世紀中期的比利時統計學家及數學家凱特勒（Lambert Adolphe Jacques Quetelet）最先提出。它的定義如下：

w = 體重，單位：公斤;
h = 身高，單位：公尺;
BMI = 身高體重指數，單位：公斤/平方公尺

輸入

輸入第一行含有一個整數 w，代表體重，單位公斤。第二行含有一個整數 h，代表身高，單位公分。

72
178

輸出

輸出 bmi 值，四捨五入到小數點以下一位數。

22.7

解題思路

簡單的四則運算，因為計算 BMI 時用的是公尺，但輸入的是公分，所以體重要先乘上 10000 再去和輸入的身高相除。

完整程式碼

AC (2ms, 108KB)

#include <stdio.h>

int main()
{
    double w, h;
    scanf(" %lf %lf", &w, &h);
    printf("%.1lf", (w * 10000) / (h * h));
    return 0;
}

數	相加和 1	相加和 2
0	0	N/A
1	1	N/A
2	2	N/A
3	3	N/A
4	4	N/A
5	5	N/A
6	6	N/A
7	7	N/A
8	8	N/A
9	9	N/A
10	1	N/A
11	2	N/A
…	…	…
16	7	N/A
17	8	N/A
18	9	N/A
19	10	1
20	2	N/A
21	3	N/A
…	…	…
26	8	N/A
27	9	N/A
28	10	1
29	11	2
30	3	N/A

數	相加和 1	相加和 2
0	0	N/A
1	1	N/A
2	2	N/A
3	3	N/A
4	4	N/A
5	5	N/A
6	6	N/A
7	7	N/A
8	8	N/A
9	9	N/A
10	1	N/A
11	2	N/A
…	…	…
16	7	N/A
17	8	N/A
18	9	N/A
19	10	1
20	2	N/A
21	3	N/A
…	…	…
26	8	N/A
27	9	N/A
28	10	1
29	11	2
30	3	N/A

數	相加和 1	相加和 2
0	0	N/A
1	1	N/A
2	2	N/A
3	3	N/A
4	4	N/A
5	5	N/A
6	6	N/A
7	7	N/A
8	8	N/A
9	9	N/A
10	1	N/A
11	2	N/A
…	…	…
16	7	N/A
17	8	N/A
18	9	N/A
19	10	1
20	2	N/A
21	3	N/A
…	…	…
26	8	N/A
27	9	N/A
28	10	1
29	11	2
30	3	N/A