m次k小值复杂度nlogm–上海科技大学2024年考研数据结构的某个题的第二问前言：当时场上没想出来，我感觉我很容易算错时间复杂度，22年的icpc济南，那道矩阵取模的题也是因为当时时间复杂度算错了结果没写。主要原因应该还是太依赖感觉了。 题目描述：这个题的第一问是无序序列求k小值。快速选择 时间空间都是o(n)，显然没有亚线性的算法。 第二问： 有m次询问，每次询问$k_i$小值要求空间复...

AOE/AOV网下的关键路径在做那本王道考研数据结构书的时候发现这个东西，以前没听说过（太菜了 1.定义一般而言这个模型可以用来表示一个项目的子项之间的依赖关系，用来管理项目进度。 1.1 AOV网AOV网指的是Activity-On-Vertex，用点表示事件，用边表示事件之间的关系（活动），边权是活动时间。这是一个DAG（有向无环图） 1.2 AOE网AOE网指的是Activi...

题解:齿轮1.题意地址:https://www.luogu.com.cn/problem/P8799 1.1 题目描述这天，小明在组装齿轮。 他一共有 $n$ 个齿轮，第 $i$ 个齿轮的半径为 $r_{i}$, 他需要把这 $n$ 个齿轮按一定顺序从左到右组装起来，这样最左边的齿轮转起来之后，可以传递到最右边的齿轮，并且这些齿轮能够起到提升或者降低转速（角速度）的作用。 小明看着这些齿轮...

题解 : Spreading the Wealth地址：https://vjudge.net/problem/UVA-11300 1：题意A Communist regime is trying to redistribute wealth in a village. They have have decided to sit everyone around a circular table...

FWT学习笔记0.参考文献参考文献 1.FWT的定义与证明首先fwt是解决一类二进制下与或非运算的卷积问题的 也就是形如$$C_i=\sum_{j\oplus k = i}A_j \times B_k$$使用fwt可以nlogn的进行计算 但是实际上似乎遇到一些任意进制下且不进位的卷积操作都可以考虑使用这种思想进行处理 1.1 AND$$c_i = \sum_{...

题解 : Fabled Rooks1.题意地址：https://vjudge.net/problem/UVA-11134 We would like to place n rooks, 1 ≤ n ≤ 5000, on a n × n board subject to the following restrictions • The i-th rook can only be placed ...

题解:So you want to be a 2n-aire1.题意地址:https://vjudge.net/problem/UVA-10900 The player starts with a prize of $1, and is asked a sequence of n questions. For each question, he may • quit and keep his...