T1 男女排队

简要题意：

求长度为 \(n\) 的01序列不包含字串101或111的个数。 \((n\leqslant 10^{18})\)

题解：

一开始往容斥的思路去想，但是在推式子的时候发现其实很难容斥掉一个子串里同时有多个101和111子串的方案数。如果我们暴力的将状态转移方程写出来，可以得到和结尾有关的两位数字有关。将四种状态全部推出来之后发现可以使用类似斐波那契数列的矩阵快速幂优化形式。代码

T2 树上最多不相交路径

简要题意：

给定一棵树和 \(m\) 条树上路径求最多在树上选择的路径的条数使得任意两条路径不相交。

题解：

很显然对于两条路径有交点当且仅当其中一条路径的LCA在另一条路径上的时候才会有交点。考虑贪心，将所有路径的LCA的深度进行排序，然后将每个LCA的子树全部标记上（因为相当于这条路径将子树全部砍断）代码

T3 生日

T4 组队比赛

简要题意：

有 \(n\) 个人，每个人玩游戏的区间是 \(\left[l_i,r_i \right)\) ，分成 \(k\) 组使得每组内的时间交至少为1，使得所有组的共同游戏时间最长。

题解：

我们将所有人按左端点排序，我们会发现有一些特别的大区间，这些区间可以完全覆盖其他区间，我们考虑这些区间，如果把它们单独拿出来，它们的贡献为区间长度，如果它们与它所包含的区间组合，不会对它包含区间的结果产生影响，所以我们考虑将这些大区间按区间长度从大到小排序，枚举 \(x\) 个大区间单独作为一组，其他区间组合起来，答案一定在其中。我们先将大区间与其他区间分开来，将大区间求个前缀和备用。考虑小区间 \(dp[i][j]\) 表示 \(i\) 个区间分为 \(j\) 组的最长共同游戏时间。
后面的部分的 \(\max\) 是一段连续的区间，并且与 \(i\) 无关，可以使用单调队列优化。代码