首页 > 其他分享 >AtCoder Beginner Contest 266 题解

AtCoder Beginner Contest 266 题解

时间：2023-02-15 19:14:42浏览次数：68  
标签：AtCoder return int 题解 void ret 266 ll define

AtCoder Beginner Contest 266 Solution

目录

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

abcd 都没什么可说的

[ABC266E] Throwing the Die

题面

你有一个普通均匀的正方体骰子，六个面写有 \(1,2,3,4,5,6\)。你在玩一个游戏，每次丢骰子之后，你可以：

  • 如果这是你的第 \(N\) 次投掷，那么你应当结束游戏。
  • 否则你可以选择重新投，或者结束游戏。

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

Solution

十分显然且简单的 期望DP。令 $ dp(i) $ 表示最多可以丢 $ i $ 次的答案，显然转移：

\[dp(i) = \sum_{j = 1}^6 \dfrac{dp(i - 1)}{6} \times[dp(i - 1) \ge j] + \dfrac{j}{6} \times [dp(i - 1) \lt j] \]

答案即 $ dp(n) $。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

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

using namespace std;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

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

int N;
ld dp[110];

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

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

[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

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

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

using namespace std;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

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

struct Edge{
    Edge* nxt;
    int to;
    bool blocked;
    OPNEW;
}ed[410000];
ROPNEW;
Edge* head[210000];

int N;
int deg[210000];
bitset < 210000 > inloop;
int col[210000], cnt(0);
basic_string < int > loop;

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

int main(){
    inloop.set();
    N = read();
    for(int i = 1; i <= N; ++i){
        int s = read(), t = read();
        head[s] = new Edge{head[s], t, false};
        head[t] = new Edge{head[t], s, false};
        ++deg[s], ++deg[t];
    }queue < int > cur;
    for(int i = 1; i <= N; ++i)if(deg[i] == 1)cur.push(i), inloop[i] = false;
    while(!cur.empty()){
        int p = cur.front(); cur.pop();
        for(auto i = head[p]; i; i = i->nxt)
            if(inloop[SON] && --deg[SON] == 1)
                inloop[SON] = false, cur.push(SON);
    }
    for(int i = 1; i <= N; ++i)if(inloop[i])loop += i;
    for(auto p : loop)for(auto i = head[p]; i; i = i->nxt)if(inloop[SON])i->blocked = true;
    for(auto p : loop)dfs(p, ++cnt);
    int Q = read();
    while(Q--){
        int s = read(), t = read();
        printf("%s\n", !(col[s] ^ col[t]) ? "Yes" : "No");
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

[ABC266G] Yet Another RGB Sequence

题面

求符合要求的字符串个数，对 \(998244353\) 取余。

满足要求的字符串 \(s\) 具备以下特性：

  1. \(s\) 由 r、g、b 构成。

  2. \(s\) 中有 \(R\) 个 r，\(G\) 个 g，\(B\) 个 b，\(k\) 个 rg。

Solution

大概就是我们根据组合意义去考虑，一种思路是先从 $ R $ 和 $ G $ 中各去掉 $ k $ 个，再考虑。

一种思路是考虑先插入 $ g $ 和 $ b $，然后找 $ k $ 个连接成 $ rg $，再将剩余的 $ r $ 插入。两种思路的式子本质相同，最终得到的式子为：

\[{G + B \choose G} \times {G \choose k} \times {R - k + B + k \choose R - k} \]

这东西复杂度显然是 $ O(n) $ 的。

然后还有二项式反演的思路，类似于前者去掉 $ k $ 的做法，然后做一遍多重集排列，再用二项式反演将 $ k $ 加上去掉 $ k + 1 $ 加上 $ k + 1 $ 然后 $ \cdots $，发现这玩意就是个二项式，用二项式反演做一下即可，复杂度差不多。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

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

using namespace std;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define MOD (998244353ll)

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

ll R, G, B, K;
ll qpow(ll a, ll b){
    ll ret(1), mul(a);
    while(b){
        if(b & 1)ret = ret * mul % MOD;
        b >>= 1;
        mul = mul * mul % MOD;
    }return ret;
}
ll GetC(ll n, ll m){
    if(m > n)return 0;
    ll ret(1);
    for(int i = 1; i <= n; ++i)(ret *= i) %= MOD;
    ll div(1);
    for(int i = 1; i <= m; ++i)(div *= i) %= MOD;
    for(int i = 1; i <= n - m; ++i)(div *= i) %= MOD;
    return ret * qpow(div, MOD - 2) % MOD;
}

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

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

[ABC266Ex] Snuke Panic (2D)

题面

二维平面直角坐标系中，你初始位于 $ (0, 0) $，每个时刻可以任意向上，左，右走一步，即步进 $ 1 $ 的距离。存在 $ n $ 条收益，当你在 $ T_i $ 时刻走到坐标 $ (X_i, Y_i) $ 的话就能够获得收益 $ A_i $，你需要最大化收益，输出最大值。

Solution

类比 ABC266D 考虑朴素 DP，显然我们可以认为对于无收益的点是无意义的，所以我们可以采用离散化的思想，令 $ dp(i) $ 表示到 $ i $ 条收益的点时的最大收益，转移显然：

\[dp(i) = \max_j\{dp(j)\} + A_i \]

这里的 $ j $ 需要满足：

\[t_j \lt t_i \]

\[y_j \lt y_i \]

\[\lvert x_i - x_j \rvert + y_i - y_j \le t_i - t_j \]

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

\[x_i - x_j + y_i - y_j \le t_i - t_j \]

\[x_j - x_i + y_i - y_j \le t_i - t_j \]

移项一下：

\[t_j - x_j - y_j \le t_i - x_i - y_i \]

\[t_j + x_j - y_j \le t_i + x_i - y_i \]

于是就变成了经典的三位偏序问题，我们将 $ y $ 排序解决，然后将最后的对于 $ x, y $ 的限制用树套树解决即可，或用 CDQ 亦可。

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

注意虽然 BIT 是不支持区间 $ \max $ 的，但支持前缀 $ \max $。

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

还有一个细节就是在 BIT 里维护的下标是离散化后的值，值则为对应的 $ dp $。

然后还有一个很重要的细节就是对于 $ t_i \lt x_i + y_i $ 的我们应该直接将其丢弃，不能作为转移。

还没完，还有一个细节，就是排序的时候不能只排 $ y $，对于 $ y $ 相同的还需要继续排 $ t - x - y $ 和 $ t + x - y $。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

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

using namespace std;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

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

int N;
ll ans(0);

struct Earn{
    ll t;
    ll x, y;
    ll v;
    ll ftmp1, ftmp2;
};
basic_string < Earn > E;
basic_string < ll > data1, data2;

class BIT_D1{
private:
    unordered_map < int, ll > tr;
public:
    int lowbit(int x){return x & -x;}
    void Modify(int x, ll v/*ftmp2, dp(j)*/){while(x <= N)tr[x] = max(tr[x], v), x += lowbit(x);}
    ll Query(int x){ll ret(0); while(x)ret = max(ret, tr[x]), x-= lowbit(x); return ret;}
};
class BIT_D2{
private:
    unordered_map < int, BIT_D1 > tr;
public:
    int lowbit(int x){return x & -x;}
    void Modify(int x1, int x2, ll v/*ftmp1, ftmp2, dp(j)*/){while(x1 <= N)tr[x1].Modify(x2, v), x1 += lowbit(x1);}
    ll Query(int x1, int x2){ll ret(0); while(x1)ret = max(ret, tr[x1].Query(x2)), x1 -= lowbit(x1); return ret;}
}bit;

int main(){
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    N = read();
    for(int i = 1; i <= N; ++i){
        int t = read(), x = read(), y = read(), v = read();
        if(t - x - y < 0)continue;
        E += {t, x, y, v, t - x - y, t + x - y};
        data1 += t - x - y, data2 += t + x - y;
    }
    sort(E.begin(), E.end(), [](const Earn &a, const Earn &b)->bool{
        if(a.y != b.y)return a.y < b.y;
        if(a.ftmp1 != b.ftmp1)return a.ftmp1 < b.ftmp1;
        return a.ftmp2 < b.ftmp2;
    });
    sort(data1.begin(), data1.end()), sort(data2.begin(), data2.end());
    for(auto &e : E)
        e.ftmp1 = distance(data1.begin(), lower_bound(data1.begin(), data1.end(), e.t - e.x - e.y)) + 1,
        e.ftmp2 = distance(data2.begin(), lower_bound(data2.begin(), data2.end(), e.t + e.x - e.y)) + 1;
    for(auto e : E){
        ll ret = bit.Query(e.ftmp1, e.ftmp2) + e.v;
        ans = max(ans, ret);
        bit.Modify(e.ftmp1, e.ftmp2, ret);
    }printf("%lld\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2023_01_12 初稿

标签：AtCoder,return,int,题解,void,ret,266,ll,define
From： https://www.cnblogs.com/tsawke/p/17124332.html

相关文章

  • [ABC268D] Unique Username 题解
    [ABC268D]UniqueUsernameSolution目录[ABC268D]UniqueUsernameSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面给定$n$各字......
  • LG-P6157 有趣的游戏 题解
    LG-P6157有趣的游戏Solution目录LG-P6157有趣的游戏Solution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面给定$n$个点的树，存在点权......
  • [ABC267D] Index × A(Not Continuous ver.) 题解.
    [ABC267E]ErasingVertices2Solution目录[ABC267E]ErasingVertices2Solution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面给定$n$......
  • [ABC268F] Best Concatenation 题解
    [ABC268F]BestConcatenationSolution目录[ABC268F]BestConcatenationSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面给定$n$......
  • [ABC268D] Unique Username 题解.
    [ABC268E]ChineseRestaurant(Three-StarVersion)Solution目录[ABC268E]ChineseRestaurant(Three-StarVersion)Solution更好的阅读体验戳此进入题面SolutionCode......
  • [ABC268Ex] Taboo 题解
    [ABC268Ex]TabooSolution目录[ABC268Ex]TabooSolution更好的阅读体验戳此进入题面SolutionCode理论复杂度正确但无法通过的代码正解代码UPD更好的阅读体验戳此进入......
  • [ABC268G] Random Student ID 题解
    [ABC268G]RandomStudentIDSolution目录[ABC268G]RandomStudentIDSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面给定$n$......
  • P9063 [yLOI2023] 分解只因数 题解
    P9063[yLOI2023]分解只因数题解题意分解给定的\(n\)的质因数，判断是否全为奇数。思想因为我不是黑子，所以我根本没考虑“只因”的发音对思路的极大提示。当我首次......
  • [ABC262D] I Hate Non-integer Number 题解
    [ABC262D]IHateNon-integerNumberSolution目录[ABC262D]IHateNon-integerNumberSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入......
  • 【题解】[Ynoi2013] 文化课
    题目分析：这个权值一看就可以使用线段树维护啊，因为很明显可以进行高效合并。对于区间合并其实就只是需要判断一下两个区间中间如果是乘号，那么造成的贡献要变成区间两边乘......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99