2024年睿抗机器人开发者大赛（RAICOM）国赛题解
目录
RC-u1 大家一起查作弊 分数 15
RC-u2 谁进线下了？II 分数 20
RC-u3 势均力敌 分数 25
RC-u4 City 不 City 分数 30
RC-u5 贪心消消乐 分数 30
RC-u1 大家一起查作弊 分数 15
简单模拟题，对于多行读入使用while(getline(cin,s))即可
// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x) fixed<<setprecision(x)// c++ 保留小数
#define den(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
typedef long long LL;
typedef pair<int, int> PII;
const int N=1000010,M=1010,INF=0x3f3f3f3f,mod=1e9+7;
const double pai=acos(-1.0);// pai
map<int,int> mp;
int t,n,m;//是不是关键字
bool check(char x){if('A'<=x and x<='Z') return true;if('a'<=x and x<='z') return true;if(isdigit(x)) return true;return false;
}
//可疑分数计算
int get(string s){int big = 0, small = 0, sz = 0;for(auto&x:s){if('A'<=x and x<='Z') big = 1;if('a'<=x and x<='z') small = 1;if(isdigit(x)) sz = 1;}if(big and small and sz) return 5;if(sz and (big or small)) return 3;if(big and small) return 1;return 0;
}
void solve(){int sum = 0,len = 0, cnt = 0;string s;while(getline(cin,s)){string now;for(auto&v:s)if(check(v)) now += v;else{if(!now.empty()){sum += get(now);len += now.size();cnt++;}now.clear();}// 可能最后还有东西if(!now.empty()){sum += get(now);len += now.size();cnt++;}}cout << sum << endl;cout << len << ' ' << cnt << endl;return ;
}
signed main ()
{ios// 不能有printf puts scanfint t=1;while(t--){solve();}
}
RC-u2 谁进线下了？II 分数 20
简单模拟，按照题目意思模拟即可
// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x) fixed<<setprecision(x)// c++ 保留小数
#define den(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
typedef long long LL;
typedef pair<int, int> PII;
const int N=1000010,M=1010,INF=0x3f3f3f3f,mod=1e9+7;
const double pai=acos(-1.0);// pai
map<int,int> mp;
int t,n,m;
int d[30] = {0,25,21,18,16};
bool st[N];
int w[N];struct code{int id,x;bool operator<(const code&t)const{if(x==t.x) return id<t.id;return x>t.x;}
}e[N];void solve(){for(int i=5;i<=20;i++) d[i] = 20 - i;cin>>n;while(n--){m = 20;while(m--){int x,r; cin>>x>>r;w[x] += d[r];st[x] = true;}} n = 30;for(int i=1;i<=n;i++) e[i]={i,w[i]};sort(e+1,e+1+n);for(int i=1;i<=n;i++){auto [id,x] = e[i];if(!st[id]) continue;cout << id << ' ' << x << endl;}cout << endl;return ;
}
signed main ()
{ios// 不能有printf puts scanfint t=1;while(t--){solve();}
}
RC-u3 势均力敌 分数 25
按照题目直接暴力枚举所有情况使用全排列 + 二进制枚举
时间复杂度大致如下 同时不会跑满所以可以通过
// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x) fixed<<setprecision(x)// c++ 保留小数
#define den(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
typedef long long LL;
typedef pair<int, int> PII;
const int N=1000010,M=1010,INF=0x3f3f3f3f,mod=1e9+7;
const double pai=acos(-1.0);// pai
map<int,int> mp;
int t,n,m;
int a[N],p[N];void solve(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];p[i] = i;}vector<int> v;int sum = 0;do{int ans = 0;for(int i=1;i<=n;i++) ans = ans * 10 + a[p[i]];v.push_back(ans);sum += ans;}while(next_permutation(p+1,p+1+n));m = v.size();for(int i=0;i<(1<<m);i++){if(__builtin_popcount(i)!=m/2) continue;int now = 0;vector<int> ans;for(int j=0;j<m;j++){if(i>>j&1){ans.push_back(v[j]);now += v[j]; }}if(now==sum/2){for(auto&v:ans) cout << v << endl;cout << endl;return ;}}return ;
}
signed main ()
{ios// 不能有printf puts scanfint t=1;while(t--){solve();}
}
RC-u4 City 不 City 分数 30
典型的分层图，一个城市有多个状态，跑一遍djikstra即可，注意本题是计算途经城市的hot值，所以初始状态是 d[s][0] = 0，在可以抵达t的时候来判断即可
// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x) fixed<<setprecision(x)// c++ 保留小数
#define den(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
typedef long long LL;
typedef pair<int, int> PII;
typedef array<int,3> ar3;
const int N=1000010,M=1010,INF=0x3f3f3f3f,mod=1e9+7;
const double pai=acos(-1.0);// pai
map<int,int> mp;
int n,m,s,t;
int h[M];
vector<PII> g[M];
int d[M][110];void solve(){cin>>n>>m>>s>>t;for(int i=1;i<=n;i++) cin>>h[i];while(m--){int a,b,c; cin>>a>>b>>c;g[a].push_back({b,c});g[b].push_back({a,c});}int ans = 2e9,pos = -1;auto dijkstra = [&](){memset(d,0x3f,sizeof d);priority_queue<ar3,vector<ar3>,greater<ar3>> q;d[s][0] = 0, q.push({0,s,0});while(!q.empty()){auto [cost,u,hot] = q.top(); q.pop();for(auto&[v,w]:g[u]){int ne = max(hot,h[v]);if(v==t){if(cost+w<ans){ans = cost + w;pos = hot;}else if(cost+w==ans and hot<pos){pos = hot;}}if(d[v][ne]>cost+w){d[v][ne] = cost + w;q.push({cost+w,v,ne});}}}};dijkstra();if(pos==-1) cout << "Impossible" << endl;else cout << ans << ' ' << pos << endl;return ;
}
signed main ()
{ios// 不能有printf puts scanfint t=1;while(t--){solve();}
}
RC-u5 贪心消消乐 分数 30
贪心模拟，每次都暴力的找到可以选取的最大矩阵即可，然后模拟下降,没有找到正解，这里贴一下别人的x*(n^4)比较暴力的做法，赛时通过了
#include <bits/stdc++.h>using namespace std;
using i64 = long long;constexpr int inf = 5E6;void solve() {int n;cin >> n;vector<vector<int>> g(n, vector<int>(n, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cin >> g[i][j];if (g[i][j] == 0) {g[i][j] = -inf;}}}vector<vector<i64>> sum(n + 1, vector<i64>(n + 1, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + g[i][j];}}i64 tot = 0;while (1) {i64 hi = 0;int a, b, c, d;for (int x1 = 0; x1 < n; x1++) {for (int y1 = 0; y1 < n; y1++) {for (int x2 = x1; x2 < n; x2++) {for (int y2 = y1; y2 < n; y2++) {if (g[y2][x2] == -inf) {break;}i64 cur = sum[y2 + 1][x2 + 1] - sum[y2 + 1][x1] - sum[y1][x2 + 1] + sum[y1][x1];if (cur > hi) {hi = cur;a = x1;b = y1;c = x2;d = y2;}if (cur < 0) {break;}}}}}if (hi <= 0) {break;}tot += hi;cout << "(" << a + 1 << ", " << b + 1 << ") (" << c + 1 << ", " << d + 1 << ") " << hi << "\n";int o = d - b + 1;for (int x = a; x <= c; x++) {for (int y = d; y >= 0; y--) {if (y >= o) {g[y][x] = g[y - o][x];} else {g[y][x] = -inf;}}}for (int i = 0; i <= n; i++) {fill(sum[i].begin(), sum[i].end(), 0);}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + g[i][j];}}}cout << tot << "\n";
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;
// cin >> T;while (T--) {solve();}return 0;
}