內容

小海豚要上初中了，也會了一點程序設計。海豚爸爸想起大約 30 年前上高一的時候自己第一次摸電腦。現在難以想像一下那種心情，那時候一個中國大陸一個大學畢業生（很稀罕的哦）月工資只有 60 元 RMB，而一台蘋果 II 要 6000 元 RMB。海豚爸爸有生以來輸入電腦的第一個程序，就是“最大公約數”。

輸入

每行 2 個數 a, b 0 < a, b < 1000000000

EOF 結束

30 24
2 4

輸出

對每對 a,b 輸出其最大公約數

6
2

解題思路

和這題完全一樣，用輾轉相除法做。

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

int m, n;

int main()
{
    while (scanf(" %d %d", &m, &n) == 2)
    {
        while (n)
        {
            m %= n;
            SWAP(m, n);
        }
        printf("%d\n", m);
    }
    return 0;
}

內容

好餓歐歐歐歐

有 n * n 個食物在你面前排成一個方陣

每個食物有它的飽足度

你想知道把其中一塊通通吃掉會獲得多少飽足度

輸入

多組測資以 EOF 結束

每組測資開始有兩個正整數 n,m (n<=500, m<=100000)

接下來 n 行有 n 個不超過 100 的正整數依序代表每個食物的飽足度

接下來 m 行每行有四個數字 x1,y1,x2,y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n)

代表你想要吃掉食物的範圍

3 3
1 2 3
4 5 6
7 8 9
1 1 3 3
1 1 1 3
1 1 3 1

輸出

對每組測資輸出 m 行，代表總飽足度

45
6
12

解題思路

吞食天地 的加強版，從一維變成二維，但解題邏輯一樣是建立總飽足度陣列之後用數學去取得目標區間。

建立總飽足度的二維陣列

總飽讀度計算流程(sum 為總飽足度矩陣)：

. . . .
. . . .
. . s .  如果要計算 s 點
. . . .

1 1 . .
1 1 . .
1 1 0 .   + 先加上 sum[s.X - 1][s.Y]
. . . .    (數字為該區域飽足度被計算到的次數)

2 2 1 .
2 2 1 .
1 1 0 .  再加上 sum[s.X][s.Y - 1]
. . . .    (這時候由於 2 的區域飽足感被重複加了兩次，所以待會要減掉)

1 1 1 .
1 1 1 .
1 1 0 .  減到 sum[s.X -1][s.Y - 1]
. . . .

1 1 1 .
1 1 1 .
1 1 1 .  最後加上 s點本身的飽足感即可。
. . . .

觀察上面流程得到以下公式

sum[s.X][s.y] = sum[s.X - 1][s.y] + sum[s.X][s.y - 1] - sum[s.X - 1][s.y - 1] + s 點的飽足感

取得 s 點到 e 點的區域飽足度

計算流程範例 :

 . . . . .
 . s 0 0 .
 . 0 0 0 .  如果要計算 s 到 e 區域的的飽足度
 . 0 0 e .       (也就是 s + e + 0 區域)
 . . . . .

 1 1 1 1 .
 1 1 1 1 .
 1 1 1 1 .  先加上 sum[e.X][e.Y] 點的飽足度
 1 1 1 1 .
 . . . . .

 0 1 1 1 .
 0 1 1 1 .
 0 1 1 1 .  減掉 sum[e.X][s.Y - 1] 點的飽足度
 0 1 1 1 .
 . . . . .

-1 0 0 0 .
 0 1 1 1 .
 0 1 1 1 .  減掉 sum[s.X - 1][e.Y] 點的飽足度
 0 1 1 1 .
 . . . . .

 0 0 0 0 .
 0 1 1 1 .
 0 1 1 1 .  加上 sum[s.X - 1][s.Y - 1] 點的飽足度，就會得到目標區域
 0 1 1 1 .
 . . . . .

觀察上面流程得到以下公式

