SZTU-ACM 2021 春期训练赛第一点五场 [组队赛]（第四届河南大学生程序设计竞赛）总结和题解
A 序号互换
题目意思很简单，就是关于26进制的互相转换，如果是26进制换10进制，直接把每一位按顺序乘26累计到下一位即可获得最终结果。如果是10进制转26进制，我们首先要把字符串转化为整形。然后每一位对26取模。逐渐除26就能得到正确的26进制。注意临时oj不能识别万能头文件，会爆ce。但是标称给的还是万能头，大家如果要补题自己改一下就好了。
#include<bits/stdc .h>using namespace std;char c[100001], b[30];int main(){ int t; long long int ans; string s, ans1; b[0] = 'Z', b[1] = 'A'; for(int i = 2; i <= 26; i ) b[i] = b[i - 1] 1; cin >> t; while(t--) { cin >> s; if(s[0] >= '0' && s[0] <= '9') { int l = s.size(); ans = 0; for(int i = 0; i < l; i ) ans = ans * 10 s[i] - '0'; int k = 0; while(ans) { c[k ] = b[ans % 26]; if(ans % 26 == 0) ans = ans / 26 - 1; else ans /= 26; } for(int i = k - 1; i >= 0; i--) printf("%c", c[i]); printf("\n"); } else { int q = 0; int ll = s.size(); for(int i = 0; i < ll; i ) q = q * 26 (s[i] - 'A' 1); printf("%d\n", q); } } return 0;}B 节能
这道题目很明显是一道区间dp的题目，但是很难直接设计出状态转移的方式。
dp [i] [j] [0]表示i到j的路灯都j已经关闭，机器人在路灯i的位置，此时已经消耗的最小电能
dp [i] [j] [1]表示i到j的路灯都已经关闭，机器人在路灯j的位置，此时已经消耗的最小电能
这样就可以得到状态转移方程为
dp [i] [j] [0] = min(dp[i 1] [j] [0] [i 1,j]路段以外未关闭路灯在机器人从i 1走的i期间消耗的电能，dp [i 1] [j] [1] [i 1,j]路段以外未关闭路灯在机器人从j走到i期间消耗的电能)
dp [i] [j] [1] = min(dp [i] [j-1] [0] [i,j-1]路段以外未关闭路灯在机器人从i走到j期间消耗的电能，dp [i] [j-1] [1] [i,j-1]路段以外未关闭路灯在机器人从j-1走到j期间消耗的电能)
对于某一段在某段时间里消耗的电能，我们可以通过维护一个前缀和来快速完成。推完状态转移方程，题目就很好写了，照着dp写就好了，需要注意的是，每一段的dp值需要初始化，而且要注意初始化0和1的顺序。错了就不能达到区间转移的效果，更多细节在代码里有注释，大家自行阅读理解
#include<bits/stdc .h>using namespace std;int f[1005][1005][2], d[1005], w[1005];//f[i][j][0]：i~j之间的灯全部关闭，且机器人此时站在i处//f[i][j][1]：i~j之间的灯全部关闭，且机器人此时站在j处。int main(){ int n, k; while(~scanf("%d", &n)) { int sum = 0; scanf("%d", &k); for(int i = 1; i <= n; i ) //对路灯功率维护前缀和 ,距离本身就是前缀和不需要自己维护 { scanf("%d%d", &d[i], &w[i]); sum = w[i]; w[i] = w[i - 1]; } f[k][k][0] = f[k][k][1] = 0; for(int i = k 1; i <= n; i ) //初始化向右走的区间 { f[k][i][1] = f[k][i - 1][1] (d[i] - d[i - 1]) * (sum - w[i - 1] w[k - 1]); //从k出发最终停留到i点，是由从k出发停留在i-1点转移得到的，需要减去k到i-1部分的电费 ; f[k][i][0] = f[k][i][1] (d[i] - d[k]) * (sum - w[i] w[k - 1]); //从i回到k需要的电费； } for(int i = k - 1; i > 0; i--) { f[i][k][0] = f[i 1][k][0] (d[i 1] - d[i]) * (sum - w[k] w[i]); f[i][k][1] = f[i][k][0] (d[k] - d[i]) * (sum - w[k] w[i - 1]); } for(int i = k - 1; i > 0; i--) for(int j = k 1; j <= n; j ) { f[i][j][0] = min(f[i 1][j][0] (d[i 1] - d[i]) * (sum - w[j] w[i]), f[i 1][j][1] (d[j] - d[i]) * (sum - w[j] w[i])); f[i][j][1] = min(f[i][j - 1][1] (d[j] - d[j - 1]) * (sum - w[j - 1] w[i - 1]), f[i][j - 1][0] (d[j] - d[i]) * (sum - w[j - 1] w[i - 1])); } printf("%d\n", min(f[1][n][0], f[1][n][1])); } return 0;}C 表达式求值
这道题目应该是很经典的一道关于栈的应用，我们用一个栈存储数字，一个栈存储符号，当遇到）的时候处理一次符号运算。符号数量一定只比栈少1个，最后数字栈中剩余的数字就是我们要求的数字，注意一些处理字符串的细节就好。
#include <bits/stdc .h>using namespace std;char a[1000];stack<int> q,f;int main(){int n,c,l;scanf("%d", &n);while(n--){scanf("%s", a);int l=strlen(a);for(int i=0;i<l;i ){if(a[i]>='0'&&a[i]<='9'){int z=0;while(a[i]>='0'&&a[i]<='9')z = z*10 a[i]-'0',i ;i--,q.push(z);} if(a[i]=='a'&&a[i 1]=='d')f.push(1); if(a[i]=='m'&&a[i 1]=='i')f.push(2); if(a[i]=='m'&&a[i 1]=='a')f.push(3); if(a[i]==')'){int c;int op=f.top();f.pop();int a=q.top();q.pop();int b=q.top();q.pop();if(op==1)c=a b;if(op==2)c=min(a,b);if(op==3)c=max(a,b);q.push(c);}}printf("%d\n", q.top());}return 0;} D 走迷宫
题目数据范围很小，很显然题目可以用搜索解决，我们只要处理如何搜出最大差值即可，不难发现，我们可以用二分来压缩差值的空间。每一次二分答案都dfs搜一遍能否走出迷宫，需要灵活把dfs和二分联系起来。
#include <bits/stdc .h>const int INF = 0x3fffffff;int n, maxn, minn, f = 0;int ret[150][150];int vis[150][150];int to_x[4] = {1, -1, 0, 0};int to_y[4] = {0, 0, 1, -1};inline int read_int(){ char c; int sign = 1; while((c = getchar()) < '0' || c > '9') if(c == '-') sign = -1; int res = c - '0'; while((c = getchar()) >= '0' && c <= '9') res = res * 10 c - '0'; return res * sign;}void dfs(int x, int y, int L, int r){ if(f) return; if(ret[x][y] > r || ret[x][y] < L) return; if(x == n && y == n) { f = 1; return; } for(int i = 0; i < 4; i ) { int xx = x to_x[i]; int yy = y to_y[i]; if(!vis[xx][yy] && xx >= 1 && xx <= n && yy >= 1 && yy <= n) { vis[xx][yy] = 1; dfs(xx, yy, L, r); } }}bool judg(int x){ for(int i = minn; i <= maxn - x; i ) { f = 0; memset(vis, 0, sizeof(vis)); int L = i, r = i x; vis[1][1] = 1; dfs(1, 1, L, r); if(f) return true; } return false;}int main(){ while(scanf("%d", &n) != EOF) { maxn = 0 - INF; minn = INF; for(int i = 1; i <= n; i ) for(int j = 1; j <= n; j ) { ret[i][j] = read_int(); if(maxn < ret[i][j]) maxn = ret[i][j]; if(minn > ret[i][j]) minn = ret[i][j]; } int L = 0, r = maxn - minn; while(L < r) { int mid = (L r) / 2; if(judg(mid)) r = mid; else L = mid 1; } printf("%d\n", r); } return 0;}E 宝物
这道题目是最短路的一个变形，我们从入口开始，对每个点进行用最短路算法进行判断，只是把最短路的条件改为能出来时能携带的最大物品量。本质时保证能联通的最大边权最小的最短路，然后对宝藏进行排序，按顺序取出，如果不能取，就停下来，由于这道题的边数很少，属于稀疏图，我们直接写SPFA就行了，需要注意所有边都是双向边，数组要开3w。dijkstra也可以解决这道题目，大家有兴趣可以自己谢谢看
#include <bits/stdc .h>using namespace std;struct node{ int v, z, next;} e[30020];int head[8010], vis[8010], max1[8010], b[8010], dis[8010], cnt;int addedge(int a, int b, int v){ e[ cnt].v = b; e[cnt].z = v; e[cnt].next = head[a]; head[a] = cnt;}void spfa(int s){ queue<int>q; q.push(s); vis[s] = 1; dis[s] = 0x3f3f3f3f; while(!q.empty()) { int d = q.front(); q.pop(); vis[d] = 0; for(int i = head[d]; i; i = e[i].next) { int v = e[i].v; if(dis[v] < min(dis[d], e[i].z)) { dis[v] = min(dis[d], e[i].z); if(vis[v] == 0) { q.push(v); vis[v] = 1; } } } }}int main(){ int n, m, k, w, a, b, c,ans; while(~scanf("%d%d%d%d", &n, &m, &k, &w)) { memset(vis, 0, sizeof(vis)); memset(dis, 0, sizeof(dis)); memset(head, 0, sizeof(head)); cnt = 0; for(int i = 0; i < k; i ) scanf("%d", &b[i]); for(int i = 1; i <= m; i ) { scanf("%d%d%d", &a, &b, &c); addedge(a, b, c); addedge(b, a, c); } spfa(1); for(int i = 0; i < k; i ) max1[i] = dis[b[i]]; ans = 0; sort(max1, max1 k); for(int i = 0; i < k; i ) if(max1[i] >= (ans 1)*w) ans ; printf("%d\n", ans); } return 0;}F Substring
题意很简单，类似于回文串，只不过这次反转后字串只要在整个字符串中有即可。题目范围很小，我们直接枚举所有字串即可解决问题
#include <bits/stdc .h>char s[105], a[105];int n, maxn, b, e;int main(){ scanf("%d", &n); while(n--) { maxn = 0; scanf("%s", s); int len = strlen(s); for(int i = 0; i < len; i ) a[len - i - 1] = s[i]; for(int i = 0; i < len - 1; i ) for(int j = i 1; j < len; j ) { for(int k = 0; k < len - j i; k ) { int judg = 0; for(int p = 0; p < j - i 1; p ) if(s[i p] != a[k p]) { judg = 1; break; } if(!judg && maxn < j - i 1) { b = i; e = j; maxn = j - i 1; } } } if(maxn) for(int i = b; i <= e; i ) printf("%c", s[i]); else printf("%c", s[0]); printf("\n"); } return 0;}G BOBSLEDDING
题目大意是我们需要保证在转弯时速度不能超过多少，每秒速度变化最多为1.问整个过程中所能保持的最大速度时多少。我们只需要先假设他一直加速，直到遇到转弯，更新当前最大速度和前面所有需要更新的值即可
#include<bits/stdc .h>using namespace std;int f[100010];int main(){int a,b,l,n;while(~scanf("%d%d",&l,&n)){memset(f,0,sizeof(f));for(int i=1;i<=n;i )scanf("%d%d",&a,&b),f[a]=b;f[0]=1;for(int i=1;i<=l;i ){if(f[i]==0||f[i]>f[i-1] 1)f[i]=f[i-1] 1;else{int q=i;while(f[i] 1<f[i-1])f[i-1]=f[i] 1,i--;}}int ans=0;for(int i=0;i<=l;i )ans=min(ans,f[i]);printf("%d\n",ans);}return 0;}H SECRET
题目给了一个加权无向图，从起点道终点共走T次，每条路只能走一次。问如何才能让权值最小的边只能走一次。对于这个题目，我们要求最小的最大权值。对于权值，显然不能枚举得出，所以我们二分权值，对于每一个二分的权值，选择满足条件的边标记为流量为1，标记起点终点用dinic跑一遍最大流。得到的最大流量就是能到达终点的次数。判断是否大于T即可结合二分答案确定最大权值
#include<bits/stdc .h>using namespace std;#define inf 0x3f3f3f3fint N, P, T;struct Edge{ int u, v, w;} e[40010];int g[220][220], vis[220], d[220];bool bfs(){ memset(vis, 0, sizeof(vis)); vis[1] = 1; queue<int>q; q.push(1); d[1] = 0; while(!q.empty()) { int u = q.front(); q.pop(); for(int i = 1; i <= N; i) { if(!vis[i] && g[u][i] > 0) { vis[i] = 1; d[i] = d[u] 1; q.push(i); } } } return vis[N];}int dfs(int u, int a){ if(u == N || a == 0) return a; int flow = 0, f; for(int i = 1; i <= N; i) { if(g[u][i] && d[i] == d[u] 1 && (f = dfs(i, min(a, g[u][i]))) > 0) { g[u][i] -= f; g[i][u] = f; flow = f; a -= f; if(!a) break; } } return flow;}int solve(){ int res = 0; while(bfs()) { res = dfs(1, inf); } return res;}bool ok(int mid){ memset(g, 0, sizeof(g)); for(int i = 1; i <= P; i) { if(e[i].w <= mid) { g[e[i].u][e[i].v] ; g[e[i].v][e[i].u] ; } } return solve() >= T;}int main(){ while(scanf("%d%d%d", &N, &P, &T) != EOF) { for(int i = 1; i <= P; i) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w); int l = 0, r = 1000010; while(l < r) { int mid = l ((r - l) >> 1); if(ok(mid)) r = mid; else l = mid 1; } cout << l << endl; } return 0;} 赞 (0)