xyq0220

分类

未归档(101) 题解(3)

/ 注册

全部文章（共104篇）

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

2019牛客暑期多校训练营（第二场）A 数学

题意 eddy走一个长度为\(n\)的环，每次能往前或往后走一步，问走到\(m\)点恰好走完所有点至少一次的概率，前\(i\)个询问的答案要乘起来分析 \(n=1,m=0\),答案为\(1\) \(n>1,m=0\),答案为\(0\) \(n>1,m \ne 0\)...

数学

2019-08-11

0 425

2019牛客暑期多校训练营（第八场）A 单调栈

题意给一个\(n*m\)的01矩阵，找有多少个全1子矩阵不被其他全1子矩阵包括。分析用单调栈找到的全1子矩阵是不能向上扩展和向右扩展的，只需判断该子矩阵能否向左和向下扩展，若四个方向都不能扩展，则该矩阵合法。是否能向左扩展可用预处理出的左边一列的高度是否大于等于该子矩阵的高度判断，是否能...

单调栈

2019-08-11

0 382

2019牛客暑期多校训练营（第八场）A 单调栈

题意给一个的01矩阵，找有多少个全1子矩阵不被其他全1子矩阵包括。分析用单调栈找到的全1子矩阵是不能向上扩展和向右扩展的，只需判断该子矩阵能否向左和向下扩展，若四个方向都不能扩展，则该矩阵合法。是否能向左扩展可用预处理出的左边一列的高度是否大于等于该子矩阵的高度判断，是否能向下扩展可用前缀和判...

2019-08-11

0 923

BZOJ 1984 月下“毛景树” 树链剖分+线段树

题意 bzoj好像把这题删了，在洛谷里找的毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~ “毛景树”上有N个节点和N-...

2019-07-19

0 490

BZOJ 3531 [Sdoi2014]旅行

题意 S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和...

2019-07-19

0 459

2019 ACM-ICPC 西安全国邀请赛 E-Tree

题意给一颗带点权的树，三种操作修改从1到s的路径上的所有点，修改从1到s的路径上的所有点，询问将1到s的路径上的所有点作为石头堆，再加上一个个数为的石头堆，进行一次尼姆博弈，先手胜利输出YES，否则输出NO 分析尼姆博弈先手必...

2019-07-19

0 535

2019 ACM-ICPC 西安全国邀请赛 E-Tree 树链剖分+线段树

题意给一颗带点权的树，三种操作 \(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的路径上的所有点作为石头堆，再加上一个个数...

线段树树链剖分

2019-05-29

0 402

2019 ACM-ICPC 西安全国邀请赛 E-Tree 树链剖分+线段树

题意给一颗带点权的树，三种操作 \(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的路径上的所有点作为石头堆，再加上一个个数...

线段树树链剖分

2019-05-29

0 410