简要题意

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

设总点集为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短路。

题目传送门

题解

状压DP。 将每一只猪打下来/没打下来用一个二进制位表示。 猪的数量不是很多，每一条抛物线至少要打到一只猪，所以可以枚举出所有可行的抛物线，这条抛物线对每一只猪能/不能打下来用一个二进制为表示。

论卡（内存）常卡了一晚上不爽去抗议要求加大内存限制的悲哀2333

题目传送门

题目传送门

中文题面还是很清楚的。

不想解释题面了。

NOI原题确实是很难的。

题目传送门

简要题面：

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