CCPC-wannafly winter camp Day1总结
Rhodoks
·
·
个人记录
队伍编号71：家在虾蟆陵下住
队员编号227
A:贪心
按区间中点(l+r)/2排序即是最优排列，本题卡O(n^2logn)所以有必要预处理区间长度的逆元。
B:签到
模拟逆序还原即可。
C:数论
贪心地想，各种颜色的点应当均匀分布，即有n\%k种颜色染(n/k)+1个点，有k-n\%k种颜色染(n/k)个点。
答案为
\sum_{k=l}^{r} n\%k*(n/k+1)*(n-n/k-1)+(k-n\%k)*n/k*(n-(n/k))
即
\sum_{k=l}^{r} (n-\lfloor n/k \rfloor * k)*(\lfloor n/k \rfloor +1)*(n-\lfloor n/k \rfloor -1)
+(k-n+\lfloor n/k \rfloor * k)*\lfloor n/k \rfloor *(n-\lfloor n/k \rfloor )
可整除分块处理，时间复杂度O(T\sqrt{n})。
D:图论+线性代数
基尔霍夫矩阵+高斯消元
一个基尔霍夫矩阵A是形如这样的：
若(u,v) \in E,则A[u][v]=A[v][u]=-1。
该图的最小生成树个数是它的基尔霍夫矩阵去掉任一列一行的行列式。
带权基尔霍夫矩阵：
若$(u,v)$边权为$w$,则$A[u][v]=A[v][u]=-w
该图的所有最小生成树权值积之和是它的基尔霍夫矩阵去掉任一列一行的行列式。
考虑若$(u,v) \in G_1~and~(u,v) \in G_2 $,则令$(u,v)$边权为$x$，否则边权为$1$。
那么设去掉一行一列的基尔霍夫矩阵是$B
|B|=\sum_{i=0}^{n}a_i x^i
那么答案为\sum_{i=0}^{n}a_i \times i，朴素算法为O(n^4)。
即|B(x)|'_{x=1}
而|B(x)|'=|B|B^{-1} \cdot B'
### E:树
考虑每一条路径会对每个点产生贡献，每个点得到的贡献只有在沿着路径移动时会发生变化。贡献本身关于到路径某端点的距离的函数是二次函数，所以沿路径向下移动一条边的贡献差是关于深度的一次函数。
考虑二维差分与前缀和，求出经过每条边的贡献变化量。
以$1$为根的答案可以通过LCA处理出来。
### F:二分
二分答案$Z$，求出$\leq Z$的矩阵元素数，和$K$比较$\text{check}$。
注意矩阵元素有正负零，需要分类讨论，细节很多。
### G:计算几何
### H:数论
### I:数据结构
### J:大模拟题