Contest Info

practice link

Solutions

A. Connect Three

签到题。

B. Minimum Diameter Tree

题目大意：给你一棵树，但是每条边的边权未定。现在要求你给这棵树赋非负的边权（可以是任意实数），使得所有边权的和为 \(s\)，且树的直径最小。

题解：将 \(s\) 平分给每个叶子所连的边。时间复杂度 \(\mathcal{O}(n)\)。

C. Vasya and Templates

签到题。

D. Rock-Paper-Scissors Champion

题目大意：有 \(n\) 个人玩石头剪刀布，每个人会固定出一种。现在每一轮任选两个相邻的人，输的淘汰，如果平局任选一人淘汰。问有多少人有最终胜出的可能。另外有 \(q\) 个询问，每次询问会改变一个人出的拳。

题解：一个人能获胜的条件显然是：他左边要么没有人能赢他，要么至少有一个人能被他赢；右边同理。用 set 和线段树维护即可。

E. Beautiful Matrix

题目大意：定义一个 \(n\times n\) 的矩阵是好的，当且仅当它的每一行都是 \(1\sim n\) 的一个排列，且任意纵向相邻的两个数都不相等。给出一个好的矩阵，问它按字典序是第几个。

题解：数位 \(dp\) 套错排。

F. Forest Fires

简单扫描线。