约瑟夫问题的一些解法

约瑟夫问题:

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

算法1(Simple算法):

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

时间复杂度$O(nm)$

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

UOJ164 V

传送门

题意:维护一个数列$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的交互题,但并不是那么难。

9-4日互测T2 factory

一道非常好的斜率DP练习题from Z博士。

题面

(因为我懒所以我吃了latex,原题是有latex的)

ARC082C ConvexScore

简要题意

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

设总点集为A。
这个凸多边形的分值为为:$2^s$

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

ARC082D Sandglass

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

一共会有k次翻转杯子,第i次翻转杯子会在第 $r_i$ 秒。

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

洛谷1970 花匠

简要题意

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

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

简要题解

CF86D-Powerful Array

简要题面

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

题目传送门

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

设$in_i$表示至少流到i的流量,$out_i$表示至少从i流出的流量。

POJ2449 k短路问题

$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短路。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×