1. 字符串拆分
定义 f(x) 为字符串 s 中不同的字符数量，例如 f(abc)=3、f(TTTTT)=1 或 f(TxTxyTxTx)=3。
给定一个字符串 s，将它分成两个非空子串 a 和 b，使得 f(a)+f(b) 是可能的最大值，请你计算该最大值。
要求支持多组数据测试
限制：
- 1⩽
- 2 \leqslant n \leqslant 2 \times 10^5，\sum n \leqslant 2 \times 10^5
算法分析
本题难度中等，考察字符串基础、数组计数和前缀和技巧。枚举分界点 i，计算分界点 i 左右两边各出现不同字符的数量，这里可以使用数组计数+前缀和优化。
当分界点从 i-1 变为 i 时：
左子串多了一个字符 s_i，右子串少了一个字符 s_i
若左子串加入 s_i 之后且 s_i 的个数为 1，那么左子串的不同字符的个数 ++
若右子串去掉 s_i 之后且 s_i 的个数为 0，那么右子串的不同字符的个数 --
初始时，左子串为空，右子串为 s_0 \sim s_{n-1}
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
void solve() {
int n;
string s;
cin >> n >> s;
int ans = 0;
int cntl = 0, cntr = 0;
vector<int> pre(130), suf(130);
rep(i, n) if (++suf[s[i]] == 1) cntr++;
rep(i, n-1) {
if (++pre[s[i]] == 1) cntl++;
if (--suf[s[i]] == 0) cntr--;
ans = max(ans, cntl+cntr);
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}
2. 龙虎斗（二）
轩轩和凯凯正在玩一款叫《龙虎斗》的游戏，游戏的棋盘是一条线段，线段上有 n 个兵营（自左至右编号 1 \sim n），相邻编号的兵营之间相隔 1 厘米，即棋盘为长度为 n-1 厘米的线段。i 号兵营里有 c_i 位工兵。 下图为 n=6 的示例：
轩轩在左侧，代表“龙”；凯凯在右侧，代表“虎”。 他们以 m 号兵营作为分界， 靠左的工兵属于龙势力，靠右的工兵属于虎势力，而第 m 号兵营中的工兵很纠结，他们不属于任何一方。
一个兵营的气势为：该兵营中的工兵数 \times 该兵营到 m 号兵营的距离；参与游戏一方的势力定义为：属于这一方所有兵营的气势之和。下图为 n=6,m=4 的示例，其中红色为龙方，黄色为虎方：
现在告诉你每一个兵营的工兵数量，请你设定分界兵营，使龙虎双方的气势差值最小。请求出这个最小差值
限制：
- 1 \leqslant n \leqslant 10^5
- 0 \leqslant c_i \leqslant 10^9
算法分析
本题难度中等，考察枚举思想与前缀和技巧。枚举分界点 i，能够发现当分界点从 i-1 移动到 i 时，左边总和增加 a_1 + a_2 + \cdots + a_{i-1}，右边总和减少 a_i + a_{i+1} + \cdots + a_n，计算这部分区间和可以使用前缀和技巧。
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<ll> c(n);
rep(i, n) cin >> c[i];
vector<ll> s(n);
s[0] = c[0];
for (int i = 1; i < n; ++i) s[i] = s[i-1]+c[i];
ll ans = 9e18, sumL = 0, sumR = 0;
for (int i = 1; i < n; ++i) {
sumR += i*c[i];
}
ans = min(ans, sumR);
for (int i = 1; i < n; ++i) {
sumL += s[i];
sumR -= s[n-1]-s[i];
ans = min(ans, abs(sumL-sumR));
}
cout << ans << '\n';
return 0;
}
3. 发积分
猴博士欠了小猴很多积分，他要在接下来 k 次课内发给小猴至少 n 分。
猴博士打算这样发积分：首先在第 1 次课发 x 分，第 2 次课发 \lceil x/2 \rceil⌉ 分，依次类推，在第 i 次课发 \lceil x/i \rceil 分。其中 \lceil y \rceil 表示大于等于 y 的最小整数。
如果 x 的值太大，积分会就很快发完了。所以猴博士要在前 k 次课发出的积分大于等于 n 分的前提下，找一个最小的 x。
限制：
- 1 \leqslant n \leqslant 10^{12}
- 1 \leqslant k \leqslant 10^6
算法分析
显然，x=n 时，可以满足要求：
\lceil\frac{x}{1}\rceil + \lceil\frac{x}{2}\rceil + \cdots + \lceil\frac{x}{k}\rceil \geqslant n
答案要求 x_{\min}，而 [x_{\min}, n] 中的任何值都满足要求。
考虑到可能的答案分成了两段，可以考虑使用二分答案法。
二分答案 = 二分框架 + 判定函数。
判断：对于当前的二分值 x，是否满足：
\lceil\frac{x}{1}\rceil + \lceil\frac{x}{2}\rceil + \cdots + \lceil\frac{x}{k}\rceil \geqslant n
每次判断时间复杂度 O(k)，二分范围为 [1, n]。
总时间复杂度 O(k\log n)。
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
ll n; int k;
cin >> n >> k;
ll wa = 0, ac = n;
while (ac-wa > 1) {
ll wj = (ac+wa)/2;
auto ok = [&]{
ll res = 0;
for (int i = 1; i <= k; ++i) {
res += (wj+i-1)/i;
}
return res >= n;
}();
(ok ? ac : wa) = wj;
}
cout << ac << '\n';
return 0;
}
4. 中位数（二）
中位数，就指将所有数字排序后，位置在最中间的数。
给定 n 个数字的序列 a_1,a_2,…,a_n，以及一个期望中位数 x。小爱想知道，最少再添加多少个数字，才能使序列中包含奇数个数字，且 x 为该序列的中位数？
限制：
- 1 \leqslant n \leqslant 10^5
- -10^9 \leqslant x, a_i \leqslant 10^9
算法分析
本题难度中等，记小于 x 的个数为 x_l，大于 x 的个数为 x_r，则等于 x 的个数为 c = n - x_l - x_r。如果 |x_l - x_r| \geqslant c 说明需要可以把 c-1 个 x 全分给其中一边，不够的再添加新的元素，否则说明需要 x 分配给左右两边，具体来说，先分给其中一边使得两边的数量相同，剩下中间的元素 x 会有多个，那么再平均分给两边，要保证总个数必须是奇数，那么中间剩下的元素个数为偶数就需要再添加一个元素。
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
int x;
cin >> x;
int cntl = 0, cntr = 0, cntx = 0;
rep(i, n) {
if (a[i] > x) cntr++;
if (a[i] < x) cntl++;
if (a[i] == x) cntx++;
}
if (cntx == 0) cout << 1+abs(cntl-cntr) << '\n';
else if (abs(cntl-cntr) >= cntx-1) cout << abs(cntl-cntr)-(cntx-1) << '\n';
else {
int d = cntx-1-abs(cntl-cntr);
if (d%2 == 0) puts("0");
else puts("1");
}
return 0;
}
5. 团队竞赛
信息学竞赛在不同的比赛中，通常有不同的赛制，其中就有一种由 3 位选手组队的团体比赛。
现有 n 名学生，其中第 i 名学生有编程能力值 a_i，小爱老师需要从中选出 3 名选手参加本次比赛。为了不让团队的实力过于悬殊，他希望选出的 3 名选手相互之间能力值之差不超过 X。
请你帮助小爱老师计算一下，有多少种组队方法？
（注意：相同的三位学生组队，只计一种选法，即不考虑选出学生相互之间的先后顺序）
限制：
- 1 \leqslant n \leqslant 10^5
- 1 \leqslant a_i, X \leqslant 10^9
算法分析
先对数组 a 按从小到大的顺序进行排序
然后注意到若 a_i \leqslant a_i+x，那么区间 [i+1, j] 中的数都是可以选的（其中 j 表示满足 a_j \leqslant a_i+x 的最大的 j），那么从其中挑选两个数的方案数就是 \binom{j-i}{2}
那么如何找最大的 j？
可以用 upper_bound 来实现
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, x;
cin >> n >> x;
vector<int> a(n);
rep(i, n) cin >> a[i];
sort(a.begin(), a.end());
ll ans = 0;
rep(i, n) {
int r = upper_bound(a.begin(), a.end(), a[i]+x) - a.begin() - 1;
ll num = r-i;
ans += num*(num-1)/2;
}
cout << ans << '\n';
return 0;
}
6. 出栈序列
如果栈顶字符的子典序 \leqslant \min(S[i:n])，则需要出栈
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
string s;
cin >> n >> s;
string r(n+1, 'z'+1);
for (int i = n-1; i >= 0; --i) {
r.at(i) = min(r.at(i+1), s.at(i));
}
stack<char> stk;
rep(i, n+1) {
while (stk.size() and stk.top() <= r.at(i)) {
cout << stk.top();
stk.pop();
}
if (i < n) stk.push(s.at(i));
}
return 0;
}
7. 大胃王比赛
高桥君参加大胃王比赛。比赛由 N 人组成的团队为基本单位参赛，高桥君的队伍的队员从 1\sim N 编号。第 i 名队员的消化代价为 A_i。
比赛有 N 种不同的食物，第 i 名队员负责吃第 i 种食物。第 i 种食物的难吃程度为 F_i。 消化代价 x 的队员吃完难吃程度 y 的食物需要花费 x\times y 秒。 整个队伍的成绩是 N 名队员吃完食物花费时间的最大值。
比赛前，高桥君的队伍会进行修行。一次修行可以将一名消化代价大于 0 的队员的消化代价减少 1。由于修行需要消耗庞大的食费，因此最多只能进行 K 次修行。
通过适当选择每位队员修行的次数，高桥队在比赛中能够获得的最好成绩是多少？
限制：
- 1 \leqslant N \leqslant 2 \times 10^5
- 0 \leqslant K \leqslant 10^{18}
- 1 \leqslant A_i \leqslant 10^6
- 1 \leqslant F_i \leqslant 10^6
算法分析
注意到，随着修行次数增多，成绩一定不会变差，所以可以二分答案。对于成绩 x，计算要使得每名队员的时间都小于等于 x，所需的最小修行次数。对每人计算要让 A_iF_i \leqslant x，A_i 需要减少的次数。最后判断修行总次数是否小于等于 K。
代码实现
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n; ll k;
cin >> n >> k;
vector<int> a(n), f(n);
rep(i, n) cin >> a[i];
rep(i, n) cin >> f[i];
ll wa = -1, ac = 1e12;
while (ac-wa > 1) {
ll wj = (ac+wa)/2;
bool ok = [&]{
ll s = 0;
rep(i, n) s += max(0ll, a[i]-wj/f[i]);
return s <= k;
}();
(ok ? ac : wa) = wj;
}
cout << ac << '\n';
return 0;
}
8. 最大频差
对于一个字符串，我们认为这个字符串中出现次数最多的字符所出现的次数，与出现次数最少的字符所出现次数的差值，称为该字符串的频差，以此来量化这个字符串中字符出现的频率是否均匀。
例如，字符串 s=’helloworld’，出现次数最多的字符是 l，出现了 3 次，出现次数最少的字符是 h，出现了 1 次，因此我们认为这个字符串的频差为 2。
现给定一个字符串ss，请问其所有子串的频差中，最大频差为多少？
限制：
- 1 \leqslant |s| \leqslant 5 \times 10^5
算法分析
枚举最多和最少的字符+最大子段和dp，具体可以参考 LC2272. 最大波动的子字符串
另外这题曾出现在noip模拟赛中
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
string s;
cin >> s;
unordered_map<char, vector<int>> idx;
rep(i, s.size()) idx[s[i]].push_back(i);
int ans = 0;
for (auto&& [c0, id0] : idx) {
for (auto&& [c1, id1] : idx) {
if (c0 == c1) continue;
int i = 0, j = 0;
int f = 0, g = INT_MIN;
while (i < id0.size() or j < id1.size()) {
if (j == id1.size() or (i < id0.size() and id0[i] < id1[j])) {
g += 1;
f = max(f, 0)+1;
++i;
}
else {
g = max({f, g, 0})-1;
f = max(f, 0)-1;
++j;
}
ans = max(ans, g);
}
}
}
cout << ans << '\n';
return 0;
}
9. [GESP样题 八级] 区间
可以用 map<int, vector<int>> 来维护值为 x 的所有下标
然后对于询问，只需做两次二分即可
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
unordered_map<int, vector<int>> mp;
rep(i, n) mp[a[i]].push_back(i);
int q;
cin >> q;
rep(qi, q) {
int l, r, x;
cin >> l >> r >> x;
--l;
auto is = mp[x];
int ans = lower_bound(is.begin(), is.end(), r) - lower_bound(is.begin(), is.end(), l);
cout << ans << '\n';
}
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int t;
cin >> t;
while (t--) solve();
return 0;
}
10. K-th Sum
假设答案为 x，原问题可以转化成满足小于 x 的数对和不超过 k-1 个中 x 的最大值
二分答案即可
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n; ll k;
cin >> n >> k;
vector<int> a(n), b(n);
rep(i, n) cin >> a[i];
rep(i, n) cin >> b[i];
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int ac = 0, wa = 2e9+5;
while (abs(ac-wa) > 1) {
int wj = (ac+wa)/2;
auto ok = [&]{
ll cnt = 0;
rep(i, n) {
int j = lower_bound(b.begin(), b.end(), wj-a[i]) - b.begin();
cnt += j;
}
return cnt <= k-1;
}();
(ok ? ac : wa) = wj;
}
cout << ac << '\n';
return 0;
}
11. Nearest Smaller Values
给定一个长度为 n 的序列 a，为数组每个值找到它左边小于它的最近的位置。如果不存在，输出 0。
限制：
- 1 \leqslant n \leqslant 2 \times 10^5
- 1 \leqslant a_i \leqslant 10^9
算法分析
维护一个单调递增的单调栈
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
stack<int> stk;
vector<int> ans;
rep(i, n) {
while (stk.size() and a[stk.top()] >= a[i]) stk.pop();
if (stk.size()) ans.push_back(stk.top()+1);
else ans.push_back(0);
stk.push(i);
}
for (int x : ans) cout << x << ' ';
return 0;
}
12. Subarray Distinct Values
给定一个长度为 n 的序列 a，统计有多少个子数组至多有 k 个不同的数。
限制：
- 1 \leqslant k \leqslant n \leqslant 2 \times 10^5
- 1 \leqslant a_i \leqslant 10^9
算法分析
维护一个大小不超过 k 的滑动窗口，同时用 std::unordered_map 来维护窗口内每个数的频率
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
rep(i, n) cin >> a[i];
ll ans = 0;
unordered_map<int, int> mp;
int l = 0;
rep(r, n) {
mp[a[r]]++;
while (mp.size() > k) {
mp[a[l]]--;
if (mp[a[l]] == 0) mp.erase(a[l]);
l++;
}
ans += r-l+1;
}
cout << ans << '\n';
return 0;
}
13. CF190D
给定一个长度为 n 的序列 a，求有多少个连续子区间满足区间中的众数的出现次数 \geqslant k
限制：
- 1 \leqslant k \leqslant n \leqslant 4 \times 10^5
- 1 \leqslant a_i \leqslant 10^9
算法分析
考虑使用双指针。
固定左指针 l，移动右指针 r 使得 cnt[a_r] + 1 = k，那么满足 t \in [r, n) 的区间 [l, t] 都是合法区间
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
rep(i, n) cin >> a[i];
ll ans = 0;
int j = 0;
map<int, int> mp;
rep(i, n) {
while (j < n and mp[a[j]]+1 < k) {
mp[a[j]]++; ++j;
}
ans += n-j;
mp[a[i]]--;
}
cout << ans << '\n';
return 0;
}
14. Prison Escape
一座监狱由 N \times M 的网格构成，每个格子中仅包含字符 0 或 1，0 表示囚犯，1 表示警卫。
囚犯每次可以向左、右、上、下移动一格。
囚犯如果走出监狱之外就可以逃出监狱，形式上，如果他走到任意一个满足以下任意条件的格子 (x, y) 时：x=0 或 y=0 或 x>n 或 y>m 。
令囚犯逃离监狱的时间为在逃出监狱之前需要越过警卫的最少次数
求出任意囚犯的最慢越狱时间。
限制：
- 1 \leqslant N, M \leqslant 3 \times 10^5
算法分析
从边界点开始做多源01bfs
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int, int>;
const int di[] = {0, 1, 0, -1};
const int dj[] = {1, 0, -1, 0};
void solve() {
int n, m;
cin >> n >> m;
vector<string> s(n);
rep(i, n) cin >> s[i];
vector a(n, vector<int>(m));
rep(i, n)rep(j, m) a[i][j] = s[i][j]-'0';
const int INF = 1001001001;
vector dist(n, vector<int>(m, INF));
deque<P> q;
rep(i, n)rep(j, m) {
if (i == 0 or j == 0 or i == n-1 or j == m-1) {
dist[i][j] = a[i][j];
if (a[i][j]) q.emplace_back(i, j);
else q.emplace_front(i, j);
}
}
while (q.size()) {
auto [i, j] = q.front(); q.pop_front();
int d = dist[i][j];
rep(v, 4) {
int ni = i+di[v], nj = j+dj[v];
if (ni < 0 or ni >= n or nj < 0 or nj >= m) continue;
int nd = d+a[ni][nj];
if (dist[ni][nj] <= nd) continue;
dist[ni][nj] = nd;
if (a[i][j]) q.emplace_back(ni, nj);
else q.emplace_front(ni, nj);
}
}
int ans = 0;
rep(i, n)rep(j, m) if (!a[i][j]) {
ans = max(ans, dist[i][j]);
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}
15. CF460C
藤藤有一个长度为 n 的数组 a
现在藤藤希望改变这个数组，使得这个数组的最小值尽可能的大。
现在藤藤可以施展 m 次魔法，每次魔法可以使得连续长度为 w 的一段每个元素 +1。
藤藤想知道最终这个数组的最小值最大可以达到多少？
限制：
- 1 \leqslant w \leqslant n \leqslant 10^5
- 1 \leqslant m \leqslant 10^5
- 1 \leqslant a_i \leqslant 10^9
算法分析
二分答案，假设为 x
可以一次性对某个 a_i 加上 d 使得他达到 x，那么相应的区间 [i, i+w) 里的数也要跟着加上 d，我们可以仅维护每个位置的增量标记，以及大小为 w 的窗口中的增量标记总和 tot，如果某个数 a_j 在这个窗口中的话，a_j \to a_j + tot
最后只需判定所有位置的增量标记总和是否不超过 m 即可
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, m, w;
cin >> n >> m >> w;
vector<int> a(n);
rep(i, n) cin >> a[i];
ll ac = 0, wa = 2e9;
while (abs(ac-wa) > 1) {
ll wj = (ac+wa)/2;
auto ok = [&]{
ll tot = 0;
vector<ll> c(n);
rep(i, n) {
if (i >= w) tot -= c[i-w];
c[i] = max(0ll, wj-(a[i]+tot));
tot += c[i];
}
return reduce(c.begin(), c.end()) <= m;
}();
(ok ? ac : wa) = wj;
}
cout << ac << '\n';
return 0;
}
16. 三色地图
有一个国家有 n 个城市，城市之间由 m 条双向道路连接。第 i 条道路连接城市 a_i,b_i。有道路直接连接的城市称作相邻的城市。
现在要制作国家的地图，要对每个城市染色，用三种不同的颜色（红绿蓝）中的一种做上标记，并且使得相邻城市的颜色不同。
问一共有多少种标记颜色的方式？
限制：
- 1 \leqslant n \leqslant 20
- 1 \leqslant m \leqslant \frac{n(n-1)}{2}
算法分析
用dfs一边遍历每个点，一边枚举每个颜色的点
直接枚举每个点的颜色是 O(3^n) 会超时。所以在搜索时，要判断当前颜色是否和相邻点同色，如果同色要剪枝。原图不一定是连通的，所以要对每个连通块做染色搜索，将每个连通块的染色方案数相乘即为答案
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> to(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
}
ll ans = 1;
vector<bool> used(n);
vector<int> vs;
vector<int> col(n, -1);
auto dfs = [&](auto& f, int v) -> void {
if (used[v]) return;
used[v] = true;
vs.push_back(v);
for (int u : to[v]) f(f, u);
};
ll now = 0;
auto dfs2 = [&](auto& f, int i) -> void {
if (i == vs.size()) { now++; return; }
int v = vs[i];
rep(c, 3) {
col[v] = c;
bool ok = true;
for (int u : to[v]) {
if (col[u] == c) ok = false;
}
if (!ok) continue;
f(f, i+1);
}
col[v] = -1;
};
rep(i, n) if (!used[i]) {
ans *= 3;
vs = vector<int>();
dfs(dfs, i);
col[vs[0]] = 0;
now = 0;
dfs2(dfs2, 1);
ans *= now;
}
cout << ans << '\n';
return 0;
}
17. Passing（★5）
给定一张包含 N 个点和 M 条边的无向图，第 i 条边连接点 A_i 和点 B_i，且边权为 C_i。
对于 k = 1, 2, \cdots, N，求从点 1 出发经过点 k 到达点 N 的最短路。
限制：
- 2 \leqslant N \leqslant 10^5
- 1 \leqslant M \leqslant \min(10^5, \frac{N(N-1)}{2})
- 1 \leqslant A_i < B_i \leqslant N
- 没有重边
- 1 \leqslant C_i \leqslant 10000
- 任意两点之间都是连通的
算法分析
答案就是从点 1 走到点 k 的最短路加上从点 k 走到点 N 的最短路。而从点 k 走到点 N 的最短路又等价于从点 N 走到点 k 的最短路。所以，我们只需跑两遍 \operatorname{Dijkstra} 即可
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int, int>;
int main() {
int n, m;
cin >> n >> m;
vector<vector<P>> g(n);
rep(i, m) {
int a, b, c;
cin >> a >> b >> c;
--a; --b;
g[a].emplace_back(b, c);
g[b].emplace_back(a, c);
}
auto f = [&](int sv) {
const int INF = 1001001001;
vector<int> dist(n, INF);
priority_queue<P, vector<P>, greater<P>> q;
dist[sv] = 0; q.emplace(0, sv);
while (q.size()) {
auto [d, v] = q.top(); q.pop();
if (dist[v] != d) continue;
for (auto [u, w] : g[v]) {
int nd = d+w;
if (dist[u] <= nd) continue;
dist[u] = nd;
q.emplace(nd, u);
}
}
return dist;
};
auto s = f(0);
auto t = f(n-1);
rep(i, n) cout << s[i]+t[i] << '\n';
return 0;
}
18. xor问题
给定一个包含 n 个正整数构成的序列 a，要求选择一个非空子序列使得它的异或和恰好为 0，求方案数。并对结果模 10^9 + 7
限制：
- 1 \leqslant n \leqslant 10^6
- 1 \leqslant a_i \leqslant 10^9
算法分析
暴力dp：
记 dp[i][j] 表示从前 i 个数中选取若干个数使得异或和等于 j 的方案数
转移：
dp[i][j] = dp[i-1][j] + dp[i-1][j^a[i]];
初始化：
dp[0][0] = 0
最后的答案为 dp[n][0]-1
时间复杂度为 \mathcal{O}(n^2a_i)
优化dp：
一个经典结论：
- \leqslant x 的若干数异或起来不会超过 2x
对于每个 i，j 只异或到 2a_i 即可，不会损失方案
时间复杂度为 \mathcal{O}(\sum a_i)
正解：
将所有数插入线性基，设线性基的大小为 r，则答案为 2^{n-r}-1 。
考虑 n-r 个不在线性基里的数，选择其 1 个非空子集，都可以用若干线性基里的数把异或和凑成 0，这部分答案为 2^{n-r}
考虑只用 r 个线性基里的数，其任意非空子集的异或和不为 0，这部分没有贡献。
- 任意异或和为 0 的非空子集，必须包含若干 n-r 个不在线性基里的数
用上述性质把对【异或和为 0 的非空子集】的计数，转化为【不在线性基里的数的非空子集】计数，一一对应，总复杂度为 \mathcal{O}(n\log a_i) 。
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
const int K = 31;
struct bitbase {
vector<int> d;
bitbase(): d(K) {}
bool add(int x) {
x = tomin(x);
if (x == 0) return false;
for (int i = K-1; i >= 0; --i) {
if (x>>i&1) {
rep(j, K) if (d[j]>>i&1) d[j] ^= x;
d[i] = x;
return true;
}
}
}
int tomin(int x) {
for (int i = K-1; i >= 0; --i) {
if (x>>i&1) x ^= d[i];
}
return x;
}
int size() {
int res = 0;
rep(i, K) if (d[i]) res++;
return res;
}
};
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n;
cin >> n;
bitbase b;
rep(i, n) {
int a;
cin >> a;
b.add(a);
}
mint ans = mint(2).pow(n-b.size());
ans -= 1;
cout << ans << '\n';
return 0;
}
19. 一的数量
给定一个整数 n，请问从 1 开始到 n 结束的所有整数的二进制表示中，共计有多少个 1 ？
限制：
- 1 \leqslant n \leqslant 2^{50}
算法分析
考虑第 i 位，可以发现 2^i 个 0 和 2^i 个 1 交替出现
那么周期就是 2^{i+1}，那么一个完整周期的贡献就是 2^i，而剩下不足一个周期的部分(假设为 r)的贡献就是 \max(0, r-2^i+1)
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
ll n;
cin >> n;
n++;
ll ans = 0;
rep(i, 51) {
ll p = 2ll<<i;
ll r = n%p;
ans += (n-r)/2;
if (r >= (1ll<<i)) {
ans += r-(1ll<<i);
}
}
cout << ans << '\n';
return 0;
}
20. 前缀第k大
给出一个数列 a_1,a_2, \cdots, a_n，保证数列中的数互不相同。再给一个正整数 k。对 i=k,k+1, \cdots, n 求：
- 将数列 a 的前 i 项从大到小排序后，第 k 个数的值。
限制：
- 1 \leqslant k \leqslant n \leqslant 5 \times 10^5
- 1 \leqslant a_i \leqslant n
算法分析
本题实际上求的是前 k 大的数中最小的数，如果能用一个数据结构存放前 k 大的数，并能同时维护最小值，就可以解决这个问题。小根堆可以完成这个任务。
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
rep(i, n) cin >> a[i];
priority_queue<int, vector<int>, greater<int>> q;
rep(i, k-1) q.push(a[i]);
for (int i = k-1; i < n; ++i) {
q.push(a[i]);
if (q.size() == k+1) q.pop();
cout << q.top() << '\n';
}
return 0;
}
21. 社团展示
某学校共有 n 个社团，其中第 i 个社团中有学生 x_i 名。
恰逢学校社团节，社团节内有一项跨社团作品展示活动，每件作品需要由至少 m 个不同社团的成员合作完成，且每个学生只能参与一个作品。
请问，按给定社团数量及每个社团的人数，最多能完成多少件作品？
限制：
- 1 \leqslant n, m \leqslant 10^5
- 1 \leqslant x_i \leqslant 10^9
算法分析
二分作品数量 P
判断能否完成 P 个作品时，用贪心法，优先从人数多的社团取出社员来完成作品（直接模拟会超时，需要转化成不等式去判断）
每个社团最多可派出 \min(x_i, P) 人，假设所有社团总共派出 S 人
- 若 S < K \cdot P，说明显然不能完成 P 个作品
- 若 S \geqslant K \cdot P，是不是一定能完成 P 个作品？答案是肯定的，可以由反证法来证。
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, m;
cin >> n >> m;
vector<ll> x(n);
rep(i, n) cin >> x[i];
ll ac = 0, wa = 2e14/m;
while (wa - ac > 1) {
ll wj = (ac + wa) / 2;
ll s = 0;
rep(i, n) s += min(x[i], wj);
if (s >= m*wj) ac = wj; else wa = wj;
}
cout << ac << '\n';
return 0;
}
请问”典中典”是啥意思？
就是题目里用到的技巧很常见
恩，这种总结很好的。从模板题到新题之间，需要熟悉每一个知识点的套路技巧。话说能加一下你的微信或qq 讨论吗？谢谢