SMU Summer 2023 Contest Round 14

A. Potion-making

就是解一个\(\frac{i}{i + j} = \frac{k}{100}\)方程,然后循环暴力找出答案

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

void solve(){
    int k;
        cin >> k;

        for(int i = 1;i <= 100;i ++){
            for(int j = 0;j < 100;j ++){
                if(i * 100 == k * (i + j)){
                    cout << i + j << '\n';
                    return ;
                }
            }
        }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){
        solve();
    }

    return 0;
}

B. Permutation Sort

其实就是特判首尾的情况

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &i : a) cin >> i;

    vector<int> b(n);
    iota(b.begin(), b.end(),1);

    if(a == b){
        cout << 0 << '\n';
        return ;
    }else {
        if(a[0] == 1 || a.back() == n)
            cout << 1 << '\n';
        else if(a[0] == n && a.back() == 1)
            cout << 3 << '\n';
        else cout << 2 << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){
        solve();
    }


    return 0;
}

D. Armchairs

\(dp[i][j]\)表示前\(j\)个椅子放\(i\)个人的最短时间

当前座位为空时,可以放人也可以不放人.

否则,为前一个座位放\(i\)个人的最短时间

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n + 1),b(1);
    for(int i = 1;i <= n;i ++){
    	cin >> a[i];
    	if(a[i] == 1)
    		b.push_back(i);
    } 

    vector dp(n + 1, vector<int> (n + 1, 0x3f3f3f3f));

    for(int i = 0;i <= n;i ++) dp[0][i] = 0;

    for(int i = 1;i < b.size();i ++){
    	for(int j = 1;j <= n;j ++){
    		if(a[j] == 0){
    			dp[i][j] = min(dp[i][j - 1], dp[i - 1][j - 1] + abs(b[i] - j));    			
    		}else
    			dp[i][j] = dp[i][j - 1];
    	}
    }

    cout << dp[b.size() - 1][n] << '\n';
    return 0;
}