abcd 都没什么可说的

[ABC266E] Throwing the Die

题面

$1,2,3,4,5,6$ 。你在玩一个游戏，每次丢骰子之后，你可以：

$N$ 次投掷，那么你应当结束游戏。
否则你可以选择重新投，或者结束游戏。

$N$ ，计算如果你希望最后一次投掷时朝上面的期望最大，那么这个期望是多少。

Solution

$dp(i)$ $i$ 次的答案，显然转移：

d p (i) = \sum_{j = 1}^{6} \frac{d p (i - 1)}{6} \times [d p (i - 1) \geq j] + \frac{j}{6} \times [d p (i - 1) < j]

$dp(n)$ 。

Code


xxxxxxxxxx
52
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
ld dp[110];
27

28
int main(){
29
    N = read();
30
    for(int i = 1; i <= N; ++i)
31
        for(int j = 1; j <= 6; ++j)
32
            dp[i] += dp[i - 1] > j ? dp[i - 1] / 6.0 : j / 6.0;
33
    printf("%.8Lf\n", dp[N]);
34
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
35
    return 0;
36
}
37

38
template < typename T >
39
inline T read(void){
40
    T ret(0);
41
    int flag(1);
42
    char c = getchar();
43
    while(c != '-' && !isdigit(c))c = getchar();
44
    if(c == '-')flag = -1, c = getchar();
45
    while(isdigit(c)){
46
        ret *= 10;
47
        ret += int(c - '0');
48
        c = getchar();
49
    }
50
    ret *= flag;
51
    return ret;
52
}

[ABC266F] Well-defined Path Queries on a Namori

题面

$N$ $N$ $Q$ $x_i,y_i$ $x_i$ $y_i$ 个点之间是否有且仅有一条简单路径。

什么是简单路径？

如果路径上的各顶点均不重复，则称这样的路径为简单路径。

Solution

思路比较容易想到。

根据定义显然为基环树，考虑发现若两点在树上路径经过环那么有多条，反之有且仅有一条。

最开始的思路是断环然后树剖加线段树查有没有环上的点，但是想了一下好像不用这么麻烦。

直接对环标记，对环上每个点进行染色并从非环边搜索下去继续染色，这样如果查询两个点颜色不同的需跨环，反之则不用，跑一下即可。

$O(n + m + q)$ 的。

Code


xxxxxxxxxx
88
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
struct Edge{
26
    Edge* nxt;
27
    int to;
28
    bool blocked;
29
    OPNEW;
30
}ed[410000];
31
ROPNEW;
32
Edge* head[210000];
33

34
int N;
35
int deg[210000];
36
bitset < 210000 > inloop;
37
int col[210000], cnt(0);
38
basic_string < int > loop;
39

40
void dfs(int p, int ccol, int fa = 0){
41
    col[p] = ccol;
42
    for(auto i = head[p]; i; i = i->nxt)
43
        if(!i->blocked && SON != fa)dfs(SON, ccol, p);
44
}
45

46
int main(){
47
    inloop.set();
48
    N = read();
49
    for(int i = 1; i <= N; ++i){
50
        int s = read(), t = read();
51
        head[s] = new Edge{head[s], t, false};
52
        head[t] = new Edge{head[t], s, false};
53
        ++deg[s], ++deg[t];
54
    }queue < int > cur;
55
    for(int i = 1; i <= N; ++i)if(deg[i] == 1)cur.push(i), inloop[i] = false;
56
    while(!cur.empty()){
57
        int p = cur.front(); cur.pop();
58
        for(auto i = head[p]; i; i = i->nxt)
59
            if(inloop[SON] && --deg[SON] == 1)
60
                inloop[SON] = false, cur.push(SON);
61
    }
62
    for(int i = 1; i <= N; ++i)if(inloop[i])loop += i;
63
    for(auto p : loop)for(auto i = head[p]; i; i = i->nxt)if(inloop[SON])i->blocked = true;
64
    for(auto p : loop)dfs(p, ++cnt);
65
    int Q = read();
66
    while(Q--){
67
        int s = read(), t = read();
68
        printf("%s\n", !(col[s] ^ col[t]) ? "Yes" : "No");
69
    }
70
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
71
    return 0;
72
}
73

