e340: 差分練習

2019-09-05

內容

給定一陣列 B，請輸出這個陣列的差分陣列 A。

定義 1 : 當 B[i]為 A[0]+A[1]+…A[i]，B 陣列為 A 陣列的前綴和。

定義 2 : 當 B 陣列為 A 陣列的前綴和，A 陣列為 B 陣列的差分陣列。

輸入

輸入的第一行有一個整數 N (1 <= N <= 200000)，代表 B 陣列大小。

第二行有 N 個整數以空白分隔，依序表示 B[0], B[1], B[2] … B[N-1]。

陣列中數字的絕對值不會超過 10^9。

5
1 2 3 4 5

輸出

輸出一行，其中有 N 個整數以空白分隔，依序表示 A[0], A[1], A[2] … A[N-1]。

1 1 1 1 1

解題思路

和上一題差不多，改成用一個整數紀錄上一個元素，輸出當前元素減去上一個元素即可。

一樣不用做 IO 優化也能過。

完整程式碼

AC (23ms, 1.1MB)

#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(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 putInt(register int src, const char suffix)
{
    register unsigned int div;
    char buffer[13], * st = buffer + 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()
{
    register int prev = 0;
    long long tmp;
    scanf("%*lld");
    while (readInt(&tmp))
        putInt((tmp - prev), ' '), prev = tmp;
    return 0;
}

e339: 前綴和練習

2019-09-05

內容

給定一陣列 A，請輸出這個陣列的前綴和陣列 B。

定義 : 當 B[i]為 A[0]+A[1]+…A[i]，B 陣列為 A 陣列的前綴和。

輸入

輸入的第一行有一個整數 N (1 <= N <= 200000)，代表 A 陣列大小。

第二行有 N 個整數以空白分隔，依序表示 A[0], A[1], A[2] … A[N-1]。

陣列中數字的絕對值不會超過 10^9。

5
1 2 3 4 5

輸出

輸出一行，其中有 N 個整數以空白分隔，依序表示 B[0], B[1], B[2] … B[N-1]。

1 3 6 10 15

解題思路

就是將自己和前面的所有項目加起來，所以用一個整數去累加，然後不斷輸出該整數即可。

注意！累加的總數可能是負值也會超過 int 上限，要使用 long long。

本題不做 IO 優化也能過。

完整程式碼

AC (21ms, 1.1MB)

#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 readLongLong(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;
}

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()
{
    register long long sum = 0;
    long long tmp;
    scanf("%*lld");
    while (readLongLong(&tmp))
        putLongLong((sum += tmp), ' ');
    return 0;
}

線上解題
ZeroJudge
e338: 放暑假了!!!!!...可惜要上暑輔...開學後還要模考...

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

2019-09-05

內容

段考後的延平:

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

XD

輸入

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

1
2
3
4

輸出

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

1
1
2
1

解題思路

算出一個整數的二進制中有幾個 1 位元，直覺反應用用右移(">>")和位元 AND ('&') 配合迴圈檢查每個位元，時間複雜度 O(n)

int popCount(int n)
{
    int res = 0;
    while(n)
    {
        res += n & 1;
        n >>= 1;
    }
    return res;
}

但這樣子還不夠快，所以改用建表 + 查表 O(1) 的方法。

作法很簡單，把每兩位元當作一組那每組就有

00, 01, 10, 11

四種狀態，1 出現的次數分別是

0 1 1 2

而當有兩組時變成

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,
1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

4 * 4 = 16 種狀態，而 1 出現的次數剛好能將他拆成左邊一組右邊一組，然後左右兩組相加，變成

(0 + 0), (0 + 1), (0 + 1), (0 + 2), (1 + 0), (1 + 1), (1 + 1), (1 + 2),
(1 + 0), (1 + 1), (1 + 1), (1 + 2), (2 + 0), (2 + 1), (2 + 1), (2 + 2)