s 到 e 點的總飽和度 = sum[e.X][e.y] - sum[e.X][s.y - 1] - sum[s.X - 1][e.y] + sum[s.X - 1][s.y - 1]

計算後輸出答案即可。

#include <stdio.h>

int sum[510][510];

int main()
{
    int n, m, sX, sY, eX, eY;
    while (scanf(" %d %d", &n, &m) == 2)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                scanf(" %d", &sum[i][j]);
                sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
            }
        }
        for (int i = 0; i < m; i++)
        {
            scanf("%d %d %d %d", &sX, &sY, &eX, &eY);
            printf("%d\n", sum[eX][eY] - sum[eX][sY - 1] - sum[sX - 1][eY] + sum[sX - 1][sY - 1]);
        }
    }
    return 0;
}

內容

好餓歐歐歐歐

有 n 個食物在你面前排成一排

每個食物有它的飽足度

你想知道把其中一段通通吃掉會獲得多少飽足度

輸入

多組測資以 EOF 結束

每組測資開始有兩個正整數 n,m (n,m <= 100000)

接下來一行有 n 個不超過一千的正整數依序代表每個食物的飽足度

接下來 m 行每行有兩個數字 l,r (1 <= l <= r <= n)

代表你想要吃掉第 l 個到第 r 個食物

3 3
1 2 3
1 3
1 2
2 3

輸出

對每組測資輸出 m 行，代表總飽足度

6
3
5

解題思路

基礎 DP 題，由於從 A 吃到 B 時不會有中間某個不吃的情況，所以總飽足度陣列可以儲存從零到該項的總飽足度，輸出時用相減的就能得到那段的飽足度。

在製作總飽足度陣列時，要計算第 i 項的總飽足度只要把 arr[i - 1] (0 到 i - 1 項的總飽足度) 加上第 i 項的飽足度即可。

#include <stdio.h>

int full[100010];

int main()
{
    int n, m, f, t;
    while (scanf(" %d %d", &n, &m) == 2)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf(" %d", &full[i]);
            full[i] += full[i - 1];
        }
        for (int i = 1; i <= m; i++)
        {
            scanf(" %d %d", &f, &t);
            printf("%d\n", full[t] - full[f - 1]);
        }
    }
    return 0;
}

內容

John 是一個赫赫有名的藝術品投資專家，每個月都會計算藝術品投資的盈虧，以審視其獲利。John 每個月月底，即開始計算其每一件藝術品的獲利狀況。由於藝術品的種類繁多，John 每個月總是要花費許多時間，計算其獲利狀況，以決定是否要將藝術品出脫。因此，他想麻煩你撰寫一支程式，計算每一件藝術品的盈虧狀況。

輸入

測試資料的第一行是一個整數 n，代表 John 總共投資了 n 件藝術品。以下 n 行，每一行有兩個整數 m 和 p，m 是該藝術品投資的金額、p 是該藝術品目前的價值。其中 1≤m,p≤100000，單位是仟元。

4
200 177
200 200
892 1000
1000 992

輸出

每一件藝術品依據它的投資金額及目前價值，計算並輸出其獲利率 x。x 為正，表示獲利；x 為負表示虧損。若 x≥10.00% 或 x≤-7.00%，即售出該藝術品，以「dispose」表示；否則，即保留該藝術品，以「keep」表示。輸出格式，請見輸出範例。

-11.50% dispose
0.00% keep
12.11% dispose
-0.80% keep

解題思路

用 EPS ( epsilon，表示一個不影響計算結果的極小值) 修正浮點數特定情況下計算後的產生的誤差， EPS2 修正 -0.00% 的問題。

修正完之後就是基本的 if 判斷。

#include <stdio.h>
#define EPS 0.00001
#define EPS2 0.0001

