StarryCoding 入门教育赛 3 题解C++

本文主要是介绍StarryCoding 入门教育赛 3 题解C++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

比赛链接：https://www.starrycoding.com/contest/8

A. 坐标变换

语法题，考察输入输出、循环结构、数学运算。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const ll p = 998244353;
const int N = 2e5 + 9;void solve()
{int n;cin >> n;ll x = 0, y = 0;for (int i = 1; i <= n; ++i){ll dx, dy;cin >> dx >> dy;x += dx, y += dy;}cout << x << ' ' << y << '\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _;cin >> _;while (_--)solve();return 0;
}

B. 自助店评分

考察STL中struing, map的使用。

对STL不熟悉的同学可以看下《算法基础课》：https://www.starrycoding.com/course/1

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const ll p = 998244353;
const int N = 2e5 + 9;void solve()
{map<string, ll> mp;int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i){string s;ll x;cin >> s >> x;mp[s] = x;}ll ans = 0;for (int i = 1; i <= m; ++i){string s;cin >> s;ans = max(ans, mp[s]);}cout << ans << '\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _;cin >> _;while (_--)solve();return 0;
}

C.打字糕手

考察题目理解能力，字符串和下标变换灵活运用。

#include <bits/stdc++.h>
using namespace std;void solve()
{string s, t;cin >> s >> t;for(int i = 0, j = 0;i < t.length() && j < s.length(); ++ i){if(t[i] == s[j]){cout << i + 1 << ' ';j ++;}}cout << '\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _;cin >> _;while(_ --)solve();return 0;
}

D.电弧陷阱

类似这种给一个矩阵，然后有些位置不能去、被挡住、有传送门之类的，一般都需要用到 $b f s$ 。这种题就类似于走迷宫，需要保证走过的点不要再走，否则会让时间复杂度变高。

显然电弧陷阱会将整个矩阵分成好几部分连通区域，我们只需要在遍历矩阵的时候判断一下当前位置，是否可以作为出发点即可开始 $b f s$ 。

此时一个连通部分的答案 = . 的数量 + 电弧数量。

. 的数量我们可以通过找到所有不会被电弧困住的地方来计算，而难点在于如何算出 电弧 的数量。

最简单的方法就是使用set维护一个pair<x, y>直接去重，最后加上 set.size() 即可。

容易出错的地方在于，如果选择将 # 周围的点修改为其他字符做标记，那么一定要在 输入完成后 和 进行bfs之前 进行标记。

还需要注意，题目保证了至少一个点为 . ，因此答案至少为 1。

#include "bits/stdc++.h"char mp[1007][1007];int vis[1007][1007], n, m, ans;const int dir[] = {0, 1, 0, -1, 0};bool check_boom(int x, int y) { // 检查 {x, y} 是否有电弧for (int i = 0; i < 4; ++ i) {int nx = x + dir[i], ny = y + dir[i + 1];if (mp[nx][ny] == '#') return false;}return true;
}bool check(int x, int y) {return x >= 1 and x <= n and y >= 1 and y <= m and mp[x][y] != '#' and check_boom(x, y) and vis[x][y] == 0;
}void bfs(int x, int y) {// . and 电弧std::set<std::pair<int, int>> set_a;std::set<std::pair<int, int>> set_b;// now {x, y}std::queue <std::pair<int, int>> q;q.push({x, y});while (!q.empty()) {auto top = q.front(); q.pop();set_a.insert(top);for (int i = 0; i < 4; ++ i) {int nx = top.first + dir[i], ny = top.second + dir[i + 1]; // next_x, next_yif (check(nx, ny)) {q.push({nx, ny});vis[nx][ny] = 1;}}}// 遍历 . 的 set，检查其周围是否有 电弧for (auto &p : set_a) {for (int i = 0; i < 4; ++ i) {int nx = p.first + dir[i], ny = p.second + dir[i + 1];if (mp[nx][ny] == '.' and vis[nx][ny] == 0) set_b.insert({nx, ny});}}   int num = set_a.size() + set_b.size();    ans = std::max(ans, num);
}signed main() {std::cin >> n >> m;for (int i = 1; i <= n; ++ i) {for (int j = 1; j <= m; ++ j) {std::cin >> mp[i][j];}}for (int i = 1; i <= n; ++ i) {for (int j = 1; j <= m; ++ j) {if (vis[i][j] == 0 and mp[i][j] == '.') {ans = std::max(1, ans); // 只要有一个位置为 . ，答案就至少为1if (check_boom(i, j)) bfs(i, j);}}}std::cout << ans;
}

E.夜游江滩

定义 $d p [i]$ 表示从 $0$ 走到 $i$ 的方案数。

初始化 $d p [0] = 1$ 。

状态转移方程为： $\sum_{j=0}[k^j \le i]dp[j]$ 。

最后输出 $d p [n]$ 。

每次转移时间复杂度为 $O (l o g (i))$ ，于是总复杂度为 $O (n l o g n)$ 。

注意特判 $k = 1$ 的情况。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
ll dp[N];
const ll p = 1e9 + 7;void solve()
{int n, k;cin >> n >> k;if(k == 1){cout << 1 << '\n';return;}dp[0] = 1;for (int i = 1; i <= n; ++i){dp[i] = 0;}for (int i = 1; i <= n; ++i){for (ll j = 1; j <= i; j *= k){dp[i] = (dp[i] + dp[i - j]) % p;}}cout << dp[n] << "\n";
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _;cin >> _;while (_--)solve();return 0;
}