2025年睿抗国赛本科组题解

今年国赛题还算比较简单，前两题为模拟，第三题栈，第四题bfs，第五题动态规划。本科组 3800 余人参赛 162 人满分，中位线 50 分。

RC-u1 谁拿冠军了？

这道题注意同一类先求和再除就行，模拟。

#include <bits/stdc++.h>using namespace std ;
int n , m , sa , sb , a1 , a2 , b1 , b2 , b3 ;
int a[1010][3] , b[1010][4] , st[1010][4] ;int main() {cin >> n >> m >> a1 >> a2 >> b1 >> b2 >> b3 ;for(int i = 1 ; i <= n ; i ++) {int d , op ;cin >> d >> op ;if(op == 1) a[d][1] ++ , b[d][1] ++ ;else if(op == 2) b[d][2] ++ ;else a[d][2] ++ , b[d][3] ++ ;}for(int i = 1 ; i <= m ; i ++) {int d , op ;cin >> d >> op ;st[d][op] = 1 ;}for(int i = 1 ; i <= 1000 ; i ++) {sa += a[i][1] * a1 - a[i][2] * a2 ;int s1 = b[i][1] * b1 , s2 = b[i][2] * b2 , s3 = b[i][3] * b3 ;if(st[i][1]) s1 /= 2 ;if(st[i][2]) s2 /= 2 ;if(st[i][3]) s3 /= 2 ;sb -= (s1 + s2 + s3) ;}cout << sa << " " << sb << "\n" ;return 0 ;
}

RC-u2 理包

模拟，一个个去匹配，我这里记录了要装入物品的相对该物品第一个*位置的坐标。

#include <bits/stdc++.h>
#define x first
#define y secondusing namespace std ;
typedef pair<int,int> PII ;
int n , m , q ;
int st[55][55] ;
vector<PII> v ;void check() {for(int i = 1 ; i <= n ; i ++) for(int j = 1 ; j <= m ; j ++) if(st[i][j] == 0) {int f = 1 ;for(int p = 0 ; p < v.size() ; p ++) {int fx = i + v[p].x , fy = j + v[p].y ;if(fx <= 0 || fx > n || fy <= 0 || fy > m || st[fx][fy]) {f = 0 ;}}if(f) {cout << i << " " << j << "\n" ;for(int p = 0 ; p < v.size() ; p ++) {int fx = i + v[p].x , fy = j + v[p].y ;st[fx][fy] = 1 ;}return ;} }cout << "-1 -1\n" ;
}
int main() {cin >> n >> m >> q ;while (q --) {int x , y , sx = -1 , sy = -1 ;cin >> x >> y ;v.clear() ;for(int i = 1 ; i <= x ; i ++)for(int j = 1 ; j <= y ; j ++){char c ;cin >> c ;if(c == '*') {if(sx == -1) {sx = i , sy = j ;v.push_back({0 , 0}) ;}else {v.push_back({i-sx,j-sy}) ;}}}check() ;}return 0 ;
}

RC-u3 删除屏蔽词

直接t.find(s)会超时，可以使用stack，每次维持一个长度为2的字符串。（不会有人没注意到第一个字符串长度为2吧。）

#include <bits/stdc++.h> using namespace std ;
int n , m = 2 , res ;
string s , t ;int main() {cin >> s >> t ;n = t.size() ;stack<char> st ;string u ;for(int i = 0 ; i < n ; i ++) {u = "" ;u += t[i] ;if(st.size()) {u = st.top() + u ;if(u == s) {st.pop() ;res ++ ;}else st.push(t[i]) ;}else st.push(t[i]) ;}string v = "" ;while(st.size()) {v += st.top() ;st.pop() ;}reverse(v.begin() , v.end()) ;cout << res << " " << v << "\n" ;return 0 ;
}

RC-u4 穷游

可以直接dijkstra，我这里用的二分+bfs，二分最贵城市的住宿费，再去bfs求从st到ed的最短时间，注意同样住宿费时要求最短时间。

