ABC266 做题笔记

· · 算法·理论

C

对于每个点，判断 S_{\triangle ABC}<S_{\triangle ABD}+S_{\triangle ACD}+S_{\triangle BCD} 即可。

D

令 dp_{i,j} 表示时间 i 在 j 的最大答案，答案即为 dp_{10^5+2,2}。

E

显然策略一定是“如果当前的值大于等于 f(n) 就立刻停止”。

枚举 f(n) dp 即可。

F

显然唯一的充要条件是：如果断掉基环树上的环，两个点在同一棵树上。

G

令 g(x)=\dbinom{r+g+b-x}{x}\times\dbinom{r+g+b-2x}{r-x,g-x,b}，f(x) 为 k=x 的答案，则 g(x)=\sum\limits_{i=0}^{+\infty}\dbinom{x+i}{x}f(i+x)。二项式反演即可。