A
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int cnt[107];
bool solve() {
int n;
cin >> n;
for (int i = 0;i < 100;i++) cnt[i] = 0;
for (int i = 1, x;i <= n;i++) cin >> x, cnt[x]++;
for (int i = 1;i < 100;i++) if (cnt[i - 1] < cnt[i]) return false;
cout << "YES" << '\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;
}
B
题目
有 \(k\) 个金块，每个价值 \(g\) 个银币，共价值 \(kg\) 个银币。
有 \(n\) 个人要分这 \(kg\) 个银币，分的方案是按照银币分的，但金块只能完整的给。
因此，若分到的 \(x\) 个银币，根据余数 \(r = x \bmod g\) 分类：
- 若 \(r \geq \left\lceil \dfrac{g}{2} \right\rceil\) ，那么将会分到 \(x - r + g\) 。
- 否则，将会分到 \(x-r\) 。
给出使得保留银币最多的方案。
题解
知识点：数学，贪心。
贪心地给每个人先分 \(\left\lceil \dfrac{g}{2} \right\rceil - 1\) 个银币，这样使得每个人不会获得的部分是最多的。
接下来，分剩下的 \(kg - n\left(\left\lceil \dfrac{g}{2} \right\rceil - 1\right)\) （若还有）。因为一开始已经给所有人分了不会获得的上限，因此对于任意一个人，只要多一个银币就会多分一个金，所以最后实际会分到 \(g \left\lceil \dfrac{kg - n \left( \left\lceil \dfrac{g}{2} \right\rceil - 1 \right)}{g} \right\rceil\) 个银币，剩下的就是保留下来的。
时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool solve() {
ll n, k, g;
cin >> n >> k >> g;
cout << k * g - (max(0LL, k * g - ((g + 1) / 2 - 1) * n) + g - 1) / g * g << '\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
题目
给出三个数 \(a,b,c\) 的位数 \(A,B,C\) ，需要构造这三个数（无前导 \(0\) ），使得满足等式 \(a+b=c\) 。
求出所有能构造出来的等式中，字典序第 \(k\) 小的等式。
题解
知识点：数学，枚举，贪心。
因为数字位数是固定的，那么字典序第 \(k\) 小就等价于按 \(a,b,c\) 为第一、二、三关键字从小到大排序后的第 \(k\) 个等式。因此，我们可以从小到大枚举 \(a\) ，判断以当前 \(a\) 构造的所有等式是否包含了第 \(k\) 个等式，若包含则构造出 \(b,c\) 即可。
现在问题变为，如何求出一个 \(a\) 能构造出多少等式。将原式变形为 \(b = c - a\) ，满足这个等式的 \(b,c\) 对的个数即为等式数量，那就是取 \([10^{B-1},10^B-1]\) 与 \([10^{C-1}-a,10^C-1-a]\) 的交集的长度。若交集不存在，则这个 \(a\) 没有有效等式，跳过即可。
当然，其实交集不存在有两种情况，一种是 \(b\) 在 \(c\) 左边，这种情况跳过这个 \(a\) 即可；一种是 \(b\) 在 \(c\) 右边，这种情况其实可以直接判断不存在，因为 \(a\) 往后会更大，\(c\) 的区间会继续往左，不可能产生交集。实际上，我们都选择跳过而不判断不存在，是没有任何影响的。
时间复杂度 \(O(10^A)\)
空间复杂度 \(O(1)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int p[7] = { 1,10,100,1000,10000,100000,1000000 };
bool solve() {
int a, b, c;
ll k;
cin >> a >> b >> c >> k;
ll sum = 0;
for (int i = p[a - 1];i < p[a];i++) {
int l = max(p[b - 1], p[c - 1] - i);
int r = min(p[b] - 1, p[c] - 1 - i);
if (l > r) continue;
int len = r - l + 1;
if (sum + len >= k) {
cout << i << " + " << k - sum - 1 + l << " = " << i + k - sum - 1 + l << '\n';
return true;
}
sum += len;
}
return false;
}
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\) 个人抽奖编号为 \(1\) 到 \(n\) ，每个人从 \([0,m]\) 选取一个整数作为自己的号码 \(a_i\) 。
中奖号码随机从 \([0,m]\) 种选取，最接近的 \(k\) 个人获奖。若出现一群人距离相同，但超人数了，那么编号较小的人获奖。
现在你的编号是 \(n+1\) 也想参与抽奖，你知道 \(n\) 个人选了的号码，想要在在 \([0,m]\) 中选一个号码使得自己的获奖概率最大。
因此，求出最多能有多少种中奖号码能使得你获奖，并给出这种情况你要选择的最小号码。
题解
知识点：数学，二分，枚举。
我们先对 \(a\) 从小到大排序，方便查找。
考虑对于一个号码 \(x\) ，有多少种中奖号码能使得 \(x\) 获奖。显然，中奖号码是一个连续的区间。
我们不妨考虑其左端点的位置，左端点是由于与从 \(x\) 往左数第 \(k\) 个人竞争第 \(k\) 个获奖位置导致的。我们假设大于 \(x\) 的第一个位置在 \(p\) ，那么左数第 \(k\) 个人应该在 \(p - k\) ，因此左端点为 \(\left\lfloor \dfrac{x + a_{p-k}}{2} \right\rfloor + 1\) （因为我们的编号最大，所以左端点必须严格靠近 \(x\) ），所以到左端点的中奖号码有 \(x - \left( \left\lfloor \dfrac{x + a_{p-k}}{2} \right\rfloor + 1 \right) + 1= \left\lceil \dfrac{x - a_{p-k}}{2} \right\rceil\) 个。
右端点同理，我们假设大于等于 \(x\) 的第一个位置在 \(p\) ，同时 \(x\) 在算左端点的时候算进去了，因此到右端点中奖号码有 \(\max\left(0, \left\lceil \dfrac{a_{p+k-1}-x}{2} \right\rceil - 1 \right)\) 个。
当然，如果左右人数不够 \(k\) 个，可以直接加到底。
接下来，显然我们是不能 \([0,m]\) 一个一个枚举的，实际上我们只需要枚举 \(a_i\) 以及 \(a_i-2,a_i-1,a_i+1,a_i+2\) 。因为可以发现，两个号码中间的位置答案其实基本是一样的，但需要分奇偶，因此考虑左右两边各两个以及号码本身。同时，要考虑所有人都能获奖的情况， \(0\) 也是答案，即使它不在 \(a_i\) 里，因此一开始直接判 \(0\) 即可。
时间复杂度 \(O(n \log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll a[1000007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k;
ll m;
cin >> n >> m >> k;
for (int i = 1;i <= n;i++) cin >> a[i];
sort(a + 1, a + n + 1);
ll mx = 0, ans = 0;
auto check = [&](ll x) {
int low = lower_bound(a + 1, a + n + 1, x) - a;
int up = upper_bound(a + 1, a + n + 1, x) - a;
ll win = 0;
if (up - k <= 0) win += x + 1;
else win += (x - a[up - k] + 1) / 2;
if (low + k - 1 > n) win += m - x;
else win += max(0LL, (a[low + k - 1] - x + 1) / 2 - 1);
if (win > mx) {
mx = win;
ans = x;
}
};
check(0);
for (int i = 1;i <= n;i++) {
if (a[i] - 2 >= 0) check(a[i] - 2);
if (a[i] - 1 >= 0) check(a[i] - 1);
check(a[i]);
if (a[i] + 1 <= m) check(a[i] + 1);
if (a[i] + 2 <= m) check(a[i] + 2);
}
cout << mx << ' ' << ans << '\n';
return 0;
}