2023 CPC 广东省赛（B，D， F）

本文主要是介绍2023 CPC 广东省赛（B，D， F），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：The 2023 Guangdong Provincial Collegiate Programming Contest

有中文题面，题意就省略了。

B Base Station Construction

思路

本题参考了官方题解。

注意观察题目数据 $n, m$ 的和都不超过 $5 e 5$ ，那么我们dp就可以从这两方面考虑，这里我们从站点而不从区间来入手。

定义dp方程： $f [i] :$ 前 $i$ 个站点，且第 $i$ 个站点必须建基站的最小花费。状态转移就是枚举上一个站点建在哪 $j$ ， $f[i] = \min_j^{i-1}f[j] +a[i]$ .

注意一个问题，有些转移是不合法的，当存在区间 $[l, r]$ 使得 $l > j, r < i$ .这样就有区间中没有站点，这是不合法的。 考虑对于每个 $i$ 找到 $p [i] :$ 最远的合法转移点，用优先队列求解，易知 $p [i]$ 一定是单调递增的，我们可以将区间按右端点排序，对于所有右端点小于当前点 $(r < i)$ 的区间存入优先队列大顶堆按左端点排序，这样每次从队首取元素判断当前最远点 $k$ 是否合法，如果不合法 $l > k$ ，就将 $k = l$ .

具体实现见代码：

struct seg{int l, r;bool operator <(const seg& A){if(r == A.r) return l < A.l; return r < A.r;}
}s[N];
priority_queue<pair<int, int> > q;
sort(s + 1, s + 1 + m);
while(!q.empty()) q.pop();
for(int i = 1, j = 0, k = 0; i <= n; i ++){while(j <= m && s[j].r < i) q.push({s[j].l, s[j].r}), j ++;if(!q.empty() && q.top().first > k) k = q.top().first; // 队列中都是r < i 的，若是 l > k 说明两个站点之间没有包含到该区间，这是不合法的，之间让k跳到lp[i] = k;
}

值得一提的是，官方题解中是用双指针求解 $p [i]$ 的，时间更加优秀。

接下来的转移就很好想了，就是对于合法区间 $f[i] = \min_{j=p[i]}^{i-1}f[j] + a[i]$ . 求区间最小值，可以用线段树维护，单点修改区间查询，转移时间复杂度 $O (n l o g n)$ 。由于 $p [i]$ 是单调递增的，可以用单调队列优化转移时间复杂度 $O (n)$ 。这里采用单调队列的方法。

最后的最后可以建立一个虚拟点来方便直接输出 $a [n + 1] = 0$ .

代码

/*
n和m之和都小于5e5 所以可以从这两方面来考虑，枚举站点和枚举区间
*/
#include <bits/stdc++.h>
using namespace std;#define ll long long
const int N = 5e5 + 10;
const ll inf = 1e18;struct seg{int l, r;bool operator <(const seg& A){if(r == A.r) return l < A.l; return r < A.r;}
}s[N];int a[N], n, m;ll f[N], p[N]; // f:前i个站点 且第i个站点必须建立电站的最小花费（枚举上一个站点j求解） p:要求两个站点之间不能有完整的区间，pi = 最小的满足有要求的站点j
priority_queue<pair<int, int> > q;ll que[N];
void solve(){cin >> n;for(int i = 1; i <= n; i ++) cin >> a[i];a[++ n] = 0; // 虚拟站点cin >> m;for(int i = 1; i <= m; i ++){cin >> s[i].l >> s[i].r;}sort(s + 1, s + 1 + m);while(!q.empty()) q.pop();for(int i = 1, j = 0, k = 0; i <= n; i ++){while(j <= m && s[j].r < i) q.push({s[j].l, s[j].r}), j ++;if(!q.empty() && q.top().first > k) k = q.top().first; // 队列中都是r < i 的，若是 l > k 说明两个站点之间没有包含到该区间，这是不合法的，之间让k跳到lp[i] = k;}int tot = 0, top = 0;f[0] = 0;for(int i = 1; i <= n; i ++){ // 求的是合法区间中p[i] ~ i - 1的最小值，由于p[i]单调递增可以用单调队列维护while(top <= tot && que[top] < p[i]) top ++;f[i] = f[que[top]] + a[i];while(tot >= top && f[que[tot]] > f[i]) tot --;que[++ tot] = i;}for(int i = 1; i <= n; i ++) que[i] = 0;cout << f[n] << "\n";
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t;cin >> t;while(t --){solve();}return 0;
}

