今天采用的是新格式。
CF1810A Beautiful Sequence
点击查看原题
点击查看思路
如果一个数字的值 \(v\)，不大于当前的位置 \(p\)，那我们可以通过删除 \(p - v\) 个数字，使它们两个对应上。
比如 \([1, 7, 2, 5, 3]\) 中的 \(3\)，其数值为 \(3\)，位置为 \(5\)，数值 \(3\) 小于等于 \(5\)，那么在 \([1, 7, 2, 5]\) 中删除任意两个数字都可以达到目的，变成 \([X, Y, 3]\)。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N];
int n;
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
if (a[i] <= i) {
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
return 0;
}
CF1810B Candies
点击查看原题
点击查看思路
应为最开始的数字为奇数 \(1\)，那么 \(奇数 \times 2 \pm 1\) 也一定是奇数，那么如果运算途中出现偶数，直接判无解即可。
接下来思考有解情况，我们不妨反过来思考。
- 如果一个数字 \(y = x \times 2 + 1\)，那么 \(x = \frac{y - 1}{2}\)。
- 如果一个数字 \(y = x \times 2 - 1\)，那么 \(x = \frac{y + 1}{2}\)。
那么我们可以倒推回去，因为最终的结果为 \(n\)，那么我们只要在 \(\frac{y + 1}{2}\) 和 \(\frac{y - 1}{2}\) 中选择一个，并将它赋值给 \(n\) 即可，这就是一次倒推。
那怎么选呢？因为 \(n\) 为奇数，那么 \(\frac{y + 1}{2}\) 和 \(\frac{y - 1}{2}\) 必为一奇一偶，那么肯定选择哪个奇数的就可以了。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
void solve() {
int x;
cin >> x;
if (x & 1) {
vector<int> opt;
opt.clear();
while (x != 1) {
if ((x + 1 >> 1) & 1) {
x = (x + 1) >> 1;
opt.push_back(1);
}
else if ((x - 1 >> 1) & 1) {
x = (x - 1) >> 1;
opt.push_back(2);
}
else {
cout << "-1\n";
return;
}
}
if (opt.size() > 40) {
cout << "-1\n";
return;
}
cout << opt.size() << '\n';
for (int i = opt.size() - 1; i >= 0; i--) cout << opt[i] << ' ';
cout << '\n';
}
else cout << "-1\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
return 0;
}
CF1810C Make It Permutation
点击查看原题
点击查看思路
我们可以枚举一个 \(i\)，
我们保留数组中 \([1, i]\) 的部分，那我们就要将 \([1, a[i]]\) 中缺少的数字补起来，代价为 \(d \times (a[i] - i)\)，即共有 \(a[i] - i\) 个数字要加上来，每次耗费 \(d\) 的金钱。
对于 \([i + 1, n]\) 的部分可以删去，共有 \(n - i\) 个要删除的数字，代价为 \(c \times (n - i)\)。
注意：
1. 也可以一个数字也不保留，但是一定要插入一个 \(1\) 呀，因为题目中说：
。
2. 一定要去重，并将删除重复数字需要的代价加到结果中。
3. 注意开long long。
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010;
int n, c, d;
int a[N];
void solve() {
cin >> n >> c >> d;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int tot = unique(a + 1, a + n + 1) - a - 1;
int ans = 0x3f3f3f3f3f3f3f3f;
for (int i = 0; i <= tot; i++) {
int del = (tot - i + n - tot) * c; // n - tot为删除重复元素的步骤数量
int get = (a[i] - i + (i == 0)) * d;
ans = min(ans, del + get);
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
return 0;
}
CF1810D Candies
点击查看原题
点击查看思路
经典的小学数学奥数题。
设 \(a\) 为每天往上爬的高度，\(b\) 为每天向下降的高度，\(n\) 为给定的需要爬上去的天数。
请注意，第 \(n\) 天爬上去了，就不会下降了。
对于操作为 \(1\) 的，我们可以确定其范围。
因为要保证第 \(n\) 天就可以到达，且第 \(n - 1\) 天不能到达，所以其范围为标红部分：
用表达式表示为 \([(a - b) \times (n - 2) + a + 1, (a - b) \times (n - 1) + a]\)，其中 \((a - b) \times (n - 2) + a\) 为第 \(n - 1\) 天可以到达的最大高度 \(+1\) 才可以符合题意；\((a - b) \times (n - 1) + a\) 为第 \(n\) 天可以到达的最大高度。
需要特判 \(n = 1\) 的情况，此时其范围为 \([1, a]\)。
如果这个区间与之前之前计算的结果有交集，那么就是可以保留的，并更新区间，否则就丢弃之。
对于操作类型为 \(2\) 的，我们先计算出爬上 \(l\) 的高度需要的时间 \(t\)，计算方法如下。
假设高度为 \(h\)。
- 首先要预留一个 \(a\)。
- 然后计算 \(\left\lfloor\frac{h - a}{a - b}\right\rfloor\) 表示到达小于等于 \(h - a\) 的位置所需要的时间。
- 如果刚好到达 \(h - a\) 的位置 \(+1\) 就可以了，否则 \(+2\)。
注意最好不要直接上取整，因为容易引起精度问题。
这样就计算出了 \(t\)，然后计算出花 \(t + 1\) 天爬上的高度范围是否与已知范围 \([l, r]\) 有交集，计算方法与前面的操作 \(1\) 类似，如果有那么证明不能准确获取其天数，输出 \(-1\)，否则输出天数。
注意我们不能直接判断已知范围 \(l\) 是否等于 \(r\)，因为有可能对于这一组询问在该区间内只有一种可能性，也是满足题意的。
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
bool check(int& l1, int& r1, int l2, int r2, bool flag) {
int ll = max(l1, l2);
int rr = min(r1, r2);
if (ll > rr) return false;
if (flag) {
l1 = ll;
r1 = rr;
}
return true;
}
void solve() {
int q;
cin >> q;
int opt, a, b, c;
int l = -1, r = 1e18;
while (q--) {
cin >> opt;
if (opt == 1) {
cin >> a >> b >> c;
int lnew = -1, rnew = -1;
if (c == 1) lnew = 1, rnew = a;
else lnew = (a - b) * (c - 2) + a + 1, rnew = (a - b) * (c - 1) + a;
if (check(l, r, lnew, rnew, true)) cout << "1 ";
else cout << "0 ";
}
else {
cin >> a >> b;
int x = l, res = 0;
if (a >= l) {
res = 1;
}
else {
x -= a;
res = x / (a - b);
x = res * (a - b);
if (x == l - a) res++;
else res += 2;
}
c = res + 1;
int lnew = -1, rnew = -1;
if (c == 1) lnew = 1, rnew = a;
else lnew = (a - b) * (c - 2) + a + 1, rnew = (a - b) * (c - 1) + a;
if (check(l, r, lnew, rnew, false)) res = -1;
cout << res << ' ';
}
}
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
return 0;
}