老 K 的博客

约瑟夫问题：

有n个人，编号为\(1..n\)，从第1个人开始报数，报到m的人离开，求最后的幸存者。

算法1（Simple算法）：

用队列模拟，可以算出每一次出队的人。

时间复杂度\(O(nm)\)

当n很小而m很大时，可以通过取膜将\(O(nm)\)优化为\(O(n^2)\)

传送门

题意：维护一个数列\(a_1...a_n\)，有以下5种操作： 1. \(a_l..a_r=a_l..a_r +x\) 2. \(a_l..a_r=max(a_l..a_r-x,0)\) 3. \(a_l..a_r=x\) 4. 查询\(a_x\) 5. 查询\(a_x\)的历史最大值

题面 一道ioi的交互题，但并不是那么难。

一道非常好的斜率DP练习题from Z博士。 ### 题面 (因为我懒所以我吃了latex，原题是有latex的)

简要题意

给定n个点，定义一个凸多边形包含点数s为：这个凸多边形覆盖的点数-这个凸多边形的角数（每一个角\(<180°\))

设总点集为A。 这个凸多边形的分值为为：\(2^s\)

求由这n个点构成的所有凸多边形的分值和\(mod 998244353\)

题意：有一个沙漏由A,B两个杯子组成。一共有X克沙子。 每秒会有一克沙子从上杯子流到下杯子，直到流完为止。

一共会有k次翻转杯子，第i次翻转杯子会在第 \(r_i\) 秒。

有q组询问，每组形如 \(t,a\) ，表示一开始A杯子在上，里面有a克沙子（B杯子里有 \(X-a\) 克沙子），求第t秒的时候A杯子里有多少沙子。 \(q,k\le 10^5\)

简要题意

给定一个序列，求最长波浪子序列。

波浪序列是指一个大一个小这样循环或一个小一个大这样循环。

简要题解

简要题面

设一个序列的分值为每个数出现次数的平方乘这个数，给定一个长度为n序列，有m组询问\([l,r]\)，求从第l个数到第r个数这个子序列的分值。

题目传送门

无源汇有上下界可行流问题。

设\(in_i\)表示至少流到i的流量，\(out_i\)表示至少从i流出的流量。

\(A^\star\)算法的经典应用----k短路问题。

\(A^\star\)算法：设\(f(x)=g(x)+h(x)\)，其中\(g(x)\)表示已花费代价，\(h(x)\)表示预估还需代价(\(h(x)\)要\(\le h^\star(x)\)）表示每次找到f值最小的拿出来扩展。

给定一个n点m边的有向图，求从s到t的k短路。

首先求出所有点x到t的最短路\(dis[x]\)，接下来用\(dis[x]\)作为\(h(x)\)跑 \(A^\star\) ，因为 \(h(x)\le h^\star(x)\) ，所以第k次找到t就是k短路。