APCS實作

Default code v1

#include <iostream>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define out cout << '\n';
#define int long long
#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")
signed main(){
    IOS
    
    return 0;
}

My default code

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int main(){
    IOS

    return 0;
}

About pragma

#pragma GCC optimize("O0")//不優化(預設)
#pragma GCC optimize("O1")//優化一些
#pragma GCC optimize("O2")//優化更多
#pragma GCC optimize("O3")//O2優化再加上inline函式優化
#pragma GCC optimize("Os")//針對程式大小進行優化(程式最小)
#pragma GCC optimize("Ofast")//O3加上一些快速但不安全的數學運算

More about pragma

#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")

1. Ofast優化，加上迴圈展開、忽略堆疊溢出攻擊。
2. 針對CPU的指令集擴充，只有一些intel支援，有些AMD也有。
3. 加開堆疊，可以讓遞迴函式跑多一點。

111/01

第一題：程式交易

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define out cout<<'\n';
#pragma GCC optimize("Ofast")
using namespace std;
int main(){
    IOS
    long long n, d, arr[105];
    cin >> n >> d;
    for(int i = 0;i < n;i++) cin >> arr[i];
    int cost = arr[0], profit = 0, pre = 0;
    bool judge = true;
    for(int i = 1;i < n;i++){
        if(judge){
            if(arr[i] - cost >= d){
                judge = false;
                profit = profit + abs(arr[i] - cost);
                cost = arr[i];
            }
        }
        else{
            if(cost - d >= arr[i]){
                cost = arr[i];
                judge = true;
            }
        }
    }
    cout << profit;

    return 0;
}

第二題：贏家預測

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
int main(){
    IOS
    // freopen("sample1.in", "r", stdin);
    int n, m, m_cnt[1005];
    ll s[1005], t[1005];
    vector<int> idx, win, lose;
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> s[i];
    for(int i = 1;i <= n;i++) cin >> t[i];
    for(int i = 0;i < n;i++){
        int tmp;
        cin >> tmp;
        idx.push_back(tmp);
    }
    for(int i = 1;i <= n;i++) m_cnt[i] = m;
    while(idx.size() > 1){
        for(int i = 0;i + 1 < (int)idx.size();i += 2){
            int a = idx[i], b = idx[i + 1];
            if(s[a] * t[a] < s[b] * t[b]) swap(a, b);

            ll new_sa = s[a] + (s[b] * t[b]) / (2 * t[a]), new_ta = t[a] + (s[b] * t[b]) / (2 * s[a]);
            s[a] = new_sa; t[a] = new_ta;
            s[b] += s[b] / 2; t[b] += t[b] / 2;

            m_cnt[b]--;
            win.push_back(a);
            if(m_cnt[b] > 0){
                lose.push_back(b);
            }
        }
        if((int)idx.size() % 2 == 1) win.push_back(idx.back());
        idx = win;
        for(int i : lose) idx.push_back(i);
        win.clear();
        lose.clear();
    }
    cout << idx[0] << '\n';

    return 0;
}

第四題：牆上海報

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
vector<ll> board(200005), post(5005);
int n, k;
int main(){
    IOS
    cin >> n >> k;
    for(int i = 1;i <= n;i++) cin >> board[i];
    for(int i = 1;i <= k;i++) cin >> post[i];
    int l = 1, r = 1000000001;
    while(l < r - 1){
        int mid = (l + r) >> 1;
        int cnt = 0, cur = 1;
        bool judge = false;
        for(int i = 1;i <= n;i++){
            if(board[i] >= mid){
                cnt++;
                if(cnt == post[cur]){
                    cnt = 0;
                    if(cur == k){
                        judge = true;
                        break;
                    }
                    cur++;
                }
            }
            else cnt = 0;
        }
        if(judge) l = mid;
        else r = mid;
    }
    cout << l << '\n';

    return 0;
}

110/9

第三題：幸運數字

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
ll n, pre[300005] = {0}, arr[300005];
bool cmp(int a, int b){
    return arr[a] > arr[b];
}
vector<ll> vec;
int main(){
    IOS
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> arr[i];
        vec.push_back(i);
        pre[i] = pre[i - 1] + arr[i];
    }
    sort(vec.begin(), vec.end(), cmp);
    int l = 1, r = n;
    while(l != r){
        while(vec.back() < l || vec.back() > r) vec.pop_back();
        int m = vec.back();
        vec.pop_back();
        ll t1 = pre[m - 1] - pre[l - 1], t2 = pre[r] - pre[m];
        if(t1 > t2) r = m - 1;
        else l = m + 1;
    }
    cout << arr[l] << '\n';

    return 0;
}

