2020-2021:teams:farmer_john:jjleo:2020北交校赛
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:jjleo:2020北交校赛 [2020/06/05 22:51] jjleo [C] |
2020-2021:teams:farmer_john:jjleo:2020北交校赛 [2020/06/25 23:05] (当前版本) jjleo ↷ 页面2020-2021:teams:farmer_john:2020北交校赛被移动至2020-2021:teams:farmer_john:jjleo:2020北交校赛 |
||
|---|---|---|---|
| 行 22: | 行 22: | ||
| p \times f_{i-1,j}, &j>0 \\ | p \times f_{i-1,j}, &j>0 \\ | ||
| \end{cases} | \end{cases} | ||
| - | $$相当于，每次$i$增加$1$，第一项变为所有值的和的$1-p$倍，除了第一项的变为前面一项的$p$倍，这样我们利用一个双端队列就可以$O(n)$解决了。 | + | $$相当于，每次$i$增加$1$，第一项变为所有值的和的$1-p$倍，第二项到最后一项变为前面一项的$p$倍，这样我们利用一个双端队列就可以$O(n)$解决了。最后答案为$1-\sum_{x=0}^{k-1}{f_{n,x}}$。 |
| + | |||
| + | =====E===== | ||
| + | * 题意:设$f(i)$是距离$\sqrt{i}$最近的整数，求$\prod_{i=1}^{n}{f(i)} \mod 10^9+7$。$(n \le 10^9)$ | ||
| + | |||
| + | * 题解:可以发现会有连续多个数的$f(i)$都是一个值，因此我们枚举$1.5,2.5,3.5...$，将其平方后向下取整，就可以确定每个整数对应的连续区间，直接快速幂即可。 | ||
| + | |||
| + | =====G===== | ||
| + | * 题意:语文题，状压dp。 | ||
| + | |||
| + | * 题解:摸了。 | ||
| + | |||
| + | =====I===== | ||
| + | * 题意:矩阵从左上角走到右下角，只能往右和往下走，每个格子有个权值，总权值为路径上所有权值的$AND$值，求最大值。 | ||
| + | |||
| + | * 题解:按位贪心，每次限制某一位必须为$1$，如果存在方案，那么将所有不可走的点全部删除，将对应的次幂加入答案并继续下一位即可；如果不存在方案则直接下一位即可。 | ||
| + | |||
| + | =====K===== | ||
| + | * 题意:$n$张地图，每张地图有两种比赛模式，第一种胜率是$p_i$，第二种胜率是$1-q_i$，如果第$i-1$场你赢了，那么第$i$场按照第一种比赛模式进行，否则按照第二种比赛模式进行。每次比赛会选择一个区间按顺序进行比赛，且区间的左端点也就是第一场比赛按照第一种比赛模式进行。$m$次询问某个区间你的胜场期望。$(n, m \le 100\,000)$ | ||
| + | |||
| + | * 题解:线段树维护每个区间的$8$个值，分别为，__区间内第一场比赛__按照**第一种/第二种**比赛模式且__区间内最后一场比赛__**获胜/失败**的**胜场期望**和**概率**，分别记为$f_{0/1,0/1},g_{0/1,0/1}$，合并的代码如下。<code cpp>inline void up(int x){ | ||
| + | for(register int i = 0;i <= 1;i++){ | ||
| + | for(register int j = 0;j <= 1;j++){ | ||
| + | t[x].f[i][j] = (1ll * t[ls(x)].g[i][0] * t[rs(x)].g[0][j] % p * (t[ls(x)].f[i][0] + t[rs(x)].f[0][j]) % p + 1ll * t[ls(x)].g[i][1] * t[rs(x)].g[1][j] % p * (t[ls(x)].f[i][1] + t[rs(x)].f[1][j]) % p) % p; | ||
| + | t[x].g[i][j] = (1ll * t[ls(x)].g[i][0] * t[rs(x)].g[0][j] % p + 1ll * t[ls(x)].g[i][1] * t[rs(x)].g[1][j] % p) % p; | ||
| + | t[x].f[i][j] = 1ll * t[x].f[i][j] * fpow(t[x].g[i][j], p - 2) % p; | ||
| + | } | ||
| + | } | ||
| + | }</code>特别需要注意，$f_{i,j}$代表的期望是在不考虑是否满足开头结尾对应的比赛是$i,j$状态下的期望，而我们在合并的过程中第一个式子是在上述条件下的期望，因此我们需要再除以这个概率才能得到正确的期望。<del>这里卡了一万年，我太菜了。</del> | ||
2020-2021/teams/farmer_john/jjleo/2020北交校赛.1591368660.txt.gz · 最后更改: 2020/06/05 22:51 由 jjleo
