2019 杭电多校 第九场

2019 Multi-University Training Contest 9

补题链接：2019 Multi-University Training Contest 9

1005 Rikka with Game (HDU 6684)

题意

Rikka 和 Yuta 玩游戏。给定一个字符串。两人轮流对字符串操作。可以选择结束游戏，也可以改变其中一个字符，改变规则是：(a ightarrow b,b ightarrow c,…,y ightarrow z,z ightarrow 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;
}