109/10

第一題：人力分配

#include <iostream>
using namespace std;
int main(){
    int a,b,c,d,e,f,n;
    cin >> a >> b >> c;//y = ax^2 + bx + c
    cin >> d >> e >> f;//y = dx^2 + ex + f
    cin >> n;
    long long int max_num = -2147483647,y1,y2;
    for(int i = 0;i <= n;i++){
        y1 = a*i*i + b*i + c;
        y2 = d*(n-i)*(n-i) + e*(n-i) + f;
        max_num = (y1+y2) > max_num ? (y1+y2) : max_num;
    }
    cout << max_num;
    
    return 0;
}

第二題：人口遷移

#include <iostream>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int r,c,k,m,max_ = -1,min_ = 2147483647;
    cin >> r >> c >> k >> m;
    int arr[r+3][c+3],temp[r+3][c+3];
    for(int i = 1;i <= r;i++){
        for(int j = 1;j <= c;j++){
            cin >> arr[i][j];
            temp[i][j] = arr[i][j];
        }
    }
    while(m > 0){
        for(int i = 1;i <= r;i++){
            for(int j = 1;j <= c;j++){
                int tmp = arr[i][j]/k;
                if(arr[i][j] == -1) continue;
                if(i != 1 && arr[i-1][j] != -1){
                    temp[i-1][j] += tmp;
                    temp[i][j] -= tmp;
                }
                if(i != r && arr[i+1][j] != -1){
                    temp[i+1][j] += tmp;
                    temp[i][j] -= tmp;
                }
                if(j != 1 && arr[i][j-1] != -1){
                    temp[i][j-1] += tmp;
                    temp[i][j] -= tmp;
                }
                if(j != c && arr[i][j+1] != -1){
                    temp[i][j+1] += tmp;
                    temp[i][j] -= tmp;
                }
            }
        }
        for(int i = 1;i <= r;i++){
            for(int j = 1;j <= c;j++){
                arr[i][j] = temp[i][j];
            }
        }
        m--;
    }
    for(int i = 1;i <= r;i++){
        for(int j = 1;j <= c;j++){
            if(arr[i][j] == -1) continue;
            if(arr[i][j] >= max_) max_ = arr[i][j];
            if(arr[i][j] <= min_) min_ = arr[i][j];
        }
    }
    cout << min_ << '\n' << max_;

    return 0;
}

108/7

第一題：購物車

#include <iostream>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int main(){
    IOS
    int a, b, n;
    cin >> a >> b >> n;
    int ans = 0;
    while(n--){
        int a_judge = 0, b_judge = 0;
        int arr[100], tmp, q = 0;
        while(true){
            cin >> tmp;
            if(tmp == 0) break;
            if(tmp == a) a_judge++;
            else if(tmp == b) b_judge++;
            else if(tmp == a*(-1)) a_judge--;
            else if(tmp == b*(-1)) b_judge--;
            else continue;
        }
        if(a_judge > 0 && b_judge > 0) ans++;
    }
    cout << ans;

    return 0;
}

第二題：骰子

#include <iostream>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
struct dice{
    int up = 1;
    int down = 6;
    int left = 5;
    int right = 2;
    int forw = 4;
    int bacw = 3;
};
int main(){
    IOS
//    dice arr[10];
//    arr[1].bacw = 100;
//    arr[1].down = 49;
//    cout << arr[0].bacw << " " << arr[0].down << '\n';
//    arr[0] = arr[1];
//    cout << arr[0].bacw << " " << arr[0].down;
    int n, m, tmp;
    dice arr[50];
    cin >> n >> m;
    while(m--){
        int a, b;
        cin >> a >> b;
        a--;
        if(b == -1){
            int ba = arr[a].bacw;
            int fo = arr[a].forw;
            int u = arr[a].up;
            int d = arr[a].down;
            arr[a].bacw = d;
            arr[a].forw = u;
            arr[a].up = ba;
            arr[a].down = fo;
        }
        else if(b == -2){
            int r = arr[a].right;
            int l = arr[a].left;
            int u = arr[a].up;
            int d = arr[a].down;
            arr[a].right = u;
            arr[a].left = d;
            arr[a].up = l;
            arr[a].down = r;
        }
        else{
            b--;
            arr[40] = arr[a];
            arr[a] = arr[b];
            arr[b] = arr[40];
        }
    }
    for(int i = 0;i < n;i++) cout << arr[i].up << " ";

    return 0;
}

