岩之痕 - 个人主页动态 - 牛客网

发布(5) 评论刷题收藏

2019-08-25 22:35

已编辑

New York University C++

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[start+1] + ... + A[end] 一、用过去推现在 定义P[k]为不限抽取次数，获得k点的概率。则P[k] = (P[k-1] + P[k-2] + ... + P[k-W])/W 简写作P[k-W, k) / W只需快速求出P[k-W, k)，就可计算P[k]。同时记得区间[k-W...

0 点赞评论收藏

分享

2019-08-23 17:03

已编辑

New York University C++

单调栈题解

单调栈 O(N) 两次遍历 创建一个栈来存各个值的下标。从左往右扫描数组，在将A[i]加入栈之前，将所有大于等于A[i]的元素出栈，此时栈顶元素就是左侧第一个小于A[i]的数的下标，在记录答案之后将i入栈，继续向右扫描。在此操作下，栈中元素一直保持单调递增，故称单调栈。 正确性证明：假设j < i是i左侧第一个满足A[j] < A[i]的数。由假设可得，对于每个k(j < k < i)，都有A[k] >= A[i]，否则与假设矛盾。这些数都会被i出栈，出栈之后栈顶元素就是j。 同理从右往左扫描即可求出右侧第一个小于A[i]的数的下标。共遍历数据两次，每个下标最多入...

0 点赞评论收藏

分享

2019-08-22 14:15

已编辑

New York University C++

暴力搜索 复杂度O(NlogN) 暴力法，需要一个函数判断一个数是否是“好数”。好数可简化为不含3，4，7的且至少含一个2或5或6或9的数。对每个数，统计每个数字的出现数量再做判断即可。时间复杂度O(NlogN)，因为要取出每个数的每个数位。 数位DP 复杂度O(logN) 好数的个数 = （只含018，25，69的数字数量） 减去 （只含018）的数字数量于是需要一个函数快速求1到N中，只含0182569和只含018的数字数量。 定义：F018(n)为区间[0, n)中只含018这3个数字的数的数量。为了方便计算，需要做以下定义。1.区间包含0，且左闭右开。2.该计算方法会为每个数加上前...

0 点赞评论收藏

分享

2019-08-22 14:15

已编辑

New York University C++

搭积木题解

题目转化 首先将题目数据按照(W, L)排序。如果(W1, L1) < (W2, L2)，再加上题目给的W <= L条件，则(W2, L2)只能被放在(W1, L1)下面。如果(W1, L1) = (W2, L2)，两个积木完全相等，先后顺序没有限制，在不影响答案正确性的情况下，可以自己加上限制，排序之后排在后面的被放在下面。 这样，排在后面的积木一定被放在下方，则每种可能搭成的塔对应排序后的积木序列的一个子序列。这样，最高能够搭成的塔的层数等于L值的最长非降子序列的长度。 求解最长非降子序列 方法一、长度数组+二分 构建长度数组A。A[k]表示长度为k的非降序列的最小结尾数值。在...

0 点赞评论收藏

分享

2019-08-22 14:16

已编辑

New York University C++

滑动窗口的最大值题解

题目 数组num的长度为N，求其所有长度为W的连续区间的最大值。 一、平衡树 直接用map来对每个出现的值计数，map可以直接加入，删除，求最大。时间复杂度O(NlogW)空间复杂度O(N) 二、Sparse Table 利用Sparse_Table算法思想，将区间[A, A + W) 分解成[A, A+R) 和[A+W-R, A+W) 其中R是满足 2*R >= W的最小的2的次方。分解成的两个小区间有重叠，但由于是求最值，重叠部分不会影响答案。预处理部分中需要得到从每个下标A开始长度为1,2,4,8,...,R的区间的最值。相比Sparse_Table算法，这里的空间可以优化成O(...

微笑服务：真的，你提供思路ok，但贴代码，贴过不了的代码。。。那还能算题解吗？

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客企业服务