A and B
sbt,不讲。
C
垃圾计算几何,问是不是一个凸包,搞份板子交就可以了。
D
简单 dp,令 \(f(i,j)\) 表示第 \(i\) 个时间在第 \(j\) 个位置的最大价值,从上一个时间转移,可以向左,向右或者不动,即:
\[f(i,j)=\max(f(i-1,j-1),f(i-1,j),f(i-1,j+1))+s(i,j) \]\(s(i,j)\) 就是读入,注意其中有一些限制。
Code
E
期望 dp,\(f_i\) 表示第 \(i\) 轮的期望,可以枚举这一次掷到的值,如果小于上一次的期望,那就不如不掷,否则就掷。
for(int i=1;i<=n;i++)
{
for(int j=1;j<=6;j++)
{
if(j>f[i-1])f[i]+=j;
else f[i]+=f[i-1];
}
f[i]/=6;
}
F
给你一棵基环树,多次询问两点之间是否有唯一路径。
先找到这个环,对于环上的每一点,都有一棵对应的子树,对其分别染色,如果颜色不同,则必定有两条路径。