题意 给一个\(n\times n\)的矩阵，找一个最大的子矩阵使其中最大值与最小值的差小于等于\(m\)。 分析 枚举子矩阵的上下边界，同时记录每一列的最大值和最小值。 然后枚举右边界，同时用两个单调队列分别维护最大值和最小值，考虑当右边界往右移动时，可行的最远的左边界一定是单调不减的，当枚举到第\(i\)列时且当前左边界为\(dl\)时，两个单调队列维护的分别是区间\([dl,i]\)的最大值和最小值，最大值-最小值>m时把左边界往右移，同时将单调队列中下标小于\(dl\)的值出队，直到得到可行的最远左边界，更新答案，复杂度为\(O(n^3)\)。 Code #inclu...

题意 给出n个点，每个点有a，b两个属性，让你从左下角到右上角划一条线，线的左边每个点的贡献是\(a_i\)，线的右边每个点的贡献是\(b_i\)，使得两部分的总和最大。 分析 找一条折线将点分割开，使总和最大。 把y离散化，然后点按x排序，设\(dp[i]\)为经过第\(i\)个点(该点当作B集合中的点)的折线的权值，之前的点中在这个点上面的点dp值要加上\(b[i]\)，之前的点中在这个点下面的点的dp值要加上\(a[i]\) \(dp[i]=max(dp[i],dp[k]+b[i]),y[k]<=y[i]\) \(dp[k]=dp[k]+b[i],y[k]&...

题意 给n个整数，求满足子集异或和为0的子集大小之和。 分析 将问题转化为求每个元素的贡献次数之和。 先对n个数求线性基，设线性基大小为r，即插入线性基的数字个数为r，可以分别计算线性基内数的贡献和线性基外的数的贡献 线性基外：共n-r个数，枚举每个数x，它可以和将线性基外剩余的n-r-1个数同时存在一个集合内，显然共有\(2^{n-r-1}\)个集合，所以x的贡献为\(2^{n-r-1}\)。 线性基内：枚举每个数x，将剩余的n-1个数再求一次线性基，设为B，分两种情况： x不能被B异或出。那么显然x不能在任意一个集合中出现，x的贡献为0。 x可以...

题意 给一个\(n\times m\)的01矩阵，1代表有墙，否则没有，每一步可以从\(b[i][j]\)走到\(b[i+1][j]\),\(b[i][j-1]\),\(b[i][j+1]\)，有两种询问： \(q=1\),将\(b[x][y]\)的状态反转 \(q=2\),计算从\(b[1][x]\)走到\(b[n][y]\)的方案数 分析 先不考虑状态反转的情况，设\(dp[i][j]\)为从第\(i-1\)层经过\(b[i-1][j]\)到达\(b[i][j]\)的方案数 \[dp[i][j]=sum(dp[i-1][k]~for~(k<j~and~b...

题意 给一个n个结点的带点权的图，找到第k小的团的权值 分析 用bitset表示团的状态，一个结点必须和团里的每个结点都连边才能加进去，所以可以直接用\(\&\)运算来判断一个结点是否能加进去后还形成团，用优先队列来维护前k小的团的权值。 Code #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define ll long long using namespace std; const int inf=1e9; const int mod=1e9+7...

题意 给一个长度为1e9的只包含1和-1的数列，1的个数不超过1e7,计算有多少对\((l,r)\)满足\(\sum_{i=l}^r a[i]>0\) 分析 dp求出每段连续的1最右端为右端点的最大子段和和最左端为左端点的最大子段和，可以得出这段1往左或右最远能扩到哪里，将相接的连续1段合并，合并后的每段区间和差值不会超过1e7,每段分别用桶来计数，细节很多要仔细想想.. Code #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define ll lo...

题意 eddy走一个长度为\(n\)的环，每次能往前或往后走一步，问走到\(m\)点恰好走完所有点至少一次的概率，前\(i\)个询问的答案要乘起来 分析 \(n=1,m=0\),答案为\(1\) \(n>1,m=0\),答案为\(0\) \(n>1,m \ne 0\),答案为\(1/(n-1)\) Code #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define ll long long using namespace st...

题意 给一个\(n*m\)的01矩阵，找有多少个全1子矩阵不被其他全1子矩阵包括。 分析 用单调栈找到的全1子矩阵是不能向上扩展和向右扩展的，只需判断该子矩阵能否向左和向下扩展，若四个方向都不能扩展，则该矩阵合法。是否能向左扩展可用预处理出的左边一列的高度是否大于等于该子矩阵的高度判断，是否能向下扩展可用前缀和判断下面一段是否全1。 Code #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define ll long long using namespace...

题意 给一个的01矩阵，找有多少个全1子矩阵不被其他全1子矩阵包括。 分析 用单调栈找到的全1子矩阵是不能向上扩展和向右扩展的，只需判断该子矩阵能否向左和向下扩展，若四个方向都不能扩展，则该矩阵合法。是否能向左扩展可用预处理出的左边一列的高度是否大于等于该子矩阵的高度判断，是否能向下扩展可用前缀和判断下面一段是否全1。 Code #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define ll long long using namespace std; const ...

题意 bzoj好像把这题删了，在洛谷里找的 毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。 爬啊爬爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~ “毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数： Change k w：将第k条树枝上毛毛果的个数改变为w个。 Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。 ...

题意 S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。 为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。 在S国的历史上常会发生以下几种事件： “CC x c“：城市x的居民全体改信了c教； “CW x w“：城市x的评级调整为w; “...

题意 给一颗带点权的树，三种操作 修改从1到s的路径上的所有点， 修改从1到s的路径上的所有点， 询问将1到s的路径上的所有点作为石头堆，再加上一个个数为的石头堆，进行一次尼姆博弈，先手胜利输出YES，否则输出NO 分析 尼姆博弈先手必胜条件为所有石头堆异或和为0，将询问转化为求1到s的路径上的所有点的异或和， 先树链剖分一下给每个点重新编号，然后线段树维护区间异或和 怎么维护区间异或和？对二进制的每一位建一颗线段树维护区间和(当前二进制位为1的数量)，若区间和为奇数说明这一位的区间异或结果为1，否则为0 怎么修...

题意 给一颗带点权的树，三种操作 \(1~s~t\) 修改从1到s的路径上的所有点，\(a[i]=a[i]|t\) \(2~s~t\) 修改从1到s的路径上的所有点，\(a[i]=a[i]\&t\) \(3~s~t\) 询问将1到s的路径上的所有点作为石头堆，再加上一个个数为\(t\)的石头堆，进行一次尼姆博弈，先手胜利输出YES，否则输出NO 分析 尼姆博弈先手必胜条件为所有石头堆异或和为0，将询问转化为求1到s的路径上的所有点的异或和， 先树链剖分一下给每个点重新编号，然后线段树维护区间异或和 怎么维护区间异或和？对二进制的每一位建一颗线段树维护区间和...

题意 给一颗带点权的树，三种操作 \(1~s~t\) 修改从1到s的路径上的所有点，\(a[i]=a[i]|t\) \(2~s~t\) 修改从1到s的路径上的所有点，\(a[i]=a[i]\&t\) \(3~s~t\) 询问将1到s的路径上的所有点作为石头堆，再加上一个个数为\(t\)的石头堆，进行一次尼姆博弈，先手胜利输出YES，否则输出NO 分析 尼姆博弈先手必胜条件为所有石头堆异或和为0，将询问转化为求1到s的路径上的所有点的异或和， 先树链剖分一下给每个点重新编号，然后线段树维护区间异或和 怎么维护区间异或和？对二进制的每一位建一颗线段树维护区间和...