2019 杭電多校 第九場

2019 Multi-University Training Contest 9

補題連結：2019 Multi-University Training Contest 9

1005 Rikka with Game (HDU 6684)

題意

Rikka 和 Yuta 玩遊戲。給定一個字元串。兩人輪流對字元串操作。可以選擇結束遊戲，也可以改變其中一個字元，改變規則是：\(a\rightarrow b,b\rightarrow c,…,y\rightarrow z,z\rightarrow a.\)。Rikka 想要字典序最小，而 Yuta 想要字典序最大。求最終的字元串是什麼。

題解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const int maxn = 100000 + 5;

int p[110];

int main() {
    std::ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--) {
        string s;
        cin >> s;
        if(s[0] != 'z' && s[0] != 'y') {
            cout << s << endl;
            continue;
        }
        if(s[0] ==  'z') {
            s[0] = 'b';
            cout << s << endl;
        } else {
            for(int i = 1; i < s.length(); ++i) {
                if(s[i] < 'y') break;
                if(s[i] == 'z') {
                    s[i] = 'b';
                    break;
                }
            }
            cout << s << endl;
        }
    }
    return 0;
}
           

1006 Rikka with Coin (HDU 6685)

給出 \(n\) 種物品的價格，現在要從無限枚 \(10\)元，\(20\)元，\(50\)元，\(100\)元的硬币中選出最少的硬币，滿足能購買任何一種物品都不用找零。

顯然如果個位不為零時沒有可行方案。

接下來考慮可行方案的求解。

\(10\) 分的硬币多隻會用一個，如果用了兩個，直接替換成一個 \(10\) 分一個 \(20\) 分一定不虧。

\(20\) 分的硬币多隻會用三個，如果用了四個，直接替換成一個 \(10\) 分兩個 \(20\) 分一個 \(50\) 分一定不虧。

\(50\) 分的硬币多隻會用一個，如果用了兩個，直接替換成一個 \(50\) 分和一個一進制一定不虧。

是以，直接暴力枚舉 \(10\), \(20\), \(50\) 的硬币的數量即可，整百的部分用一進制硬币填充。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const int maxn = 100 + 5;

int w[maxn];

bool judge(int n, int a, int b, int c) {
    for(int i = 0; i <= a; ++i) {
        for(int j = 0; j <= b; ++j) {
            for(int k = 0; k <= c; ++k) {
                if(i * 50 + j * 20 + k * 10 == n) {
                    return true;
                }
            }
        }
    }
    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int flag = 0;
        for(int i = 0; i < n; ++i) {
            cin >> w[i];
            if(w[i] % 10) {
                flag = 1;
            }
        }
        if(flag) {
            cout << -1 << endl;
            continue;
        }
        int ans = inf;
        for(int j = 0; j <= 1; ++j) {
            for(int k = 0; k <= 3; ++k) {
                for(int l = 0; l <= 1; ++l) {
                    int flag = 1;
                    int cnt = 0;
                    for(int i = 0; i < n; ++i) {
                        if(w[i] < 100) {
                            if(judge(w[i], j, k, l)) {
                                continue;
                            } else {
                                flag = 0;
                                break;
                            }
                        } else {
                            if(judge(w[i] % 100 + 100, j, k, l)) {
                                cnt = max(cnt, (w[i] - 100) / 100);
                            } else if(judge(w[i] % 100, j, k, l)) {
                                cnt = max(cnt, w[i] / 100);
                            } else {
                                flag = 0;
                                break;
                            }
                        }
                    }
                    if(flag) {
                        ans = min(ans, cnt + j + k + l);
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}