# 演算法課程題解 - 複雜度

# 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(偶數位數字)$的和)，看看這個數字是否是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 演算法 題解`