之後 6 位, 8 位 … 32 位皆可用同理求得，而由於過程是簡單遞迴，所以可以用巨集來建表減少程式的運算消耗 (如下方程式碼)，最後查表輸出，但由於 2³² 太大了，所以表只建到 2¹⁶ 然後用右移(">>")和位元 AND ('&') 來拆成前 16 位和後 16 位再相加求得 1 的總數輸出。

輸入輸出量極大，要做 IO 優化。

–

題外話: 本題出題者應該是想要用時間卡開頭 O(n) 的算法，但本來 O(n) 就沒多慢，所以連帶著用 O(1) 算法但 IO 優化不夠好的人一起被卡掉了，結果就產生了討論區精彩的筆戰，然後不知道是不是因為太精采的關係，每次 Loading 進這題都要讀很久…

完整程式碼

AC (0.2s, 2.1MB)

#pragma GCC optimize(3)
#include <stdio.h>
#define MAX 65535
#define BUFSIZ 1048576
#define BUFMAX 1048560
#define  BIT2(n)       n,         n+1,       n+1,        n+2
#define  BIT4(n)  BIT2(n),  BIT2(n+1),  BIT2(n+1),  BIT2(n+2)
#define  BIT6(n)  BIT4(n),  BIT4(n+1),  BIT4(n+1),  BIT4(n+2)
#define  BIT8(n)  BIT6(n),  BIT6(n+1),  BIT6(n+1),  BIT6(n+2)
#define BIT10(n)  BIT8(n),  BIT8(n+1),  BIT8(n+1),  BIT8(n+2)
#define BIT12(n) BIT10(n), BIT10(n+1), BIT10(n+1), BIT10(n+2)
#define BIT14(n) BIT12(n), BIT12(n+1), BIT12(n+1), BIT12(n+2)
#define BIT16(n) BIT14(n), BIT14(n+1), BIT14(n+1), BIT14(n+2)

const unsigned char TABLE[MAX + 1] = { BIT16(0) };
char output[BUFSIZ];

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 readUInt(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;
}

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

int main()
{
    int n;
    char *end = output + BUFMAX;
    register char* oTop = output;
    while (readUInt(&n))
    {
        oTop = setUInt(oTop, TABLE[n & MAX] + TABLE[(n >> 16) & MAX], '\n');
        if (oTop > end)
        {
            *oTop = 0;
            fputs(output, stdout);
            oTop = output;
        }
    }
    *oTop = 0;
    fputs(output, stdout);
    return 0;
}

e319: 小王的積木 Again!

2019-09-05

內容

給你一些數字

這些數字中只有一個只出現 1 次,其他數字則出現了 3 次

求這個只出現 1 次的數字

輸入

第一行有一個整數 N(4<=N<4*10^6)

接下來有 N 個整數,每個整數皆在 int 範圍以內

4
2 2 2 1

輸出

只出現 1 次的數字

1

解題思路

d708 的困難版，看不懂邏輯的可以先去看那題的題解。

位元操作，邏輯如下 (註解區的 t0 ~ t3 指的是所有位元的操作情況非整數)

while (readUInt(&t0))
{
    // -- 3 --
    // 當之前的 t2 和現在的 t0 都出現 1 時，將 t1 設為 1，並把剛才進位至 3 的位元清 0 (因為計算過了)
    // t1 為 1 的位元在在下一個 loop 必定會被歸 0
    // (因為 t2 和 t0 為 0，t0 為 0 時這個 loop 就不可能讓 t2 變成 1，t2 在這個 loop 為 0 時，t1 在下個 loop 就不可能為 1)
    t1 = t2 & t0;
    t2 &= ~t1;
    t0 &= ~t1;
    // -- 2 --
    // 當之前的 t1 和現在的 t0 都出現 1 時
    // 將他們 t2 設為 1
    t2 ^= t1 & t0;
    // -- 1 --
    // 之前的 t1 或現在的 t0 出現 1 的位元為 1
    // 之前的 t1 且現在的 t0 出現的則歸 0 (上面已經進位置 t2 了)
    // 都沒有則繼續維持 0
    t1 ^= t0;
}

