🔖 quiz扫描线前缀和树状数组线段树

一维区间

问题简述

坐标轴上存在 N 条线段，有 Q 次查询，每次查询询问与给定区间 [aq,bq] 相交的线段数量。（相交指存在重叠的区域，包括相互包含的情况）

问题简析

先对线段进行排序：左端点小的排在前面，左端点相同时，右端点小的排在前面。

记 f(x) 为左端点在点 x 上的线段条数，

🔖 quiz经典问题约瑟夫环

经典约瑟夫环问题

有 N 个人围坐成一圈，任选某个人将其编号为 0，其右手边的人编号为 1，以此类推，将全部 N 个人进行唯一编号。由编号为 0 的人从 1 开始报数，其右手边的人报下一个数，以此类推。报到 M 的人起身离开，TA 右手边的人又从 1 开始报数，直到所有人起身离开，求最后一个起身离开的人的编号。

🔖 专题训练解题报告

前言

这两天奶奶做手术，我在医院里陪护，奶奶不会说普通话所以只好一直陪在旁边。实在有些闲得慌，正好在刷知乎的时候看到了《剑指offer》的推荐，搜了下发现有 OJ 收录了原书中的题目，于是开始尝试手机写代码23333（没有带电脑）。 强迫症晚期，一上手就非要做完不可，还好题目量少。使用低效率的方式做一件并不紧要的事情实在是太浪费生命了。（不过也有人说，生命就是用来浪费的2333

🔖 quiz分治追击

问题描述

给定一个长度为 N+1 的数列 A={a0,a1,a2⋯,aN}.
其中 1⩽ai⩽N,0⩽i⩽N,N⩾1

🔖 acm算法动态规划背包问题

01背包

有 N 件物品和一个容量为 C 的背包。
其中，第 i 件物品体积为 vi [1]，价值为 wi。
求选择将哪些物品装入背包可使获得的价值总和最大。

问题简析

因为每件物品只有两种选择：放或不放入背包。且每件物品之间相互独立，即无论第 i 件物品怎么选都不影响第 j(i<j⩽N)

🔖 reactreact reconciliation

预备知识

Reconciliation

使用 React 构建的应用，在初次渲染时 React 会调用的 render() 方法生成一棵 React Elements 树，在下一次 props, state 发生变化时，将重新调用 render() 方法并得到一棵新的 React Elements 树。为了高效地完成更新，需要计算出两棵树之间的差异，然后仅对差异部分应用更新。收集差异的过程被称为

🔖 quiz动态规划

问题描述

有 K 个鸡蛋和 N 层楼，测试最多试验几次可以测出让鸡蛋摔碎的最低楼层。假定鸡蛋无磨损，即如果在第 x 层楼扔下没碎，那么在第 x 层楼重复扔无限次都不会碎。没碎的鸡蛋可以重复使用（用于测试），已碎的鸡蛋无法继续使用。

算法一

将 N 层楼看作长度为 N 的区间，记 dp(k,n)

© 2017-2025 光和尘有花满渚、有酒盈瓯