AtCoder Beginner Contest 266

ABCD 比较简单就不写了。

E. Throwing the Die

有 \(k\) 次掷骰子的机会，可以任意时刻喊停，得分就是停的时候骰子向上的数字，问最优策略期望得分。

期望要倒着算。设 \(f[x]\) 表示可以掷 \(x\) 次的最优期望得分，首先有 \(f[1] = 3.5\) 。

接下来考虑 \(f[i]\) 已知求 \(f[i + 1]\) ：枚举第 \(i+1\) 次的六种可能情况，如果本次得分比 \(f[i]\) 要大就不会再投了，否则会继续投。

因此方程为 \(f[i + 1] =\frac{1}{6}\sum_{j=1}^6j\times\big[j > f[i]\big]+f[i]\times \big[j \le f[i]\big]\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
int main() {
    int n = rd();
  	double f[101] = {0, 3.5};
    for (int i = 2; i <= n; ++i) {
      	f[i] = 0;
        for (int j = 1; j <= 6; ++j) {
            if (1.0 * j < f[i - 1]) f[i] += f[i - 1] / 6;
            else f[i] += j / 6.0;
        }
    }
    printf("%.10lf\n", f[n]);
    return 0;
}

F. Well-defined Path Queries on a Namori

给一棵无向基环树，\(q\) 次问 \(u_i\) 和 \(v_i\) 之间的简单路径是否唯一。

路径不经过环就唯一，因此拓扑把环找出来删掉，如果两个点在同一棵树内答案就是 Yes 。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll rd() {
    ll x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 200007
#define pb push_back

vector<int> e[N];

bool vis[N];

int deg[N];

queue<int> q;

int col[N], cnt;

void dfs(int u, int c) {
    for (auto v : e[u]) 
        if (!col[v]) {
            col[v] = c; dfs(v, c);
        }
}

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        int u = rd(), v = rd();
        e[u].pb(v); e[v].pb(u);
        ++deg[u]; ++deg[v];
    }
    for (int i = 1; i <= n; ++i) 
        if (deg[i] == 1) {vis[i] = true; q.push(i);}
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto v : e[u])
            if (!vis[v]) {
                --deg[v];
                if (deg[v] == 1) {
                    vis[v] = true;
                    q.push(v);
                }
            }
    }
    for (int i = 1; i <= n; ++i) 
        if (!vis[i]) col[i] = ++cnt;
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) dfs(i, col[i]);
    for (int q = rd(); q; --q) {
        int u = rd(), v = rd();
        puts(col[u] == col[v] ? "Yes" : "No");
    }
    return 0;
}

G. Yet Another RGB Sequence

计数 \(R\) 个 r ，\(G\) 个 g ，\(B\) 个 b 的字符串，且其中rg 子串恰好 \(k\ (k\le \min(R,G))\) 个。

先数出来 \(k\) 个 rg 、\(G-k\) 个 g 、\(B\) 个 b 的字符串个数是 \(\frac{(G+B)!}{k!(G-k)!B!}\) （多重集的排列）

再将剩下的 \(R-k\) 个 r 插进去，因为不能插在 g 前面，所以只能插在 rg 或 b 的前面（及最后）

