Blog
I use blog to record something.
LCA
求法 1.tarjan 的离线求法，用并查集维护。不多赘述 2.欧拉序： 树的欧拉序是对树进行DFS的一种序列。有两种形式： 1、在每个结点进和出都加进序列。 2、只要到达每一个结点就把他加进序列。 eg： 欧拉序为:1...
封闭集计数
题面 给定一张无向图，请支持以下操作： 插入一条无向边，输出当前有多少个“封闭集” 所谓“封闭集”，指的是一个边的非空子集 S，满足从任意一个点出发，都可以回到这个点（注意每个点可以经过多次，但是每条边需要经过一次。同时，一个孤立点视...
最短路拓展
次短路 就是在维护最短路的时候，顺便维护一下次短路。维护方法如下(spfa) 如果最短路被更新，那么就把次短路更新为之前的最短路 如果当前次短路大于最短路，且最短路没被更新，那么尝试更新 如果最短路没被更新，那么就尝试...
路灯的改建计划
题面 在的CDSS的文翁路上，新建了若干漂亮的路灯，这给同学们晚上的出行带来很大的方便。但是，问题随之出现了。 一天晚上，OI组的FHH 同学正往校门外走，忽然眼前一片漆黑，于是直接把眼镜都摔掉了，再也找不到。后来FHH 同学从学校管...
bzoj1047 HAOI2007理想的正方形
题面 有一个ab的整数组成的矩阵，现请你从中找出一个nn的正方形区域，使得该区域所有数中的最大值和最小值 的差最小。 输入 第一行为3个整数，分别表示a,b,n的值第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每 ...