b373: [福州19中]車廂重組

2019-08-14

內容

車廂重組 carry

【問題描述】

在一個舊式的火車站旁邊有一座橋，其橋面可以繞河中心的橋墩水平旋轉。一個車站的職工發現橋的長度最多能容納兩節車廂，如果將橋旋轉 180 度，則可以把相鄰兩節車廂的位置交換，用這種方法可以重新排列車廂的順序。於是他就負責用這座橋將進站的車廂按車廂號從小到大排列。他退休後，火車站決定將這一工作自動化，其中一項重要的工作是編一個程序，輸入初始的車廂順序，計算最少用多少步就能將車廂排序。

車廂編號從 1 開始。

輸入

輸入文件有兩行數據，第一行是車廂總數 N（不大於 10000），第二行是 N 個不同的數表示初始的車廂順序，每 2 個數之間用一個空格隔開。

4
4 3 2 1

輸出

一個數據，是最少的旋轉次數。

6

解題思路

因為橋一次只能換兩節車廂，所以其實就是在問 bubble sort(氣泡排序) 的交換次數，實作氣泡排序並在交換時紀錄次數即可。

這題也可以用 merge sort(合併排序) 來做，時間複雜度可以從 O(n²) 降到 O(nlogn)，但由於測資過弱所以沒有具體意義。

完整程式碼

AC (3ms, 124KB)

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

int index[10000];

int main()
{
    int n, max, count;
    while (scanf(" %d", &n) == 1)
    {
        max = n - 1, count = 0;
        for (int i = 0; i < n; i++)
            scanf(" %d", &index[i]);
        for (int i = 0; i < max; i++)
        {
            for (int j = 0; j < max - i; j++)
            {
                if (index[j] > index[j + 1])
                    SWAP(index[j], index[j + 1]), count++;
            }
        }
        printf("%d\n", count);
    }
    return 0;
}

b367: 翻轉世界

2019-08-14

內容

有位勇士排除萬難後,來到了最後一關—–[翻轉世界]

他發現所有物品都翻轉了 180 度

如果要繼續前進必須做出一項選擇,也就是找到翻轉後不會改變的東西!

例如:

110

000

011

若翻轉 180 度:

110

000

011

現在給你一張圖

請你幫忙這位勇士吧,因為除了必須判斷這個問題以外,還必須打倒翻轉世界的怪物才行

所以請你寫一個程式幫他

輸入

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

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

N 代表長,M 代表寬 (0<N,M<11)

而接下會有 N 行,每一行會有 M 個數字 r (0<=r<2³¹-1)

2
3 3
1 1 0
0 1 0
0 1 1
1 5
0 0 1 0 1

輸出

對於每個測資,判斷是否可以符合翻轉 180 度不會改變的圖形
是的話請輸出 go forward

否的話請輸出 keep defending

go forward
keep defending

解題思路

讀入陣列，之後分別從頭開始往後和從尾開始往前判斷是否相等，如果某次匹配不相等或是頭 ≥ 尾時斷開，之後輸出答案即可。

Ex: [0 : 20] , [1 : 19] , [2 : 18] … [9 : 11] , [10 : 10]

雖然輸入有二維陣列，但判斷邏輯和上面處理一維陣列的方式是一樣的，所以在輸入時把二微陣列壓縮成一維，方便之後判斷。

完整程式碼

AC (2ms, 104KB)

#include <stdio.h>

int main()
{
    int kase, n, m, s, e, list[150];
    scanf(" %d", &kase);
    while (kase--)
    {
        scanf(" %d %d", &n, &m);
        s = 0, e = n * m - 1;
        for (int i = 0; i <= e; i++)
            scanf(" %d", &list[i]);
        while (list[s] == list[e])
        {
            if (s > e)
                break;
            s++, e--;
        }
        puts(s < e ? "keep defending" : "go forward");
    }
    return 0;
}

b294: 經濟大恐荒

2019-08-14

內容

西元 2505 年 1 月 1 日，發生了世界經濟大恐荒。從那天起，物價飛漲。第一天一個饅頭只要一元，第二天就要二元，第三天要賣三元，以此類推。

給你從第一天起文文每天所買的饅頭數，請問他總共花了多少錢？

輸入

輸入第一行有一個整數 n，代表文文從第一天起，連續買了 n 天的饅頭。

第二行會有 n 個整數，依序為第一天到第 n 天文文所買的饅頭數量。

