链接：https://ac.nowcoder.com/acm/contest/119895
A – ICPC Penalty
算法：
模拟。
思路：
无。
关键代码：
void miyan()
{
string s;
int n, t;
cin >> s >> n >> t;
if (s == "Accepted")
cout << t + 20 * (n - 1) << endl;
else
cout << 0 << endl;
}B – 小苯的无限数组
算法：
数学。
思路：
无。
关键代码：
void miyan()
{
ll n, k;
cin >> n >> k;
cout << n * (1ll << k) << endl;
}C – 小苯的真假游戏
算法：
模拟。
思路：
发现答案小于等于 \(2\)。
当钦定 \(a[1]\) 的话是否为真时，即可确定 \(a[n], a[n – 1], ….., a[2]\)，最后判断 \(a[2]\) 说的与钦定的值是否相等即可。
关键代码：
void miyan()
{
int n;
string s;
cin >> n >> s;
auto get = [&](bool flag) -> bool
{
bool cur = flag;
for (int i = n; i >= 1; --i)
{
if (cur)
cur = s[i % n] - '0';
else
cur = 1 - (s[i % n] - '0');
}
return (cur == flag);
};
cout << get(1) + get(0) << endl;
}D – 小苯的区间选数2.0
算法：
贪心。
思路：
设当前尝试选择的数字为 \(x\)，小根堆为 \(q\)，贪心策略：
- 将所有左边界小于等于 \(x\) 的区间都加入至堆中，弹出所有右边界小于 \(x\) 的区间，此时剩余的区间中都包含 \(x\)；
- 执行完上述操作后，如果队列为空，\(mex\) 只能为 \(x\)，否则在堆顶的区间中钦定 \(x\)，并弹出该区间，然后尝试选择 \(x + 1\)；
- 循环执行该操作，即可确定最终答案。
关键代码：
void miyan()
{
int n;
cin >> n;
vector<pii> a(n);
for (auto &[x, y] : a)
cin >> x >> y;
ranges::sort(a);
int mex = 0;
int idx = 0;
priority_queue<int, vector<int>, greater<>> q;
while (1)
{
while (idx < n && a[idx].first <= mex)
{
q.push(a[idx].second);
++idx;
}
while (q.size() && q.top() < mex)
q.pop();
if (q.empty())
break;
q.pop();
++mex;
}
cout << mex << endl;
}E – 小苯的GCD疑问1.0
算法：
打表。
思路：
打表发现对于任意的 \((l, r, k)\)，其最优答案都为 \(gcd = 1\) 的情况。
既选择所有的数字，使用等差数列求和公式计算答案即可。
关键代码：
void miyan()
{
ll l, r, k;
cin >> l >> r >> k;
cout << (l + r) * (r - l + 1ll) / 2ll - r << endl;
}F – 小苯的GCD疑问2.0
思路1：
打表。
打表发现最优 \(gcd\) 都集中在 \(\frac{n}{k}\) 周围，容易得到思路：尽可能多的枚举 \(\frac{n}{k}\) 周围的数字。
当钦定 \(gcd\) 为 \(d\) 时，那么在 \([1, n]\) 中 \(gcd\) 为 \(d\) 且元素个数最多数字集合是什么？容易想到该集合就是 \(d\) 的倍数的集合，定义 \(cnt\) 为集合大小。
对于 \(cnt\)，容易得到其值为 \(\lfloor \frac{n}{d} \rfloor\)。
那么关于 \(d\) 的答案就为：
\(d \times d \times (1 + cnt) \times cnt \div 2\)
此时就可以在 \(O(1)\) 的时间内得到 \(gcd\) 为 \(d\) 的答案。
代码：
void miyan()
{
ll n, k;
cin >> n >> k;
ll ans = 0;
for (ll d = n / k; d >= max(1ll, n / k - N); --d)
{
ll x = n / d;
ll start = d, end = x * d;
ll cur = (start + end) * x / 2 * d;
ans = max(ans, cur);
}
cout << ans << endl;
}思路 2：
整除分块。
枚举 \(gcd\)，钦定 \(gcd\) 为 \(d\)。
发现存在 \(d ∈ [l, r]\)，使得任意 \(\lfloor \frac{n}{d} \rfloor = \lfloor \frac{n}{l} \rfloor\)，那么关于 \([l, r]\) 的答案就为 \(\sum_{d = l}^{r} \lfloor \frac{n}{l} \rfloor\)，遂考虑整除分块优化。
void miyan()
{
ll n, k;
cin >> n >> k;
ll ans = 0;
for (ll l = 1, r; l <= n; l = r + 1)
{
ll cnt = n / l;
if (cnt < k)
break;
r = n / cnt;
ll start = r, end = n / r * r;
ll cur = (start + end) * cnt / 2 * r;
ans = max(ans, cur);
}
cout << ans << endl;
}
