B - Christmas Trees
在x轴上种树，种树的坐标为 A + k M A+kM A+kM
求 L , R L,R L,R之间（闭区间）有几棵树
首先将 L R LR LR平移A，这样种树坐标为 k M kM kM
然后求 L L L能包含的 k k k和 R R R能包含的 k k k
最后求出区间树的数量，注意两边都是闭区间。C++64位会越界，用python写就好了。
C - Socks 2
有 N N N对袜子，每种袜子都是一种颜色 C i = i C_i=i Ci=i
现在有一些颜色 A 1 , A 2 , . . . A k A_1,A_2,...A_k A1,A2,...Ak少了一只，需要将其重新配对，若只剩奇数只袜子则扔掉一只。
配对后每对袜子的分数是 ∣ C i − C j ∣ |C_i-C_j| ∣Ci−Cj∣
最小化总分之和。
首先是贪心配对，如单独的袜子是偶数，那么按小到大两两组合。
如例子 [ 1 , 3 ] [1,3] [1,3]中
如果是 [ 1 , 2 ] , [ 2 , 3 ] [1,2],[2,3] [1,2],[2,3]，答案总分和 [ 1 , 3 ] , [ 2 , 2 ] [1,3],[2,2] [1,3],[2,2]是一样的。
我们在单独的袜子中观察，因为相邻的两项如果中间有成对袜子
记 a i < b < a j a_i<b<a_j ai<b<aj，其中 a i , a j a_i,a_j ai,aj是单独袜子，而 b b b是成对袜子
那么 ( b − a i ) + ( a j − b ) = ( a j − a i ) + ( b − b ) (b-a_i)+(a_j-b)=(a_j-a_i)+(b-b) (b−ai)+(aj−b)=(aj−ai)+(b−b)
也就是分数和成对袜子无关，只需要将单独袜子排序。当单独袜子是偶数时，直接两两组合。
如单独的袜子是奇数，那么需要遍历每一只可能丢弃的袜子
[ 1 , 3 , 5 , 6 , 7 ] [1,3,5,6,7] [1,3,5,6,7]
首先 3 − 1 + 6 − 5 3-1+6-5 3−1+6−5
然后 3 − 1 + 7 − 5 = ( 3 − 1 + 6 − 5 ) − 6 + 7 3-1+7-5=(3-1+6-5)-6+7 3−1+7−5=(3−1+6−5)−6+7
然后 3 − 1 + 7 − 6 = ( 3 − 1 + 7 − 5 ) + 6 − 5 3-1+7-6=(3-1+7-5)+6-5 3−1+7−6=(3−1+7−5)+6−5
然后 5 − 1 + 7 − 6 = ( 3 − 1 + 7 − 6 ) − 3 + 5 5-1+7-6=(3-1+7-6)-3+5 5−1+7−6=(3−1+7−6)−3+5
…交错进行更新。
D - Reindeer and Sleigh
有 N N N只雪橇，每只雪橇都是由 A i A_i Ai只驯鹿拉动。
现在给出 X X X只鹿，问最多能拉几只雪橇。
裸考lower_bound的使用方法。
E - Christmas Color Grid 1
N ∗ N N*N N∗N的方格里面，每个格子为红或者绿。
随机抽一个红色的格子将其转换为绿格子，问转换后绿色的连通格个数的期望值。
首先dfs一遍绿色的连通格子数原来有几个 c n t cnt cnt，并对不同连通块标上号。
然后对于每个红格子，求其周围有几个不同的连通块 s z sz sz，答案就是 c n t − ( s z − 1 ) cnt-(sz-1) cnt−(sz−1)
F - Christmas Present 2
圣诞老人要给平面坐标上的 N N N个小朋友发礼物
他从 S x , S y Sx,Sy Sx,Sy点的家里出发，依次访问 1.... n 1....n 1....n号小朋友，最后需要回到家。
但是他一次只能携带 K K K件礼物，因此送完 K K K件礼物后需要回到家。
问圣诞老人最少的行程距离。
dp滑动窗口最值。
很明显的有 1... n 1...n 1...n的状态划分，不要想去上一步维护礼物的数量，而是干脆用回到家作为一个状态结束的标志，然后维护 k k k步。
设 f ( i ) f(i) f(i)为访问完 i i i个小朋友后回到家的最短距离。从 i − k i-k i−k切分状态。
f ( i ) = min { f ( i − k ) + d i + d i − k + 1 + p a t h ( i − k + 1 , i ) } f(i)=\min \bigg \{ f(i-k)+d_i+d_{i-k+1} + path(i-k+1,i) \bigg \} f(i)=min{f(i−k)+di+di−k+1+path(i−k+1,i)}
其中 p a t h ( i − k + 1 , i ) path(i-k+1,i) path(i−k+1,i)代表从 i − k + 1 i-k+1 i−k+1点到 i i i点的路径距离，这个距离可以用前缀和求出来：
s [ i ] − s [ i − k + 1 ] s[i]-s[i-k+1] s[i]−s[i−k+1]
整理可得：
f ( i ) = min { f ( i − k ) + d i + d i − k + 1 + s i − s i − k + 1 } k < = K f(i)=\min \bigg \{ f(i-k)+d_i+d_{i-k+1}+s_i-s_{i-k+1} \bigg \} \quad k<= K f(i)=min{f(i−k)+di+di−k+1+si−si−k+1}k<=K
这里把 i i i相关的提出来，剩下的部分为：
f ( i ) = min { f ( i − k ) + d i − k + 1 − s i − k + 1 } + s i + d i k < = K f(i)=\min \bigg \{ f(i-k)+d_{i-k+1}-s_{i-k+1} \bigg \} + s_i+d_i \quad k<= K f(i)=min{f(i−k)+di−k+1−si−k+1}+si+dik<=K
剩下的那部分就交由最小堆来解决。
G - Christmas Color Grid 2
N ∗ N N*N N∗N的方格里面，每个格子为红或者绿。
随机抽一绿色的格子将其转换为红格子，问转换后绿色的联通格个数的期望值。
前面和E题类似。求连通图的个数。
然后建图。tarjan求对每个节点割完后的连通子图个数。
