A题:Only Pluses
思路:
数据范围小,直接暴力枚举。
code:
inline void solve() {
int a, b, c; cin >> a >> b >> c;
int ans = 0;
for (int i = a; i <= a + 5; i ++ ) {
for (int j = b; j <= b + 5; j ++ ) {
for (int k = c; k <= c + 5; k ++ ) {
if (i + j + k <= a + b + c + 5) {
ans = max(ans, i * j * k);
}
}
}
}
cout << ans << endl;
return;
}
优化:
极差越小,立方体的体积越大。
inline void solve() {
priority_queue<int, vector<int>, greater<int>> q;
for (int i = 0; i < 3; i ++ ) {
int x; cin >> x;
q.push(x);
}
int cnt = 5;
while (cnt -- ) {
int p = q.top() + 1; q.pop();
q.push(p);
}
int sum = 1;
while (q.size()) {
sum *= q.top(); q.pop();
}
cout << sum << endl;
return;
}
B题:Angry Monk
思路:
由题意,如果我们要将 3 和 2 进行合并,那么就要将2 全部拆成 1,再把 3 和 1进行一一合并。
显然地,我们要去拆 k - 1个,让原本的数全都变成1,然后再将1与剩下来的那一个数进行合并。
对于一个数 x ,进行拆+合并的操作次数为 x - 1 + x 次
那么,我们就知道了,剩下来的那一个数一定是最大的那一个,而将其他的数全部拆掉与其合并即可。
code:
inline void solve() {
ll n, k; cin >> n >> k;
vector<ll> a(k + 1);
for (int i = 1; i <= k; i ++ ) cin >> a[i];
sort(a.begin() + 1, a.end());
ll ans = 0;
for (int i = 1; i <= k - 1; i ++ ) {
ans += (a[i] - 1) + a[i];
}
cout << ans << endl;
return;
}
优化:
我们只需统计总数和最大的数即可。
inline void solve() {
ll n, k; cin >> n >> k;
ll sum = 0, maxv = -1;
for (int i = 1; i <= k; i ++ ) {
ll x; cin >> x;
sum += x;
maxv = max(maxv, x);
}
cout << (sum - maxv) * 2 - (k - 1) << endl;
return;
}
C题:Gorilla and Permutation
思路:
最简单的想法就是输出一个降序的排列。
但是很明显的,错了。
错在小于等于取值的情况,因为这样先取了2,再取了1,这样2的贡献是2 * 2,总的是5。
如果是先取1,再取2,这样的贡献是1 * 2 + 2 = 4 。
那么我们只要前面降序后面升序即可。
code:
inline void solve() {
ll n, m, k; cin >> n >> m >> k;
for (int i = n; i >= m + 1 ; i -- ) cout << i << ' ';
for (int i = 1; i <= m; i ++ ) cout << i << ' ';
cout << endl;
return;
}
D题:Test of Love
思路:
被卡了一下的题。
首先在水中不能跳跃,我们只能一格格移动,但是用while遍历的话肯定要超时,所以我们用pos[i]指代 i 的位置上到其后的第一个不是W的格子的位置。
我们又可以知道,在L上时,我们最优的策略一定是跳到下一个L上
因为我们能够跳跃的距离是一定的,跳到下一个L,相当于白嫖了一段距离。
如果不能跳到的话,那么我们一定是跳到最远处,不然可能会遇到C或者使得在水中的次数增加导致亏损。
所以
我们如果在W中时,只能不断向右,遇到C直接失败。
如果到了L,进行L的最优跳跃。
还要注意一开始在岸边的跳跃情况,这时候由于m小,我们可以直接遍历开头。
返回情况用cnt和k的比较就行。
code:
inline void solve() {
int n, m, k; cin >> n >> m >> k;
string s; cin >> s;
s = " " + s + "Q";
int last1 = n + 1, last2 = n + 1;
vector<int> pos(n + 1);
for (int i = n; i >= 1; i -- ) {
if (s[i] == 'L') {
pos[i] = last1;
last1 = i;
}
if (s[i] != 'W') {
last2 = i;
}else {
pos[i] = last2;
}
}
function<bool(int)> check = [&](int cur) {
int cnt = 0;
while (cur != n + 1) {
cur += 1;
if (cur == n + 1) return cnt <= k;
if (s[cur] == 'C') return false;
else if (s[cur] == 'W') {
cnt += pos[cur] - cur;
cur = pos[cur] - 1;
}else {
if (pos[cur] - cur <= m) cur = pos[cur] - 1;
else {
cur = min(cur + m, n + 1) - 1;
}
}
}
return cnt <= k;
};
if (m >= n + 1) cout << "YES\n";
else {
bool ok = false;
for (int i = 0; i < m; i ++ ) {
if (check(i)) {
ok = true;
break;
}
}
cout << (ok ? "YES\n" : "NO\n");
}
return;
}
E题:Novice's Mistake
思路:
直接遍历
我们直接遍历a和b肯定是不现实的,但是b跟位数有关系,所以我们只需遍历a,然后遍历位数即可,因为按照题意就是删去b位a的末尾字符串。
第一层遍历我们遍历a,第二层遍历我们遍历留下来的位数。
min(6, dig * a) 因为最后剩下来的不超过1e6,所以用了这个。
code:
int cal(int x) {
int res = 0;
while (x) res += 1, x /= 10;
return res;
}
inline void solve() {
int n; cin >> n;
int dig = cal(n);
vector<PII> res;
for (int a = 1; a <= 1e4; a ++ ) {
for (int i = 1; i <= min(6, dig * a); i ++ ) {
string s = to_string(n);
while (s.size() < i) s = s + s;
while (s.size() > i) s.pop_back();
int m = stoll(s);
if (m == a * n - (dig * a - i) && i != dig * a) {
res.push_back({a, dig * a - i});
}
}
}
cout << res.size() << endl;
for (auto [x, y] : res) cout << x << ' ' << y << endl;
return;
}