xyq0220

题解

未归档(101)

/ 注册

全部文章 / 题解（共3篇）

牛客练习赛71 C- 数学考试 DP

牛客练习赛71 C- 数学考试题意求的排列，有个限制条件，第个限制条件表示前个数不能是的排列，求符合要求的排列的个数。答案对 20000311 取模。做法1 设为满足限制的情况下放好了排列的前个数且最大值为的方案数，转移如下：，说明这一位有限制。否则，，表示若，那...

DP

2020-10-14

2 627

牛客练习赛71 E- 神奇的迷宫点分治+NTT

牛客练习赛71 E- 神奇的迷宫题意给一颗个点的树，每条边的长度均为，Alice和Bob两人依次传送到树的某两个结点。对于任意一个人，传送到点的概率为，假设两人传送到的结点之间的最短距离为，那么他们挑战这个树的困难度为。问他们挑战这个树的困难度的期望是多少。分析令表示两人最短距离为的概率...

点分治 ntt

2020-10-13

3 659

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

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

2019-08-11

0 923