#include <bits/stdc++.h>
#define x first
#define y secondusing namespace std ;
typedef pair<int,int> PII ;
int n , m , st , ed ;
int v[1010] , d[1010];
vector<PII> g[1010] ;bool check(int mid) {for(int i = 1 ; i <= n ; i ++)d[i] = 1e9 ;d[st] = 0 ;queue<int> q ;q.push(st) ;while(q.size()) {auto t = q.front() ;q.pop() ;for(int i = 0 ; i < g[t].size() ; i ++) {int j = g[t][i].x , ct = g[t][i].y ;if(j == ed) {d[j] = min(d[j] , ct + d[t]) ;}else if(v[j] <= mid) {if(d[j] > d[t] + ct) {d[j] = d[t] + ct ;q.push(j) ;}}}}return d[ed] != 1e9 ;
}
int main() {cin >> n >> m ;for(int i = 1 ; i <= n ; i ++) cin >> v[i] ;for(int i = 0 ; i < m ; i ++) {int a , b , c ;cin >> a >> b >> c ;g[a].push_back({b , c}) ;g[b].push_back({a , c}) ;}cin >> st >> ed ;int l = 0 , r = 100000 ;while (l < r) {int mid = (l + r) / 2 ;if(check(mid)) r = mid ;else l = mid + 1 ;}check(l) ;cout << l << " " << d[ed] << "\n" ;return 0 ;
}

RC-u5 工序优化

第一眼dp，第二眼，看对了。
f[i][j]表示前i个点合并j次的最少时间，pt[i][j]代表对应的最小花费。
全部初始化为1e9，f[0][0]=pt[0][0]=0。
三重循环，以此枚举i,j和p,p表示将当前i合并至p，注意需要求最少时间的最小花费。
最后枚举操作次数，求最小值。

#include <bits/stdc++.h>using namespace std ;
int n , k ;
int t[310] , p[310] , c[310] , sp[310] , sc[310] ;
int f[310][310] , pt[310][310] ;int main() {cin >> n >> k ;for(int i = 1 ; i <= n ; i ++) {cin >> t[i] >> p[i] >> c[i] ;sc[i] = sc[i - 1] + c[i] ;sp[i] = sp[i - 1] + p[i] ;}for(int i = 0 ; i <= n ; i ++)for(int j = 0 ; j <= k ; j ++)f[i][j] = 1e9 , pt[i][j] = 1e9 ;f[0][0] = pt[0][0] = 0 ;for(int i = 1 ; i <= n ; i ++)for(int j = 0 ; j <= min(i - 1 , k) ; j ++) {if(j == 0) {f[i][j] = f[i - 1][j] + t[i] * p[i] ;pt[i][j] = pt[i - 1][j] ;}else {f[i][j] = f[i - 1][j] + t[i] * p[i] ;pt[i][j] = pt[i - 1][j] ;for(int v = 1 ; v <= i - 1 ; v ++) {int ck = i - v ;if(ck <= j) {if(f[i][j] > f[v - 1][j - ck] + t[v] * (sp[i] - sp[v - 1])) {f[i][j] = f[v - 1][j - ck] + t[v] * (sp[i] - sp[v - 1]) ;pt[i][j] = pt[v - 1][j - ck] + sc[i] - sc[v] ;}else if(f[i][j] == f[v - 1][j - ck] + t[v] * (sp[i] - sp[v - 1])) {pt[i][j] = min(pt[i][j] , pt[v - 1][j - ck] + sc[i] - sc[v]) ;}}}}}int res = 1e9 , rc = 1e9 ;for(int i = 0 ; i <= k ; i ++) {if(f[n][i] < res) {res = f[n][i] , rc = pt[n][i] ;}else if(f[n][i] == res) rc = min(rc , pt[n][i]) ;}cout << res << " " << rc << "\n" ;return 0 ;
}