题目链接：https://atcoder.jp/contests/abc467/tasks

A - Obesity#

根据题目给出的公式计算 $BMI$ 即可。注意输入的身高 $H$ 单位为厘米，需要先乘 $0.01$ 转换为米，所以 $BMI = \frac{W}{(H \times 0.01)^2}$ 。最后判断 $BMI$ 是否大于等于 $25$ ，满足就输出 $Yes$ ，否则输出 $No$ 。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
using ull = unsigned long long;
6
#define endl '\n'
7
#define mod 998244353
8
typedef pair<ll, ll> pll;
9
typedef pair<int, int> pii;
10

11
void solved() {
12
    int h, w;
13
    cin >> h >> w;
14
    if(w * 1.0 / (h * h * 0.0001)  >= 25)
15
        cout << "Yes" << endl;
16
    else cout << "No" << endl;
17
}
18

19
int main() {
20
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
21
    int _ = 1;
22
    //cin >> _;
23
    while (_--) {
24
        solved();
25
    }
26
    return 0;
27
}

B - Keep the Change#

对于第 $i$ 家商店，商品价格为 $A_i$ ，支付了 $B_i$ ，所以找零为 $B_i - A_i$ 。当 $s_i$ 为 $take$ 时高桥拿走了找零，并没有产生损失；当 $s_i$ 为 $keep$ 时没有拿走找零，相比每次都拿走找零的情况就损失了 $B_i - A_i$ 元。我们遍历所有商店，将所有 $keep$ 对应的找零累加起来就是最终答案。时间复杂度为 $O(N)$ 。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
using ull = unsigned long long;
6
#define endl '\n'
7
#define mod 998244353
8
typedef pair<ll, ll> pll;
9
typedef pair<int, int> pii;
10

11
int a[110], b[110];
12

13
void solved() {
14
    int n; cin >> n;
15
    vector<string> s(n + 1);
16
    for(int i = 1; i <= n;i++){
17
        cin >> a[i] >> b[i] >> s[i];
18
    }
19
    ll ans = 0;
20
    for(int i = 1; i <= n;i++)
21
        if(s[i] == "keep")
22
            ans += b[i] - a[i];
23
    cout << ans << endl;
24
}
25

26
int main() {
27
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
28
    int _ = 1;
29
    //cin >> _;
30
    while (_--) {
31
        solved();
32
    }
33
    return 0;
34
}

C - Adjacent Sums (easy)#

这题因为 $M = 2$ ，所以对一个数增加两次不会改变它模 $2$ 的余数。因此每个 $A_i$ 最多只需要增加一次，我们只需要判断哪些位置的奇偶性需要改变。
首先考虑不修改 $A_1$ 的情况。我们从左往右遍历，对于当前位置 $i$ ，前面的 $A_i$ 已经确定，如果 $(A_i + A_{i + 1}) \bmod 2 \neq B_i$ ，那么只能让 $A_{i + 1}$ 加一来满足条件，同时让操作次数 $cnt$ 加一。这样一直遍历到末尾，就能得到一种合法方案。
不过 $A_1$ 也可以选择加一。如果将上面方案中所有数的修改状态全部取反，即原来加一的数不加，原来不加的数加一，那么任意一对相邻的数都会同时改变两次，它们的和模 $2$ 不变，所以仍然是一种合法方案。这个方案的操作次数就是 $N-cnt$ 。
由于第一个数只有修改和不修改两种情况，后面的修改状态又都会被前一个数唯一确定，所以所有方案就在这两种情况中。最终答案为 $\min(cnt, N-cnt)$ ，时间复杂度为 $O(N)$ 。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
using ull = unsigned long long;
6
#define endl '\n'
7
#define mod 998244353
8
typedef pair<ll, ll> pll;
9
typedef pair<int, int> pii;
10

11
void solved() {
12
    int N, M;
13
    cin >> N >> M;
14
    vector<int> A(N + 1, 0), B(N, 0);
15
    for(int i = 1; i <= N;i++) cin >> A[i];
16
    for(int i = 1; i < N;i++) cin >> B[i];
17

18
    int cnt = 0;
19
    for(int i = 1; i < N;i++){
20
        if((A[i] + A[i + 1]) % 2 != B[i]){
21
            A[i + 1]++; cnt++;
22
        }
23
    }
24
    cout << min(cnt, N - cnt) << endl;
25
}
26

27
int main() {
28
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
29
    int _ = 1;
30
    //cin >> _;
31
    while (_--) {
32
        solved();
33
    }
34
    return 0;
35
}

D - Concentric Circles#

对于两个不同的点 $P,Q$ ，所有到 $P,Q$ 距离相等的点组成线段 $PQ$ 的垂直平分线。也就是说，圆 $C_1$ 的圆心必须在线段 $PQ$ 的垂直平分线上。同理，圆 $C_2$ 的圆心必须在线段 $RS$ 的垂直平分线上。因此题目可以转化为判断这两条垂直平分线是否存在公共点。
令向量 $\vec{PQ}=(a_1,b_1)$ ， $\vec{RS}=(a_2,b_2)$ 。如果它们的行列式 $a_1b_2-a_2b_1 \neq 0$ ，说明两条线段不平行，那么它们的垂直平分线也不平行，一定存在唯一交点，直接输出 $Yes$ 。
如果行列式等于 $0$ ，两条垂直平分线相互平行，此时只有它们重合才存在公共点。我们将 $\vec{PQ}$ 除以 $\gcd(|a_1|,|b_1|)$ 得到最简方向向量 $(dx,dy)$ 。线段 $PQ$ 中点在这个方向上的投影可以用 $dx(P_x+Q_x)+dy(P_y+Q_y)$ 表示，这里使用坐标和代替中点坐标是为了避免浮点数。线段 $RS$ 同理计算，如果两者投影相等，就说明两条垂直平分线重合，输出 $Yes$ ，否则输出 $No$ 。
每组数据只进行了常数次计算，时间复杂度为 $O(TlogV)$ ，其中 $V$ 为坐标差的绝对值， $logV$ 来自求最大公约数。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
using ull = unsigned long long;
6
#define endl '\n'
7
#define mod 998244353
8
typedef pair<ll, ll> pll;
9
typedef pair<int, int> pii;
10

11
void solved() {
12
    ll px, py, qx, qy, rx, ry, sx, sy;
13
    cin >> px >> py >> qx >> qy >> rx >> ry >> sx >> sy;
14

15
    ll a1 = qx - px, b1 = qy - py;
16
    ll a2 = sx - rx, b2 = sy - ry;
17

18
    ll determinant = a1 * b2 - a2 * b1;
19
    bool ok;
20
    if (determinant != 0) ok = true;
21
    else{
22
        ll g = gcd(abs(a1), abs(b1));
23
        ll dx = a1 / g, dy = b1 / g;
24

25
        ll projection1 = dx * (px + qx) + dy * (py + qy);
26
        ll projection2 = dx * (rx + sx) + dy * (ry + sy);
27
        ok = projection1 == projection2;
28
    }
29
    std::cout << (ok ? "Yes" : "No") << endl;
30
}
31

32
int main() {
33
    ios::sync_with_stdio(false), cin.tie(nullptr), std::cout.tie(nullptr);
34
    int _ = 1;
35
    cin >> _;
36
    while (_--) {
37
        solved();
38
    }
39
    return 0;
40
}

Mkrari的个人博客

A - Obesity#

B - Keep the Change#

C - Adjacent Sums (easy)#

D - Concentric Circles#