輸入測資量極大，要做輸入優化，且優化時因記憶體限制 5MB 所以要注意 buffer 大小。

完整程式碼

AC (37ms, 108KB)

#include <stdio.h>
#define BUFSIZ 8192

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

inline char readUInt(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;
}

int main()
{
    unsigned int t0, t1 = 0, t2 = 0, t3 = 0;
    scanf(" %*d");
    while (readUInt(&t0))
    {
        t3 = t2 & t0;
        t2 &= ~t3;
        t0 &= ~t3;
        t2 ^= t1 & t0;
        t1 ^= t0;
    }
    printf("%d", t1);
    return 0;
}

d708: 小王的積木

2019-09-05

內容

自從小涵去商店買了那麼多的積木，小王也去買了一大堆。
不過小王比較喜歡數學，所以他買的積木上寫的只有數字；因為他認為偶數比較吉利，於是他買的積木是全是偶數快的。
聽說小涵少了一個積木，他便整理了一下他的，可是他發現他也少了一塊積木…（很無語吧…）
上次他見你已經幫小涵找到了積木，於是就請你來幫他找找，而且他還告訴你：“我的積木比小涵的好找很多。”
半信半疑的你決定幫幫他。

輸入

只有一筆測資。測資末尾會有多餘信息，忽略就好。//感謝 asas 提醒。2015/8/6

輸入數據的第一行，是小王告訴你他的積木個數 N（N 一定是一個正偶數，而且 2<=N<=1000000，你看他的積木可沒有小涵的多）。
接下來每行有（N-1）個數字，表示小王每個積木上的數字（可以用 longint 存儲）。

8
1
2
3
2
3
4
4

輸出

對於每組測資，輸出小王缺少的那塊積木的數字。

1

解題思路

e319 的簡易版。

利用兩相同數經 XOR 運算後因為偶一為零會變成 0 的特性，將一個整數 0 和每個數字都 XOR 一遍，最後的值就會是只出現一次的那個 (出現偶數次的都互相抵銷掉了)

本題不用做輸入優化也能輕鬆過。

完整程式碼

AC (10ms, 1.1MB)

#include <stdio.h>
#define BUFSIZ 1048576

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

inline char readUInt(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;
}

int main()
{
    unsigned int n, ans = 0, tmp;
    scanf(" %d", &n);
    while (--n)
    {
        readUInt(&tmp);
        ans ^= tmp;
    }
    printf("%d", ans);
    return 0;
}

線上解題
ZeroJudge
e307: 請讓我留在你的回憶裡

e307: 請讓我留在你的回憶裡

2019-09-05

內容

背景介紹，不是很重要見原題

輸入

幸(サチ/Sachi)失去記憶了,頭腦一片空白

請你幫她移除記憶中的空白,找回她的記憶吧

輸入只有一行,含有一個字串 s (|s|<=108)

s 含有所有可印出的字元(包含空白),請你移除其中的空白

移除方式如下:

若連續的空白數為偶數,則全部移除

若為奇數,則移除到只剩下一個空白

M y n am e i s S a c h i .

輸出

移除空白後剩下的字元

My name is Sachi.

解題思路

簡單的字串處理，重點在 IO 優化。

完整程式碼

AC (0.1s, 2.1MB)

#include <stdio.h>
#define BUFSIZ 1048576
#define BUFMAX 1048000

char output[BUFSIZ];

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

int main()
{
    register char tmp, * oTop = output, isOdd = 0, *max = output + BUFMAX;
    while (tmp = readChar())
    {
        if (tmp == ' ')
            isOdd = ~isOdd;
        else
        {
            if (isOdd)
                * oTop++ = ' ', isOdd = 0;
            *oTop++ = tmp;
            if (oTop > max)
            {
                *oTop = '\0';
                fputs(output, stdout);
                oTop = output;
            }
        }
    }
    *oTop = '\0';
    fputs(output, stdout);
    return 0;
}