108/6

第一題：籃球比賽

#include<iostream>
using namespace std;
struct bask{
    int first,second;
};
int main(){
    bask a[5],b[5],sum1,sum2;
    sum1.first = 0;
    sum1.second = 0;
    sum2.first = 0;
    sum2.second = 0;
    for(int i = 0;i < 4;i++){
        cin >> a[i].first;
        sum1.first += a[i].first;
    }
    for(int i = 0;i < 4;i++){
        cin >> b[i].first;
        sum2.first += b[i].first;
    }
    int one = 0,two = 0;
    if(sum1.first > sum2.first) one++;
    else if(sum1.first < sum2.first) two++;
    for(int i = 0;i < 4;i++){
        cin >> a[i].second;
        sum1.second += a[i].second;
    }
    for(int i = 0;i < 4;i++){
        cin >> b[i].second;
        sum2.second += b[i].second;
    }
    if(sum1.second > sum2.second) one++;
    else if(sum1.second < sum2.second) two++;
    cout << sum1.first << ":" << sum2.first << endl;
    cout << sum1.second << ":" << sum2.second << endl;
    if(one > two) cout << "Win";
    else if(one < two) cout << "Lose";
    else if(one == two) cout << "Tie";
    
    return 0;
}

108/2

第一題：合成函數

#include <iostream>
#include <sstream>
using namespace std;
int cacu(){
    string str;
    cin >> str;
    if(str == "f"){
        int x = cacu();
        return (2 * x) - 3;
    }
    else if(str == "g"){
        int a = cacu();
        int b = cacu();
        return (2 * a) + b - 7;
    }
    else if(str == "h"){
        int q = cacu();
        int w = cacu();
        int e = cacu();
        return (3 * q) - (2 * w) + e;
    }
    else{
        stringstream ss;
        int num = 0;
        ss << str;
        ss >> num;
        return num;
    }
}
int main(){
    int a = cacu();
    cout << a ;
    
    return 0;
}

107/10

第二題：子集合的和

#include <iostream>
#include <algorithm>
#include <climits>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
int n, p, arr[30], close = 2e10, ans = 0, cnt = 0;
void rec(int i, int num){
    if(i >= n){
        if(p - num > 0 && (p-num) < close){
            close = p-num;
            ans = num;
            cnt++;
        }
        return;
    }
    rec(i + 1, num + arr[i]);
    rec(i + 1, num);
    return;
}
signed main(){
    IOS
    cin >> n >> p;
    for(int i = 0;i < n;i++) cin >> arr[i];
    rec(0, 0);
    cout << ans;

    return 0;
}

第三題：二維黑白影像編碼

#include <iostream>
#include <algorithm>
#include <cstring>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define out cout<<'\n';
#define int long long
#pragma GCC optimize("Ofast")
using namespace std;
string str;
int num, idx = -1;
int matrix(int n){
    idx++;
    if(str[idx] == '0') return 0;
    else if(str[idx] == '1') return n * n;
    else if(str[idx] == '2'){
        int cnt = 0;
        for(int i = 0;i < 4;i++){
            cnt += matrix(n/2);
        }
        return cnt;
    }
}
signed main(){
    cin >> str;
    cin >> num;
    int output = matrix(num);
    cout << output;

	return 0;
}

107/02

第三題：支點切割

#include <bits/stdc++.h>
using namespace std;
int arr[50001];
long long prefix[50005], suffix[50005];
int reg(int k, int l, int r){
    if(k < 1) return 0;
    if(r - l <= 1) return 0;
    
    prefix[l] = 0;
    long long delta1 = 0;
    for(int i = l + 1;i <= r;i++){
        delta1 += arr[i - 1];
        prefix[i] = prefix[i - 1] + delta1;
    }
    // for(int i = 0;i <= 7;i++) cout << prefix[i] << ' ';
    // cout << endl;
    suffix[r] = 0;
    long long delta2 = 0;
    for(int i = r - 1;i >= l;i--){
        delta2 += arr[i + 1];
        suffix[i] = suffix[i + 1] + delta2;
    }
    // for(int i = 0;i <= 7;i++) cout << suffix[i] << ' ';
    // cout << endl;
    long long min_j = 2e18;
    int idx = 0;
    for(int i = l + 1;i < r;i++){
        long long cost = abs(prefix[i] - suffix[i]);
        if(cost < min_j){
            min_j = cost;
            idx = i;
        }
    }
    // cout << idx << '\n';
    k--;
    return arr[idx] + reg(k, l, idx-1) + reg(k, idx+1, r);
}
int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 1;i <= n;i++) cin >> arr[i];
    cout << reg(k, 1, n);

    return 0;
}

