演算法課程題解 - 複雜度

UVa 11577

題目

https://zerojudge.tw/ShowProblem?problemid=d267
對每個測試資料，輸出頻率最高的字母。

解法 by tim25871014

想法

1. 統計每個字母分別出現幾次。
2. 根據統計，計算出現最多次的字母是幾次，假設是
   $x$次。
3. 印出所有出現
   $x$次的字母。

這題因為輸入資料是以換行隔開，所以需要用getline函數一次輸入一行。

AC code

#include<iostream>
#include<string>
using namespace std;
string s;

int main() {
    int t;
    cin >> t;
    getline(cin, s);
    while(t--) {
        int cnt[26] = {}, maxx = 0;
        getline(cin, s);
        for(auto i: s) if(i <= 'Z' && i >= 'A') cnt[i - 'A']++;
        for(auto i: s) if(i <= 'z' && i >= 'a') cnt[i - 'a']++;
        for(int i=0;i<26;i++) maxx = max(maxx, cnt[i]);
        for(int i=0;i<26;i++) if(cnt[i] == maxx) cout << char(i + 'a');
        cout << endl;
    }
}

UVa 11764

題目

http://domen111.github.io/UVa-Easy-Viewer/?11764
a high jump 代表跳到一個較高的牆，同樣，a low jump跳到一個較矮的牆。你能找出 a high jump 和 a low jump 的總數嗎?

解法 by tim25871014

想法

語法題。

AC code

#include<iostream>
using namespace std;

int main() {
    int n, cases, a[51];
    cin >> cases;
    for(int t=1;t<=cases;t++) {
        cin >> n;
        int high = 0, low = 0;
        for(int i=0;i<n;i++) cin >> a[i];
        for(int i=1;i<n;i++) {
            if(a[i] > a[i-1]) high++;
            if(a[i] < a[i-1]) low++;
        }
        printf("Case %d: %d %d\n", t, high, low); 
    }
}

UVa 11661

題目

http://domen111.github.io/UVa-Easy-Viewer/?11661
在一個數線上有很多餐廳跟藥局，求距離最近的餐廳跟藥局有多遠。

解法 by tim25871014

想法

想像你開車從最左邊走到最右邊，頭腦不斷記住上一個看到的建築物是什麼(sign)、那個建築物在哪裡(pos)。

每次看到新的建築物，需要進行兩個動作：

1. 回顧：比對上一個與這一個是不是(藥局+餐廳)或是(餐廳+藥局)的組合，如果是的話就嘗試更新答案。
2. 紀錄：將這次看到的建築物類型與位置紀錄下來，以便下次回顧

AC code

#include<iostream>
#include<string>
using namespace std;
string s;

int main() {
    int n;
    while(cin >> n, n) {
        cin >> s;
        int ans = 2147483647, pos = -1;
        char sign = '#';
        for(int i=0;i<s.size();i++) {
            /// 回顧
            if((s[i] == 'R' && sign == 'D') || (s[i] == 'D' && sign == 'R')) {
                ans = min(ans, i - pos), pos = i;
            else if(s[i] == 'Z') ans = 0;
            /// 紀錄
            if(s[i] != '.') sign = s[i], pos = i;
        }
        cout << ans << endl;
    }
}

UVa 11743

題目

http://domen111.github.io/UVa-Easy-Viewer/?11743
實作一種一種校檢演算法來確認信用卡卡號。

解法 by tim25871014

想法

我不知道這題跟時間複雜度有啥關係。

令

$F(x)$是

$x$乘以二之後的各個位數和
那麼我們要算的就是(奇數位數字和)+(

$F(\mathrm{偶}\mathrm{數}\mathrm{位}\mathrm{數}\mathrm{字})$的和)，看看這個數字是否是10的倍數。

$F(x)$的值稍微手算就可以得到。

AC code

#include<iostream>
using namespace std;

int f[] = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int t, a;
    cin >> t;
    while(t--) {
        int sum = 0;
        for(int i=0;i<4;i++) {
            cin >> a;
            sum += (a%10) + f[(a/10)%10] + ((a/100)%10) + f[(a/1000)%10];
        }
        cout << ((sum % 10) ? "Invalid\n" : "Valid\n");
    }
}

UVa 11942

題目

http://domen111.github.io/UVa-Easy-Viewer/?11942

給

$N$個數列，每個數列各十個數字，對於每個數列請輸出此數列是否為遞增或遞減數列。

解法 by tim25871014

想法

實作一個函數，用來判斷數列是否遞增，也就是檢查每一項是都否比前一項大。

反之，檢查遞減關係就是檢查每一項是否都比前一項小。

AC code

#include<iostream>
using namespace std;

bool isincreasing(int a[]) {
    for(int i=1;i<10;i++) if(a[i] < a[i-1]) return false;
    return true;
}

bool isdecreasing(int a[]) {
    for(int i=1;i<10;i++) if(a[i] > a[i-1]) return false;
    return true;
}

int main() {
    int a[11], n;
    cin >> n;
    cout << "Lumberjacks:\n";
    while(n--) {
        for(int i=0;i<10;i++) cin >> a[i];
        cout << ((!isincreasing(a) && !isdecreasing(a)) ? "Unordered\n" : "Ordered\n");
    }
}

tags: SCIST 演算法 題解