tag: 图论

参考：出题人 Itst 的题解。 确实是神仙，不好想。 ...

很多分类讨论的题，不对拍很容易被卡正确性。 ...

还可以。 ...

还行吧，但我实在太菜了，水题都不会做 ...

时间比较近的比赛果然难度大一些。。。 ...

因为是久远的比赛，没有什么特别难的题。 没有 DP 好评（） ...

Description 给定一个仅包含 a~h 的字符串。 有一个 $n$​​​​ 个结点的无向图，编号为 $0$​​​​​ 到 $n−1$​​​​​​ 结点 $i$​​​ 与结点 $j$​​ 间有边相连当且仅当 $|i-j|=1$​ 或 $S_i=S_j$。 求这个无向图的直径和有多少对点间的最短距离与直径相同。 $n\leq10^5$ ...

Description 给一个无向图，$n$​​​ 个点 $m$​​ 条边，给定一个 01 序列，如果 $a_i=1$​，要求走到这个点奇数次，否则，要求走到这个点偶数次，请你任选起点，输出满足要求的经过点的序列和序列长度，序列长度不能超过 $4n$。 ...

Description 一个竞赛图的度数集合是由该竞赛图中每个点的出度所构成的集合。 现给定一个 $m$ 个元素的集合，第 $i$ 个元素是 $a_i$。判断其是否是一个竞赛图的度数集合,如果是，找到点数最小的满足条件的竞赛图。 $1\le m\le 31$，$0\le a_i\le 30$，$a_i$ 互不相同。 ...