Codeforces Round #887 (Div. 2) A-D
比赛链接
A
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[507];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
int ans = 1e9;
for (int i = 2;i <= n;i++) ans = min(ans, max(0, a[i] - a[i - 1] + 1));
cout << (ans + 1) / 2 << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
B
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool solve() {
int n, k;
cin >> n >> k;
int ans = 0;
for (int i = 0;i <= n;i++) {
int a = n, b = i;
int cnt = 2;
while (cnt < k && 0 <= a - b && a - b <= b) {
cnt++;
a -= b;
swap(a, b);
}
if (cnt == k) ans++;
}
cout << ans << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
C
题意
有一个数字集合 \(\{ 1,2,3,\cdots,10^{1000} \}\) 。
给定一个长为 $n $ 正整数数组 \(a\) ，每轮删除集合中排名 \(a_1,\cdots,a_n\) 的数字。
一共删 \(k\) 轮，问最后集合中最小的元素。
题解
知识点：枚举，贪心。
首先特判 \(a_1 \geq 2\) 的情况，答案就是 \(1\) 。
考虑从最后一轮逆推最后一个数的排名 \(x\) ，一开始 \(x = 1\) 。
我们考虑上一轮在 \(x\) 之前删了 \(pos\) 个数，那么 \(pos\) 应该满足 \(a_{pos} < x + pos <a_{pos+1}\) 。我们知道 \(a_{pos}\) 的递增速率是大于等于 \(pos\) 的，更具体地说，我们有 \(a_{pos} - pos < x < a_{pos+1} - pos-1+1\) ，显然 \(a_{pos}-pos\) 随着 \(pos\) 增加是不严格递增的，因此任意 \(pos\) 产生的区间都是非空的，所以我们一定能找到一个 \(pos\) 满足条件，可以考虑二分这个 \(pos\) 。
但我们注意到 \(x\) 是严格递增的，因此我们可以保留上一轮的 \(pos\) 继续递增。因此，复杂度可以优化成线性。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[200007];
bool solve() {
int n, k;
cin >> n >> k;
for (int i = 1;i <= n;i++) cin >> a[i], a[i] -= i;
if (a[1] + 1 >= 2) {
cout << 1 << '\n';
return true;
}
ll x = 1;
int pos = 0;
for (int i = 1;i <= k;i++) {
while (pos < n) {
if (a[pos] < x && x < a[pos + 1] + 1) break;
pos++;
}
x += pos;
}
cout << x << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
D
题意
给定一个长为 \(n\) 的数组 \(a\) ，要求构造长为 \(n\) 的数组 \(b\) ，满足对于 \(1 \leq i \leq n\) 有 \(a_i\) 个下标 \(j\) 使得 \(b_i + b_j > 0\) 。
其中 \(a_i \in [0,n]\) ，要求 \(b_i \neq 0\) 且不存在 \(b_i + b_j = 0\) 。
题解
知识点：构造。
可以考虑从绝对值最大的数字开始构造，因为这些数字确定后可以直接删除，不会影响或产生确定的影响。显然，我们有 \(a_i < a_j\) 则 \(b_i<b_j\) ，同时若绝对值最大的数字 \(b_x<0\) 则 \(a_x = 0\) 否则 \(a_x = n\) 。
我们考虑将 \(a\) 从小到大排序，每次删除按如下操作：
-
若 \(a_1 = 0\) 成立，则 \(b_1 = -n\) ；若 \(a_n = n\) 成立，则 \(b_n = n\) ；若前面两者同时成立或不成立，则无解。
同时成立代表，既有一个数字和任何数字加都是小于等于 \(0\) ，又有一个数字加任何数字都是大于 \(0\) 矛盾。
同时不成立代表，不存在绝对值最大的数字（因为存在就一定会有 \(a_1 = 0\) 或 \(a_n = n\) ）矛盾。
-
删去后，令 \(n \to n-1\) 。若删去的是 \(a_n\) ，则令所有 \(a_i\) 减 \(1\) 。
-
若存在剩余数字，则回到步骤 \(1\) ，否则就构造完成。
注意，构造时要保证原来的顺序。
时间复杂度 \(O(n \log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[100007];
int b[100007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
vector<int> ord(n + 1);
iota(ord.begin() + 1, ord.end(), 1);
sort(ord.begin() + 1, ord.end(), [&](int i, int j) {return a[i] < a[j];});
int l = 1, r = n, delta = 0;
while (l <= r) {
int ok = (a[ord[l]] - delta == 0) ^ (a[ord[r]] - delta == r - l + 1);
if (!ok) return false;
if (a[ord[l]] - delta == 0) {
b[ord[l]] = -(r - l + 1);
l++;
}
else {
b[ord[r]] = r - l + 1;
r--;
delta++;
}
}
cout << "YES" << '\n';
for (int i = 1;i <= n;i++) cout << b[i] << " \n"[i == n];
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << "NO" << '\n';
}
return 0;
}