CF1929题解

C - Sasha and the Casino

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

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

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

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，只能选择一个子树中的节点，且注意排除空集。

  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}) $
  • $ 若选了u,则v只能是0，即0000.. $
  • $ 若不选u,则至少有一个v要选1，即所有方案数-方案(0000) $
  • 所有总方案数即01的排列组合
• $ dp_{u,2}=dp_{u,2}+ \sum dp_{v,1}+dp_{v,2} $
  • $ 若选u,则加dp_{v,1} $
  • $ 不选u,则加dp_{v,2} $

    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";
    }