74
template < typename T >
75
inline T read(void){
76
    T ret(0);
77
    int flag(1);
78
    char c = getchar();
79
    while(c != '-' && !isdigit(c))c = getchar();
80
    if(c == '-')flag = -1, c = getchar();
81
    while(isdigit(c)){
82
        ret *= 10;
83
        ret += int(c - '0');
84
        c = getchar();
85
    }
86
    ret *= flag;
87
    return ret;
88
}

[ABC266G] Yet Another RGB Sequence

题面

$998244353$ 取余。

$s$ 具备以下特性：

$s$ 由 r、g、b 构成。
$s$ $R$ r $G$ g $B$ b $k$ 个 rg。

Solution

$R$ $G$ $k$ 个，再考虑。

$g$ $b$ $k$ $rg$ $r$ 插入。两种思路的式子本质相同，最终得到的式子为：

(\binom{G + B}{G}) \times (\binom{G}{k}) \times (\binom{R - k + B + k}{R - k})

$O(n)$ 的。

$k$ $k$ $k + 1$ $k + 1$ $\cdots$ ，发现这玩意就是个二项式，用二项式反演做一下即可，复杂度差不多。

Code


xxxxxxxxxx
67
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (998244353ll)
23

24
template < typename T = int >
25
inline T read(void);
26

27
ll R, G, B, K;
28
ll qpow(ll a, ll b){
29
    ll ret(1), mul(a);
30
    while(b){
31
        if(b & 1)ret = ret * mul % MOD;
32
        b >>= 1;
33
        mul = mul * mul % MOD;
34
    }return ret;
35
}
36
ll GetC(ll n, ll m){
37
    if(m > n)return 0;
38
    ll ret(1);
39
    for(int i = 1; i <= n; ++i)(ret *= i) %= MOD;
40
    ll div(1);
41
    for(int i = 1; i <= m; ++i)(div *= i) %= MOD;
42
    for(int i = 1; i <= n - m; ++i)(div *= i) %= MOD;
43
    return ret * qpow(div, MOD - 2) % MOD;
44
}
45

46
int main(){
47
    R = read(), G = read(), B = read(), K = read();
48
    printf("%lld\n", GetC(G + B, G) * GetC(G, K) % MOD * GetC(R + B, R - K) % MOD);
49
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
50
    return 0;
51
}
52

53
template < typename T >
54
inline T read(void){
55
    T ret(0);
56
    int flag(1);
57
    char c = getchar();
58
    while(c != '-' && !isdigit(c))c = getchar();
59
    if(c == '-')flag = -1, c = getchar();
60
    while(isdigit(c)){
61
        ret *= 10;
62
        ret += int(c - '0');
63
        c = getchar();
64
    }
65
    ret *= flag;
66
    return ret;
67
}

[ABC266Ex] Snuke Panic (2D)

题面

$(0, 0)$ $1$ $n$ $T_i$ $(X_i, Y_i)$ $A_i$ ，你需要最大化收益，输出最大值。

Solution

$dp(i)$ $i$ 条收益的点时的最大收益，转移显然：

d p (i) = max_{j} {d p (j)} + A_{i}

$j$ 需要满足：

t_{j} < t_{i}

y_{j} < y_{i}

| x_{i} - x_{j} | + y_{i} - y_{j} \leq t_{i} - t_{j}

$t_j \lt t_i$ 是无效的限制，对于最后一个因为绝对值的存在可以拆成两个限制，同时关键点在于，若用 CDQ 解决那么我们不能有或起来的条件，故不难发现可以拆成如下两个条件：

x_{i} - x_{j} + y_{i} - y_{j} \leq t_{i} - t_{j}

x_{j} - x_{i} + y_{i} - y_{j} \leq t_{i} - t_{j}

移项一下：

t_{j} - x_{j} - y_{j} \leq t_{i} - x_{i} - y_{i}

t_{j} + x_{j} - y_{j} \leq t_{i} + x_{i} - y_{i}

$y$ $x, y$ 的限制用树套树解决即可，或用 CDQ 亦可。

这里我们考虑使用 BIT套BIT，即二维BIT 解决。

$\max$ $\max$ 。

同时注意需要对其全部离散化。

$dp$ 。

$t_i \lt x_i + y_i$ 的我们应该直接将其丢弃，不能作为转移。

