岩之痕

题解

/ 注册

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

K点游戏题解

题目输入：N, K, W输出：从0点开始每次增加[1, W]的随机数，直到大于等于K点。问最终点数小于等于N的概率。符号定义： A[start, end) = A[start] + A[start+1] + ... + A[end - 1]A[start, end] = A[start] + A...

概率论差分数组

2019-08-25

2 1048

单调栈题解

单调栈 O(N) 两次遍历创建一个栈来存各个值的下标。从左往右扫描数组，在将A[i]加入栈之前，将所有大于等于A[i]的元素出栈，此时栈顶元素就是左侧第一个小于A[i]的数的下标，在记录答案之后将i入栈，继续向右扫描。在此操作下，栈中元素一直保持单调递增，故称单调栈。正确性证明：假设j <...

单调栈线段树莫队算法

2019-08-22

8 1098

X游戏题解

暴力搜索复杂度O(NlogN) 暴力法，需要一个函数判断一个数是否是“好数”。好数可简化为不含3，4，7的且至少含一个2或5或6或9的数。对每个数，统计每个数字的出现数量再做判断即可。时间复杂度O(NlogN)，因为要取出每个数的每个数位。数位DP 复杂度O(logN) 好数的个数 = （只...

字符串数位DP 动态规划

2019-08-21

1 828

搭积木题解

题目转化首先将题目数据按照(W, L)排序。如果(W1, L1) < (W2, L2)，再加上题目给的W <= L条件，则(W2, L2)只能被放在(W1, L1)下面。如果(W1, L1) = (W2, L2)，两个积木完全相等，先后顺序没有限制，在不影响答案正确性的情况下，可以自己...

树状数组最长上升子序列

2019-08-18

0 1009

滑动窗口的最大值题解

题目数组num的长度为N，求其所有长度为W的连续区间的最大值。一、平衡树直接用map来对每个出现的值计数，map可以直接加入，删除，求最大。时间复杂度O(NlogW)空间复杂度O(N) 二、Sparse Table 利用Sparse_Table算法思想，将区间[A, A + W) 分解成[A...

单调队列

2019-08-11

10 2037