2019牛客暑期多校训练营第 6 场

rank solved A B C D E F G H I J
5 Done O O O O O Ø O O Ø O

A

Solved by XLor.

签到。

B

Solved by Henry.

模拟。

C

Solved by XLor.

求每个本质不同回文的子串的本质回文子串个数。

D

Solved by Forsaken.

确定一个答案可行范围,再 $O(n\log n)$ 判断是否可行。

E

Solved by Henry.

点数模 $4$ 为 $1$ 或 $0$。

点分成 $4$ 块,$1$ 和 $2$ 块连完全图,$1$ 和 $2$,$1$ 和 $3$,$2$ 和 $4$ 块间连完全二分图。

剩余的一个点连到 $1$ 和 $2$ 块的所有点。

G

Solved by Henry.

去重后暴力。

H

Solved by Henry.

枚举 $A$ 和 $B$ 的两个点,bfs 处理出最短路。

I

UpSolved by XLor.

建出圆方树,树上直接概率 dp。

环上只需要多考虑从左右两边都不能到达一个点的概率。

J

Solved by Forsaken.

签到。