$y$ $y$ $t - x - y$ $t + x - y$ 。

Code


xxxxxxxxxx
95
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define npt nullptr
6
#define SON i->to
7
#define OPNEW void* operator new(size_t)
8
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
9

10
using namespace std;
11

12
mt19937 rnd(random_device{}());
13
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
14
bool rnddd(int x){return rndd(1, 100) <= x;}
15

16
typedef unsigned int uint;
17
typedef unsigned long long unll;
18
typedef long long ll;
19
typedef long double ld;
20

21
template < typename T = int >
22
inline T read(void);
23

24
int N;
25
ll ans(0);
26

27
struct Earn{
28
    ll t;
29
    ll x, y;
30
    ll v;
31
    ll ftmp1, ftmp2;
32
};
33
basic_string < Earn > E;
34
basic_string < ll > data1, data2;
35

36
class BIT_D1{
37
private:
38
    unordered_map < int, ll > tr;
39
public:
40
    int lowbit(int x){return x & -x;}
41
    void Modify(int x, ll v/*ftmp2, dp(j)*/){while(x <= N)tr[x] = max(tr[x], v), x += lowbit(x);}
42
    ll Query(int x){ll ret(0); while(x)ret = max(ret, tr[x]), x-= lowbit(x); return ret;}
43
};
44
class BIT_D2{
45
private:
46
    unordered_map < int, BIT_D1 > tr;
47
public:
48
    int lowbit(int x){return x & -x;}
49
    void Modify(int x1, int x2, ll v/*ftmp1, ftmp2, dp(j)*/){while(x1 <= N)tr[x1].Modify(x2, v), x1 += lowbit(x1);}
50
    ll Query(int x1, int x2){ll ret(0); while(x1)ret = max(ret, tr[x1].Query(x2)), x1 -= lowbit(x1); return ret;}
51
}bit;
52

53
int main(){
54
    // freopen("in.txt", "r", stdin);
55
    // freopen("out.txt", "w", stdout);
56
    N = read();
57
    for(int i = 1; i <= N; ++i){
58
        int t = read(), x = read(), y = read(), v = read();
59
        if(t - x - y < 0)continue;
60
        E += {t, x, y, v, t - x - y, t + x - y};
61
        data1 += t - x - y, data2 += t + x - y;
62
    }
63
    sort(E.begin(), E.end(), [](const Earn &a, const Earn &b)->bool{
64
        if(a.y != b.y)return a.y < b.y;
65
        if(a.ftmp1 != b.ftmp1)return a.ftmp1 < b.ftmp1;
66
        return a.ftmp2 < b.ftmp2;
67
    });
68
    sort(data1.begin(), data1.end()), sort(data2.begin(), data2.end());
69
    for(auto &e : E)
70
        e.ftmp1 = distance(data1.begin(), lower_bound(data1.begin(), data1.end(), e.t - e.x - e.y)) + 1,
71
        e.ftmp2 = distance(data2.begin(), lower_bound(data2.begin(), data2.end(), e.t + e.x - e.y)) + 1;
72
    for(auto e : E){
73
        ll ret = bit.Query(e.ftmp1, e.ftmp2) + e.v;
74
        ans = max(ans, ret);
75
        bit.Modify(e.ftmp1, e.ftmp2, ret);
76
    }printf("%lld\n", ans);
77
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
78
    return 0;
79
}
80

81
template < typename T >
82
inline T read(void){
83
    T ret(0);
84
    int flag(1);
85
    char c = getchar();
86
    while(c != '-' && !isdigit(c))c = getchar();
87
    if(c == '-')flag = -1, c = getchar();
88
    while(isdigit(c)){
89
        ret *= 10;
90
        ret += int(c - '0');
91
        c = getchar();
92
    }
93
    ret *= flag;
94
    return ret;
95
}

UPD

update-2023_01_12 初稿

AtCoder Beginner Contest 266 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

abcd 都没什么可说的

[ABC266E] Throwing the Die

题面

Solution

Code

[ABC266F] Well-defined Path Queries on a Namori

题面

Solution

Code

[ABC266G] Yet Another RGB Sequence

题面

Solution

Code

[ABC266Ex] Snuke Panic (2D)

题面

Solution

Code

UPD