赛纲介绍
本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目名称 题目难度 T1 压缩字符串 入门 T2 汉明距离Ⅰ 入门 T3 拼图 普及- T4 汉明距离 普及/提高- T5 导线 普及/提高- T6 打工 普及+/提高
T1
模拟
题目大意
按照题意模拟，判断两个相邻的字符是否是相同的
题解思路
每次输入一个字符压缩，判断和之前的字符压缩的字符是否是一样的。
复杂度分析
O(n)O(n)O(n)
参考代码
T2
模拟
题目大意
汉明距离代表两个数二进制位的不同的位置的数目。我们需要计算所有的 (x,yx, yx,y),(0≤x<y≤n0 \le x<y\le n0≤x<y≤n), x,yx,yx,y之间汉明距离的和
题解思路
对于每一个 nnn ，直接枚举所有可能的 (x,yx, yx,y),(0≤x<y≤n0 \le x<y\le n0≤x<y≤n)。 对于每一对之间计算他们的汉明距离的和即可。
复杂度分析
O(t×n2logVt\times n^2 \log Vt×n2logV)
参考代码
T3
模拟
题目大意
现在我们有两种矩形，分别为 1×41\times 41×4 与 2×32\times 32×3 的矩形，矩形可以任意选择，问，能否拼成 n×mn \times mn×m 的矩形。
题解思路
生成矩形的面积有什么性质。应该为偶数,接下来我们考虑 n , m 的取值；
我们定义 n≤mn \le mn≤m
* 当 n=1n = 1n=1 时，mmm 应该满足是 444 的倍数。 (情况1)
* 当 n=2n = 2n=2 时 ，我们注意到 m≥6m \ge 6m≥6 时，所有的数都可以转换为 a×4+b×3a \times 4 + b\times 3a×4+b×3。那么我们考虑 m=2,3,4,5m = 2,3,4,5m=2,3,4,5
的情况，其中m=2,m=5m=2,m=5m=2,m=5 两个情况不可以。 (情况2)
* 当 n=3n= 3n=3 时，因为 n×mn \times mn×m 是偶数 ， mmm 是偶数。一定可以。 (情况3)
* 当 nmod 4=0n \mod 4 = 0nmod4=0 时，可以用 1×41\times 41×4 的拼出。 (情况4)
* 当 n≥6且nmod 4=2n \ge 6 且 n \mod 4 =2n≥6且nmod4=2 ，m≥6m \ge 6m≥6 ， n=4×a+2n = 4 \times a + 2n=4×a+2 可以将图变成情况4 和情况 2 的组合， 一定可以。
* 当 n≥5且nmod 2=1n\ge 5 且 n \mod 2 =1n≥5且nmod2=1 ，mmm 是偶数 , m≥6m \ge 6m≥6， n=2×a+3n = 2 \times a +3n=2×a+3 ,可以将图变成情况3 和情况 2 的组合， 一定可以。
复杂度分析
O(t)O(t)O(t)
参考代码
T4
组合数,dp
题目大意
题解思路
我们定义 f[i][j]f[i][j]f[i][j] 为小于等于 iii 的数中，与 iii 相差位数为 jjj 的情况数。我们设 iii 二进制位数为 ttt 位 ，我们可以将小于 iii 的数看做是两类，
* 第 ttt 位不为 111 ,那么前 t−1t-1t−1 位如何选择这个数都比 iii 小，那么就可以在 （ t−1t- 1t−1 ） 位中选择 k−1k-1k−1 位作为不同的位置。
* 第 ttt 位为 111 , 那么第 ttt 位相同，需要在前 t−1t -1t−1 位找到 kkk 位不同，且小于 iii 的数，起值等于 f[i - (1 << t)][j]
之后进行前缀和操作统计相应的答案。
复杂度分析
O(nlogn)O(n \log n )O(nlogn)
参考代码
T5
题目大意
有 nnn 个水平线段和 mmm 个垂直线段，每个线都有一个颜色，开始横竖导线之间是绝缘的，你可以执行如下的操作，让一次横着的导线和竖着的导线之间导电，问最少经过多少次操作，相同颜色的线缆之间会导电。问最少经过多少次操作，会让所有的的颜色想相同的导线之间导电，在最少的操作次数下，有多少种可能的操作方法。
题解思路
问题一：单色焊接
问题描述：
有 nnn 个水平线段和 mmm 个垂直线段，所有线段颜色相同。需要多少次焊接才能将所有线段连接成一个整体？有多少种不同的焊接方案？
分析：
1. 焊接次数：
* 每次焊接可以连接一个水平线段和一个垂直线段。初始时有 nnn 个水平线段和 mmm 个垂直线段，最终需要连接成一个整体（即 1 个连通块）。
* 每次焊接减少 1 个独立线段（因为焊接是将两个线段连接，相当于减少 1 个独立单位）。
* 初始独立线段数为 n+mn + mn+m，最终为 1，因此需要 (n+m)−1=n+m−1(n + m) - 1 = n + m - 1(n+m)−1=n+m−1 次焊接。
2. 焊接方案数：
* 焊接顺序可以建模为一个路径问题：从 (0,0)(0, 0)(0,0) 到 (n,m)(n, m)(n,m)，每次选择焊接一个水平线段（向右走）或一个垂直线段（向上走）。
* 总步数为 n+mn + mn+m，其中 nnn 步向右，mmm 步向上。
* 因此方案数为组合数 (n+mn)\binom{n + m}{n}(nn+m )。
* 但焊接是从第一个焊接开始的，所以实际路径是从 (1,1)(1, 1)(1,1) 到 (n,m)(n, m)(n,m)，步数为 (n−1)+(m−1)=n+m−2(n - 1) + (m - 1) = n + m - 2(n−1)+(m−1)=n+m−2，方向为 n−1n - 1n−1 右和 m−1m - 1m−1 上。
* 因此方案数为 (n+m−2n−1)\binom{n + m - 2}{n - 1}(n−1n+m−2 )。
结论：
* 焊接次数：n+m−1n + m - 1n+m−1 次。
* 方案数：(n+m−2n−1)\binom{n + m - 2}{n - 1}(n−1n+m−2 )。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
问题二：双色焊接
问题描述：
现在有两种颜色的线段（颜色 aaa 和 bbb）：
* 颜色 aaa 的覆盖范围为左上角 (x1,y1)(x_1, y_1)(x1 ,y1 ) 到右下角 (x2,y2)(x_2, y_2)(x2 ,y2 )。
* 颜色 bbb 的覆盖范围为左上角 (x3,y3)(x_3, y_3)(x3 ,y3 ) 到右下角 (x4,y4)(x_4, y_4)(x4 ,y4 )。
需要将两种颜色的线段分别连通。问如何焊接？如果两种颜色的范围有重叠，如何处理？
分析：
1. 无重叠情况：
* 如果颜色 aaa 和 bbb 的矩形区域不重叠（即 x2<x3x_2 < x_3x2 <x3 或 x4<x1x_4 < x_1x4 <x1 或 y2<y3y_2 < y_3y2 <y3 或 y4<y1y_4 < y_1y4 <y1 ），则可以完全独立处理。
* 分别对颜色 aaa 和 bbb 使用问题一的思路。
2. 有重叠情况：
* 如果颜色 aaa 和 bbb 的矩形区域重叠，那么他们的焊接路径一定会有冲突。那么我们可以将两个颜色当成一个颜色，这样就可以多通过一次操作避免冲突。
因此本题就是看不同颜色的区间范围是否存在冲突，存在冲突的点则当成一个颜色来连接。
复杂度分析
O（max(n,m)\max(n,m)max(n,m)）
参考代码
T6
虚树
题目大意
现在有一颗树，树上有一些节点，我们可以待在某个节点一段时间tit_iti ，最终赚得一定的钱数pip_ipi ，同时在一条边上移动会花费1个单位时间，求在一个定时间 wiw_iwi 最多会赚多少钱。
题解思路
问题一
当树的节点比较小的时候，我们可以通过什么方法来解决这个问题。
很明显我们可以通过一个背包来解决这个问题。
在树上我们根据花费多少模拟背包操作，之后将背包中的信息整合，对父节点进行背包操作。
但是节点数似乎很多，直接背包容易tle，
优化
现在树上一共有 nnn 个点,在这 nnn 个节点上进行背包 dpdpdp ,维护会发生超时，那么我们可以怎么做呢？首先，我们发现可以赚钱的节点很少 mmm，我们沿着这些节点往上走，我们发现，最多会有 mmm 次相遇，也就意味着，不同的背包最多合并 mmm 次。那么我们是否只要在这些需要合并的点上进行记录就可以了？
我们叫这些合并的点叫做虚点。
这些虚点我们可以通过 lcalcalca 求得。
关于求 lcalcalca 可以实现树剖或者倍增预处理并实现，之后在新树上进行dp
复杂度分析
O(n+mlogn+m×W2n + m\log n + m\times W^2n+mlogn+m×W2)
参考代码
> 本题可以在分组背包中进行一定的剪枝通过，如过深的节点忽略，将原理数组背包转换为离散化背包，可以大量优化计算的过程，
