题目大意 给出一个n*n的矩阵,给出m个询问,每个询问形如x,y,z,表示询问以x,y为中心点的z*z子矩阵的最大值MAX和最小值MIN,输出(MIN+MAX)/2。并将x,y修改为(MIN+MAX)/2(向下取整)。 Solution 支持修改一个数,并询问一个区间中的最大、最小值,可以想到用线段 …

题目大意 给定一棵带边权的树,有q次询问,每次给定m个关键点,要求删掉一些边,使得根不与任何关键点连通。 题解 咳咳 只要会虚树,这就是一道裸题。 我这种蒟蒻也只会写裸题了。。。 对每次询问建一遍虚树,然后在虚树上跑DP。 代码 #include <cstdio> #include …

题目大意 给出一幅无向图,每个点上有两种权值A,B。 求一条1到n的路径,使路径上A的最大值+B的最大值最小。 Solution 如果要使一条路径上一种权值的最大值最小,这条路径一定在这种权值的最小生成树上。但A的最小生成树和B的最小生成树不同,所以不能直接求最小生成树。 而如果我们从小到大枚举一种 …

题目大意 不包含4或8,且至少包含3个连续数字的数为合法的手机号码。问l,r区间内合法的手机号码有几个? Solution 这题是很显然的数位DP。当然,如果直接套dp方程可能会显得麻烦,所以还是用记忆化搜索。思路直接描述有点困难,所以直接看代码和注释。 代码 #include<cstdio …

题目大意 给你一些点,每个点有它的点权(各不相同),一些点之间本来就有边。要维护两种操作: B u v,连接u,v两点。 Q u k,询问u所在联通块中第k小的点。 Solution 要合并两个联通块,并询问一个联通块中第k小的点,本来可以用平衡树做。用启发式合并,可以做到两个log。 我们也可以用 …

题目传送门:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1648 将I号点和min(n+1,a[I]+I)连边,这显然是一棵以n+1号点为根的树。于是修改a[I]就相当于修改I的父亲,可以用Link Cut Tree维护 …

题目大意 你要对一些员工进行裁员,裁掉一个员工都可以获得一些收益(可能为负)。员工之间有上下级关系,要裁掉一个员工,必须要裁掉他的所有下属。问获得的最大收益是多少。 Solution 对于这种最大收益的题,我们可以考虑构造最小割模型。假设我们已经裁掉了那些收益为正的人,但不能裁了上司而不裁下属。设置 …

#include <cstdio> int main() { int x, y; scanf("%d%d", &x, &y); printf("%d\n", x + y); return 0; }

这是AKteam发表的第一篇博客 #include<iostream> using namespace std; int main() { cout<<"Hello World"<<endl; return 0; }