e305: Xor 運算

2019-09-05

內容

有一個函式如下

C/C++:

long long sumxor(long long N) {
    long long ans = 0;
    for (long long i = 0; i < N; i++) {
        if ((N ^ i) == (N + i))ans++;
    }
    return ans;
}

Python:

def sumxor(N) :
    ans = 0
    for i in range(N) :
        if ((N ^ i) == (N + i)) :
            ans += 1
            return ans

Java:

public static long sumxor(long N) {
    long ans = 0;
    for (long i = 0; i < N; i++) {
        if ((N ^ i) == (N + i)) ans++;
    }
    return ans;
}

Pascal:

var
    i, N: int64;
    ans : int64 = 0;
function sumxor(N: int64):int64;
begin
    ans:=0;
    for i := 0 to N do begin
        if ((N xor i) = (N + i)) then ans:=ans+1;
        if (N=0) ans:=0;
        sumxor:=ans;
    end;
end;

因為要處理的 N 很大,現在請你優化這個函式

輸入

多筆測資

一行有一個整數 N(N<10¹⁵)

4
10

輸出

輸出函式的回傳值

4
4

解題思路

a ^ b 和 a + b 相等的情況只有在轉換成二進制後位元 1 不重疊的情況 (如下)

48 + 1 = (11000) + (00001)，此時不論用 XOR 或 + 都會變成 (11001)

而由於有多個 0 ，所以要算出所有組合數 : 2^{最大位元 1 後面 0 的數量} 舉例來說，上面的 48 最大位元 1 為 (‘1’1000)，後面共有 3 個 0 ，所以就是 2³ = 8，而因為是 2 的乘冪，所以可以用位元運算加速，如底部程式碼。

雖然 0 符合以上邏輯，但因為 0 沒有辦法進行位元操作所以要做特殊處理。

完整程式碼

AC (6ms, 104KB)

#include <stdio.h>

long long n, ans;

int main()
{
    while (scanf(" %llu", &n) == 1)
    {
        if (n)
        {
            ans = 1;
            do
            {
                if (!(n & 1))
                    ans <<= 1;
            } while (n >>= 1);
            printf("%llu\n", ans);
        }
        else puts("0");
    }
    return 0;
}

線上解題
ZeroJudge
e295: 基本題-小崴的IO優化挑戰

e295: 基本題-小崴的IO優化挑戰

2019-09-05

內容

小崴的 IO 優化挑戰!!!
把輸入的很多組數字加起來再輸出!!

數字幾個沒限制!!!

加油!!! 小心 TLE!!

輸入

每一行兩個 unsigned int a & b

EOF 結尾

1 2
3 4
5 6
7 8

輸出

每一行再輸出一個 unsigned int c=a+b

3
7
11
15

解題思路

如題，簡單的加法和 IO 優化。

完整程式碼

AC (22ms, 2.1MB)

#include <stdio.h>
#define BUFSIZ 1048576
#define BUFMAX 1048570
char output[BUFSIZ];

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 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;
}

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

int main()
{
    unsigned int n, m;
    register char* oTop = output;
    char* end = output + BUFMAX;
    while (readUInt(&n), readUInt(&m))
    {
        oTop = setUInt(oTop, n + m, '\n');
        if (oTop > end)
        {
            *oTop = '\0';
            puts(output);
            oTop = output;
        }
    }
    *oTop = '\0';
    puts(output);
    return 0;
}

e284: 放暑假了!!!!!

2019-09-05

內容

暑假水題大放送!!!來解個水題消暑吧!!!
請判斷一個數是否為 2 的乘冪!

輸入

一個整數(int 可以存的下)

