AtCoder Beginner Contest 265
2022/8/26 23:27:50
本文主要是介绍AtCoder Beginner Contest 265,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
AtCoder Beginner Contest 265
https://atcoder.jp/contests/abc265
A - Apple
有两种购买策略:\(x\) 元买一个苹果 or \(y\) 元买三个苹果,问买 \(n\) 个苹果最少要花多少钱
#include <bits/stdc++.h> using namespace std; int main () { int x, y, n; cin >> x >> y >> n; if (n < 3 || x * 3 <= y) { cout << x * n << endl; } else { cout << (n/3)*y + (n%3)*x; } }
B - Explore
从 \(i-1\) 走到 \(i\) 点需要消耗 \(a_i\), 有 \(m\) 个点 \(b_i\) 存在补助,初始有 \(t\), 问能不能从 \(1\) 走到 \(n\)
注意先减再添加补助
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e5 + 5; int n, m, t; int a[N], b[N]; signed main () { cin >> n >> m >> t; for (int i = 2; i <= n; i++) cin >> a[i]; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; b[x] = y; } for (int i = 2; i <= n; i++) { t -= a[i]; if (t <= 0) { cout << "No\n"; return 0; } t += b[i]; } cout << "Yes\n"; } //模拟
C - Belt Conveyor
有 \(n*m\) 的地图,初始在 \((1,1)\), 规则:\(U\) 向上一格,\(D\) 向下一格,\(R\) 向右一格,\(R\) 向左一格。
问走到哪里时下一步就出界,永不出界输出 \(-1\)
按题意模拟,如果走完了整个地图还不出界,则永不出界。
#include <bits/stdc++.h> using namespace std; const int N = 505; int n, m; char a[N][N]; bool check (int x, int y) { if (x > n || x <= 0 || y > m || y <= 0) return false; return true; } signed main () { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { cin >> a[i][j]; } int x = 1, y = 1, sx, sy; int cnt = n * m; while (1) { cnt --; sx = x, sy = y; if (a[x][y] == 'U') x --; else if (a[x][y] == 'D') x ++; else if (a[x][y] == 'R') y ++; else if (a[x][y] == 'L') y --; if (!check (x, y)) { cout << sx << ' ' << sy; break; } if (cnt <= 0) { cout << -1; break; } //x = sx, y = sy; } } //一直走走到出界
D - Iroha and Haiku (New ABC Edition)
现有一数列 \(A=(A_0,...,A_{N-1})\), 问能不能找到四点 \(x,y,z,w\), 满足:
暴力 \(set\) 查找
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 2e5 + 5; int n, p, q, r; int sum[N]; signed main () { cin >> n >> p >> q >> r; set<int> s; s.insert (0); for (int i = 1; i <= n; i++) { int x; cin >> x; sum[i] = sum[i-1] + x; s.insert (sum[i]); } for (int i = 1; i <= n; i++) { if (s.count (sum[i-1]+p) && s.count (sum[i-1]+p+q) && s.count (sum[i-1]+p+q+r)) { cout << "Yes\n"; return 0; } } cout << "No\n"; } //sum[y-1]-sum[x-1]=p //sum[z-1]-sum[y-1]=q //sum[w-1]-sum[z-1]=r
E - Warp
假设现在在 \((x,y)\), 下一步可以选择走到 \((x+A,y+B)\) or \((x+C,y+D)\) or \((x+E,y+F)\), 且有 \(m\) 个障碍, 问走 \(n\) 步能有多少种可能的路径
定义状态 \(f[i][j][k]:\) 表示 1走了 \(i\) 次,2走了 \(j\) 次,3走了 \(k\) 次。
线性 dp 路径转移即可
#include <bits/stdc++.h> #define int long long using namespace std; typedef pair<int, int> pii; const int N = 305, mod = 998244353; int A, B, C, D, E, F, n, m; int f[N][N][N]; //1走了i次,2走了j次,3走了k次 signed main () { cin >> n >> m >> A >> B >> C >> D >> E >> F; set<pii> s; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; s.insert({x, y}); } f[0][0][0] = 1; for (int i = 0; i <= n; i++) for (int j = 0; j <= n - i; j++) for (int k = 0; k <= n - i - j; k++) { int x = i*A + j*C + k*E, y = i*B + j*D + k*F; if (!i && !j && !k) continue; if (s.count ({x, y})) continue; if (i) f[i][j][k] += f[i-1][j][k]; if (j) f[i][j][k] += f[i][j-1][k]; if (k) f[i][j][k] += f[i][j][k-1]; f[i][j][k] %= mod; } int ans = 0; for (int i = 0; i <= n; i++) for (int j = 0; j <= n - i; j++) { ans += f[i][j][n-i-j], ans %= mod; } cout << ans; } //移动n次
F - Manhattan Cafe
题意:有两点 \(p,q\), 各有 \(n\) 个维度,问有多少个点满足到 \(p\) 和 \(q\) 的曼哈顿距离均 \(\leq d\)
分析:可以把这样的点分为两类————在 \(p,q\) 之间的,在 \(p,q\) 外的。
对于在两点之外的 \(x_i\), 每走一格,\(d_{p_i},d_{q_i}\) 都会同时 \(\pm 1\);
对于在两点之间的 \(x_i\), 则是 \(d_{p_i}+d_{q_i}=\) 定值,即 \(d_{p_i}\pm1,d_{q_i}\mp1\)。
由这两种特殊性质得,可以维护矩阵的主对角线和副对角线的前缀和,即可dp 转移
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 1005, M = 105, mod = 998244353; int p[M], q[M], dp[N][N], C[N][N], E[N][N]; int n, d; signed main() { cin >> n >> d; for (int i = 0; i < n; i++) cin >> p[i]; for (int i = 0; i < n; i++) cin >> q[i]; dp[0][0] = 1; for (int k = 0; k < n; k++) { int z = abs(p[k] - q[k]); for (int i = 0; i <= d; i++) for (int j = 0; j <= d; j++) { C[i+1][j+1] = (C[i][j] + dp[i][j]) % mod; //主对角线 E[i+1][j] = (E[i][j+1] + dp[i][j]) % mod; //副对角线 dp[i][j] = (C[i][max(j-z, 0ll)] + C[max(i-z, 0ll)][j]) % mod; int m = max(z - j, 0ll); if (i >= m) dp[i][j] = (dp[i][j] + E[i+1-m][j-z+m]) % mod; if (i >= z) dp[i][j] = (dp[i][j] - E[i-z][j+1] + mod) % mod; } } int ans = 0; for (int i = 0; i <= d; i++) for (int j = 0; j <= d; j++) ans = (ans + dp[i][j]) % mod; cout << ans; }
这篇关于AtCoder Beginner Contest 265的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享