category: Solutions

Description 给定三条线段，判断能否构成 A，即是否满足以下条件： 有两条线段有公共点（下称“第一、二条线段”，另一条线段称“第三条线段”）； 第三条线段的两个端点分别在第一、二条线段上； 第一、二条线段夹角大于 $0$，小于 $\dfrac{\pi}{2}$； 第三条线段分别将第一、二条线段截成两段，较短的线段与较长的线段的长度比不小于 $\dfrac14$。 ...

Description 生日演唱会采用一男一女合唱的形式，每个男生和女生都有一个演唱水平值，两个水平值分别为 $a$ 和 $b$ 的同学演唱将会给大家带来 $a\times b$ 的愉悦度。演唱会开始时，$a$ 名男生和 $b$​ 名女生各排成一列。 我将会从两列的第一位同学开始，分别挑选一名男生和一名女生。如果觉得某位同学不适合登台，我就会请他回到座位，直到挑选到一位满意的同学为止。若最后有一位男生或女生找不到搭档，我只好请剩下的所有人(包括那名同学)回到座位。如果连续的一些女生或者男生没有登台演唱会损失她(他)们水平值之和的平方的愉悦度。请求出大家能获得最大的愉悦值。（回去了就不能再上来）。 $n\leq 300$ ...

前言 最近字符串模拟赛中遇到了一道诡异的题，std 的方法是启发式合并 Trie 树，但我写了个更简单（？）的 BFS＋Trie树+LCA 做法。 后来得知是 CF 的题，就上来交一波，结果确实 AC 了。 这做法大概是对的，但是似乎有点慢（还难写）… ...