int main()
{
    int n, m, p;
    double gap;
    while (scanf(" %d", &n) == 1)
    {
        for (int i = 0; i < n; i++)
        {
            scanf(" %d %d", &m, &p);
            gap = (double)((p - m) * 100) / m;
            gap += gap < 0 ? -EPS : EPS;
            if (gap < EPS2 && gap > -EPS2)
                gap = 0;
            printf("%.2lf%% %s\n", gap, gap < 10 && gap > -7 ? "keep" : "dispose");
        }
    }
    return 0;
}

內容

排列數字一定很容易嗎

現在給你一堆數字

請你幫我排序

輸入

多筆測資

每筆測資第一行輸入一正整數 N

皆下來的 N 行每行有一個整數 Xi (1 <= i <= N)

（0 < N < 1000, | Xi | < 10¹⁰⁰)

5
1
3
2
5
0
4
222222222222222222222222222
111111111111111
-44444444444444444444444444444444444444444444444444444
33333333333333333333333333333333333333333333

輸出

將排序好的數字由小到大分行輸出

範例如下

0
1
2
3
5
-44444444444444444444444444444444444444444444444444444
111111111111111
222222222222222222222222222
33333333333333333333333333333333333333333333

解題思路

定義一個結構

typedef struct node
{
    int Length;
    char Num[110];
}BigNum;

輸入時將大數字串存入 Num ，並將其長度存入 Length 。
如果 Num[0] 為 ‘-‘ 則將 Length 改為 -Length 。

比較 BigNum 時，先比較 BigNum.Length 如果 BigNum.Length 一樣再用 strcmp() 比較 BigNum.Num 。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node
{
    int Length;
    char Num[110];
}BigNum;

BigNum list[1000], * sort[1000];

int cmp(const BigNum** lhs, const BigNum** rhs)
{
    if ((*lhs)->Length != (*rhs)->Length)
        return (*lhs)->Length - (*rhs)->Length;
    return (*lhs)->Length < 0 ? strcmp((*rhs)->Num, (*lhs)->Num) : strcmp((*lhs)->Num, (*rhs)->Num);
}

int main()
{
    int n;
    while (scanf("%d", &n) == 1)
    {
        for (int i = 0; i < n; i++)
        {
            scanf(" %s", list[i].Num);
            list[i].Length = list[i].Num[0] == '-' ? -((int)strlen(list[i].Num)) : strlen(list[i].Num);
            sort[i] = &list[i];
        }
        qsort(sort, n, sizeof(BigNum*), cmp);
        for (int i = 0; i < n; i++)
            puts(sort[i]->Num);
    }
    return 0;
}

內容

鄭學長的手機裡有不可告人的秘密，為了不被發現那些照片和簡訊，他小心翼翼地把手機上鎖了。
幸好，你是個會寫程式的天才，你能夠產生所有的密碼去嘗試，現在趕快動手吧！
噢！還有一件事，基於某些理由，你知道鄭學長的密碼沒有重覆的字。

輸入

輸入為一個 n (n<=8)，代表鄭學長的密碼位數。

3
2

輸出

輸出所有可能的密碼，依字典順序反向排列（因為你覺得他的密碼應該在後半段）。

321
312
231
213
132
123
21
12

解題思路

經典遞迴題目，先宣告一個 unUse 陣列，在數字被使用後就把 unUse[i] 設成 0 代表 i 被使用過，並在使用結束在復原回去。

接下來用遞迴遍歷從 333 到 111 (假設 n = 3) 的所有可能，在遍歷時如果遇到 unUse[i] == 0 的情況代表 i 在之前已經被使用過了，因為題目說數字不會重複，所以直接跳過該分支。

由於在遍歷時已經排除了數字重複的情況，所以答案直接輸出即可。

#include <stdio.h>

int n;
char unUse[10] = "012345678", output[10];

void dfs(int now, char* oTop)
{
    if (now == n)
    {
        puts(output);
        return;
    }
    for (int i = n; i; i--)
    {
        if (unUse[i])
        {
            *oTop = unUse[i] , unUse[i] = 0;
            dfs(now + 1 , oTop + 1);
            unUse[i] = *oTop;
        }
    }
}

