上海计算机学会4月月赛 丙组题解

标签：$gcd$
题意：求$a$和$b$的最大公约数（$1\le a,b\le 1,000,000,000$）
题解：辗转相除法$gcd(a,b)=gcd(b,a\%b)$
代码：

#include <bits/stdc++.h>
using namespace std;int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}int main() {int a, b;cin >> a >> b;cout << gcd(a, b) << endl;// 手写gcd 或者 直接调用库函数__gcd// cout << __gcd(a, b) << endl;return 0;
}

标签：字符串
题意：给定一个字符串$p$和字符串$t$，判断$p$是否是$t$的一个子序列。子序列就是字符串中保持原本顺序但不必连续的字符序列。（$1\le \mid p\mid \le \mid t\mid \le 300,000$）
题解：从前往后遍历字符串$p$的每个字符，同时遍历字符串$t$，一直到找到对应字符或者到最后一个字符为止，找到后同时往后推一位，继续找；没找到，直接输出$No$跳出即可。
代码：

#include <bits/stdc++.h>
using namespace std;int main() {string p, t;cin >> p >> t;int n = p.size(), m = t.size();for (int i = 0, j = 0; i < n; i++, j++) {while (j < m && t[j] != p[i]) j++;if (j == m) { // 到t字符串最后没找到对应的字符cout << "No";return 0;}}cout << "Yes";return 0;
}

标签：逆序数、思维、前缀和
题意：给定一个长度为$n$的$01$序列，$1$和$0$相邻就将$1$调后面去，问最终调换的次数。
（$1\le n\le 300,000$）
题解：很典型的一个逆序数，求每个数后面有多少的比自己小的数，因为$n$比较大，两层循环去求逆序数肯定会超时，这边可以通过归并排序或者树状数组之类的数据结构去查询。但是这个序列中又只有$1$和$0$，那我们可以通过后缀和统计一下$0$的数量，到时候从前往后跑一下每个$1$的位置，统计一下每个$1$的位置后面有多少个$0$的数。
或者反过来想看看每个$0$之前有多少个$1$，直接正着跑一边，对应计数即可。下面给出两种算法的代码
这边注意一个细节，最坏情况 数量可能爆$int$，得开$longlong$。
代码 1：

#include <bits/stdc++.h>
using namespace std;string s;
int suf[300005]; // 后缀0的数量int main() {cin >> s;int n = s.size();long long ans = 0;for (int i = n - 1; i >= 0; i--) {suf[i] = suf[i + 1];if (s[i] == '0') suf[i]++;}for (int i = 0; i < n; i++) {if (s[i] == '1') ans += suf[i + 1];}cout << ans << endl;return 0;
}

代码 2：

#include <bits/stdc++.h>
using namespace std;int main() {string s;cin >> s;int n = s.size();long long ans = 0, cnt = 0; // cnt: 前缀1的数量for (int i = 0; i < n; i++) {if (s[i] == '1') cnt++;else ans += cnt;}cout << ans << endl;return 0;
}

标签：$gcd$、结构体排序
题意：给定正整数 $n$，请按从小到大的顺序输出所有大于$0$且小于$1$的，分母不超过$n$的最简分数。（$2\le n\le 500$）
题解：按照题目要求把所有的情况都列出来存到结构体数组里面，这边判一下是否互质，不互质就不存了，不然到时候会有重复（比如$1/2，2/4$化成最简都是$1/2$）。然后按照分数值从小到大排序一下，输出即可。
代码：

#include <bits/stdc++.h>
using namespace std;int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}struct node {int a, b;double c;
}p[250005];bool cmp(node x, node y) {return x.c < y.c;
}int main() {int n, cnt = 0;cin >> n;for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= n; j++) {if (gcd(i, j) == 1) { // 互质p[++cnt].a = i;p[cnt].b = j;p[cnt].c = 1.0 * p[cnt].a / p[cnt].b;}}}sort(p + 1, p + 1 + cnt, cmp);for (int i = 1; i <= cnt; i++) {cout << p[i].a << "/" << p[i].b << endl;}return 0;
}

标签：$bfs$
题意：给定一个$n$ x $m$的数字迷宫，每个位置有一个数字$a[i][j]$，表示走到该格子之后，可以往上下左右任意方向移动$a[i][j]$的距离。求从$(1,1)$移动到$(n,m)$位置，最少需要走多少次。
题解：裸的$bfs$，在基础模板上改下变化的新移动位置即可。
代码：

#include <bits/stdc++.h>
using namespace std;int n, m, a[1005][1005];
int vis[1005][1005];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};struct node {int x, y, step;
};int main() {cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> a[i][j];queue<node> q;q.push({1, 1, 0});vis[1][1] = 1;while (!q.empty()) {node cur = q.front();if (cur.x == n && cur.y == m) {cout << cur.step << endl;return 0;}q.pop();for (int i = 0; i < 4; i++) {int nx = cur.x + a[cur.x][cur.y] * dx[i];int ny = cur.y + a[cur.x][cur.y] * dy[i];if (nx < 1 || nx > n || ny < 1 || ny > m) continue;if (vis[nx][ny]) continue;vis[nx][ny] = 1;q.push({nx, ny, cur.step + 1});}}cout << "No Solution" << endl;return 0;
}