感觉这次集训的题目都没有很难，有的题目涉及到数学公式推导，有的是暑假期间练的很多的含数据结构优化或者贪心的思维题，还有就是dp和图论，以及一些字符串算法
1. dp {
- 线性dp 代表 ： D3T2( 护栏补片，双层枚举的一道线性dp) D4T2(双规格补给，分组背包问题）
- 树形dp代表 ： D3T5(恰好经过的检查站，dp统计最大总收益和达到总收益的合法路径数） D1T5(边界补偿，树形背包问题）
- 区间dp代表： D5T2(博弈类的区间dp) D2T5(双温反应，基础类型的区间dp)
- 状压dp代表： D4T5(旅行商问题变种）
}
2. 图论{
- 最短路代表： D2T6(连续通行证，多维迪杰斯特拉）
- 并查集代表： D2T4(雾中的检查站，反向建图的并查集） D5T4(双指标组网，带限制的最小生成树）
- LCA & 树状差分代表 ： D3T6(撤单后的共线压力，树状差分 + LCA）
- 树状数组代表： D3T4(菱形接收区，树状数组动态求和+矩阵优化取值范围）
- }
3. 数学{
代表：D4T3 (错峰亮灯日，周期性数学问题） D5T1(嵌套播报，字符串中的拼接组合问题）D2T3(双层展架， 数对问题）
}
4. 基础算法{
代表： D1T1(折返信号，栈优化） D1T3(安静与回声，map优化存数的下标）D1T4(维护间隔，堆优化）D2T1(撤下一条光带，枚举+前缀和优化） D3T1(单灯校验，枚举+二进制优化） D2T2(不能断开的货链，二分查找）
}
5.字符串算法{
代表：D4T4(双钥匙窗口，字符串哈希 \|\| KMP)
}
这些题目里面有考试的时候没写出来，听完后感觉很简单的，也有算法步骤特别复杂的，总之就是感觉至上，能秒的题就先秒，不能秒的慢慢推
代表例题：
1. D1T5(边界补偿， 树形背包问题）{
- 题意： 有一棵树，点 i 有收益
wi，边有非负补偿费ce。需要选择恰好 K个点，且这些点在树上连通。所选点的收益相加；每条恰有一个端点被选中的边需要支付一次补偿费。两端都选中或都未选中的边不收费。求最大净收益
2. 思路：如果能看出来这题就是在选与不选中做决策，每次到达一个新的节点时比较选择当前子树的收益和不选择当前子树的收益，那么这题就是一道很裸的树形背包问题（我就没看出来）。
但关键是选与不选的问题。我们设dp[u][k] 表示为走到第u个节点且我们已经选择了k个点时的最大净收益，那么当我们到达子树v时，如果选择子树v，那么 k+1，状态变为： dp[v][k + 1] = max(dp[v][k + 1], dp[u][k] + w[v]) （w[v]表示当前节点的权），但是如果我们不选子树v，我们就不可能会继续经过子树v的任何剩余节点（本题保证数据为一棵树），那么dp[v][k] = max(dp[v][k], dp[u][k] - c) （减c是因为我们之前选择的u为单一节点，所以要减去父边的赔偿），最后将原树大小与子树大小合并，并覆盖原来的dp数组的状态，继续前进，直到选满k个节点为止
3.算法： 树形dp
4. 时间复杂度：O (n^2)完全可以通过n <= 2500
5.核心代码：
vector<long long> tmp(min(K, sz[u] + sz[v]) + 1, -INF);//覆盖状态
for (int j = 1; j <= min(K, sz[u]); ++j) {
if (dp[u][j] == -INF) continue;
tmp[j] = max(tmp[j], dp[u][j] - c);//不选子树v,减去边的赔偿
for (int k = 1; k <= min(K - j, sz[v]); ++k) {
if (dp[v][k] == -INF) continue;// 状态不可达
tmp[j + k] = max(tmp[j + k], dp[u][j] + dp[v][k]);//选当前子树，总和为原子树权值加上新子树权值
}
}
sz[u] += sz[v];
for (int j = 1; j <= min(K, sz[u]); ++j) {
dp[u][j] = tmp[j];
}
}
2. D2T6(连续通行证，多维dijkstra){
- 题意： 有向图中，每条边有正通行费。需要从点 1 到点 n，允许重复经过点和边。你最多使用 K 张通行证。每张证统一支付 C，连续覆盖接下来至少 1 条、至多 L 条边，覆盖边无需另付通行费；可提前结束覆盖。两张证的覆盖不能重叠，但可以紧邻。未覆盖的边按原费支付。求最小费用，不可达输出 -1。
2. 思路：
这题给人的第一感觉就是最短路，初始化一个负无穷的dist数组。但这题有个限制条件很烦人，就是我们可以使用通行证来跳过需要付费的边，而且每张通行证最多能覆盖L条边，并且还能提前结束覆盖，因此我们就必须要增加dist的维度.
定义: dist[u][k][l] : 表示到第u个点且已经使用了k张通行证，且当前所使用的通行证已经覆盖了L条边的最小代价,cost为当前的普通代价
分类讨论： 1. 当我们当前使用的通行证还能继续覆盖边（l < L),且我们选择继续覆盖时： if(cost > dist[v][k][l + 1]) dist[u][k][l + 1] = cost;
2. 当我们当前使用的通行证已经不能继续覆盖，且我们选择再购买一张时：if(k < K) dist[u][k + 1][L] = cost + C;
3. 当我们当前使用的通行证已经不能继续覆盖，且我们选择走普通路线时：if(cost + w > dist[v][k][0]) dist[v][k][0] = cost + w;
4.当我们正在覆盖边中，可我们选择提前结束覆盖时：if(cost + w > dist[v][k][0]) dist[v][k][0] = cost + w;
5. 当我们正在走普通路线，且我们选择购买通行证时： if(k < K) dist[v][k][L] = cost + C;
最终答案 返回当 u == n 时的dist 值
3. 算法： 最短路
4. 时间复杂度： O(MKL log NKL)
5. 核心代码：
if (cost + w < dist[v][k][0]) { //在满足路程最短的前提下
dist[v][k][0] = cost + w;
pq.push({cost + w, v, k, 0});
}
// 2. 买新证（如果还有额度）
if (k < K) {
if (cost + C < dist[v][k + 1][1]) {
dist[v][k + 1][1] = cost + C;
pq.push({cost + C, v, k + 1, 1});
}
}
} else {
// 正在覆盖中
// 1. 继续覆盖（如果未达上限）
if (l < L) {
if (cost < dist[v][k][l + 1]) {
dist[v][k][l + 1] = cost;
pq.push({cost, v, k, l + 1});
}
}
// 2. 提前结束
if(cost + w < dist[v][k][0]){
dist[v][k][0] = cost + w;
pq.push({dist[v][k][0], v, k, 0});
}
// 3. 提前结束覆盖，并买新证
if (k < K) {
if (cost + C < dist[v][k + 1][1]) {
dist[v][k + 1][1] = cost + C;
pq.push({cost + C, v, k + 1, 1});
}
}
}
3. D4T5 (有先后的巡检，旅行商问题变种，状压dp){
1.题意：n 个设备需要各巡检一次，可以从任意设备开始，在任意设备结束。矩阵 ci,jci,j 表示从设备 i 直接到设备 j 的费用，-1 表示不能直接到达。另有 m 条先后要求 u,v，要求 u 必须在 v 之前巡检。只允许按巡检顺序使用相邻两设备之间的一条直接边，不能经过已巡检设备中转。求最小总费用和取得该费用的巡检顺序数，数量对 998244353 取模；无解输出 -1 0。
2.思路：只要看到每个设备都必须巡检一遍，且给定数据为一个矩阵，且n <= 18, 就注定了这题是一道裸的状压dp. 但是这题有个前置条件，就是会给定m个检查顺序，要求u必须在v之前巡检完成。这是这题与旅行商问题的不同处之一，且我们还需要维护到达最终状态的路径总共有多少条
旅行商问题想必大家都很熟悉，就是将每个点的到达看做01状态，到达表示为1，我们只需要枚举到达状态与下一步的状态，将两种状态产生的价值合并起来就能得到
最终答案。但是针对这题的先后顺序怎么办呢？
我们假设当前状态u = 1 为 0011(1和2已经到达），下一步状态v = 3为0111， 假设u = 1真的在v = 3 之前到达了，那么将他们两个进行位与就可以得到：0111 最终位与的结果就等于v的状态 所以针对先后问题，我们可以将其印射成一个个二进制串，只要前一个的状态和后一个的状态位与的结果等于后一个的状态，那么这条路径就是合法的
接下来的问题就非常简单。路径的计数我们就只需要在找到一种合法情况时进行分类讨论： 1. 当前的结果比原先更优： g[v][nxt] = g[u][mask] (g是计数数组，nxt是下一步的状态，mask是上一步的状态)
2. 当前的结果跟原先相等： g[v][nxt] = (g[v][nxt] + g[u][mask]) % mod：要记得取模
最终结果： dp[n][full] 和 g[n][full] (full 表示全1二进制串）
3. 算法： 状压dp
4. 时间复杂度： O(2^n * n^2)
- 核心代码：
for (int mask = 0; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++) {
if (dp[i][mask] == INF) continue; // 状态不可达
for (int j = 0; j < n; j++) {
if ((mask >> j) & 1) continue; // j 已被访问
if (cost[i][j] == -1) continue; // 不可直接到达
if ((mask & pre[j]) != pre[j]) continue; // 前驱条件未满足
int nxt = mask | (1 << j);
int newcost = dp[i][mask] + cost[i][j];
if (newcost < dp[j][nxt]) {
dp[j][nxt] = newcost;
f[j][nxt] = f[i][mask];
} else if (newcost == dp[j][nxt]) {
f[j][nxt] = (f[j][nxt] + f[i][mask]) % mod;
}
}
}
}
}
4.D3T4(菱形接收区，树状数组 + 矩阵优化，数学）{
1.题意：平面上 n 个发射点的坐标为 (xi,yi)(xi,yi)，权值为 wi≥0 wi≥0，不同点允许同坐标。一次接收查询给出中心 (x,y)(x,y) 和半径 r，收取所有满足 ∣xi−x∣+∣yi−y∣≤r 的点的权值。求每次查询的权值之和。
2.思路：
这题暴力特别好做，就是对于每次查询直接暴力枚举每个点看是否满足其哈密顿距离小于圆的距离r即可。但难就难在正解的思维太抽象，以至于全军覆没
首先对于每 2个点，我们考虑将其坐标进行转化，定义u = x + y, v = x - y,查询坐标 U = X + Y, V = X - Y 哈密顿公式转化：|xi - x| + |yi - y| <= r -> max(| u - U|, |v - V|) 不难发现此时的 横纵坐标的取值范围就变成： U - r <= u <= U + r, V - r <= v <= V + r 在坐标轴上面呈现的是一个正方形，这样确定取值范围有利于我们求合法点权，也就是二维前缀和优化（别问我怎么来的，问就是感觉是这样的）
但是由于这题的点的横纵坐标的取值范围非常大，导致这题的坐标系非常大，所以普通的二维前缀和数组会被直接pass掉。对于这种涉及到动态求和的问题就需要用到树状数组：单点加（add）和前缀和（sum）
树状数组在这题作为工具使用，而对于每次查询我们需要对其横坐标进行排序，来确保当前的点权增加一定连续，再二分一个合法区间，判断依据为所有满足要求的点的纵坐标，来确定最终会有多少个点会被纳入计算，最后用树状数组求前缀和即可
3.算法：树状数组，二分，数学
4. 时间复杂度：O(n log log n)
5.代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct Point{
LL x, y, w;
};
struct Query{
LL x, y;
int id, k;
};
vector<LL> tree;
void add(int x, LL v){
for(; x < tree.size(); x += (x & -x)){
tree[x] += v;
}
}
LL sum(int x){
LL res = 0;
for(; x; x -= (x & -x)){
res += tree[x];
}
return res;
}
bool cmp1(Point a, Point b) { return a.x < b.x; }
bool cmp0(Query a, Query b) { return a.x < b.x; }
int main(){
freopen("t4.in","r",stdin);
freopen("t4.out","w",stdout);
int n, q;
cin >> n >> q;
vector<Point> a(n); // 点的信息
vector<Query> b; // 查询的信息
vector<LL> ys; //保存所有点变换后v的坐标
for(int i = 0; i < n; i++) {
LL x, y, w;
cin >> x >> y >> w;
a[i] = {x + y, x - y, w};
ys.push_back(x - y);
}
for(int i = 0; i < q; i++) {
LL x, y, r;
cin >> x >> y >> r;
LL l = x + y - r, h = x + y + r;
LL d = x - y - r, t = x - y + r;
b.push_back({h, t, i, 1}); // 矩阵优化取值范围
b.push_back({l - 1, t, i, -1});
b.push_back({h, d - 1, i, -1});
b.push_back({l - 1, d - 1, i, 1});
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end()); // 按横坐标排序
sort(a.begin(), a.end(), cmp1);
sort(b.begin(), b.end(), cmp0);
tree.resize(ys.size() + 1);
vector<LL> ans(q);
int j = 0;
for(auto p : b) {
while(j < n && a[j].x <= p.x) {
int k = lower_bound(ys.begin(), ys.end(), a[j].y) - ys.begin() + 1;
add(k, a[j].w);
j++;
}
int k = upper_bound(ys.begin(), ys.end(), p.y) - ys.begin();
ans[p.id] += p.k * sum(k);
}
for(int i = 0; i < q; i++) cout << ans[i] << endl;
}
}
5. D5T1（嵌套播报，错题,基础算法，数学）{
1.题意：播报表达式由小写字母、方括号和十进制正整数组成。字母表示自己；相邻表达式表示连接；[E]k 表示将非空表达式 E 的展开结果重复 k 次。k 紧跟右方括号，是无前导零的整数，不属于输出字母。表达式保证合法。展开后字符串为 s1……sN，字母 a—z 的值为 1—26。求N与sum(i * s[i]) 的值
2.思路：
由于数据范围过大，所以导致暴力只能拿10分，但是思路很简单，这里就不细说
这题很烦人的地方在于k的值很大，导致没有办法直接暴力展开整个字符串来计算sum,因此我们就需要考虑对字符串的信息进行简化： 令三元组(L, S, W,）= {当前字符串的长度，当前字符串的权值，当前字符串的加权值} （那当前字符串的权值和加权值有什么区别呢？实际上就是字符的权值和跟整个字符串的权值总和）
举个例子： 现在给你字符串[[a]2b]2, 那么当栈遇到a时就首先会将a的权值和加权值放入栈内: st.push(1,1,1) 当遇到2时，总和会从1*2 = 2，长度也会变成2,并和栈顶元素合并。当遇到b时，我们会先将其进行存储，将其长度与栈顶元素进行合并，而遇到2时只需要再乘以2即可，而新的权值和会变成原串：aa 的和与当前串b 的和，加权值： La * Sa + (k - 1) k / 2 * Sa (Sa 指新的权值和，La指新的字符串长度），其字符串也会从原来的 aab变成aabaab,原权值和 = 7， 现加权权值和 = 7 + 7 * 3 = 28， 符合我们的公式
因此我们只需要在遇到新的字符时将其与栈顶的字符串进行合并，遇到数字时按照La = La +Lb,Sa = Sa + Sb, Wa = Wa + Wa ( k -1) * k / 2 进行转移即可。转移需开long long
3. 算法： 栈
4. 时间复杂度：转移 O(n)
5. 核心代码：
long long k_minus_1_mod = (k_mod - 1 + MOD) % MOD;
long long term = k_mod * k_minus_1_mod % MOD * INV2 % MOD; // k(k-1)/2
Node outer;
outer.len = inner.len * k_mod % MOD;
outer.total = inner.total * k_mod % MOD;
outer.sum = (k_mod * inner.sum % MOD
+ inner.len * inner.total % MOD * term % MOD) % MOD;
// 合并到外层
Node& cur = st.back();
cur.sum = (cur.sum + outer.sum + cur.len * outer.total) % MOD;
cur.total = (cur.total + outer.total) % MOD;
cur.len = (cur.len + outer.len) % MOD;
}
6. D2T4(雾中的异色站，并查集，图论）{
1.题意：无向图中每个站点有高度 hihi 和颜色 ci∈{0,1}。雾线高度为 H 时，仅保留高度不低于 H 的站点以及两端都保留的边。对每次查询 H，求保留图中颜色不同且互相可达的无序点对数。不同查询彼此独立。
2. 思路：
这题不知道怎么回事，考试的时候没去做，虽然说能想到是并查集。
这题如果我们一个一个去按照给定的查询顺序来找有多少对点能满足高于当前的雾色高度且能互相到达的点对会非常麻烦，时间复杂度会很高，因此我们考虑将其进行排序。因为雾色高度的逐渐降低只会让我们图中符合要求的点对数量变多而不会变少，因此就是一个不断合并的过程，因此我们考虑用并查集来解决这道题
接下来要解决的问题就非常简单，排完序之后我们需要线性扫描查找被激活的点的个数，点对的颜色cnt[u][0]表示当前点的颜色为0，cnt[u][1]表示当前点的颜色为1，个数统计（乘法原理）： 如果一个连通块中的点对数量为a, 另一个连通块中的点对数量为b,那么将两个连通块合并后的合法点对数量就为： a * b cnt[u][1] *= cnt[v][0], cnt[u][0] *= cnt[v][1] (题目要求一定是异色）, ans += cnt[u][1] + cnt[u][0]
3.算法：并查集
4.时间复杂度：合并O(1),遍历O(n)
5.核心代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 70005;
using ll = long long;
int n, m, q;
int hei[N], col[N];
vector<int> adj[N];
int fa[N];
ll cnt[2][N];
ll ans = 0;
bool active[N];
int H[N], ansOut[N];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void uni(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
ans += cnt[0][rx] * cnt[1][ry] + cnt[1][rx] * cnt[0][ry];
fa[rx] = ry;
cnt[0][ry] += cnt[0][rx];
cnt[1][ry] += cnt[1][rx];
}
int main() {
freopen("t4.in","r",stdin);
freopen("t4.out","w",stdout);
cin >> n >> m >> q;
for (int i = 1; i <= n; ++i) cin >> hei[i];
for (int i = 1; i <= n; ++i) cin >> col[i];
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= q; ++i) cin >> H[i];
vector<int> pt(n);
iota(pt.begin(), pt.end(), 1);
sort(pt.begin(), pt.end(), [&](int a, int b) {
return hei[a] > hei[b];
});
vector<int> qt(q);
iota(qt.begin(), qt.end(), 1);
sort(qt.begin(), qt.end(), [&](int a, int b) {
return H[a] > H[b];
});
for (int i = 1; i <= n; ++i) {
fa[i] = i;
cnt[0][i] = cnt[1][i] = 0;
active[i] = false;
}
int ptr = 0; // 指向当前待激活的点
// 离线处理查询
for (int qi = 0; qi < q; ++qi) {
int idx = qt[qi];
int curH = H[idx];
// 激活所有高度 >= curH 的点
while (ptr < n && hei[pt[ptr]] >= curH) {
int u = pt[ptr];
active[u] = true;
// 初始化该点的颜色计数
if (col[u] == 0) cnt[0][u] = 1;
else cnt[1][u] = 1;
// 遍历它的所有邻居，如果邻居已经激活，就合并
for (int v : adj[u]) {
if (active[v]) {
uni(u, v);
}
}
ptr++;
}
ansOut[idx] = ans;
}
// 按原顺序输出
for (int i = 1; i <= q; ++i) {
cout << ansOut[i] << endl;
}
}
}
7.D4T4 (双钥匙窗口，KMP||字符串哈希）{
1.题意：日志串 s 由小写字母与 # 构成，两个钥匙串 p、q 只含小写字母。选择 s 中 p 的一次完整出现与其后 q 的一次完整出现，要求两次出现不重叠，中间隔着 0 到 G 个字符，且这些间隔字符中不能出现 #。出现位置不同视为不同选择；p 与 q 可以相同。求合法选择对数。
2.思路：
这题有两种做法，字符串哈希的做法已经课上讲过了，就是初始化： h[i] = h[i - 1] * base + s[i], p[i] = p[i - 1] * base % mod , 然后枚举字符串中与子串哈希值一致的位置 l, r。查找： h[r] - h[l - 1] * p[r - l + 1] 这里讲一下kmp的做法
kmp想必大家也不陌生，就是利用最长公共前后缀数组来快速匹配子串在原串中出现的位置。而这题kmp就是模版，但是很容易错：
vector<int> res; // 最终返回的子串在原串中开头出现的位置数组
int n = text.size(), m = pattern.size();
if (m == 0) return res;
vector<int> pi(m, 0); // next数组
for (int i = 1; i < m; i++) { // 匹配最长公共前后缀
int j = pi[i - 1];
while (j > 0 && pattern[i] != pattern[j]) j = pi[j - 1]; // 这里如果j初始化为0的话判定条件就是j > 0
if (pattern[i] == pattern[j]) j++;// 模式串匹配成功
pi[i] = j;
}
int j = 0;
for (int i = 0; i < n; i++) { //匹配位置
while (j > 0 && text[i] != pattern[j]) j = pi[j - 1];
if (text[i] == pattern[j]) j++;
if (j == m) {
res.push_back(i - m + 1);//如果最终返回成功了，说明当前位置是子串的开头
j = pi[j - 1]；
}
}
return res；
之后的位置匹配问题就只需要利用双指针，任取一个字符串的匹配数组，从开头往后扫描，限制条件： pos_q <= pos_p + G + p.size() && pos_q >= pos_p + p.size() ,且中间不能有# r扫描到一个合法位置以后再将l往前推进，最后ans += r - l
- 算法： Kmp,字符串哈希，双指针
4.时间复杂度：匹配O(1)，查找O(n)
5.核心代码：
int min_j = i + len_p; //合法下界
int max_j = i + len_p + G; // 合法上界，不能超过G个字符
int hash_limit = next_hash[i + len_p] - 1;
if (max_j > hash_limit) max_j = hash_limit; // 不能含有#
if (min_j > max_j) continue; // 无合法 q
while (l < sz_q && pos_q[l] < min_j) l++;
while (r < sz_q && pos_q[r] <= max_j) r++;
if (r < l) r = l;
ans += (r - l); // 累加合法对数
评论
0