5
1 2 3 4 5

輸出

輸出文文買饅頭所花的金額。

55

解題思路

簡單的迴圈四則。

完整程式碼

######

#include <stdio.h>

int main()
{
    int n , num , sum;
    while (scanf(" %d", &n) == 1)
    {
        sum = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf(" %d", &num);
            sum += num * i;
        }
        printf("%d\n", sum);
    }
    return 0;
}

b265: Q11286 - Conformity

2019-08-14

內容

Waterloo 大學的新鮮人由於興趣不同，對於課程的選擇不盡相同，而校方希望他們所選的課程儘量一致，所以設立了一個獎項，頒發給選擇的「課程組合」為「最受歡迎的課程組合」的學生。

輸入

輸入有多組測試資料，每組資料的開頭有一個整數 n 表示新生的人數( 1 <= n <= 10000 )，接下來有 n 列分別為這些新生所選擇的課程代號，每列有 5 個表示課程代號的整數，其值介於 100 ~ 499。當 n = 0 表示測試資料結束。

3
100 101 102 103 488
100 200 300 101 102
103 102 101 488 100
3
200 202 204 206 208
123 234 345 456 321
100 200 300 400 444
0

輸出

一組課程的受歡迎程度視所有剛好選擇該組課程的學生人數而定，如果沒有其他「課程組合」的人數比此「課程組合」的人數高，則該課程為最受歡迎的「課程組合」，請對每組測試資料輸出選擇最受歡迎的「課程組合」的人數。

2
3

解題思路

解題方向 :

由於”選課順序”不影響”課程組合”，所以先將輸入的選課排序好避免因不同的”選課順序”被視為不同的”課程組合”。
將排序好的課程組合打成一個雜湊值(Hash)。
查看雜湊表的 Hash，如果已經有 Hash 存過得到的雜湊值，則該 Hash 的 Count+1，反之則新增一個 Key 為得到的雜湊值的 Hash，並將該 Hash 新增至雜湊表。 (這段的 Hash 指的是 struct Hash)
輸入完全部課程組合後，再完整的遍歷一次雜湊表即可取得 “最受歡迎的課程組合”的總修課人數。

一些注意事項 :

雜湊表大小設為 2 的次方數，這樣可以在存雜湊值進去時用 & 取代 % 來加速。
因為有多組輸入，所以每次計算完都要清空一次雜湊表。
“最受歡迎的課程組合”可以是複數堂，也就是說，當”最受歡迎的課程組合”人數為 3，且有 3 堂修課人數為 3 的課程組合時，答案應該是 3(堂) * 3(人) = 9 人。
雜湊運算並不是安全的判斷方式，因為可能會產生雜湊碰撞(兩不同的資料得到一樣的雜湊資)，但由於發生機率過低，所以這裡無視這個問題。

完整程式碼

AC (62ms, 344KB)

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

typedef struct Hash
{
    unsigned int Key;
    int Count;
    struct Hash* Next;
}Hash;

Hash HashTable[1024];
unsigned int list[5];
int n;

int cmp(const unsigned int* lhs, const unsigned int* rhs)
{
    return *lhs - *rhs;
}

inline unsigned int toHash(unsigned int src[])
{
    return (src[0] << 28) + (src[1] << 21) + (src[2] << 14) + (src[3] << 7) + src[4];
}

inline void AddHash(unsigned int hash)
{
    Hash* now = &HashTable[hash & 1023];
    while (now->Key != hash)
    {
        if (now->Next == NULL)
        {
            now = now->Next = malloc(sizeof(Hash));
            now->Key = hash;
            now->Next = NULL;
            now->Count = 1;
            return;
        }
        now = now->Next;
    }
    now->Count++;
}

int PopularityCount()
{
    int max = 0, count = 0;
    Hash* now, * tmp;
    for (int i = 0; i < 1024; i++)
    {
        if (HashTable[i].Next != NULL)
        {
            now = HashTable[i].Next;
            do
            {
                if (max <= now->Count)
                {
                    if (max == now->Count)
                        count += max;
                    else
                        count = max = now->Count;
                }
                tmp = now;
                now = now->Next;
                free(tmp);
            } while (now != NULL);
            HashTable[i].Next = NULL;
        }
    }
    return count;
}

