上海计算机学会 4 月月赛 丙组题解
本次比赛涉及知识点: g c d gcd gcd、字符串、逆序数、思维、前缀和、结构体排序、 b f s bfs bfs
比赛链接:https://iai.sh.cn/contest/61
第一题:T1最大公约数
标签: g c d gcd gcd
题意:求 a a a和 b b b的最大公约数( 1 ≤ a , b ≤ 1 , 000 , 000 , 000 1≤a,b≤1,000,000,000 1≤a,b≤1,000,000,000)
题解:辗转相除法 g c d ( a , b ) = g c d ( b , a % b ) gcd(a,b)=gcd(b,a\%b) 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;
}
第二题:T2子序列的判定
标签:字符串
题意:给定一个字符串 p p p和字符串 t t t,判断 p p p是否是 t t t的一个子序列。子序列就是字符串中保持原本顺序但不必连续的字符序列。( 1 ≤ ∣ p ∣ ≤ ∣ t ∣ ≤ 300 , 000 1≤∣p∣≤∣t∣≤300,000 1≤∣p∣≤∣t∣≤300,000)
题解:从前往后遍历字符串 p p p的每个字符,同时遍历字符串 t t t,一直到找到对应字符或者到最后一个字符为止,找到后同时往后推一位,继续找;没找到,直接输出 N o No 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;
}
第三题:T3交换的次数
标签:逆序数、思维、前缀和
题意:给定一个长度为 n n n的 01 01 01序列, 1 1 1和 0 0 0相邻就将 1 1 1调后面去,问最终调换的次数。
( 1 ≤ n ≤ 300 , 000 1≤n≤300,000 1≤n≤300,000)
题解:很典型的一个逆序数,求每个数后面有多少的比自己小的数,因为 n n n比较大,两层循环去求逆序数肯定会超时,这边可以通过归并排序或者树状数组之类的数据结构去查询。但是这个序列中又只有 1 1 1和 0 0 0,那我们可以通过后缀和统计一下 0 0 0的数量,到时候从前往后跑一下每个 1 1 1的位置,统计一下每个 1 1 1的位置后面有多少个 0 0 0的数。
或者反过来想看看每个 0 0 0之前有多少个 1 1 1,直接正着跑一边,对应计数即可。下面给出两种算法的代码
这边注意一个细节,最坏情况 数量可能爆 i n t int int,得开 l o n g l o n g long\ long long long。
代码 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;
}
第四题:T4排序分数
标签: g c d gcd gcd、结构体排序
题意:给定正整数 n n n,请按从小到大的顺序输出所有大于 0 0 0且小于 1 1 1的,分母不超过 n n n的最简分数。( 2 ≤ n ≤ 500 2≤n≤500 2≤n≤500)
题解:按照题目要求把所有的情况都列出来存到结构体数组里面,这边判一下是否互质,不互质就不存了,不然到时候会有重复(比如 1 / 2 , 2 / 4 1/2,2/4 1/2,2/4化成最简都是 1 / 2 1/2 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;
}
第五题:T5数字迷宫
标签: b f s bfs bfs
题意:给定一个 n n n x m m m的数字迷宫,每个位置有一个数字 a [ i ] [ j ] a[i][j] a[i][j],表示走到该格子之后,可以往上下左右任意方向移动 a [ i ] [ j ] a[i][j] a[i][j]的距离。求从 ( 1 , 1 ) (1,1) (1,1)移动到 ( n , m ) (n,m) (n,m)位置,最少需要走多少次。
题解:裸的 b f s bfs 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;
}