阅读量:0
2022年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛
2024.8.2 12:00————16:00
过题数790/1500
补题数943.33/1500
- A+B Problem
- Komorebi的数学课
- 次佛锅
- Setsuna的K数列
- Wiki下象棋
- 黄金律法
- 天气预报
- 叠硬币
- A+B Problem again
- 史东薇尔城
- 取模
- 剪绳子
- 数硬币
- 截肢葛瑞克
- 上海施工小学
A - A+B Problem
题解：
给出一个长度为n的数组，对于数组中的每一个数字a，再数组中的其他数字中找到一个b使得a+b最大。输出n个数字。
找出数组最大值并判断有几个，有多个的话输出所有的数字加上最大值的结果即可，只有一个的话，最大的数字要加上第二大的数字，别的加上最大的数字即可。
代码：
#include<bits/stdc++.h> using namespace std; #define int long long int a[100005]; int an[100005]; signed main() { int n; cin >> n; int ma = 0; int ma2 = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; if(a[i] > ma)ma = a[i]; } int t = 0; int wz; for (int i = 1; i <= n; i++) { if(ma == a[i]){ wz = i; t++; continue; } an[i] = a[i]+ma; if(an[i] > ma2)ma2 = an[i]; } if(t == 1) { for (int i = 1; i <= n; i++) { if(i == wz)an[i] = ma2; cout << an[i] << ' '; } } else { for (int i = 1; i <= n; i++) { if(a[i] == ma)an[i] = a[i]+ma; cout << an[i] << ' '; } } return 0; } B - Komorebi的数学课
题解：
输出n的n次方mod（n+2）
代码：
#include<bits/stdc++.h> using namespace std; #define int long long int n; int qpow(int base,int power,int mod) { int res = 1; while(power) { if(power & 1)res= res*base%mod; base= base*base%mod; power >>=1; } return res; } signed main() { cin >> n; cout << qpow(n,n,n+2); return 0; } C - 次佛锅
题解：
第一行给出一串字符串，表示这个食材有多少个，相同食材可能多次出现。
用map存取查找即可。
代码：
#include<bits/stdc++.h> using namespace std; #define int long long int n; string s; int t; map<string,int>mp; signed main() { getline(cin,s); string p = " "; int lt = 0; for (int i = 0; i < s.length(); i++) { while(('a' <= s[i] && s[i] <= 'z') || 'A' <= s[i] && s[i] <= 'Z') { p = p+s[i]; i++; } while('0' <= s[i] && s[i] <= '9') { lt = lt*10 + s[i]-'0'; i++; } if(s[i] == ' ') { if('0' <= s[i-1] && s[i-1] <= '9') { mp[p] += lt; p = ' '; lt = 0; } } } mp[p] += lt; cin >> t; while(t--) { string q; cin >> q; q = ' '+q; cout << mp[q] << endl; } return 0; } D - Setsuna的K数列
最近好像总是遇到类似题，不知道是不是我的错觉，就是这种用位运算代替直接运算的，会方便很多，但敏感度不够，更多的是看感觉。
题解：
给定俩个整数n和k，创建一个集合A，包含k的所有整数次幂，去A中任意个元素相加，并放进一个新的集合B，将B中的元素从小到大排序输出第n项。
可以考虑到其实就是从第1个数字到第n个数字，每个位上的1分别代表加上了k的i次方，且就是一个递增的序列，所以直接快速幂输出即可。
代码：
#include<bits/stdc++.h> using namespace std; #define int long long int n; string s; int t; map<string,int>mp; signed main() { getline(cin,s); string p = " "; int lt = 0; for (int i = 0; i < s.length(); i++) { while(('a' <= s[i] && s[i] <= 'z') || 'A' <= s[i] && s[i] <= 'Z') { p = p+s[i]; i++; } while('0' <= s[i] && s[i] <= '9') { lt = lt*10 + s[i]-'0'; i++; } if(s[i] == ' ') { if('0' <= s[i-1] && s[i-1] <= '9') { mp[p] += lt; p = ' '; lt = 0; } } } mp[p] += lt; cin >> t; while(t--) { string q; cin >> q; q = ' '+q; cout << mp[q] << endl; } return 0; } E - Wiki下象棋
当时写了dfs，怎么都想不起来bfs怎么写，最后果然是没有写出来。dfs一直tle，优化也没用。
题解：
t组数据，每组给出棋盘的行列数和每个棋子的个数，坐标，起点和终点。
bfs跑俩遍就可以，对于马脚特判一下。
代码：
#include<bits/stdc++.h> using namespace std; #define int long long const int N = 310; int dx[] = {-2,-2,-1,1,2,2,1,-1}; int dy[] = {-1,1,2,2,1,-1,-2,-2}; int t; bool st[N][N]; int vis[N][N]; int n,m,k,a,b,c,d; int ans = 1e9; int ans1 = 1e9; typedef pair<int,int> PII; void bfs(int x,int y) { queue<PII>q; memset(vis,-1,sizeof vis); vis[x][y] = 0; q.push({x,y}); while(!q.empty()) { x=q.front().first; y=q.front().second; for (int i = 0; i < 8; i++) { int ax = x+dx[i],ay = y+dy[i]; if(ax < 1 || ax > n || ay < 1 || ay > m)continue; if(st[ax][ay])continue; if(vis[ax][ay] == -1) { vis[ax][ay] = vis[x][y]+1; q.push({ax,ay}); } } q.pop(); } cout << vis[c][d] << ' '; return ; } void bfs1(int x,int y) { queue<PII>q; memset(vis,-1,sizeof vis); vis[x][y] = 0; q.push({x,y}); while(!q.empty()) { x = q.front().first; y = q.front().second; for (int i = 0; i < 8; i++) { int ax = x+dx[i],ay = y+dy[i]; if(ax < 1 || ax > n || ay < 1 || ay > m)continue; if(dx[i] == -2 && st[x-1][y])continue; if(dx[i] == 2 && st[x+1][y])continue; if(dy[i] == 2 && st[x][y+1])continue; if(dy[i] == -2 && st[x][y-1])continue; if(st[ax][ay])continue; if(vis[ax][ay] == -1) { vis[ax][ay] = vis[x][y]+1; q.push({ax,ay}); } } q.pop(); } cout << vis[c][d] << endl; return ; } signed main() { cin >> t; while(t--) { memset(st,0,sizeof st); cin >> n >> m >> k >> a >> b >> c >> d; while(k--) { int la,lb; cin >> la >> lb; st[la][lb] = true; } ans = 5000; memset(vis,0,sizeof vis); bfs(a,b); ans1 = 5000; memset(vis,0,sizeof vis); bfs1(a,b); } } F - 黄金律法
很奇怪的一道题，当时看过的人多直接试了一下，结果竟然过了。好像是不等式的知识？
题解：
有n个武器的属性值和n个魔法的属性值，现在要求单个属性对应单个魔法相乘求和的最小值。
一个递增一个递减相乘求和即可。
代码：
#include<bits/stdc++.h> using namespace std; #define int long long const int N = 1e6+10; int t; int w[N],m[N]; signed main() { cin >> t; while(t--) { int n; cin >> n; for (int i = 1; i <= n; i++)cin >> w[i]; sort(w+1,w+1+n); for (int i = 1; i <= n; i++)cin >> m[i]; sort(m+1,m+1+n,greater<int>()); int ans = 0; for (int i = 1; i <= n; i++) { ans += (w[i]*m[i]); } cout << ans << endl; } return 0; } G - 天气预报
题解：
未来n天的天气用一个字符串来表示，0表示晴朗，1表示会下青蛙。现在要求找出区间，可以一天都不选，使得他在这段时间内至少可以出去玩a天，休息b天。
对于这段区间的左节点循环遍历，右节点二分判断找到最接近的满足条件的日子，后面的所有日子都满足，直接相加就可以，很简单的二分。
代码：
#include<bits/stdc++.h> using namespace std; #define int long long #define ll long long const int N = 1e6+10; int n,a,b; int aa[N],bb[N]; //晴朗 休息 int check(int i,int j) { ll p = aa[j] - aa[i-1]; ll q = bb[j] - bb[i-1]; if(p >= a && q >= b)return 1; return 0; } signed main() { cin >> n >> a >> b; string s; cin >> s; s = ' '+s; for (int i = 1; i <= n; i++) { if(s[i] == '0') { aa[i] = aa[i-1]+1; bb[i] = bb[i-1]; } else { bb[i] = bb[i-1]+1; aa[i] = aa[i-1]; } } int ans = 0; // int m = 0; // for (int i = 1; i <= n; i++) { // if(aa[i]-aa[m] >= a && bb[i]-bb[m] >= b){ // ans += (n-i+1); // m++; // } // } // for (int i = m; i <= n; i++) { // if(aa[n]-aa[i] >= a && bb[n]-bb[i] >= b) { // ans++; // } // else break; // } if(a==0&&b==0)ans++;//特殊情况：当a和b均为0时，可以一天也不选 for(int i=1;i<=n;i++){ ll l=i,r=n; while(l<r){ ll mid=(l+r)/2; if(check(i,mid))r=mid; else l=mid+1; } if(check(i,l))ans+=(n-l+1); } cout << ans << endl; return 0; } J - 史东薇尔城
题解：
有n个节点和m条边，询问t次，每次si，ti。需要从si跑回1再跑到ti，球最短路径。
也就是从1跑到si再跑到ti。跑一遍Dijkstra然后输出最短距离即可。
代码：
#include<bits/stdc++.h> using namespace std; #define int long long const int N = 1e6+10; int n,m; int dis[N],vis[N]; const int INF = 0x3f3f3f3f; typedef pair<int,int>PII; #define endl "\n" struct ty { int to,next,w; }edge[N+1000]; int cnt = 0; int head[N]; void add_edge(int u,int v,int w) { cnt++; edge[cnt].to = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt; } void dij(int x) { priority_queue<PII,vector<PII>,greater<PII>>pq; pq.push({0,x}); dis[x] = 0; while(!pq.empty()) { int x = pq.top().second; pq.pop(); //一开始一直写在continue以后跑死循环了 if(vis[x])continue; vis[x] = 1; for (int i = head[x]; i!=-1; i = edge[i].next) { if(!vis[edge[i].to]) { if(dis[edge[i].to] > dis[x] + edge[i].w) { dis[edge[i].to] = dis[x] + edge[i].w; pq.push({dis[edge[i].to],edge[i].to}); } } } } } signed main( ){ scanf("%lld %lld",&n,&m); memset(head,-1,sizeof head); int a,b,c; for (int i = 1; i <= m; i++) { scanf("%lld %lld %lld",&a,&b,&c); add_edge(a,b,c); add_edge(b,a,c); } int t; scanf("%lld",&t); memset(dis,INF,sizeof dis); memset(vis,0,sizeof vis); dij(1); //别再里面跑！浪费时间！ int si,ti; while(t--) { cin >> si >> ti; printf("%lld\n",dis[si]+dis[ti]); } return 0; } L - 剪绳子
题解：
十米的绳子，C表示在这个位置减一刀，A表示在这个位置询问这条绳子的长度。
怀疑是数据太水了，暴力跑了一遍就过了。
官方给出的题解是一开始把所有点当成一个绳子，然后把每一截绳子练成一个并查集，倒着往前遍历，C表示连上这俩个并查集，A表示查询。储存输出。
代码：
#include<bits/stdc++.h> using namespace std; #define int long long set<double>p; signed main() { int q; cin >> q; while(q--) { char s; cin >> s; double m; cin >> m; if( s== 'A') { double gg = 0; double now = 10; for (auto x: p) { if(x > m){ now = x; break; } else gg = x; } double res = now-gg; printf("%0.5lf\n",res); } else { p.insert(m); } } return 0; } 