int main()
{
    while (scanf(" %d", &n) == 1 && n)
    {
        for (int i = 0; i < n; i++)
        {
            scanf(" %u %u %u %u %u", &list[0], &list[1], &list[2], &list[3], &list[4]);
            qsort(list, 5, sizeof(unsigned int), cmp);
            AddHash(toHash(list));
        }
        printf("%d\n", PopularityCount());
    }
    return 0;
}

a982: 迷宮問題#1

2019-08-14

內容

給你一個 NXN 格的迷宮, 迷宮中以#代表障礙物, 以.代表路, 你固定在(2,2)出發, 目的地是(n-1,n-1), 求包括起點和終點, 最少路徑的長度。

輸入

N(N 不超過 100)

N 行 N 列由#和.組成的迷宮

9
##########
#.......##
#.#####.##
#.......##
##.#.#####
#..#.#..##
#.##.##.##
#.......##
#########

輸出

一個正整數, 代表最短路徑的長度, 如果不可能到達終點, 則印出 No solution!

13

解題思路

基礎 BFS 題目，因為測資不大所以直接在矩陣上模擬 Dijkstra 演算法

具體流程如下 :

先把地圖導入二維陣列，障礙物設成-1，空地設為任一最大步驟數(邊長 * 邊長)不會達到的極大值。
將起點位置設為 1
遍歷整個陣列，如果遇到 1 就將它周圍大於 1 的數字改為 2
繼續遍歷，遇到 2 就將它周圍大於 2 的數字改為 3
之後同理，不斷遍歷陣列直到終點不為極大值即是答案。

由於題目有可能會有無法抵達終點的情況，所以如果遍歷完一輪但陣列沒有發生改變就代表已經沒有路了，跳出迴圈並輸出”No solution!”。

完整程式碼

AC (4ms, 112KB)

#include <stdio.h>
#define MAX 2147483647

int table[100][100];

int main()
{
    int n, end, now;
    char tmp, moving;
    while (scanf(" %d", &n) == 1)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                scanf(" %c", &tmp);
                table[i][j] = tmp == '#' ? -1 : MAX;
            }
        }
        end = n - 2, now = 0, moving = table[1][1] = 1;
        while (table[end][end] == MAX && moving)
        {
            moving = 0, now++;
            for (int i = 1; i <= end; i++)
            {
                for (int j = 1; j <= end; j++)
                {
                    if (table[i][j] == now)
                    {
                        if (table[i][j + 1] > now) table[i][j + 1] = now + 1;
                        if (table[i][j - 1] > now) table[i][j - 1] = now + 1;
                        if (table[i + 1][j] > now) table[i + 1][j] = now + 1;
                        if (table[i - 1][j] > now) table[i - 1][j] = now + 1;
                        moving = 1;
                    }
                }
            }
        }
        if (moving)
            printf("%d\n", table[end][end]);
        else
            puts("No solution!");

    }
    return 0;
}

a981: 求和問題

2019-08-14

內容

給你 N 個正整數, 試求哪幾個之和剛好為 M, 印出所有合條件的解, 如有多組解, 請按由小到大的順序印出(格式可參考樣例輸出)

輸入

n m (1<=n<=30, 1<=m<=100000000)

n 個正整數, 全部以空格分開

10 100
10 20 40 30 50 80 60 70 5 15

輸出

其和剛好等於 m 的數, 如果有多組解則按由小到大全部印出, 如果無解則印出-1

5 10 15 20 50
5 10 15 30 40
5 10 15 70
5 15 20 60
5 15 30 50
5 15 80
10 20 30 40
10 20 70
10 30 60
10 40 50
20 30 50
20 80
30 70
40 60

解題思路

由於要由小至大輸出，所以先把數字按順序排好，接下來窮舉全部的可能，如果窮舉過程中被窮舉到的值相加等於目標值則印出答案。

因為窮舉到的值相加超過目標值之後不可能再出現”窮舉到的值總和 = 目標值”的情況，所以可以把它剪枝掉。

又因為窮舉的陣列已經被排序過了，下一個窮舉值必 ≥ 當前窮舉值，所以當窮舉到的值總和 + 當前的窮舉值 > 目標值時，接下來也都不可能再出現”窮舉到的值總和 = 目標值”，所以當發生這種情況時也可以進行剪枝。

完整程式碼

AC (0.2s, 96KB)

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

int n, m, next, list[50], output[50];
char noAns;

int cmp(const int* lhs, const int* rhs)
{
    return *lhs - *rhs;
}