106/10

第一題：邏輯運算子

#include<iostream>
using namespace std;
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if(a > 0) a = 1;
    else a = 0;
    if(b > 0) b = 1;
    else b = 0;
    bool judge = true;
    if((a == b && a == 1 && c == 1) || (a != b && c == 0) || (a == b && a == 0 && c == 0)){
     cout << "AND" << endl;
     judge = false;
    }
    if(((a == 1 || b == 1) && c == 1) || (a == 0 && b == 0 && c == 0)){
     cout << "OR" << endl;
     judge = false;
    }
    if((a == b && c == 0) || (a != b && c == 1)){
     cout << "XOR" << endl;
     judge = false;
    }
    if(judge) cout << "IMPOSSIBLE";

    return 0;
}

第二題:交錯字串

#include <iostream>
#include <cctype>
using namespace std;
int main(){
    int k;
    string str;
    cin >> k >> str;
    int count_max = 0;
    for(int j = 0;j < str.size();j++){
        bool judge = true;
        bool out = false;
        if(isupper(str[j])) judge = false;
        else judge = true;
        int counts = 0,index = 0,before = 0;
        for(int i = j;i < str.size();i++){
            if(judge){
                if(islower(str[i])) index++;
                else out = true;
            }
            else{
                if(isupper(str[i])) index++;
                else out = true;
            }
            if(index == k && out == false){
                counts += k;
                judge = !judge;
                index = 0;
            }
            if(out){
                count_max = counts > count_max ? counts : count_max;
                break;
            }
        }
    }
    if(str.size() == 1 && k == 1) count_max = 1;
    cout << count_max;
    return 0;
}

第三題：樹的高度與根

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
long long parent[100005] = {0}, h[100005] = {0}, total = 0, child[100005];
int root;
queue<int> Q;
int main(){
    IOS
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> child[i];
        if(child[i] == 0) Q.emplace(i);
        for(int j = 0;j < child[i];j++){
            int foo;
            cin >> foo;
            parent[foo] = i;
        }
    }
    while(true){
        int data = Q.front();
        Q.pop();
        total += h[data];
        if(parent[data] == 0){
            root = data;
            break;
        }
        h[parent[data]] = max(h[parent[data]], h[data]+1);
        child[parent[data]]--;
        if(child[parent[data]] == 0) Q.emplace(parent[data]);
    }
    cout << root << ' ' << total;

    return 0;
}

106/3

第一題：秘密差

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int suma = 0,sumb = 0;
    string num;
    cin >> num;
    vector<int> a,b;
    for(int i = 0;i < num.length();i++){
        if(i%2 == 0) a.push_back(num[i]-48);
        else b.push_back(num[i]-48);
    }
    for(int i = 0;i < a.size();i++){
        suma += a[i];
    }
    for(int i = 0;i < b.size();i++){
        sumb += b[i];
    }
    cout << abs(suma-sumb);

    return 0;
}

第二題：小群體

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n;
    cin >> n;
    int id[50001];
    for(int i = 0;i < n;i++)
        cin >> id[i];
    int num = 0;
    bool boolean[50001];
    fill(boolean,boolean+50001,1);
    for(int i = 0;i < n;i++){
        if(boolean[i]){
            if(i == id[id[i]]){
                num++;
                boolean[i] = false;
                boolean[id[i]] = false;
            }
            else if(id[i] != id[id[i]]){
                int temp = i,j = id[i];
                boolean[i] = false;
                while(id[j] != temp){
                    boolean[j] = false;
                    j = id[j];
                }
                boolean[j] = false;
                num++;
            }
        }
    }
    cout << num << endl;
    
    return 0;
}

第三題：數字龍捲風