1
2
3
4

輸出

如果是,輸出”Yes”,如果不是,輸出”No”

Yes
Yes
No
Yes

解題思路

由於二進制進位的關係， 2ⁿ-1 的數 (如下)

2⁰ - 1 = 0 = 0000
2¹ - 1 = 1 = 0001
2² - 1 = 3 = 0011
2³ - 1 = 7 = 0111

因為 2ⁿ-1 中 1 的位元必會從最小位元連續出現，所以加上 1 進位後，原本的 1 都會因為進位變成 0 (如下)

2⁰ = 1 = 0001
2¹ = 2 = 0010
2² = 4 = 0100
2³ = 8 = 1000

這時候發現 2ⁿ 和 2ⁿ-1 中位元 1 必定不會重疊，所以當輸入為 2ⁿ和 2ⁿ-1 利用位元 AND ('&')做運算時得到的結果必為 0。

而由於不是 2ⁿ-1 的數中位元 1 不可能同時滿足從最小位元開始連續出現且完全沒有斷開兩個條件，所以上面的特殊情況只會出現在 2ⁿ 和 2ⁿ-1 做位元 AND 時。

已經能確定是 2ⁿ 專有的情況了，就能用 n & (n - 1) 來判斷，如果為 0 輸出 "YES"，反之輸出 "NO"。

本題輸入輸出量極大，一定要做 IO 優化，輸入中包含特例 0，這時候應該輸出 "YES"。

完整程式碼

AC (73ms, 2.1MB)

#include <stdio.h>
#define BUFSIZ 1048576
#define BUFMAX 1048570
char output[BUFSIZ];

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 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;
}

int main()
{
    unsigned int n;
    register char* oTop = output;
    char* end = output + BUFMAX;
    while (readUInt(&n))
    {
        if (n & (n - 1) | !n)
            * oTop++ = 'N', * oTop++ = 'o', * oTop++ = '\n';
        else
            *oTop++ = 'Y', * oTop++ = 'e', * oTop++ = 's', * oTop++ = '\n';
        if (oTop > end)
        {
            *oTop = '\0';
            puts(output);
            oTop = output;
        }
    }
    *oTop = '\0';
    puts(output);
    return 0;
}

在開頭再加上命令編譯時對程式進行優化的指令

AC (69ms, 2.1MB)

#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")
#pragma comment(linker, "/stack:200000000")

e273: 微分入門課

2019-09-04

內容

求一個多項式函數 f(x) 對 x 微分的結果

輸入

有多筆測資

每筆測資包含:

第一行有一個整數 n(n<=1000)

第二行有 n 個整數,代表多項式函數 f(x)之係數(按照降冪排列),且保證所有係數皆小於 50,大於 0

3
1 2 1

輸出

輸出此多項式函數對 x 微分的結果(降冪排列且輸出係數即可)

2 2

解題思路

用程式實作微分。

這題主要是優化，除了基本的 IO 優化外，乘法因為範圍不大所以先建好一個乘法表之後直接查表取值。

完整程式碼

AC (0.1s, 1.3MB)

#include <stdio.h>
#define BUFSIZ 1048576

unsigned int mTable[55][1010];
char output[50000];

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 readUInt(unsigned register 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;
}

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

int main()
{
    unsigned int n, tmp;
    char* oTop;
    for (int i = 1; i < 50; ++i)
    {
        for (int j = 1; j < 1000; ++j)
            mTable[i][j] = mTable[i][j - 1] + i;
    }
    while (readUInt(&n))
    {
        if (n <= 1)
        {
            puts("0");
            if (!n) continue;
        }
        else
        {
            oTop = output;
            while (--n)
            {
                readUInt(&tmp);
                oTop = setUInt(oTop, mTable[tmp][n], ' ');
            }
            *(oTop - 1) = '\0';
            puts(output);
        }
        readUInt(&tmp);
    }
    return 0;
}