void dfs(int sum, int start, int depth)
{
    for (int i = start; i < n; i++)
    {
        next = sum + list[i];
        if (next >= m)
        {
            if (next == m)
            {
                for (int j = 0; j < depth; j++)
                    printf("%d ", output[j]);
                printf("%d\n", list[i]);
                noAns = 0;
            }
            if (list[i] < list[i + 1])
                return;
        }
        output[depth] = list[i];
        if (next + list[i] <= m)
            dfs(next, i + 1, depth + 1);
    }
}

int main()
{
    while (scanf(" %d %d", &n, &m) == 2)
    {
        noAns = 1;
        for (int i = 0; i < n; i++)
            scanf(" %d", &list[i]);
        qsort(list, n, sizeof(int), cmp);
        dfs(0, 0, 0);
        if (noAns)
            puts("-1");
    }
    return 0;
}

a915: 二維點排序

2019-08-14

內容

給你 n 個二維平面上的點，要求你把他們按照以 x 軸坐標為第一關鍵字，y 軸坐標為第二關鍵字的方式從小到大來進行排序。

輸入

第一行輸入一個正整數 n。
接下來 n 行，第 i 行有兩個個以空格隔開的正整數 x[i]和 y[i]，表示第 i 個點為(x[i],y[i])。

4
2 4
1 2
3 4
2 3

輸出

輸出 n 行，第 i 行表示排序好後第 i 個點的坐標。

1 2
2 3
2 4
3 4

解題思路

簡單的條件判斷和排序。

完整程式碼

AC (2ms, 112KB)

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000

typedef struct node
{
    int x, y;
}Point;

Point list[MAX], * sort[MAX];

int cmp(const Point** lhs, const Point** rhs)
{
    return (*lhs)->x == (*rhs)->x ? (*lhs)->y - (*rhs)->y : (*lhs)->x - (*rhs)->x;
}

int main()
{
    for (int i = 0; i < MAX; i++)
        sort[i] = &list[i];
    int n;
    while (scanf(" %d", &n) == 1)
    {
        for (int i = 0; i < n; i++)
            scanf(" %d %d", &list[i].x, &list[i].y);
        qsort(sort, n, sizeof(Point*), cmp);
        for (int i = 0; i < n; i++)
            printf("%d %d\n", sort[i]->x, sort[i]->y);
    }
    return 0;
}

a799: 正值國

2019-08-14

內容

很久很久以前，有一個國家叫做「正值國」，這個國家的人做什麼事都非常正直，做人坦蕩蕩。也因此，國家平安和樂、生活富足。

但是，這個國家有一個不成文的習俗，就是他們不喜歡負數，他們把負數視為邪惡的象徵，所以他們非常討厭看到負數。他們只要看到負數，就會直接把負號去掉，例如”-1”會變成”1”。

筱華是剛從其他國家搬來正值國的一位中學生，他每次只要在數學考捲上寫到負數，就會被其他同學和老師狠狠的痛打一頓，你可以幫幫他嗎？

輸入

輸入只有一行，包含一個整數 N。

對於配分 40%的測試資料，保證 N>=0。

對於配分 100%的測試資料，保證-2147483647<N<2147483647。

-5

輸出

請輸出一個整數，代表正值國喜歡的數字

5

解題思路

簡單的條件判斷。

完整程式碼

AC (2ms, 104KB)

#include <stdio.h>

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

a746: 畫蛇添足

2019-08-14

內容

楚有祠者，賜其舍人巵酒。舍人相謂曰：“數人飲之不足，一人飲之有餘，請畫地為蛇，先成者飲酒。”一人蛇先成，引酒且飲之，乃左手持巵，右手畫蛇曰：“吾能為之足。”未成，一人之蛇成，奪其巵曰：“蛇固無足，子安能為之足？”遂飲其酒。為蛇足者，終亡其酒。

話說那位先畫出了蛇卻沒喝到酒的人，想一雪前恥！所以他找到了天才的你，請你幫他編個程式打敗其他人。

他給你一塊用圍欄圍起的，邊長為 n 的正方形地（已經分為 n*n 個邊長為 1 的小正方形），如下圖所示：

地上按順序已經畫了 m 個點（在地（x,y）上），請你編個程式，將這些點依次連起來。

不過，這回他會不會再畫蛇添足，就由不得我們了= =|||。