#include <iostream>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define out cout << '\n';
#pragma GCC optimize("Ofast")
using namespace std;
int n, dir, arr[55][55];
void left(int *i,int *j){
    *j = *j-1;
    cout << arr[*i][*j];
}
void up(int * i,int * j){
    *i = *i - 1;
    cout << arr[*i][*j];
}
void right(int *i,int *j){
    *j = *j+1;
    cout << arr[*i][*j];

}
void down(int *i,int *j){
    *i = *i+1;
    cout << arr[*i][*j];
}
int main(){
    IOS
    cin >> n;
    cin >> dir; // 0-left // 1-up // 2-right // 3-down
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            cin >> arr[i][j];
        }
    }
    int cnt = 0, step = 0, idx = 0, a = n/2, b = n/2;
    int n1, n2, n3, n4;
    switch(dir){
    case 0:
        n1 = 1; n2 = 2; n3 = 3; n4 = 0;
        break;
    case 1:
        n1 = 0; n2 = 1; n3 = 2; n4 = 3;
        break;
    case 2:
        n1 = 3; n2 = 0; n3 = 1; n4 = 2;
        break;
    case 3:
        n1 = 2; n2 = 3; n3 = 0; n4 = 1;
        break;
    }
    cout << arr[a][b];
    for(int i = 0;i < (n * n)-1;){
        if(step % 2 == 0) cnt++;
        if(idx == n1){
            for(int j = 0;j < cnt;j++){
                if(i >= (n * n)-1) break;
                up(&a, &b);
                i++;
            }
        }
        if(idx == n2){
            for(int j = 0;j < cnt;j++){
                if(i >= (n * n)-1) break;
                right(&a, &b);
                i++;
            }
        }
        if(idx == n3){
            for(int j = 0;j < cnt;j++){
                if(i >= (n * n)-1) break;
                down(&a, &b);
                i++;
            }
        }
        if(idx == n4){
            for(int j = 0;j < cnt;j++){
                if(i >= (n * n)-1) break;
                left(&a, &b);
                i++;
            }
        }
        step++;
        if(idx == 3) idx = -1;
        idx++;
    }
    out
    return 0;
}

第四題：基地台

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
int n, k, arr[50005];
bool valid(int num){
    int cover = arr[0] + num, cnt = 1;
    for(int i = 1;i < n;i++){
        if(cover < arr[i]){
            cover = arr[i] + num;
            cnt++;
        }
    }
    return (cnt <= k);
}
int main(){
    IOS
    cin >> n >> k;
    for(int i = 0;i < n;i++) cin >> arr[i];
    sort(arr, arr + n);
    int l = 0, r = (arr[n - 1] - arr[0]) / k + 1, ans;
    while(l < r){
        int mid = (l + r) >> 1;
        if(valid(mid)) ans = mid, r = mid;
        else l = mid + 1;
    }
    cout << ans << '\n';

    return 0;
}

105/10

第一題：三角形辨別

 #include <iostream>
 #include <algorithm>
 using namespace std;
 int main(){
     int arr[4];
     cin >> arr[0] >> arr[1] >> arr[2];
     sort(arr,arr+3);
     cout << arr[0] << " " << arr[1] << " " << arr[2] << endl;
     if((arr[0] + arr[1]) <= arr[2]) cout << "No";
     else if(((arr[0] * arr[0]) + (arr[1] * arr[1]) < (arr[2] * arr[2]))) cout << "Obtuse";
     else if(((arr[0] * arr[0]) + (arr[1] * arr[1]) == (arr[2] * arr[2]))) cout << "Right";
     else if(((arr[0] * arr[0]) + (arr[1] * arr[1]) > (arr[2] * arr[2]))) cout << "Acute";
     
     return 0;
 }

第二題：最大和

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,m,sum = 0,k = 0;
    int s[21][21],msum[21];
    cin >> n >> m;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin >> s[i][j];
        }
    }
    for(int i = 0;i < n;i++){
        int temp = 0;
        for(int j = 0;j < m;j++){
            if(s[i][j] > temp) temp=s[i][j];
        }
        msum[i] = temp;
    }
    for(int i= 0;i < n;i++){
        sum+=msum[i];
    }
    cout << sum << endl;
    for(int i = 0;i < n;i++){
        if(sum%msum[i] == 0) continue;
        else msum[i] = 300;
    }
    for(int i = 0;i < n;i++){
        if(msum[i] != 300){
            cout << msum[i];
            if(i != n-1) cout << " ";
            k = 1;
        }
    }
    if(k == 0) cout << "-1";

    return 0;
}

