thyzzs's Blog
题解 T93270 【轰炸城市】 题解 T93270 【轰炸城市】
传送门 30%的题解： 直接每次询问枚举所有点。 60%的题解： 坐标值很小，可以尝试用链表，可以做到$O(n)$的时间复杂度 100%的题解： $map$套$multiset$ $X$坐标开个$mapx$，里面存的是每个$X$坐标的
2019-08-20 Life in OI
题解
题解 T93222 【生成树】 题解 T93222 【生成树】
传送门 30%的题解： 是一棵树，所以只要枚举根，然后计算代价即可 100%的题解： $vals[S]$表示集合$S$的权值和 设计状态$F[S][h]$, 表示现在已经选择了的点的集合是$S$，$h$表示当前深度 枚举S的补集的子集
2019-08-20 Life in OI
题解
题解 T93336 【最短路】 题解 T93336 【最短路】
传送门 30%的做法 floyd预处理出每两点间的最短路,每次询问$O(1)$回答 复杂度$O(n^3+q)$ 另外20%的做法 树的情况 对于$u,v$的最短路，求出他们的LCA为$k$，$ans=d[u]+d[v]-2*d[k
2019-08-20 Life in OI
题解
题解 T93284 【最大公因数】 题解 T93284 【最大公因数】
传送门 30%的做法 暴力枚举删掉哪些数即可，复杂度$O(n \log (\max(a_i)) \times 2^n)$ 另外20%的做法 枚举删掉一些数后的最大公因数$g$，那么不能被$g$整除的数的个数即为要删的数的个数，对结果取$\
2019-08-18 Life in OI
题解
题解 T93283 【集合】 题解 T93283 【集合】
传送门 考虑如何将s中的每种数分到$a$和$b$集中假设一个数$x$有$k$个，可以对$a$和$b$集“好的”数的个数差产生什么影响？$k=1$ 让一个集合“好的”数个数++，另一集合的个数不变 $k=2$ 让两个集合“好的”数个数都++
2019-08-18 Life in OI
题解
4 / 4