• 注册
    • 登录
    • 搜索
    • 版块
    • 最新
    • 标签
    • 热门
    • 用户
    • 群组
    • 荣誉
    • 搜索

    老年退役选手的复建之路

    综合讨论区
    10
    29
    1649
    正在加载更多帖子
    • 从旧到新
    • 从新到旧
    • 最多赞同
    回复
    • 在新帖中回复
    登录后回复
    此主题已被删除。只有拥有主题管理权限的用户可以查看。
    • xujing691691
      xujing691691 最后由 编辑

      leetcode P2736. 最大和查询
      7ed75883-784a-4f6e-ae60-b0e4ac50c22f-image.png

      一眼二维偏序问题，年轻的时候可以十分钟写完但是我现在只能告诉你我一顿可以吃一个九寸的披萨

      将询问离线化排序，再把数组1排序之后就可以转化为数组2上的一个区间（前缀）问题

      树状数组3年没写了，写的时候下标写错了没发现导致调了半天唉

      57d56222-597e-496f-8d03-602fc5ab2b20-image.png

      1 条回复 最后回复 回复 引用 5
      • 半
        半熟。 R'lyehs Explorers 最后由 编辑

        老登的秽土重生重回巅峰之路，不得不狠狠观看了

        言念君子，温其如玉

        1 条回复 最后回复 回复 引用 1
        • xujing691691
          xujing691691 最后由 编辑

          leetcode P689. 三个无重叠子数组的最大和

          给你一个数组，选择三段等长不交区间使得和最大
          暴力枚举下标显然是O(n^3)的，考虑预处理前缀和后缀，那么我们只需要枚举中间区间的下标即可，O(n)滚一遍
          这题数据规模好像可以放O(n^2)过
          1747a0ec-6528-4443-8625-2cb3c9e976e6-image.png

          1 条回复 最后回复 回复 引用 2
          • xujing691691
            xujing691691 最后由 xujing691691 编辑

            leetcode P1659. 最大化网格幸福感

            一眼爆搜然后脑算了下复杂度不太行，那只能上状压dp了(状压dp裸题)
            dp[i][m][n][pos]，i为目前格子编号 m,n为已经放好的人的数量 pos为i-5到i-1的前置状态，滚一遍就行

            代码能力退化调了半天主要是两个问题：
            1.dp初始状态一定要置-INF
            2.网格边界问题(主要n=1的情况特判)

            7058023f-4977-4a8b-a716-e91e55dafea6-image.png

            P2931. 购买物品的最大开销
            正难反易，倒序贪心就行
            0924143c-8138-49d2-923c-2d9a040a23c3-image.png

            1 条回复 最后回复 回复 引用 3
            • xiaofeng
              xiaofeng 下饭胡辣汤 拉莱耶队 中国队支援组 最后由 编辑

              卧槽你来真的

              1 条回复 最后回复 回复 引用 2
              • xujing691691
                xujing691691 最后由 编辑

                leetcode P2589. 完成所有任务的最少时间

                贪心的想法是把每个区间段按照右端点排序，然后进行染色处理，区间染色可以使用线段树加速

                尝试了一下不看板子现场推线段树，代码能力真退化了好多... 线段树上二分调了半天

                最后好像二分的不是很好还多了个log

                2b7ccd19-062c-4f1c-bb4c-e5f52855c8c0-image.png

                1 条回复 最后回复 回复 引用 1
                • xujing691691
                  xujing691691 最后由 xujing691691 编辑

                  P220. 存在重复元素 III
                  题不难，滑动窗口+区间求个数，但是我直接写了个map套树状数组的两个log的做法被卡常了，重新写一遍离散化

                  d25b8914-659f-47cc-ae7a-3a154e6f0c78-image.png
                  4c0c2f74-fccf-4487-b544-f238d21064f2-image.png
                  这三个方法返回的都是指针，所以要减去首地址
                  lower_bound返回的是第一个>=该元素的指针
                  upper_bound返回的是第一个>该元素的指针
                  注意一下临界的细节就行

                  c9b16318-5eb6-4169-a846-2449dac9679f-image.png

                  P2290. 到达角落需要移除障碍物的最小数目
                  01最短路，没啥好说的
                  倒是稀疏矩阵怎么建图还需要想想

                  e0fe71bb-998d-4492-b616-e0d0ca6231ae-image.png

                  P2897. 对数组执行操作使平方和最大
                  按位贪心
                  cfc21ff6-f948-4415-92f0-f719ff744ef0-image.png

                  P2876. 有向图访问计数
                  正着做很难，把边全部反向就会发现是一个环套树的森林，可以转换为每一个节点能够由多少个节点达到，如果树中没有环这个值就是节点的深度。
                  那么我们将大环看成根，缩点之后就很好做了。首先找该连通分量中的环，先通过判重获得环中一个顶点，然后再沿着该顶点一路将环中所有点找到，初始化它们的答案值，最后跑一遍dfs就行了。
                  细节还是蛮多的

                  58556d24-0f06-419c-a0e9-b9ab1eb07791-image.png

                  LCP 20. 快速公交
                  妈的这题卡了半天
                  首先考虑到玩家坐公交车的数量一定比较少且当较远路程的时候大部分时间一定花在坐车上，所以想当然的建图跑最短路
                  写到一半之后发现这是个假算法，在顶点为1e6以上的时候仍然可以存在步行部分路程，所以这题只能贪心
                  那么显然从终点倒推是最优的，注意到一个事实就是为了坐一班车，假设该车可跳跃的倍数为jump[i]，那么步行的距离一定不会超过jump[i]，否则一定绕了远路。所以就模仿Dijkstra的过程，从终点到起点进行稀疏图的最短路就好了。因为前面的结论，实际上该图的有效顶点和有效边数量相当少。
                  57054831-8115-4f93-84d0-678ab3d1c090-image.png

                  1 条回复 最后回复 回复 引用 1
                  • xujing691691
                    xujing691691 最后由 编辑

                    P85. 最大矩形
                    单调栈裸题，导下标导了半天
                    aa3e544d-0898-484a-9b6b-b1245b60c077-image.png

                    1 条回复 最后回复 回复 引用 1
                    • xujing691691
                      xujing691691 最后由 编辑

                      P629. K 个逆序对数组

                      一眼二维dp，只要算每一位对答案的整体贡献（准确的说是这一位对排在它后面元素的贡献）就可以，容易发现选择一位之后它不会影响后面选择的任何答案
                      dp[i][j]代表确定好前i位，逆序对数量为k的方案数
                      直接打了个暴力裸上去了本地跑最大测试点1.5s然后一提交超时...
                      注意到转移的时候本质上就是区间加，所以维护前缀数组就好，复杂度严格O(n^2)

                      8da6cf1c-2f7f-489b-8b68-0b1c9e525fb9-image.png

                      P1751. 最多可以参加的会议数目 II

                      很逆天的一题
                      首先这个模型是线段模型，是比01背包更简单的，因为选择某条线段的之后只会影响和它有交集的线段；更具体地说，选择某条线段之后剩余选择的线段只能从左端点严格大于其右端点的线段中找
                      那么显然把所有线段按照左端点排序，但是线段长度规模是1e9，我就一开始打了离散化+排序，dp[i][j]代表从x坐标i开始选择，已经选择j条线段的最大代价
                      然后就超时了...2e6的数据规模愣是支持不了sort+两次lower_bound

                      就只能重新修改做法，仍然是把线段按照左端点排序，dp[i][j]代表第0~i-1条线段都不能选，已经选择j条线段的最大代价

                      那么转移的时候需要找到选择该线段之后恰好能选择的下一条编号最小的线段，可以用upper_bound快速查找
                      时间是1e6的一个sort+一次upper_bound...就过了
                      339efaa7-a063-4fe2-968e-47e61694a563-image.png

                      1 条回复 最后回复 回复 引用 0
                      • xujing691691
                        xujing691691 最后由 编辑

                        P1092. 最短公共超序列
                        主要练一下带输出答案的dp，题很简单
                        dp[i][j]代表str1转移到i位，str2转移到j位的最小代价
                        新开pre数组记录每次dp时候转移的前驱，再倒推输出答案
                        fa4b8c6c-733d-459c-acde-54a3ee5d87ce-image.png

                        1 条回复 最后回复 回复 引用 0
                        • xujing691691
                          xujing691691 最后由 编辑

                          P218 天际线问题

                          给你若干个矩形，让你描述出最顶端的轮廓

                          不用stl的话是个线段树染色，涉及到区间染色和单点查询最值，用stl的multiset就能很好的解决这个问题

                          注意multiset想要删除单个元素需要s.erase(s.find(x))，否则会删除等值的所有元素

                          那就按照x轴排序，处理完同一坐标的所有内容之后用s.rbegin()获取最大值就好

                          P1330 翻转子数组得到最大的数组值

                          稍微有点复杂的一道题

                          首先显然的，翻转一个区间之后，中间的元素对整体答案的贡献完全不变，那么区别就区别在四个临界元素上：假设反转的区间为[l,r]，那么影响答案的四个元素为a,l...r,b，原来的答案为abs(l-a)+abs(b-r)，那么变动之后的答案为abs(r-a)+abs(r-b)，差值就为abs(r-a)+abs(r-b)-abs(l-a)-abs(b-r)...

                          是不是晕了？

                          涉及到绝对值的问题都要尝试拆绝对值，更具体一点就是尽可能分类讨论。因为我们只需要取最大值，那么就可以暴力枚举每种可能然后取个max就好。
                          循环的思路肯定是固定一侧(即l,a)而枚举另一侧(r,b)，那么之前的-abs(l-a)-abs(b-r)就可以扔到一边，我们根据前面的四种情况拆绝对值之后变成四个式子：

                          a-l+b-r
                          -a+l+b-r
                          -a+l-b+r
                          a-l-b+r

                          那么循环的时候a,l的部分是固定的，我们只要维护右侧b,r的后缀max值：

                          +b-r-abs(b-r)
                          -b+r-abs(b-r)

                          和左边取max就行。注意到l,r不能为边界，故边界需要再特判一下。

                          1 条回复 最后回复 回复 引用 0
                          • xujing691691
                            xujing691691 最后由 编辑

                            P42 接雨水
                            也是个单调栈的问题，画一下就知道最后形成的形状一定是一个类似于小山的（存在一个最高点，两边递减），那么就先确定最高点的位置（存在多个最高点任意选一个不影响结果），可以用单调栈把左右两侧的轮廓算出来，答案就出来了

                            P2818. 操作使得分最大

                            很缝合的一道题
                            每个点的得分可以用线性筛+分解质因数来预处理，单次查询是log级别的。然后我们去计算每个点的总贡献：先预处理每个点向左、向右”延展“的数量，即向左/右中value小于该点的值有多少个，这一部分可以用单调栈优化（怎么又是单调栈= =），设向左延展的长度为l，向右为r，那么该点一共能贡献的区间数量就是(l+1)*(r+1)了。排序之后贪心即可

                            1 条回复 最后回复 回复 引用 1
                            • 咕
                              咕咕能手 对战开拓区首领 最后由 编辑

                              啊？？？

                              1 条回复 最后回复 回复 引用 0
                              • xujing691691
                                xujing691691 最后由 编辑

                                诈尸
                                P1955. 统计特殊子序列的数目
                                简单的线性dp, dp[i]代表着取完数列中位置i的数字后的子序列个数
                                暴力转移n^2，但是因为题目数字只有三种所以合并状态就行了

                                P2528. 最大化城市的最小电量

                                一般这种带"最小值最大"的题目都是二分答案，答案显然具有单调性，那么这个问题可以转化为能否存在一种分配方法使得总电量均大于k
                                从左到右贪心就行，尽可能的将供电站靠后建，具体的说就是利用一个滑动窗口来进行维护，当一个数字将要出队列的时候检查它的电量是否达标，实际上就是区间和的问题，同样用滑动窗口维护
                                边界还是有点恶心的，就是最靠右的几个供电站我第一次忘判了，可以特判也可以暴力的将数组拉长至两倍（右边用0补齐）

                                1 条回复 最后回复 回复 引用 0
                                • Starmie
                                  Starmie 最后由 编辑

                                  鲸哥有空讲讲ologn求两个有序数组的中位数，我上次和同事没云出来

                                  xujing691691 1 条回复 最后回复 回复 引用 0
                                  • xujing691691
                                    xujing691691 @Starmie 最后由 xujing691691 编辑

                                    @Starmie
                                    这个模型可以推广为O(logn)求两个有序数组合并之后的第k大问题
                                    第k大，就是把数组里面前(n-k)个比它小的数字都删了，答案就一眼丁真了
                                    简单的想法就是效仿普通的归并，每次比较数组头两个数字，把小的踢出去，一共要踢(n-k)个比较小的数字
                                    那么我们考虑加速，有没有可能同时踢某个数组的一段数字呢？当然是可以的，为了方便起见我们假设剩下还需要踢k个数，那么这两个数组中一定存在某个数组，它的前floor(k/2)个数是可以直接踢出去的
                                    具体的，我们比较这两个数组中的第k/2个数字大小(数组长度不足k/2则取末尾)，更小的那个，它以及它之前的数字是一定可以全踢的
                                    01000527-a0cb-462e-8029-922b63c3fe62-image.png
                                    那么原本一共要踢k个数字，每次k值折半，严格logn级别

                                    （lc上好像有原题我今天有空了写一下）
                                    edit: e11c40a7-dc0e-4b3b-bdbc-04442c085875-image.png

                                    1 条回复 最后回复 回复 引用 2
                                    • xujing691691
                                      xujing691691 最后由 xujing691691 编辑

                                      面试题 17.20. 连续中值

                                      随机产生数字并传递给一个方法。你能否完成这个方法，在每次产生新值时，寻找当前所有值的中间值（中位数）并保存。

                                      动态维护集合中的中位数，要求复杂度均摊O(logn)
                                      首先这题平衡树肯定可以做，有没有更简单的办法呢？
                                      设某个状态中位数已经求出来了为x，那么对于新加的元素：如果元素>x，则新中位数一定为x的后继；<x，为x的前驱，这点很显然
                                      换言之我们只需要维护当前中位数的后继和前驱就好了，但是这个好像又涉及到平衡树了...
                                      假设我们找到了x的前驱为y，那么我们必须要马上获得y的前驱...好消息是，我们不需要对<x的所有数排序，只需要每次获取最大值就行了，是不是很像堆？
                                      所以我们维护一个大根堆和一个小根堆，大根堆维护<mid的数值，小根堆维护>mid的数值就好了，每次插入数字的时候将其与mid比较，当两个堆差值>2的时候及时平衡（就是把一个堆的顶部移到另外一个堆里就好）。

                                      面试题 17.19. 消失的两个数字
                                      给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
                                      设缺的两个数字为a b
                                      遍历第一遍可以把a+b找到，a一定<(a+b)/2
                                      遍历第二遍把a找到就行了

                                      1 条回复 最后回复 回复 引用 1
                                      • YANZUI烟醉
                                        YANZUI烟醉 Eevee Family 最后由 编辑

                                        看不懂，感觉很厉害

                                        海底月是天上月

                                        1 条回复 最后回复 回复 引用 1
                                        • 半
                                          半熟。 R'lyehs Explorers 最后由 编辑

                                          看的想学计算机

                                          言念君子，温其如玉

                                          1 条回复 最后回复 回复 引用 0
                                          • xujing691691
                                            xujing691691 最后由 编辑

                                            778 水位上升的泳池中游泳
                                            二分答案+bfs

                                            793 阶乘函数后k个零
                                            首先考虑到2*5=0且5的数量远小于2，不难发现F(x)实际上就是从1到x的数组中所有5的因数个数（当然我是打表之后强行总结的哈哈）。
                                            那么第一个问题就是快速求F(x)，x/5显然是1到x中能被5整除的个数，那么把这个数字再/5就是能被25整除的个数，这样递归一下就行，复杂度O(logN)。
                                            之前的打表发现：凡是存在x,k使得F(x)=k，那么满足上式的x的数量一定为5，换句话说我们只要验证给定的k，是否存在某一个x即可。F函数显然单调，二分一下就行了。
                                            复杂度两个log

                                            yiyue 1 条回复 最后回复 回复 引用 2
                                            • First post
                                              Last post