CF1677
luanXiPing_AKed_IOI
·
·
个人记录
CF1677
CF1677C Tokitsukaze and Two Colorful Tapes
考虑将同位两种颜色连边，会形成若干个环。
对于一个有 k 个点的环，可以将最大的 \lfloor\frac{k}{2}\rfloor 和最小的 \lfloor\frac{k}{2}\rfloor 个点相邻排列，空余位置（如果有）随便放一个数，这样的贡献是 2\sum_{i=1}^{\lfloor\frac{k}{2}\rfloor}n-2i+1，使用并查集维护连通块大小，对 \sum\lfloor\frac{k}{2}\rfloor 求和后计算即可。
CF1677D Tokitsukaze and Permutations
答案为 0 是好判的。
设原序列 p，对其进行一次冒泡，v_{i}^{\rq}=\max(v_{i+1}-1,0)，因此 p 前 k 项的信息已c丢失，答案要乘以 k!。考虑 v^{\rq} 前 n-k 项的意义，进行分讨：
\begin{cases}
1& v_{i}^{\rq}>0\\
k+1& v_{i}^{\rq}=0\\
i+k& v_{i}^{\rq}=-1\\
\end{cases}
将上述贡献相乘即为答案。