SRM579 RockPaperScissors
题意你要和一堆骰子玩剪刀石头布。有 $n$ 个骰子，每个骰子有三种结果：R，S，P。概率分别是 $pR_i,pS_i,pP_i$。每次你会随机选择一个没有用过的骰子，然后你决定好出什么，然后扔这个骰子。如果获胜得 $3$ 分，平局得 $1$ 分，失败得 $0$ 分。你无法分辨出每一次拿出的骰子是什么，但你可以通过每一局的结果来决策之后的操作。求期望最多可以获得多少得分。$1 \leq n \...
题意你要和一堆骰子玩剪刀石头布。有 $n$ 个骰子，每个骰子有三种结果：R，S，P。概率分别是 $pR_i,pS_i,pP_i$。每次你会随机选择一个没有用过的骰子，然后你决定好出什么，然后扔这个骰子。如果获胜得 $3$ 分，平局得 $1$ 分，失败得 $0$ 分。你无法分辨出每一次拿出的骰子是什么，但你可以通过每一局的结果来决策之后的操作。求期望最多可以获得多少得分。$1 \leq n \...
A打表可以发现 $k>1$ 先手必胜，$k=1$ 取决于 $n$ 的奇偶性。具体证明：考虑如果 $n$ 是奇数的话，先手第一步取中间的那一块，序列变成了互相独立的两部分，之后先手只需要在没有被后手操作的块里模拟后手动作即可。如果 $n$ 是偶数的话，$k>1$ 也可以类似的划分成两段长度相等的段。$k=1$ 等价于每次只能取一个，所以 $n$ 是偶数的话后手能赢。#include...
A考虑分步做合成 coal 和合成 craft 。发现我们做 $n$ 次替换后拥有的 stick 数量是 $nx-n+1$，首先要凑出 $k$ 个 coal，然后还要剩下来 $k$ 个 stick 合成，所以我们造 stick 的限制就有 $nx-n+1 \geq ky+k$，这样 $n$ 就是交易 stick 用掉的次数了，再加上 $k$（交易 coal 的次数）B把未被锁定的位置从大到小...
A根据期望的线性性，现在转变成了求每个点有多少概率是被自己覆盖的：显然是要在子树内第一个被选中的，所以答案就是 $\sum_{i=1}^n \frac{1}{sz_i}$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define...