ARC082C ConvexScore

简要题意

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

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

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

ARC082D Sandglass

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

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

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

POJ2449 k短路问题

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

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

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

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

POJ2096 期望DP

题目传送门

简要题面:

一个程序有n个子程序。有s种bug,每天能等概率随机在一个子程序中找到一个bug,如果一个子程序中的一种bug被找到了,再下一次这个子程序的这种bug被找到的概率依然不变。问期望至少需要多少天能在每个子程序中都至少找到一个bug,把每一种bug都最少找到一次。

|

博客使用Disqus作为评论系统