AtCoder Beginner Contest 266 A-D
2022/8/28 6:23:58
本文主要是介绍AtCoder Beginner Contest 266 A-D,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
AtCoder Beginner Contest 266
https://atcoder.jp/contests/abc266
EF 待补
A - Middle Letter
输出字符串最中间的那个字母
#include <bits/stdc++.h> using namespace std; int main () { string s; cin >> s; cout << s[(s.size()+1)/2-1]; }
B - Modulo Number
题意:\(N\in [-10^{18}, 10^{18}], x\in [0, 998244352]\), 给定 \(N\), 求 \(x\),使得 \((N-x) \%\,998244353=0\)
分析:不难发现就是要找到一个和 \(N\) 同余的 \(x\)
#include <bits/stdc++.h> #define int long long using namespace std; const int mod = 998244353; int n; int MOD (int x) { while (x < 0) x += mod; return x % mod; } signed main () { cin >> n; cout << MOD (n); } //倍数 //N与x同余
C - Convex Quadrilateral
题意:给四个点的坐标,问构成的图形是否为凸多边形
注:给的点满足不重合,不共线,不相邻的边一定没有公共点,也就是保证四个点一定构成四边形
分析:高中知识,分别判断两条对角线是否都能把两个点隔开(不在同一边),判断的方式就是————
设对角线 \(AC\) 方程为 \(Ax+By+C=0\), 若 \((Ax_b+By_b+C)*(Ax_d+By_d+C)<0\), 则 \(B,D\) 在对角线 \(AC\) 的两边;同理再判断一下对角线 \(BD\) 能否把 \(A,C\) 划分到两边即可。
至于直线方程怎么写,相信也不难,两点式一般式之类的都能解出来,我手算的结果是:
\(A = y_1-y_2, B = x_2-x_1, C = x_1*y_2 - x_2*y_1;\)
#include<bits/stdc++.h> #define int long long using namespace std; int x[5], y[5]; signed main () { for (int i = 1; i <= 4; i++) cin >> x[i] >> y[i]; //判两条对角线 int A, B, C, X, Y; A = y[1] - y[3], B = x[3] - x[1], C = x[1]*y[3] - x[3]*y[1]; X = A*x[2] + B*y[2] + C, Y = A*x[4] + B*y[4] + C; //cout << X << ' ' << Y << endl; if (X * Y > 0) { cout << "No\n"; return 0; } A = y[2] - y[4], B = x[4] - x[2], C = x[2]*y[4] - x[4]*y[2]; X = A*x[1] + B*y[1] + C, Y = A*x[3] + B*y[3] + C; if (X * Y > 0) { cout << "No\n"; return 0; } cout << "Yes"; } //判断是否为凸多边形 //判断点是否在直线的两边 //Ax+By+C < 0 //A = y1-y2, B = x2-x1, C = x1y2 - x2y1;
D - Snuke Panic (1D)
这一道题和 \(kuangbin\) 专题里的免费馅饼十分相似
题意:\(t_i\) 时刻在 \(x_i\) 处会出现价值为 \(a_i\) 的东西。人一开始在 \(0\) 的位置,每次只能向右或向左移动一格,且花费一单位时间。人与物品的坐标取值只可能为 \(0,1,2,3,4\)。问人能得到的最大价值为多少
分析:定义 \(dp\) 数组\(f_{i,j}\)表示第 \(i\) 秒时在位置 \(j\) 时所能得到的最大价值,然后逆推转移即可。
#include <bits/stdc++.h> #define endl "\n" #define int long long using namespace std; typedef pair<int, int> pii; const int N = 1e5 + 5; int n, m; int f[N][7]; //第i秒时在位置j int dx[] = {-1, 0, 1}; signed main () { ios::sync_with_stdio (0);cin.tie(0);cout.tie(0); memset (f, 0, sizeof f); cin >> n; for (int i = 0; i < n; i++) { int ti, xi, ai; cin >> ti >> xi >> ai; f[ti][xi] = ai; m = max (m, ti); } //cout << "m=" << m << endl; for (int t = m-1; t >= 0; t--) { f[t][0] += max (f[t+1][0], f[t+1][1]); for (int x = 1; x < 4; x++) { f[t][x] += max (f[t+1][x], max (f[t+1][x+1], f[t+1][x-1])); } f[t][4] += max (f[t+1][4], f[t+1][3]); cout << endl; } cout << f[0][0] << endl; }
E - Throwing the Die
F - Well-defined Path Queries on a Namori
这篇关于AtCoder Beginner Contest 266 A-D的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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专业技术文章分享