小白月赛 Round 126 题解
A 小红打舞萌
比较规则是：
- 数字越大越难。
- 数字相同时，带
比不带
转化一下， 。
void solve() {
string a, b;
cin >> a >> b;
int A = 0, B = 0;
for (auto v : a) {
if (isdigit(v)) {
A = A * 20 + 2 * (v - '0');
} else {
A++;
}
}
for (auto v : b) {
if (isdigit(v)) {
B = B * 20 + 2 * (v - '0');
} else {
B++;
}
}
cout << (A > B ? "Yes" : "No") << endl;
}
B 小红写谱
我们不难发现两个规律：
- 连续的同一个键没有贡献。
- 顺时针/逆时针走过每一个键的贡献是最小的。
所以只需要统计哪些键位出现过即可，然后以每一个出现的键为起点，旋转一圈的贡献。
当然我们不难发现，这个最优贡献就相当于整一圈减去相差最远的两个键之间的距离。
void solve() {
int n;
cin >> n;
vector<bool> vis(9);
for (int i = 0, x; i < n; i++) {
cin >> x;
vis[x] = 1;
}
vector<int> a;
for (int i = 0; i < 9; ++i) {
if (vis[i]) {
a.pb(i);
}
}
int mx = 0, p = a.back() - 8;
for (int x : a) {
mx = max(mx, x - p);
p = x;
}
cout << 8 - mx << endl;
}
C 小红出勤
对于任意一首必选歌 ，它的游玩次数
必须至少等于出勤次数
。
每次出勤最多玩 首歌，也就是说
次出勤能够提供的总游玩容量为
。所有的游玩记录总和
必须能被塞进这
次出勤中
void solve() {
int n, p, k;
cin >> n >> p >> k;
map<string, int> cnt;
ll tot = 0;
for (int i = 0; i < n; i++) {
string s;
int a;
cin >> s >> a;
cnt[s] = a;
tot += a;
}
int mx = inf;
for (int i = 0; i < k; i++) {
string s;
cin >> s;
mx = min(mx, cnt[s]);
}
if (p < k) {
cout << -1 << endl;
return;
}
ll mn = (tot + p - 1) / p;
if (mn > mx) {
cout << -1 << endl;
} else {
cout << mn << " " << mx << endl;
}
}
D 小红越级（easy）
法1（ ）：
为了算不舒适，我们只需要算舒适的个数就行了。
对于一首歌，它能提供的舒适范围为 。
那么对于多个区间 ，然后查单点，很容易想到使用差分数组。
对于每个有效区间 ，执行
和
。
处理完所有歌曲后，对 数组求前缀和，
即为能力为
时的舒适歌曲数量。
void solve() {
int n, q;
cin >> n >> q;
vector<int> diff(n + 2, 0);
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
int l1 = a - 1, r1 = a + 1, l2 = b - 1, r2 = b + 1;
if (r1 + 1 >= l2) {
int L = max(1, l1);
int R = min(n, r2);
if (L <= R) {
diff[L]++;
if (R + 1 <= n + 1) {
diff[R + 1]--;
}
}
} else {
int L1 = max(1, l1);
int R1 = min(n, r1);
if (L1 <= R1) {
diff[L1]++;
if (R1 + 1 <= n + 1) {
diff[R1 + 1]--;
}
}
int L2 = max(1, l2);
int R2 = min(n, r2);
if (L2 <= R2) {
diff[L2]++;
if (R2 + 1 <= n + 1) {
diff[R2 + 1]--;
}
}
}
}
vector<int> cnt(n + 1);
int cur = 0;
for (int i = 1; i <= n; ++i) {
cur += diff[i];
cnt[i] = cur;
}
for (int i = 0; i < q; ++i) {
int k;
cin >> k;
cout << n - cnt[k] << " ";
}
cout << endl;
}
法2（ ）：
对于每次询问 ，我们需要计算有多少个区间覆盖了点
。
覆盖点 的区间数量 = (起点
的区间数量) - (终点
的区间数量)。
#include <bits/extc++.h>
using namespace __gnu_pbds;
using Tree = tree<PII, null_type, less<PII>, rb_tree_tag,
tree_order_statistics_node_update>;
void solve() {
int n, q;
cin >> n >> q;
Tree L, R;
int id = 0;
auto insert = [&](int l, int r) {
L.insert({l, ++id});
R.insert({r, ++id});
};
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
int l1 = a - 1, r1 = a + 1;
int l2 = b - 1, r2 = b + 1;
if (r1 + 1 >= l2) {
insert(min(l1, l2), max(r1, r2));
} else {
insert(l1, r1);
insert(l2, r2);
}
}
for (int i = 0; i < q; ++i) {
int k;
cin >> k;
cout << n - L.order_of_key({k, inf}) + R.order_of_key({k, -inf}) << " ";
}
cout << endl;
}
E 小红做梦
主播觉得最阴的一题，给我搞完气爆两颗。
不难想到去枚举除的次数，然后 的次数即为满足
。
我们只需要用 和
模拟两个边界即可。
void solve() {
ll x, a, b, c;
cin >> x >> a >> b >> c;
ll ans = INF, cur = x;
auto ssolve = [&](ll X) {
ll l = 1005, r = 1011;
while (1) {
if (l <= X && X < r) {
return 0ll;
}
if (X < l) {
ll n = (l - X + c - 1) / c;
if (n * c + X < r) {
return n;
}
}
l *= 10, r *= 10;
}
};
for (int i = 0; i <= 17; ++i) {
ans = min(ans, a * i + ssolve(cur) * b);
cur /= 10;
}
cout << ans << endl;
}
F 小红开机厅
由三角不等式可知，平面上任意一点到 的距离之和
，且
与
同奇偶。
- 情况
（
）：
- 满足条件的点构成了以
为对角顶点的实心矩形区域。
- 该矩形内的整数点数量为
。
- 满足条件的点构成了以
- 情况
（
）：
- 满足条件的点构成了围绕该矩形的一个环状边界。
- 该边界上的整数点数量为
。（读者自证不难）
哈希表记录机厅距离，排一下即可。
void solve() {
int n;
cin >> n;
ll xa, ya, xb, yb;
cin >> xa >> ya >> xb >> yb;
ll X = llabs(xa - xb), Y = llabs(ya - yb);
ll L = X + Y;
int ch = 0;
if (xa == xb && ya == yb) {
ch = 1;
} else {
ch = 2;
}
vector<ll> qs(n);
map<ll, int> cnt;
for (int i = 0; i < n; ++i) {
ll x, y;
cin >> x >> y;
ll dist = llabs(x - xa) + llabs(y - ya) + llabs(x - xb) + llabs(y - yb);
qs[i] = dist;
cnt[dist]++;
}
for (int i = 0; i < n; ++i) {
ll K = qs[i];
ll tot = 0;
if (K == L) {
tot = (X + 1) * (Y + 1);
} else {
tot = 2 * K;
}
ll ex = 0;
if (K == L) {
ex += ch;
}
if (cnt.count(K)) {
ex += cnt[K];
}
cout << (tot - ex) << " ";
}
cout << endl;
}
G 小红越级（hard）
难度为 能力为
，不舒适度为
对于每首歌，它的最低不舒适度为
我们要计算所有歌的总和
是分段线性的。我们可以通过维护其二阶差分（斜率的变化率）来快速计算。记
为在
处斜率的变化量
对于一首歌 ，我们考察
从小到大变化时
的斜率变化：
-
两个“舒适区间”重叠或相接 (
)：
此时
和
的并集是一个连续区间
。
在此区间内代价为 0，左边斜率 -1，右边斜率 1。
- 在
处（对应
），斜率从 -1 变为 0（增加 1）。
- 在
处（对应
），斜率从 0 变为 1（增加 1）。
- 在
-
两个区间分离 (
)
此时有两个零代价区间
在
右侧选
，策略从选
-
在
（增加 1）。
-
在
处：斜率
（增加 1）。
-
切换点：位于中点
附近。
-
若
是偶数，峰值正好在
时选
），
属于右坡（斜率
）。所以在
处斜率减少
-
若
。
处斜率
（减少 1），
处斜率
（减少 1）。
-
-
在
-
在
-
void solve() {
int n, q;
cin >> n >> q;
vector<int> diff(n + 10, 0);
ll cur = 0;
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
cur += (a - 1);
if (b - a <= 2) {
diff[a] += 1;
if (b + 2 <= n + 5) {
diff[b + 2] += 1;
}
} else {
diff[a] += 1;
if (a + 2 <= n + 5) {
diff[a + 2] += 1;
}
int sum = a + b;
int m = sum / 2;
if (sum % 2 == 0) {
if (m + 1 <= n + 5) {
diff[m + 1] -= 2;
}
} else {
if (m + 1 <= n + 5) {
diff[m + 1] -= 1;
}
if (m + 2 <= n + 5) {
diff[m + 2] -= 1;
}
}
if (b <= n + 5) {
diff[b] += 1;
}
if (b + 2 <= n + 5) {
diff[b + 2] += 1;
}
}
}
vector<ll> ans(n + 1);
ll S = -n;
for (int k = 1; k <= n; ++k) {
S += diff[k];
cur += S;
ans[k] = cur;
}
for (int i = 0; i < q; ++i) {
int k;
cin >> k;
cout << ans[k] << " ";
}
cout << endl;
}
头文件
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define endl "\n"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using TIII = tuple<int, int, int>;
using TLLL = tuple<ll, ll, ll>;
constexpr int inf = (ll)1e9 + 7;
constexpr ll INF = (ll)2e18 + 9;
// constexpr ll INF = (ll)4e18;
// constexpr ll MOD = 1e9 + 7;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
void init() {
}
void solve() {
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
init();
int t = 1;
cin >> t;
for (int _ = 1; _ <= t; ++_) {
solve();
}
return 0;
}
京公网安备 11010502036488号