A - Nine or Nein
- 预估难度：
入门 - 标签：条件分支
题意
给定两个正整数 \(A\) 和 \(B\)。
如果以下值中至少有一个等于 \(9\)，请输出 Nine；否则，请输出 Nein。
- \(A + B\)
- \(A - B\)
- \(A \times B\)
- \(A \div B\)
数据范围
- \(1 \leq A \leq 100\)
- \(1 \leq B \leq 100\)
代码
#include<bits/stdc++.h>
using namespace std;int main()
{int a, b;cin >> a >> b;if(a + b == 9 || a - b == 9 || a * b == 9 || a == 9 * b)cout << "Nine";elsecout << "Nein";return 0;
}
B - Survey Tabulation
- 预估难度：
普及- - 标签：字符串、计数思想
题意
高桥正在统计一项调查的结果。
共有 \(N\) 人参与了调查，第 \(i\) 个人的回答是一个由英文字母组成的字符串 \(S_i\)。
请找出本次调查中，给出相同回答的最多人数。
注意：回答中的字母不区分大小写。
例如，AtCoder、ATCODER 和 atcoder 均被视为相同的回答。
数据范围
- \(1 \leq N \leq 100\)
- \(S_i\) 仅包含大小写英文字母，且长度不超过 \(10\)
思路
将所有字符串统一转为大写或小写，然后根据计数思想，借助 map 或是手动维护 string 数组对每种字符串的出现次数进行统计即可。
代码
#include<bits/stdc++.h>
using namespace std;int main()
{map<string, int> cnt;int n, ans = 0;cin >> n;while(n--){string s;cin >> s;// 全部转大写for(int i = 0; i < s.size(); i++)if(s[i] >= 'a' && s[i] <= 'z')s[i] = s[i] - 'a' + 'A';// 记录出现次数 并取最大值ans = max(ans, ++cnt[s]);}cout << ans;return 0;
}
C - Cookies and Greedy Takahashi
- 预估难度：
普及- - 标签：排序、双指针
题意
在数轴上有 \(N\) 个位置放有饼干，第 \(i\) 块饼干的坐标为 \(A_i\)。
高桥最初位于数轴上的坐标 \(0\) 处，他将重复执行以下动作，直到捡起所有的 \(N\) 块饼干：
- 动作：移动到距离当前位置最近的饼干所在的坐标（如果存在多块这样的饼干，则选择坐标最小的那一块），并捡起该饼干。
请计算高桥在捡起所有饼干的过程中所移动的总距离。
数据范围
- \(1 \leq N \leq 3\times 10^5\)
- \(-10^9 \leq A_i \leq 10^9\)
- \(A_i\neq 0\) 且 \(A_i\) 互不相同
思路
记高桥过程中所在位置为 \(x\)。
首先根据“\(A_i \ne 0\) 且 \(A_i\) 互不相同”这两个条件可以得知，如果有多块饼干与坐标 \(x\) 的距离相同，这样的饼干有且只有两块，且一左一右。如果出现这样的情况，我们只需要优先拿左边（坐标较小）的那块即可。
因为高桥初始位置 \(x = 0\)，可以发现在过程中，如果高桥下一步选择往左捡饼干，那么这块饼干只可能是负半轴坐标最大的饼干；如果选择往右捡饼干，那么这块饼干只可能是正半轴坐标最小的饼干这两者之一。
因此我们只需要先对所有饼干按坐标排序，然后双指针维护满足 \(A_l \lt 0\) 且还没被捡走的饼干的最大下标 \(l\)，以及满足 \(A_r \gt 0\) 且还没被捡走的饼干的最小下标 \(r\)，即可直接 \(O(N)\) 模拟。
时间复杂度 \(O(N\log N)\)。
代码
#include<bits/stdc++.h>
using namespace std;int n, a[300005];int main()
{cin >> n;for(int i = 1; i <= n; i++)cin >> a[i];sort(a + 1, a + n + 1);int r = upper_bound(a + 1, a + n + 1, 0) - a; // > 0 的最小下标int l = r - 1; // < 0 的最大下标int x = 0; // 当前坐标long long ans = 0;// 两边饼干都还没捡完while(l >= 1 && r <= n){if(x - a[l] <= a[r] - x) // 左边更近{ans += x - a[l];x = a[l--];}else // 右边更近{ans += a[r] - x;x = a[r++];}}// 如果某一边还没捡完，直接按顺序捡while(l >= 1){ans += x - a[l];x = a[l--];}while(r <= n){ans += a[r] - x;x = a[r++];}cout << ans;return 0;
}
D - Chargers
- 预估难度：
普及 - 标签：优先队列、数学
题意
有一个拥有无限个充电槽的充电器。在时间 \(0\) 时，所有充电槽均为空。
每块电池的最大容量为 \(V\)。当电池插入充电槽时，其电量会以 \(1\) 的速率进行充电（即每经过 \(1\) 单位时间，电量增加 \(1\)），直到电量达到最大容量。
请按顺序处理 \(Q\) 个查询。
第 \(q\) 个查询的格式为以下两种之一，保证 \(t_1 < \dots < t_Q\)。
- 类型 1（\(1\) \(t_q\) \(w_q\)）：在时间 \(t_q\)，将一块电量为 \(w_q\) 的电池插入一个充电槽。
- 类型 2（\(2\) \(t_q\)）：在时间 \(t_q\)，将当前电量最高的电池从充电槽中拔出，并输出该电池的电量。如果没有任何电池插在充电槽中，则输出
-1。
数据范围
- \(1 \leq Q \leq 3 \times 10^5\)
- \(1 \leq V \leq 10^9\)
- 对于第 1 种询问： \(1 \leq t_q \leq 10^9\)，\(0 \leq w_q \leq V\)
- 对于第 2 种询问： \(1 \leq t_q \leq 10^9\)
- \(t_1 < \dots < t_Q\)
思路
如果我们在时间 \(x\) 将一块电量为 \(w\) 的电池插入充电槽，然后在时间 \(y\) 将其取出，暂不考虑最大容量的限制，那么其电量可以描述为 \(w + y - x\)。
由于每次询问 2 会给定一个终止充电的时间，然后询问电量最大的电池，也就相当于上式的 \(y\) 是给定的。那么为了找出 \(w+y-x\) 最大的电池，我们只需要在所有充电槽中找出 \(w - x\) 最大的那一块电池即可。
因此，每当有一块电量为 \(w\) 的电池在时间 \(x\) 插入充电槽，我们只需要借助容器直接维护 \(w-x\) 这一数值，能够实现每次取最大值并快速移除即可。这里可以借助优先队列或是 multiset。
最后考虑最大容量的限制，可以发现当 \(w+y-x \gt V\) 时，此时我们需要将电池电量直接当 \(V\) 看，但这并不影响我们每次取最大值的操作，只需要在最后输出实际电量时记得和 \(V\) 取个 \(\min\) 再输出即可。
时间复杂度 \(O(Q\log Q)\)。
代码
#include<bits/stdc++.h>
using namespace std;int main()
{priority_queue<int> pq; // 维护 初始电量-开始充电时间 的最大值int Q, V;cin >> Q >> V;while(Q--){int op, t, w;cin >> op >> t;if(op == 1){cin >> w;pq.push(w - t);}else{if(pq.empty())cout << "-1\n";else{cout << min(V, pq.top() + t) << "\n";pq.pop();}}}return 0;
}
E - Sum of Square of Sum
- 预估难度：
普及+/提高 - 标签：组合数学
题意
有 \(N\) 个球，分别编号为 \(1\) 到 \(N\)。第 \(i\) 个球上写有一个整数 \(A_i\)。
对于从这 \(N\) 个球中选出若干个球的一种方案，定义该方案的得分为：选出的所有球的数字之和的平方。
请计算从 \(N\) 个球中选出 \(K\) 个球的所有 \(\binom{N}{K}\) 种方案的得分之和，结果对 \(998244353\) 取模。
数据范围
- \(1 \leq K \leq N \leq 2\times 10^5\)
- \(1 \leq A_i \leq 10^9\)
思路
当 \(K=1\) 时，答案即 \(\sum\limits_{i=1}^N A_i^2\)。
当 \(K\gt 1\) 时，记选出的数为 \(B_1, B_2, \ldots, B_K\)，那么得分即：
单独考虑左右两部分贡献。
- 对于左半部分，单独考虑每个元素 \(A_i\) 的贡献：
- 如果 \(A_i\) 被选中，对应的方案数共 \(\binom{N-1}{K-1}\) 种。
- 此时 \(A_i\) 对左半部分产生的贡献为 \(A_i^2\)，那么所有 \(A_i\) 的总贡献即 \(\sum\limits_{i=1}^N A_i^2\)。
- 可得整个左半部分对最终答案的贡献为 \(\binom{N-1}{K-1} \sum\limits_{i=1}^N A_i^2\)。
- 对于右半部分，考虑前后两个元素 \(A_i, A_j\) \((i \lt j)\) 的贡献：
- 如果 \(A_i, A_j\) 两数被同时选中，对应的方案数共 \(\binom{N-2}{K-2}\) 种。
- 此时元素对 \(A_i, A_j\) \((i \lt j)\) 对右半部分产生的贡献为 \(A_iA_j\)，那么所有元素对的总贡献即 \(\sum\limits_{i=1}^K\sum\limits_{j=i+1}^K A_iA_j = \dfrac{(\sum\limits_{i=1}^N A_i)^2 - \sum\limits_{i=1}^N A_i^2}{2}\)。
- 可得整个右半部分对最终答案的贡献为 \(\binom{N-2}{K-2} \left ( (\sum\limits_{i=1}^N A_i)^2 - \sum\limits_{i=1}^N A_i^2 \right )\)
因此答案为：
时间复杂度 \(O(N + \log N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const ll mod = 998244353;int n, k;
ll a[200005];ll fac[200005], inv[200005];ll qpow(ll a, ll n)
{ll r = 1;while(n){if(n & 1)r = r * a % mod;a = a * a % mod;n >>= 1;}return r;
}void init(int n)
{fac[0] = 1;for(int i = 1; i <= n; i++)fac[i] = fac[i - 1] * i % mod;inv[n] = qpow(fac[n], mod - 2);for(int i = n - 1; i >= 0; i--)inv[i] = inv[i + 1] * (i + 1) % mod;
}ll getC(int n, int m)
{if(n < m)return 0;return fac[n] * inv[m] % mod * inv[n - m] % mod;
}int main()
{cin >> n >> k;init(n);ll sum = 0; // 总和ll sum2 = 0; // 平方和for(int i = 1; i <= n; i++){cin >> a[i];sum = (sum + a[i]) % mod;sum2 = (sum2 + a[i] * a[i]) % mod;}if(k == 1)cout << sum2 << "\n";else{ll ans = getC(n-1, k-1) * sum2 % mod;ans = (ans + getC(n-2, k-2) * ((sum * sum % mod - sum2 + mod) % mod)) % mod;cout << ans << "\n";}return 0;
}