輸入

多組測資，以 EOF 結束。

每組測資第一行，有兩個數字，即為題目所述之 n，m（1≤n,m≤500）。

接下來 m 行，每行兩個數字，表示第 1…m 個點在地（x,y）上。保證前一個點和後一個點所確定的線段一定平行於圍欄的一邊。

4 5
1 1
1 4
4 4
4 1
1 1
4 5
1 1
1 4
4 4
4 1
1 1

輸出

對於每組測資輸出一次。

用“-”和“|”圈出這塊地（當然是畫過畫之後的），這塊地分為 n*n 個邊長為 1 的小正方形，其中沒有被畫點或線的用“ ”表示，其餘用“*”表示。

如輸入範例在連接後，紅色的為被畫點和線的地，黑色的為沒有被畫點和線的地。

輸出範例如下。

------
|****|
|*  *|
|*  *|
|****|
------

------
|****|
|*  *|
|*  *|
|****|
------
------
|****|
|*  *|
|*  *|
|****|
------

解題思路

簡單的迴圈和條件判斷。

完整程式碼

AC (3ms, 336KB)

#include <stdio.h>

char table[510][510];

inline void setGate(int n)
{
    for (int i = n; i; i--)
    {
        for (int j = n; j; j--)
            table[i][j] = ' ';
        table[i][0] = table[i][n + 1] = '|', table[i][n + 2] = '\0';
    }
    for (int i = n + 1; i >= 0; i--)
        table[0][i] = table[n + 1][i] = '-';
    table[0][n + 2] = table[n + 1][n + 2] = '\0';
}

int main()
{
    int n, m, sX, sY, eX, eY;
    while (scanf("%d %d", &n, &m) == 2)
    {
        setGate(n);
        scanf(" %d %d", &sX, &sY);
        table[sX][sY] = '*';
        while (--m)
        {
            scanf(" %d %d", &eX, &eY);
            if (sX == eX)
            {
                if (sY < eY)
                    while (++sY < eY) table[sX][sY] = '*';
                else
                    while (--sY > eY) table[sX][sY] = '*';
            }
            else
            {
                if (sX < eX)
                    while (++sX < eX) table[sX][sY] = '*';
                else
                    while (--sX > eX) table[sX][sY] = '*';
            }
            table[sX][sY] = '*';
        }
        for (int i = 0; i <= n + 1; i++)
            puts(table[i]);
    }
    return 0;
}

a740: 質因數之和

2019-08-13

內容

求一個數全部質因數之和

比如，

6 = 2 x 3，則輸出 2 + 3 = 5

8 = 2 x 2 x 2，則輸出 2 + 2 + 2 = 6

輸入

每行一個正整數，x<2000000000, 以 EOF 為結束

19
32

輸出

對應的因數和

19
10

解題思路

用判斷質數裡的方法判斷質數，如果輸入是質數，直接輸出輸入值當答案，如果不是則從質數表第 0 項試除輸入值到最後一項或輸入值等於 1 為止 (但由於輸入值不是質數所以一定會在質數表結束前變成 1，故不用做值數表結束的判斷)

完整程式碼

AC (2ms, 196KB)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 47000

int primeList[5000], pLen;

int cmp(const int* lhs, const int* rhs)
{
    return *lhs - *rhs;
}

void SetPrimeList()
{
    char isNot[MAX] = { 0 };
    primeList[pLen++] = 2;
    for (int i = 3; i < MAX; i += 2)
    {
        if (isNot[i])continue;
        primeList[pLen++] = i;
        for (int j = i << 1; j < MAX; j += i)
            isNot[j] = 1;
    }
}

char isPrime(int n)
{
    if (n < MAX)
    {
        int* item = (int*)bsearch(&n, primeList, pLen, sizeof(int), cmp);
        return (item != NULL);
    }
    else
    {
        for (int i = 0, max = sqrt(n); primeList[i] <= max; i++)
        {
            if (!(n % primeList[i]))
                return 0;
        }
        return 1;
    }
}

int main()
{
    SetPrimeList();
    int n, ans;
    while (scanf(" %d", &n) == 1)
    {
        if (isPrime(n))
            printf("%d\n", n);
        else
        {
            ans = 0;
            for (int i = 0; n > 1; i++)
            {
                while (!(n % primeList[i]))
                {
                    n /= primeList[i];
                    ans += primeList[i];
                }
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}