P9520[JOISC2022]监狱题目描述有一棵\(N\)个节点的树，有\(M\)个囚犯，要从\(S_i\)走到\(T_i\)。每一时刻可以发布一个命令让一名囚犯走到相邻的节点，要求任意时刻囚犯不能走到同一个节点上，求是否可以令每一个囚犯从\(S_i\)走到\(T_i\)。做法解析首先我们可以发现一个

212024.7.141得分题目T1T2T3T4总分得分\(100\)\(10\)\(100\)\(0\)\(210\)排名：rank\(2\)。2题解T1考虑到原先距离\(2\)的现在变为距离\(1\)，那么记原先两点间距离为\(D(i,j)\)，那么答案其实就是：\[\sum_{i=1}^n\sum_{j=i+1}^n\lceil\dfrac{D(i,j

写\(2-SAT\)时刷到的，发现好像一点不会，学习下。1.线段树优化建图当一个点与一段区间连边时，暴力连是\(O(n^2)\)的。因为线段树有一个肥肠优秀的性质，一个区间最多被分为\(O(logn)\)个节点。so，我们可以把区间当成放到线段树上，这样是\(O(nlogn)\)的。具体的，我们建立一个

题目链接：[JOISC2022Day1]监狱本题的思路并不刁钻，但十分考验代码能力，因此本蒟蒻尽量讲的仔细一点，尽量串联起思路与代码中的重点，当然也方便本人加深理解。Analysis:首先对于两个的罪犯，我们思考他们在什么情况下不合法，无非以下几种：两个囚犯路径有重合，且相向而行。两

优化建图发现并没有人写得很详细的样子，那我也摆烂好惹点击查看目录目录前言线段树优化建图单点连区间区间连区间例题解题：倍增优化建图例题解题：前言众所周知，连边的时间复杂度一般是\(O(1)\)，但，当连边的对象是一个连续的树上区间的时候，我们或许有更优的连边方式：优化建图。