发布时间：2024-02-17

C - Sasha and the Casino

题意：
赔率为k的赌场，保证至多连续输x次。求a元本金能否保证在有限时间内赢得任意金额

思路：
本质上是个博弈问题,赌场可以随意决定输赢

每一次下注都必须将本金全赚回来,否则赌场判赢连续输的次数重置,但是本金减少了,这样的话不能赢任意金额
撑x次后仍然有足够金额则算赢

cpp

void solve(){
    ll k,x,a;
    cin>>k>>x>>a;
    int cnt=0;
    ll A=a;
    k--;
    for(int i=1;i<=x;i++){
        int c=A-a+1;
        int m=(c+k-1)/k;
        a-=m;
        if(a<=0){
            cout<<"NO\n";
            return;
        }
        cnt+=m;
    }
    int c=A-a+1;
    int m=(c+k-1)/k;
    if(a<m){
        cout<<"NO\n";
        return;
    }
    cout<<"YES\n";
}

D - Sasha and a Walk in the City

题意：
有一棵树，求满足以下条件点集的数量：

树上任意一条简单路径至多包含点集中的两个点。

思路：
思考一个点集,所有点(任意两点)汇集到的一个点必定不是该点集
可以分成两个情况：

任意两点之间不存在父子关系；
或存在一个点是其它所有节点的父亲，但不是它们的 LCA（即是它们 LCA 的祖先）。

$dp_u 表示以u为根的子树的方案数(不存在父子关系)$

对于第一种情况,如果选择u,则不能选择子树任意点(即只选u),方案数为1;如果不选,则子树方案独立,任意相乘
对于第二种情况,我们必须选择u，而为了防止成为 LCA，只能选择一个子树中的节点，且注意排除空集。

cpp

void solve(){
    int n;
    cin>>n;
    vector<int> adj[n+1],in(n+1);
    vector<ll> f(n+1);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        in[u]++;
        in[v]++;
    }
    ll ans=0;
    function<void(int,int)> dfs=[&](int u,int fa){
        f[u]=1;
        for(auto v:adj[u]){
            if(v==fa)continue;
            dfs(v,u);
            (f[u]*=f[v])%=mod;
            (ans+=f[v]-1)%=mod;
        }
        (f[u]+=1)%=mod;
    };
    dfs(1,0);
    (ans+=f[1])%=mod;
    cout<<ans<<"\n";
}

另一种解法：

$dp_{i,j} 表示以i出发的任意简单路径,有j个危险路口的方案数$
$dp_{u,0}=1 即为空集$
$dp_{u,1}=\prod(dp_{v,0}+dp_{v,1})$ $d p_{u, 1} = \prod (d p_{v, 0} + d p_{v, 1})$
- $若选了u,则v只能是0，即0000..$
- $若不选u,则至少有一个v要选1，即所有方案数-方案(0000)$
- 所有总方案数即01的排列组合
$dp_{u,2}=dp_{u,2}+ \sum dp_{v,1}+dp_{v,2}$ $d p_{u, 2} = d p_{u, 2} + \sum d p_{v, 1} + d p_{v, 2}$
- $若选u,则加dp_{v,1}$
- $不选u,则加dp_{v,2}$

cpp

vector<int> e[N];
int n, dp[N][3]; 
void dfs(int now, int fa) {
    for(auto it: e[now]) {
        if(it == fa)  continue;
        dfs(it, now);
        dp[now][0] = 1;
        dp[now][1] = (dp[now][1] * (dp[it][0] + dp[it][1])) % MOD;
        dp[now][2] = (dp[now][2] + dp[it][1] + dp[it][2]) % MOD;
    }
}
void solve(){
    cin >> n;
    for(int i = 1; i <= n; i ++) {e[i].clear();  dp[i][0] = dp[i][1] = 1, dp[i][2] = 0;}
    for(int i = 1; i < n; i ++) {
        int u, v;  cin >> u >> v;
        e[u].push_back(v), e[v].push_back(u);
    }
    dfs(1, -1);
    cout << (dp[1][0] + dp[1][1] + dp[1][2]) % MOD << "\n";
}

C - Sasha and the Casino ​

D - Sasha and a Walk in the City ​

C - Sasha and the Casino

D - Sasha and a Walk in the City