第三題：定時Ｋ彈

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> vec;
    for(int i = 0;i < n;i++)
        vec.push_back(i);
    int index = 0;
    for(int i = 0;i < k;i++){
        index = (index+m-1) % vec.size();
        vec.erase(vec.begin() + index);
        index %= vec.size();
    }
    cout << vec[index] + 1 << endl;
 
    return 0;
}

105/3

第一題：成績指標

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> vec,pass,fail;
    int num,temp,minelement,maxelement,length;
    cin >> num;
    for(int i = 0;i < num;i++){
        cin >> temp;
        vec.push_back(temp);
    }
    sort(vec.begin(),vec.end());
    for(int i = 0;i < num;i++){
        cout << vec[i] << " ";
    }
    for(int i = num-1;i >= 0;i--){
        if(vec[i] >= 60) pass.push_back(vec[i]);
        if(vec[i] < 60) fail.push_back(vec[i]);
    }
    cout << endl;
    if(pass.empty()){
        maxelement = *max_element(fail.begin(),fail.end());
        cout << maxelement << endl;
        cout << "worst case" << endl;
        return 0;
    }
    if(fail.empty()){
        minelement = *min_element(pass.begin(),pass.end());
        cout << "best case" << endl;
        cout << minelement << endl;
        return 0;
    }
    minelement = *min_element(pass.begin(),pass.end());
    maxelement = *max_element(fail.begin(),fail.end());
    if(fail.empty() == false && pass.empty() == false)
        cout << maxelement << '\n' << minelement << endl;
    return 0;
}

第二題：矩陣轉換

#include <iostream>
#include <stack>
using namespace std;
void flip(int arr[100][100],int &r,int &c);
void change(int arr[100][100],int r,int c);//up and down
int main(){
    int r,c,m;
    while(cin >> r >> c >> m){
        int arr[100][100];
        for(int i = 0;i < r;i++){
            for(int j = 0;j < c;j++){
                cin >> arr[i][j];
            }
        }
        stack<int> s;
        for(int i = 0;i < m;i++){
            int tmp;
            cin >> tmp;
            s.push(tmp);
        }
        int l = s.size();
        for(int i = 0;i < l;i++){
            if(s.top() == 0) flip(arr,r,c);
            else change(arr,r,c);
            s.pop();
        }
        cout << r << " " << c << endl;
        for(int i = 0;i < r;i++){
            for(int j = 0;j < c;j++){
                cout << arr[i][j];
                if(j != c-1) cout << " ";
            }
            cout << endl;
        }
    }
    return 0;
}
void flip(int arr[100][100],int &r,int &c){//旋轉
    int temp[100][100];
    for(int i = 0;i < r;i++){
        for(int j = 0;j < c;j++){
            temp[c-j-1][i] = arr[i][j];
        }
    }
    for(int i = 0;i < c;i++){
        for(int j = 0;j < r;j++){
            arr[i][j] = temp[i][j];
        }
    }
    int t = c;
    c = r;
    r = t;
}
void change(int arr[100][100],int r,int c){
    int temp[100][100];
    for(int i = 0;i<r;i++){
        for(int j = 0;j < c;j++){
            temp[r-i-1][j] = arr[i][j];
        }
    }
    for(int i = 0;i < r;i++){
        for(int j = 0;j < c;j++){
            arr[i][j] = temp[i][j];
        }
    }
}

第三題:線段覆蓋長度

#include <iostream>
#include <algorithm>
using namespace std;
struct node{
    int a;
    int b;
};
bool cmp(node x,node y){
    if(x.a == y.a) return x.b < y.b;
    else return x.a < y.a;
}
node c[10001];
int main(){
    int n,big,small,ans = 0;
    cin >> n;
    for(int i = 0;i < n;i++)
        cin >> c[i].a >> c[i].b;
    sort(c,c+n,cmp);
    for(int i = 0;i < n;i++){
        small = c[i].a;
        big = c[i].b;
        while((i+1 < n) && c[i+1].a < big){
            if(c[i+1].b <= big){
                i++;
            }
            else{
                big = c[i+1].b;
                i++;
            }
        }
        ans = ans + big - small;
    }
    cout << ans;
    
    return 0;
}