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 想要字典序最大。求最终的字符串是什么。
题解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| #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; }
|
题意
给出 $n$ 种物品的价格,现在要从无限枚 $10$元,$20$元,$50$元,$100$元的硬币中选出最少的硬币,满足能购买任何一种物品都不用找零。
题解
显然如果个位不为零时没有可行方案。
接下来考虑可行方案的求解。
$10$ 分的硬币多只会用一个,如果用了两个,直接替换成一个 $10$ 分一个 $20$ 分一定不亏。
$20$ 分的硬币多只会用三个,如果用了四个,直接替换成一个 $10$ 分两个 $20$ 分一个 $50$ 分一定不亏。
$50$ 分的硬币多只会用一个,如果用了两个,直接替换成一个 $50$ 分和一个一元一定不亏。
因此,直接暴力枚举 $10$, $20$, $50$ 的硬币的数量即可,整百的部分用一元硬币填充。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
| #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; }
|