xyq0220

未归档

题解(3)

/ 注册

全部文章 / 未归档（共101篇）

洛谷P3193 GT考试 kmp+矩阵优化dp

题意求\(N\)位数字序列（可以有前导0）中不出现某\(M\)位子串的个数，模\(K\)。 \(N<=10^9,M<=20,K<=1000\) 分析设\(dp[i][j]\)表示匹配串下标\(i\)匹配到模式串下标\(j\)时，满足要求的方案数；枚举匹配串的...

kmp 矩阵 DP

2019-09-03

0 476

洛谷p2375 kmp

题意给你一个字符串，让你求一个\(num\)数组，\(num[i]\)为长度为\(i\)的前缀的公共前后缀长度不超过\(\lfloor \frac{i}{2}\rfloor\)的个数，例如"\(aaaaa\)",\(num[1]=0,num[2]=num[3]=1,num...

kmp

2019-09-03

0 370

2019icpc南京网络赛 A 主席树

题意给一个\(n\times n\)的螺旋矩阵，给出其中的\(m\)个点的值分别为各个点上数字的数位之和，给出\(q\)个询问，每次询问从\((x1,y1)\)到\((x2,y2)\)的子矩阵的和。分析用官方题解的方法\(O(1)\)推出点\((x,y)\)上的值，将这\(m\)个点按\...

主席树

2019-09-01

0 336

2019icpc南京网络赛 F 主席树

题意给一个\(n\)的全排列数组\(a\)，求一个递推数组每一项的值：\(ans[i]=ans[j]+1\)，\(j\)为\(a[pos[i]-k]到a[pos[i]+k],(pos[i]为i在数组a中的下标)\)中小于\(i\)的最大的值。分析这题set的做法更优秀，但是想练习一下在主...

主席树

2019-09-01

0 371

2019牛客暑期多校训练营（第三场）F 单调队列

题意给一个\(n\times n\)的矩阵，找一个最大的子矩阵使其中最大值与最小值的差小于等于\(m\)。分析枚举子矩阵的上下边界，同时记录每一列的最大值和最小值。然后枚举右边界，同时用两个单调队列分别维护最大值和最小值，考虑当右边界往右移动时，可行的最远的左边界一定是单调不减的，当...

单调队列

2019-08-22

0 424

2019牛客暑期多校训练营（第一场）I dp+线段树

题意给出n个点，每个点有a，b两个属性，让你从左下角到右上角划一条线，线的左边每个点的贡献是\(a_i\)，线的右边每个点的贡献是\(b_i\)，使得两部分的总和最大。分析找一条折线将点分割开，使总和最大。把y离散化，然后点按x排序，设\(dp[i]\)为经过第\(i\)个点(该...

DP 线段树

2019-08-20

0 404

2019牛客暑期多校训练营（第一场）H 线性基+计算贡献

题意给n个整数，求满足子集异或和为0的子集大小之和。分析将问题转化为求每个元素的贡献次数之和。先对n个数求线性基，设线性基大小为r，即插入线性基的数字个数为r，可以分别计算线性基内数的贡献和线性基外的数的贡献线性基外：共n-r个数，枚举每个数x，它可以和将线性基外剩余的n-...

线性基计算贡献

2019-08-16

0 336

2019牛客暑期多校训练营（第二场）E 线段树维护dp转移矩阵

题意给一个\(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\),计算从\(...

线段树 DP 矩阵

2019-08-16

0 401

2019牛客暑期多校训练营（第二场）D bitset

题意给一个n个结点的带点权的图，找到第k小的团的权值分析用bitset表示团的状态，一个结点必须和团里的每个结点都连边才能加进去，所以可以直接用\(\&\)运算来判断一个结点是否能加进去后还形成团，用优先队列来维护前k小的团的权值。 Code #include<bits...

bitset

2019-08-13

0 442

2019牛客暑期多校训练营（第二场）J

题意给一个长度为1e9的只包含1和-1的数列，1的个数不超过1e7,计算有多少对\((l,r)\)满足\(\sum_{i=l}^r a[i]>0\) 分析 dp求出每段连续的1最右端为右端点的最大子段和和最左端为左端点的最大子段和，可以得出这段1往左或右最远能扩到哪里，将相接的连续1段...

2019-08-11

0 400