因此就是 \(B+k\) 个隔板和 \(R-k\) 个球的排列个数问题，方案数为 \({R+B\choose R-k}\) ，两部分乘起来即可。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll rd() {
    ll x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 2000007

#define mod 998244353

int fac[N], ifac[N];

inline int fpow(int x, int t) {
    int res = 1;
    for (; t; t >>= 1, x = 1ll * x * x % mod)
        if (t & 1) res = 1ll * res * x % mod;
    return res;
}
 
inline void init() {
    fac[0] = ifac[0] = 1;
    for (int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[N - 1] = fpow(fac[N - 1], mod - 2);
    for (int i = N - 2; i; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
}
 
inline int C(int n, int m) {
    if (n < m) return 0;
    return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

int main() {
    init();
    int r = rd(), g = rd(), b = rd(), k = rd();
    r -= k; g -= k; 
    int ans = 1ll * fac[g + b + k] * ifac[g] % mod * ifac[b] % mod * ifac[k] % mod;
    b += k;
    printf("%lld\n", 1ll * ans * C(r + b, r) % mod);
    return 0;
}

Ex. Snuke Panic (2D)

二维平面上 \(n\ (n\le 10^5)\) 个点，位于 \((x_i,y_i)\) ，出现时间 \(t_i\) ，价值 \(a_i\) 。

开始你在 \((0,0)\) ，每秒四选一：\(x\) 方向 \(+1/-1/y\) 方向 \(+1/\) 不动。

恰好在 \(t_i\) 时刻到达 \((x_i,y_i)\) ，可以获得 \(a_i\) ，求能得到的最大价值。

直接设 \(f[t][x][y]\) 表示前 \(t\) 秒， \(t\) 时在 \((x,y)\) 能得到的最大价值；设 \(val(t,x,y)\) 表示 \(t\) 时刻 \((x,y)\) 的价值。 \[ f[t][x][y]= \max \{f[t'][x'][y']\ |\ t' \le t, y' \le y, |x-x'|+y-y'\le t - t'\} + val(t,x,y) \] 由后两个限制条件有 \(t-t\ge y - y'\ge 0\) 因此第一个条件可以丢掉，剩下的条件写为： \[ \left\{ \begin{array}{l} y' \le y\\ x - x' + y - y' \le t - t'\\ x'-x + y - y' \le t - t' \end{array} \right. \ \ \Longrightarrow \left\{ \begin{array}{l} y' \le y\\ t' - x' - y' \le t - x - y\\ t' + x' - y' \le t + x - y \end{array} \right. \]

可以发现做个线性变换之后是个三维偏序，令 \(a=t-x-y,b=t+x-y\) ，有： \[ f[a][b][y] = \max\{f[a'][b'][y']\ |\ a'\le a, b'\le b, y'\le y \} + val(a,b,y) \] 三维都从小到大排序后可以去掉一维，剩下两维用二维树状数组维护即可，答案显然只会在 \(val(a,b,y)\) 有值处统计到。

但是即使离散化的二维树状数组也开不下，需要将一维用 unordered_map 代替，时空复杂度均为 \(\mathcal O(n\log^2n)\) 。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll rd() {
    ll x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define pb push_back
#define lowbit(x) ((x) & -(x))
#define all(x) (x).begin(), (x).end()

#define N 100007

struct node {int y, a, b, w;} g[N];

vector<int> A, B;

int X, Y;

unordered_map<int, ll> c[N];

inline ll max(ll a, ll b) {return a > b ? a : b;}

inline void upd(int x, int y, ll w) {
    for (int i = x; i <= X; i += lowbit(i))
        for (int j = y; j <= Y; j += lowbit(j)) c[i][j] = max(c[i][j], w);
}

inline ll qmax(int x, int y) {
    ll res = 0;
    for (int i = x; i; i -= lowbit(i))
        for (int j = y; j; j -= lowbit(j)) res = max(res, c[i][j]);
    return res;
}

int main() {  
    int n = rd(), m = 0;
    for (int i = 1; i <= n; ++i) {
        int t = rd(), x = rd(), y = rd(), w = rd();
        if (t - x - y < 0 || t + x - y < 0) continue;
        g[++m].y = y; g[m].w = w;
        g[m].a = t - x - y; A.pb(g[m].a);
        g[m].b = t + x - y; B.pb(g[m].b);
    }
    n = m;
    auto cmp = [&](node a, node b) {
        if (a.y != b.y) return a.y < b.y;
        if (a.a != b.a) return a.a < b.a;
        return a.b < b.b;
    };
    sort(g + 1, g + 1 + n, cmp);
    sort(all(A)); A.erase(unique(all(A)), A.end()); X = A.size();
    sort(all(B)); B.erase(unique(all(B)), B.end()); Y = B.size();

    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        int a = lower_bound(all(A), g[i].a) - A.begin() + 1;
        int b = lower_bound(all(B), g[i].b) - B.begin() + 1;
        ll nw = qmax(a, b) + g[i].w;
        ans = max(ans, nw); upd(a, b, nw);
    }
    printf("%lld\n", ans);
    return 0;
}