by ftiasch

总结

  • 失误太多,尤其是读题不仔细(C、H),忽略了关键条件。。
  • A写崩了。。
  • 要锻炼快速切水题的能力

A(W)

求矩阵N次方,N很大,要找循环节

B

推公式
我们考虑所有球都取光的情况,因为是等概率的,所以假设取完后还可以再取。
若a赢,则最后两个球不为a,若最后一个为b,概率为$\frac{b}{a+b+c}$
若去掉所有b,则最后一个为c的概率为$\frac{c}{a+c}$,反之同理
因此a胜的概率为 $\frac{b}{a+b+c}\frac{c}{a+c} + \frac{c}{a+b+c}\frac{b}{a+b}$
b胜,c胜同理

C

看似求哈密顿道路,实际上因为边总是从编号小的到大,所以路径就是1->2-> ... ->n

D(GW)

总是优先减mod 3不为0的数,用优先队列模拟即可

G(G)

把公式展开,维护一个部分和就行了

H

因为$\sum a_i < 1e6$,因此最多只有大概1000种数,然后直接暴力就行了。。。

J(G)

贪心,因为可以视为消掉了n-1条边,所以我们每次选边两端较小的那个