Sakana~
0%

AtCoder Beginner Contest 266 A-G

发表于 更新于 分类于

abc266 A-G 题解

AtCoder Beginner Contest 266 A-G

https://atcoder.jp/contests/abc266

A - Middle Letter

输出字符串最中间的那个字母

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>

using namespace std;

int main () {
    string s;
    cin >> s;
    cout << s[(s.size()+1)/2-1];
}

B - Modulo Number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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

题意：给四个点的坐标，问构成的图形是否为凸多边形
注：给的点满足不重合，不共线，不相邻的边一定没有公共点，也就是保证四个点一定构成四边形

分析：高中知识，分别判断两条对角线是否都能把两个点隔开（不在同一边），判断的方式就是————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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$ 专题里的免费馅饼十分相似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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

题意：n 轮游戏，每次可以丢一枚骰子，每次丢完可以选择结束游戏或者继续。
结束游戏时的分数为最终得分，如果一直按照最优策略来投，求 n 轮游戏的期望得分。

分析：最开始没读懂题，不知道什么时候结束为最优。
其实就是：如果下一轮投的点数比当前的期望更高，那么继续投下去就可以增加期望，所以会选择继续投
然后就可以直接 dp 了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>

using namespace std;
const int N = 105;
double f[N];

int main () {
    int n;
    cin >> n;
    f[1] = 3.5;
    for (int i = 2; i <= n; i++) {
        for (double j = 1.0; j <= 6.0; j++) {
            if (j >= f[i-1])    f[i] += j;
            else    f[i] += f[i-1];
        }
        f[i] /= 6;
    }
    cout << fixed << setprecision (8) << f[n] << endl;
}
//f[i]表示第i轮的期望,点数比期望大就继续投

F - Well-defined Path Queries on a Namori

题意

给定一个有 n 个点，n 条边的无向图，q 次查询两点 ui, vi 之间是否只存在一条简单路径(每条边只走一次)

分析

观察样例：
n 个点 n 条边，不难得出图上必定有且仅有一个环，那么这就是一个基环树。
相当于是一个环把树劈开，然后环上每一点都连着一条链。
可以以环上的每一点作为根节点，它连着的那条树上的所有点的根都是这个在环上的点。
则只需判断待查询的 u,v 点的根是否相同。

相同则 Yes，因为不会进入环，有且仅有一条简单路径；
不同则 No, 因为会进入环，不止一条简单路径。

Code

topsort + dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5, M = N*2;
int n, q;
int h[N], e[M], ne[M], idx;
int fa[N], d[N];

void add (int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void topsort () {
    queue <int> q;
    for (int i = 1; i <= n; i++) {
        if (d[i] == 1)  q.push (i);
    }

    while (!q.empty()) {
        int t = q.front();
        q.pop ();
        fa[t] = -1; //无环

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (--d[j] == 1)    q.push (j);
        }
    }
}

void dfs (int u, int v) {
    fa[u] = v;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (fa[j] == -1)    dfs (j, v);
    }
}

int main () {
    memset (h, -1, sizeof h);
    cin >> n;

    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        add (a, b), add (b, a);
        d[a] ++, d[b] ++;
    }

    //topsort找环
    topsort ();
    for (int i = 1; i <= n; i++) {
        if (fa[i] == 0) dfs (i, i);
    }

    cin >> q;
    while (q --) {
        int u, v;
        cin >> u >> v;
        if (fa[u] == fa[v])     cout << "Yes\n";
        else    cout << "No\n";
    }
}


//dfs合并到环上

G - Yet Another RGB Sequence

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const int P = 998244353, N = 3e6 + 5;
int R, G, B, K;

using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(i64 x) : x(norm(x % P)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

Z fac[N], inv[N];
 
Z C(int x,int y){
	return fac[x] * inv[y] * inv[x-y];
}

signed main () {
    cin >> R >> G >> B >> K;
    int N = R + G + B;

    fac[0] = 1;
    for (int i = 1; i <= N; i++)    fac[i] = fac[i-1] * i;
    inv[N] = fac[N].inv();
    for (int i = N; i; i--)     inv[i-1] = inv[i] * i; 

    Z ans = C(G+B, G) * C(G, K) * C(B+R, R-K);
    cout << ans;
}

Ex - Snuke Panic (2D)

题意