D New Houses

思路

容易知道，对于不喜欢一起住的人即 $a_i<b_i$ 的人，当迫不得已必须一起住的时候，价值就会减少 $b_i-a_i$ ，当出现这种情况的时候，肯定是选减少价值最少的去一起住，这是本题唯一的算法贪心点。

接下来我们就不用思考那么多边界问题，直接大力分类讨论！具体看代码，每行几乎都有详细注释。

代码

#include <bits/stdc++.h>
using namespace std;#define ll long long
const int N = 1e6 + 10;struct node{int a, b;
};bool cmp(node &A, node &B){return A.b - A.a < B.b - B.a;
}
void solve(){int n, m;cin >> n >> m;vector<node> A, B;ll sumA = 0, sumB = 0;for(int i = 1; i <= n; i ++){int a, b;cin >> a >> b;if(a >= b) A.push_back({a, b}), sumA += a; // 按喜好区分，将价值求和else B.push_back({a, b}), sumB += b;}int sizA = A.size(), sizB = B.size();if(sizB == 0){ // 没有喜欢单独住的if(sizA == 1) cout << A[0].b << "\n"; // 如果只有一个人，必须单独住else cout << sumA << "\n"; // 直接输出全部一起住的价值return ;}sort(B.begin(), B.end(), cmp); // 按如果不能独自住，按损失的最少的排序if(sizA == 0){ // 全是喜欢独自住的if(m < sizB * 2 - 1){ // 不能全部单独住for(auto [a, b] : B){ // 枚举有多少是必须一起住的sumB -= (b - a); // 将一起住的减少的值减去m --;sizB --;if(m >= sizB * 2) break; // 满足剩下的人可以单独住结束}} cout << sumB << "\n";return ;}if(sizA == 1){ // 只有一个喜欢一起住的ll ans = sumB;m --;if(m < sizB * 2){ // 剩下的人不能全部单独住ans += A[0].a; // 喜欢一起住的人就能加上价值for(auto [a, b] : B){ans -= (b - a);m --;sizB --;if(m >= sizB * 2) break;}}else{ // 剩下的人可以全部单独住，分情况讨论ans = max(sumB + A[0].b, sumB - (B[0].b - B[0].a) + A[0].a); // 全部单独住，或者有一对一起住}cout << ans << "\n";return ;}// sizA > 1 && sizB > 0// 喜欢一起住的肯定都一起住，剩下的位置让无法独自住，选减少价值最小的一起住ll ans = sumA + sumB;m -= sizA;if(m < sizB * 2){for(auto [a, b] : B){ans -= (b - a);m --;sizB --;if(m >= sizB * 2) break;}}cout << ans << "\n";
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t;cin >> t;while(t --){solve();}return 0;
}

F Traveling in Cells

大致题意：每个格子有颜色和价值（两者都有修改操作）每次给定颜色集合 $A$ 只能走集合内颜色的格子，问从 $x$ 点开始最多能收集到多少价值。

思路

对于这种维护东西很多很杂无从下手的问题我们开始逐步简化。

对于每一个询问我们要解决的主要问题是：从给定点 $x$ 出发最远能走到的边界 $[l, r]$ 是多少，解决这个问题后，只需要用一个线段树/树状数组就可以维护单点修改，区间求和输出答案了。

对于从 $x$ 开始最多能走多远，无疑是有单调性的，即如果往左边走我们不能走到 $l$ 点，那么 $1\sim l-1$ 肯定也不能走到，右边同理。既然有单调性我们就考虑二分。要二分就必须知道一个区间内颜色有多少个是属于集合 $A$ 的，注意每次给定颜色集合大小 $k$ ，保证 $\sum k_i \leq 1e^6$ ，所以我们可以对每个颜色分开查询，最后算总数是否等于我们二分出来的该区间长度即可。

到此为此问题被简化为询问一个区间内指定单一颜色的个数（带修），我们继续简化问题。如果问题保证所有点只有两种颜色我们是否能解决该问题？显然用线段树就能很方便解决，将颜色分为黑白 $0/1$ 维护每个区间的价值，区间之和就代表白色点的个数。
回到有多种颜色的问题，我们是否能对每一种颜色都建一棵线段树呢？对于颜色 $i$ 的线段树，颜色 $i$ 代表 $1$ ，其他颜色代表 $0$ . 关于 $n$ 棵线段树空间不够的问题我们可以动态开点，每次只新增一条链空间复杂度为 $O ((n + q) l o g n)$ .

时间复杂度：二分答案 + 线段树，上界取决于询问的集合总大小 $k$ ，所以为 $O((logn)^2 \sum k_i)$ .
到此为止问题已经在逐步简化下解决了具体见代码及注释。

代码

/*
对区间的价值用树状数组维护
对颜色用线段树维护，即对每种颜色建立一棵线段树，动态开点保证空间，对于颜色i, 区间[l, r].sum 表示的是区间中颜色i的数量
*/
#include <bits/stdc++.h>
using namespace std;#define ll long long
typedef vector<int> Vec;
const int N = 1e5 + 10, MAX = 1e5;int n, q;int v[N], c[N];int T[N], tot; // T[i]:颜色为i的线段树的根
struct node{ int ls, rs, sum;
}tr[N * 200];void update(int& p, int loc, int k, int l = 1, int r = MAX){ // 对于该颜色更新点loc的价值+1if(!p) p = ++ tot;tr[p].sum += k;if(l == r) return ;int mid = (l + r) >> 1;if(loc <= mid) update(tr[p].ls, loc, k, l, mid);else update(tr[p].rs, loc, k, mid + 1, r);
}int query(int p, int ql, int qr, int l = 1, int r = MAX){ // 对于颜色i查询区间[ql, qr]该颜色的个数if(!p) return 0;if(ql <= l && r <= qr) return tr[p].sum;int mid = (l + r) >> 1, ans = 0;if(ql <= mid) ans += query(tr[p].ls, ql, qr, l, mid);if(qr > mid) ans += query(tr[p].rs, ql, qr, mid + 1, r);return ans; 
}ll val[N]; // 树状数组维护单点修改和区间求和
int lowbit(int x){ return x & -x; }
void update(int r, int k){for(int i = r; i <= n; i += lowbit(i)) val[i] += k;
}
ll get_sum(int l, int r){ll ans = 0;for(int i = r; i; i -= lowbit(i)) ans += val[i];for(int i = l - 1; i; i -= lowbit(i)) ans -= val[i];return ans;
}Vec ci; // 每次查询的颜色集合
bool check(int len, int l, int r){int sum = 0;for(auto x : ci){sum += query(T[x], l, r); // 对于所有集合中的颜色查询[l, r].sum}return sum == len;
}void get_ans(){int x, k;cin >> x >> k;ci.clear();for(int i = 1, y; i <= k; i ++){cin >> y;ci.push_back(y);}sort(ci.begin(), ci.end());ci.erase(unique(ci.begin(), ci.end()), ci.end()); // 去重int l = 1, r = n;int Lr = x;while(l <= Lr){ // 二分找最远能到的左边界int mid = (l + Lr) >> 1;if(check(x - mid + 1, mid, x)) Lr = mid - 1;else l = mid + 1;}int Rl = x;while(Rl <= r){ // 二分找最远合法的右边界int mid = (Rl + r) >> 1;if(check(mid - x + 1, x, mid)) Rl = mid + 1;else r = mid - 1;}cout << get_sum(l, r) << "\n"; // 输出求和
}void clear(){for(int i = 0; i <= tot; i ++) tr[i] = {0, 0, 0};for(int i = 1; i <= n; i ++) T[i] = val[i] = 0;tot = 0;
}
void solve(){cin >> n >> q;clear();for(int i = 1; i <= n; i ++){cin >> c[i];update(T[c[i]], i, 1);}for(int i = 1; i <= n; i ++){cin >> v[i];update(i, v[i]);}for(int i = 1; i <= q; i ++){int op, p, x;cin >> op;if(op == 1){ // 更改颜色cin >> p >> x;update(T[c[p]], p, -1);c[p] = x;update(T[c[p]], p, 1);}else if(op == 2){ // 更改价值cin >> p >> x;update(p, x - v[p]);v[p] = x;}else get_ans();}
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t;cin >> t;while(t --){solve();}return 0;
}