2022年“蓝桥杯”上海理工大学校选赛（重现赛）A~E

题目地址

A

思路+代码

签到，因为数不大我们只需要枚举，输出每次枚举的时候得到的$t1+t2$的最大值。

#include <bits/stdc++.h>
#include <algorithm>
#include <stack>
#define mem(s, i) memset(s, i, sizeof(s))
#define INF 0x3f3f3f3f;
#define ll long long
using namespace std;
void solve()
{int num;scanf("%d",&num);int m = num;int x = m%10, y = m/10;int sum = 0;int  cnt = 1;while(y > 0){//cout<<x<<" "<<y<<endl;sum = max(x+y,sum);x = x +pow(10,cnt)*(y%10);y = y/10;cnt++;}printf("%d",sum);}
int main()
{ios::sync_with_stdio(false);solve();return 0;
}

B

思路+代码

我们定义一个结构体，记录每次输入的队伍的名字name，输入次序序号xuhao，学会的知识数量ans。
$cmp$比较大小的规则就是如果两个队伍的学会的知识数量一样我们就比较输入次序的大小，否则就按学会的知识数量从大到小排序。
输出规则，我们只要遇到队伍的知识数量比后一个大，我们输出当前队伍名后就结束输出。

#include <bits/stdc++.h>
#include <algorithm>
#include <stack>
#define mem(s, i) memset(s, i, sizeof(s))
#define INF 0x3f3f3f3f;
#define ll long long
using namespace std;
struct node{char name[12];int ans;int num[1005];int xuhao;
}s[1005];
bool cmp(node x, node y){if(x.ans==y.ans)return x.xuhao < y.xuhao;else return x.ans > y.ans;
}
void solve()
{int n;scanf("%d",&n);s[0].xuhao = 0;for(int i = 1;i <= n;i++){scanf("%s",&s[i].name);//duimings[i].xuhao = s[i-1].xuhao+1;s[i].ans = 0;mem(s[i].num,0);for(int j = 0;j < 3;j++){int k, point;scanf("%d",&k);for(int l = 0;l < k;l++){scanf("%d",&point);if(s[i].num[point] == 0){s[i].num[point] = 1;s[i].ans++;}}}}sort(s+1,s+n+1,cmp);for(int i = 1;i <= n;i++){if(s[i].ans > s[i+1].ans){printf("%s\n",s[i].name);break;}else if(s[i].ans == s[i].ans){printf("%s\n",s[i].name);}}
}
int main()
{ios::sync_with_stdio(false);solve();return 0;
}

C

思路+代码

找规律
做的时候很折磨
如果目的地地址和$i?(i+1)/2$相同，那么i就是步数，如果目的地地址大于$i?(i+1)/2$，那么如果这个得到的$i?(i+1)/2$-目的地地址是个偶数，那么$i$就是步数。

#include <bits/stdc++.h>
#include <algorithm>
#include <stack>
#define mem(s, i) memset(s, i, sizeof(s))
#define INF 0x3f3f3f3f;
#define ll long long
using namespace std;
const int N = 1e5+5;
int func(int x){int sum = 0, t = 0;for(int i = 1;x>0;i++){sum += i;t++;if(sum == x){break;}if(sum > x&&(sum-x)%2==0){break;}}return t;
}
void solve()
{int n, m;cin>>n>>m;int t1 = func(n), t2 = func(m);if(t1==t2){printf("Draw");}else if(t1 < t2){printf("Tari %d",t1);}else{printf("Erini %d",t2);}
}
int main()
{ios::sync_with_stdio(false);solve();return 0;
}

D

思路+代码

最近看了BFS，所以就用BFS写的

#include <bits/stdc++.h>
#include <algorithm>
#include <stack>
#define mem(s, i) memset(s, i, sizeof(s))
#define INF 0x3f3f3f3f;
#define ll long long
using namespace std;
int n, m;
int p[105][105];
int vim[105][105];
int dx[2] = {0,1};
int dy[2] = {1,0};
struct node{int x, y;int price;
}head, tail;
queue<node> q;
bool check(int x, int y){if(x <= n&&x>=1&&y <= m&&y >= 1){return true;}return false;
}
void bfs(int x, int y, ll pri){head.x = x, head.y = y, head.price = pri;vim[x][y] = p[x][y];q.push(head);while(!q.empty()){tail = q.front();q.pop();for(int i = 0;i < 2;i++){head.x = tail.x+dx[i];head.y = tail.y+dy[i];if(check(head.x,head.y)){head.price = tail.price+p[head.x][head.y];if(vim[head.x][head.y]&&head.price<=vim[head.x][head.y]){continue;}vim[head.x][head.y] = head.price;q.push(head);}}}
}
void solve()
{scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){scanf("%d",&p[i][j]);}}bfs(1,1,p[1][1]);printf("%lld",vim[n][m]);
}
int main()
{ios::sync_with_stdio(false);solve();return 0;
}

E

思路+代码

结构体，记录输入的顶点。
我们输入的顶点需要比较大小，因为我们要得到从$1$~$n$间哪段需要截断，以便后续的排序。
$cmp$排序，先比较两个点的目的顶点是否相同，相同就按起点从小到大的排序规则，否则就按目的顶点从小到大的规则排序。
重要代码片段
起点为$flag$=0。我们判断这里其实有判重的意思，就是需要截断的n对顶点的重合部分就是$flag>s[i].a$那部分。

int flag = 0, ans = 0;for(int i = 0;i < m;i++){if(flag <= s[i].a){flag = s[i].b;ans++;}}

完整代码

#include <bits/stdc++.h>
#include <algorithm>
#include <stack>
#define mem(s, i) memset(s, i, sizeof(s))
#define INF 0x3f3f3f3f;
#define ll long long
using namespace std;
const int N = 1e5+5;
struct node{int a, b;
}s[N];
bool cmp(node x, node y){if(x.b == y.b){return x.a < y.a;}return x.b < y.b;
}
void solve()
{int n, m;scanf("%d%d",&n,&m);for(int i = 0;i < m;i++){scanf("%d%d",&s[i].a,&s[i].b);if(s[i].a > s[i].b)swap(s[i].a,s[i].b);}sort(s,s+m,cmp);int flag = 0, ans = 0;for(int i = 0;i < m;i++){if(flag <= s[i].a){flag = s[i].b;ans++;}}printf("%d",ans);
}
int main()
{ios::sync_with_stdio(false);solve();return 0;
}