int main()
{
    while (scanf("%d", &n) == 1)
    {
        output[n] = '\0';
        dfs(0, output);
    }
    return 0;
}

內容

輸出一螺旋矩陣。

輸入

每行有一正整數 T，代表有幾組測試資料

接下來有 T 行， 每行有 N、M 兩正整數

N 為矩陣長寬，就是會有 N*N 矩陣

M 為方向，M=1 為順時鐘，M=2 為逆時鐘

N 範圍為 1~100 之間

2
3 1
2 2

輸出

把矩陣輸出，矩陣值之間寬度為 5，就是[00000]寬度

C++可用 setw(5)或 C 的%5d 輸出

1     2     3
8     9     4
7     6     5

1     4
2     3

解題思路

螺旋路徑走訪二微矩陣的方法：

1. sr = er = ec = 0 , sc = -1 (因為他是進入點)
2. sc++ , 從 table[sr,sc] 走訪到 table[sr,ec] (左上 → 右上)
3. sr++ , 從 table[sr,ec] 走訪到 table[er,ec] (右上 → 右下)
4. ec++ , 從 table[er,ec] 走訪到 table[er,sc] (右下 → 左下)
5. er++ , 從 table[er,sc] 走訪到 table[sr,sc] (左下 → 左上)
6. 判斷已走訪的元素數量是否等於二維矩陣最大元素數，是：跳出迴圈，否：回到(1.)

順逆時針部分只要再輸出時反過來輸出就可以了。

table[i][j] → table[j][i]

#include <stdio.h>

int table[100][100];

int main()
{
    int kase, n, m;
    scanf(" %d", &kase);
    while (kase--)
    {
        scanf(" %d %d", &n, &m);
        int now = 1, end = n * n, sr = 0, sc = -1, er = n - 1, ec = n - 1, i, j;
        while (now <= end)
        {
            for (j = ++sc; j <= ec; j++)
                table[sr][j] = now++;
            for (i = ++sr; i <= er; i++)
                table[i][ec] = now++;
            for (j = --ec; j >= sc; j--)
                table[er][j] = now++;
            for (i = --er; i >= sr; i--)
                table[i][sc] = now++;
        }
        if (m == 1)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    printf("%5d", table[i][j]);
                putchar('\n');
            }
        }
        else
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    printf("%5d", table[j][i]);
                putchar('\n');
            }
        }
    }
    return 0;
}

內容

一個數在電腦裡遞增時需要進位幾次。

輸入

輸入的每一行有一個十進制正整數 N (1<=N<=2147483647)。
輸入的最後一行有一個 0，代表輸入的結束，這個數字請勿做任何處理。

1
4
7
17
0

輸出

對於每個正整數 N ，請輸出以二進制計算 N+1 時所需的進位次數。

1
0
3
1

解題思路

迴圈判斷最低位元，當最低位元為 1 時 count++、並將輸入右移 1 位元，當最低位元為 0 時代表到這位元就不會進位了，跳出迴圈輸出答案。

#include<stdio.h>

int main()
{
    int n, count;
    while (scanf(" %d", &n) && n)
    {
        count = 0;
        while (n & 1)
            count++, n >>= 1;
        printf("%d\n", count);
    }
    return 0;
}

內容

話說同學們正在學習二元一次方程組。
　　二元一次方程組的練習題鋪天蓋地地湧向同學們，同學們正苦惱於一次次地四則運算、移項、合併同類項等等。
　　他們知道你很聰明，想請你幫他們編一個解二元一次方程組的程序。
　　我們假定二元一次方程組的一般格式如下：(a,b,c,d,e,f 為常數,x,y 為未知數)
　　　　 ax+by=c
　　　　 dx+ey=f
　　程序讀入 a,b,c,d,e,f 後，輸出解。
　　當然，方程組也有可能存在無解或有無窮解的情況：如果(x,y)沒有相對應的實數對滿足方程組則無解；相反，如果(x,y)有多組對應的實數對滿足方程組則有無數解。
　　如果無解，就輸出“No answer”；如果有無窮解，就輸出“Too many”。

