前言
题解
RC-u1 谁拿冠军了？
分值：15 分
考察点：hash 表的使用
注意点：明明某一天里，可能存在多个相同操作，需要求其总和，在除 2。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m; cin >> n >> m;
int A1, A2, B1, B2, B3; cin >> A1 >> A2 >> B1 >> B2 >> B3;
// 利用 array<int, 2> 表示二元组 (d,op)
map<array<int, 2>, int> ops;
for(int i = 0; i < n; i++){
int d, op; cin >> d >> op; ops[{d, op}] += 1;
}
// 题意保证 一天最多一个操作
map<int, int> ban;
for(int i = 0; i < m; i++){
int t, op; cin >> t >> op; ban[t] = op;
}
int sw1 = 0, sw2 = 0;
for(auto [k, cnt]: ops){
auto [d, op] = k;
// 减半影响的操作
if(ban.count(d) && ban[d] == op){
if(op == 1){ sw1 += A1 * cnt; sw2 -= B1 * cnt / 2; }
else if(op == 2){ sw2 -= B2 * cnt / 2; }
else if(op == 3){ sw1 -= A2 * cnt; sw2 -= B3 * cnt / 2; }
} else {
if(op == 1){ sw1 += A1 * cnt; sw2 -= B1 * cnt; }
else if(op == 2){ sw2 -= B2 * cnt; }
else if(op == 3){ sw1 -= A2 * cnt; sw2 -= B3 * cnt; }
}
}
cout << sw1 << " " << sw2 << "\n";
return 0;
}
RC-u2 理包
分值：20 分
思路：模拟
枚举包裹的空坐标，然后以物品坐标系，以相对偏移向量尝试填充匹配。
感觉码量有点大，看起来简单，但写起来稍头痛。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, q; cin >> n >> m >> q;
vector<string> g(n);
for(int i = 0; i < n; i++){ g[i].resize(m, '.'); }
while(q-- > 0){
int r, c; cin >> r >> c;
vector<string> mat(r);
int sy = -1, sx = -1;
for(int i = 0; i < r; i++){
cin >> mat[i];
if(sy == -1){
for(int j = 0; j < c; j++){
if(mat[i][j] == '*'){ sy = i; sx = j; break; }
}
}
}
// 以物品坐标去匹配包裹，oy/ox 是相对偏移向量
auto check = [&](int oy, int ox)->bool{
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
if(mat[i][j] == '*'){
if(i + oy >= 0 && i + oy < n && j + ox >= 0 && j + ox < m){
if(g[i + oy][j + ox] == '*'){ return false; }
} else { return false; }
}
}
}
return true;
};
// 以物品坐标去填充包裹，oy/ox 是相对偏移向量
auto fill = [&](int oy, int ox){
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
if(mat[i][j] == '*'){ g[i + oy][j + ox] = '*'; }
}
}
};
// 从包裹坐标出发，寻找空格去，查询是否放入物品
auto solve = [&](int &ay, int &ax)->bool{
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(g[i][j] == '.'){
if(check(i - sy, j - sx)){ ay = i; ax = j; fill(i - sy, j - sx); return true; }
}
}
}
return false;
};
int ay = 0, ax = 0;
if(solve(ay, ax)){ cout << (ay + 1) << " " << (ax + 1) << "\n"; }
else{ cout << -1 << " " << -1 << "\n"; }
}
return 0;
}
RC-u3 删除屏蔽词
分值：25 分
思路：模拟 + 栈
这题限定模式串固定为 2，如果为 k，那这题就麻烦了。 就是当前字符，以及栈顶元素，是否构成模式串。 注意：需要输出 删除次数，不是最后文本的长度。
#include <bits/stdc++.h>
using namespace std;
int main() {
string p; string s;
getline(cin, p);
getline(cin, s);
int del = 0;
stack<char> stk;
for(char c: s){
// 核心代码，就是这一行
if(c == p[1] && !stk.empty() && stk.top() == p[0]){ stk.pop(); del++; }
else{ stk.push(c); }
}
string buf;
while(!stk.empty()){ buf.push_back(stk.top()); stk.pop(); }
reverse(buf.begin(), buf.end());
cout << del << " " << buf << "\n";
return 0;
}
RC-u4 穷游
分值：30 分
思路：二分 + dijkstra
可以先确定最小的住宿费用，再求解此基础上的最小时长。 这个套路，在睿抗编程赛中，多次出现。 二分 check 的核心逻辑是连通性，为了简化代码，可以复用带限制的求时长 dijkstra。 这样在追求编码效率 和 代码 AC 之间达到一个好的平衡。
#include <bits/stdc++.h>
using namespace std;
struct E{ int v, w; E(){} E(int v, int w):v(v),w(w){} };
struct P{ int u, c; P(){} P(int u, int c):u(u),c(c){} };
int main() {
int n, m; cin >> n >> m;
vector<int> prices(n);
for(int& x: prices) cin >> x;
vector<vector<E>> g(n);
for(int i = 0; i < m; i++){
int u, v, w; cin >> u >> v >> w; u--; v--;
g[u].push_back(E(v, w)); g[v].push_back(E(u, w));
}
int s, e; cin >> s >> e; s--; e--;
auto comp = [](const P& lhs, const P& rhs){ return lhs.c > rhs.c; };
int inf = 0x3f3f3f3f;
auto dijkstra = [&](int limit){
vector<int> dp(n, inf); dp[s] = 0;
priority_queue<P, vector<P>, decltype(comp)> pq(comp);
pq.push(P(s, 0));
while(!pq.empty()){
P p = pq.top(); pq.pop();
if(p.c > dp[p.u]) continue;
if(p.u == e){ return p.c; }
for(E &e: g[p.u]){
if(prices[e.v] > limit) continue;
if(dp[e.v] > p.c + e.w){ dp[e.v] = p.c + e.w; pq.push(P(e.v, dp[e.v])); }
}
}
return inf;
};
int l = 0, r = *max_element(prices.begin(), prices.end());
// 二分确认最小费用
while(l <= r){
int mid = l + (r - l)/2;
int ret = dijkstra(mid);
if(ret != inf){ r = mid - 1; }
else{ l = mid + 1; }
}
// 再求解最小时长
int ret = dijkstra(l);
cout << l << " " << ret << "\n";
return 0;
}
RC-u5 工序优化
分值：30
思路：动态规划
题目可以归纳如下，更好的理解。 定义一个 merge 操作：
- 第 i 项可以和第 i-1 项合并，时间合并，工作时间按第 i-1 项为准，但需额外消耗 Ci。
- 合并可以连续，即 [a, b] 的连续区间可以合并，操作次数为 (b - a) 次。
- 这个操作为最多 k 次。
如何理解呢？ 定义把 [a, b] 连续区间进行合并，则： E[a,b] 合并的时间消耗 = (∑ Pi) * Ta E[a,b] 合并的代价 = cost[a,b] = ∑ Ci
能理解这个核心的概念后，那个这个 dp 就相对容易解。
- 定义状态 dp[i][j] 为前 i 项，使用 j 次 merge 操作的最小时间/代价。
- 转移方程 dp[i+1+s][j+s] = min_{s∈[0, k-j]} { dp[i][j] + E[i+1, i+1+s] }。
- 结果 ans = min_{j∈[0, k]} { dp[n-1][j] }。
时间复杂度为 O(n*k^2)。
#include <bits/stdc++.h>
using namespace std;
const int64_t inf = (int64_t)1e18;
struct W{ int t, p, c; W(){} W(int t, int p, int c):t(t),p(p),c(c){} };
struct E{ int64_t p = inf; int64_t c = 0; bool operator<(const E&rhs)const{return p != rhs.p ? p < rhs.p : c < rhs.c;} E operator+(const E&rhs)const{return{p+rhs.p, c+rhs.c};} };
int main() {
int n, k; cin >> n >> k;
vector<W> tasks(n);
for(int i = 0; i < n; i++){ W &w = tasks[i]; cin >> w.t >> w.p >> w.c; }
// 预处理，时间和费用的前缀和
vector<int64_t> pre_p(n + 1, 0); vector<int64_t> pre_c(n + 1, 0);
for(int i = 0; i < n; i++){ pre_p[i + 1] = pre_p[i] + tasks[i].p; pre_c[i + 1] = pre_c[i] + tasks[i].c; }
// 定义 dp[i][j], 前 i 项使用 j 次操作的最小时间/费用
vector<vector<E>> dp(n, vector<E>(k + 1));
for(int i = 0; i <= k && i < n; i++){ dp[i][i] = {(pre_p[i + 1] - pre_p[0]) * tasks[0].t, pre_c[i + 1] - pre_c[1]}; }
// 刷表
for(int i = 0; i < n; i++){
for(int j = 0; j <= k; j++){
for(int s = 0; s + j <= k && i + s + 1 < n; s++){
E tmp = {(pre_p[i + s + 2] - pre_p[i + 1]) * tasks[i + 1].t, pre_c[i + s + 2] - pre_c[i + 2]};
E tmp2 = dp[i][j] + tmp;
if(tmp2 < dp[i + s + 1][j + s]){ dp[i + s + 1][j + s] = tmp2; }
}
}
}
E ans = {inf, 0};
for(int i = 0; i <= k; i++){
if(dp[n - 1][i] < ans){ ans = dp[n - 1][i]; }
}
cout << ans.p << " " << ans.c << "\n";
return 0;
}