輸入

輸入僅 1 行，包含 6 個整數，a,b,c,d,e,f。輸入數據保證正確。

1 1 2 1 -1 0

輸出

如果有解，那麼第 1 行先輸出“x=”，再輸出 x 的值，第 2 行先輸出“y=”，再輸出 y 的值，均保留 2 位小數，請參照樣例輸出。
　　如果無解或有無數解則按要求輸出“No answer”或“Too many”。

x=1.00
y=1.00

解題思路

把二元一次方程式轉成程式碼。

#include<stdio.h>

double a, b, c, d, e, f, x, y;

int main()
{
    scanf(" %lf %lf %lf %lf %lf %lf", &a, &b, &c, &d, &e, &f);
    if (a * e == d * b)
        puts(b * f == e * c ? "Too many" : "No answer");
    else
        printf("x=%.2lf\ny=%.2lf\n", (c * e - b * f) / (a * e - d * b), (d * c - a * f) / (b * d - a * e));
    return 0;
}

內容

我們常用數字密碼鎖來保護重要的東西，但要是不小心忘了密碼麻煩就大了！
以四位數字的密碼鎖為例，我們最多要嘗試 10^4=10000 次才能解鎖。這時候要是
有辦法知道目前嘗試的密碼錯了幾個字，那解鎖的速度就快多了。請寫一個程式，
可以判斷每組數字跟正確答案差了幾個字。

輸入

多筆輸入。
第一行有四個介於 0-9 之間的數字，代表正確的密碼
第二行有一個整數 n，1<=n<=10000，代表接下來嘗試 n 組密碼
接下來有 n 行，每行有四個介於 0-9 之間的數字，每行各代表一組嘗試的密碼。

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

1 1 1 5
4
1 1 1 1
0 9 2 8
1 5 2 3
1 1 5 1

輸出

輸出 n 行。
對於每組嘗試的密碼，若有 p 個數字的值正確，且在正確的位子上，
另外有 q 個數字的值正確，但不在正確的位子上，
輸出 pAqB。
範例見測資。

1A1B
2A2B
2A0B
0A4B
3A0B
0A0B
1A1B
2A2B

解題思路

開兩個陣列 ansCount 和 testCount 分別保留 ans 和 test 無法完全配對的數字。

再來用迴圈判斷，
判斷時會有三種情況

1. 完全配對 (A)

   A+1

2. 無法配對，且無法和之前無法配對的數字配對

   把他記錄進無法配對的陣列

3. 無法配對，但可以和之前無法配對的數字配對 (B)

   B+1 , 把和他配對的數字刪掉

最後輸出得到的 A 和 B 即可。

#include <stdio.h>

int n;
char ans[4], test[4];

int main()
{
    while (scanf(" %d %d %d %d %d", &ans[0], &ans[1], &ans[2], &ans[3], &n) == 5)
    {
        while (n--)
        {
            char ansCount[10] = { 0 }, testCount[10] = { 0 }, a = 0, b = 0;
            scanf(" %d %d %d %d", &test[0], &test[1], &test[2], &test[3]);
            for (int i = 0; i < 4; i++)
            {
                if (test[i] == ans[i])
                    a++;
                else
                {
                    if (ansCount[test[i]])
                        b++, ansCount[test[i]]--;
                    else
                        testCount[test[i]]++;
                    //
                    if (testCount[ans[i]])
                        b++, testCount[ans[i]]--;
                    else
                        ansCount[ans[i]]++;
                }
            }
            printf("%dA%dB\n", a, b);
        }
    }
    return 0;
}