给出 $n\,(1\le n\le 4000000)$ 天的股票价格，每天可买进或卖出一股，可以同时买进或卖出，也可以不操作，但最终手上只能有一股。问最多 $k$ 次买进和卖出后的最大收益。

有一个 $(n + 2) \times m$ 的长方形，除了第一行和最后一行，其他每一行每一天最左边和最右边的格子都有 $p$ 的概率被摧毁，每行之间独立且左边和右边独立，求 $k$ 天之后最上面一行与最下面一行四联通的概率。

其中 $1\le n,m\le 1500,\,0\le k\le 10^5$，答案对 $10^9+7$ 取模。

有一张二分图，左边有 $n_1$ 个点，右边有 $n_2$ 个点，$m$ 条边。每个点可能有一种颜色 R 或者 B，也可能没有，也就是 U。现在要给一些边染色，把边染成 R 要花费 $r$ 的代价，把边染成 B 要花费 $b$ 的代价，要求对于每个颜色为 R 的点，与之相邻的边中 R 的边严格多于 B 的边；对于每个颜色为 B 的点，与之相邻的边中 B 的边严格多于 R 的边。求花费最小的方案，输出任意一种，无解输出 $-1$。其中 $1 \le n_1, n_2, m, r, b \le 200$。

给定一个长度为$n$的字符串，其中只有 '(', ')', '?' 三种字符，其中 '?' 可以为 '(' 或者 ')'。对于一个括号序列，定义其权值为其通过删除字符后可以得到的合法的括号匹配的最深的深度，求出所有可能的括号序列（即问号替换后）的权值和。

在 D1 中，$n\le 2000$；在 D2 中，$n\le 10^6$。

题意大概就是有$n$个点，每个点其坐标$x_i,y_i$与权值$c_i$，其中$1\le n\le 5\cdot 10^5,0\le x_i,y_i\le 10^9,-10^6\le c_i\le 10^6$。

让你选一个正方形，该正方形的左下角及右上角必须在$y=x$这条直线上。所获得的权值为在正方形内的点的权值和减去正方形的边权。输出所获的最大权值及其选择正方形的左下角$x_1,y_1$及右上角$x_2,y_2$，要求$0\le x_1=y_1\le x_2=y_2\le 2\cdot 10^9$。

感觉tf的时候还是打几场VP好……

加*号的是当场过掉的，这样以后复习可以用。

决定开个新坑，刷一些CF上的dp题。

现在做了几题：

题目大意

我们定义一棵树的删除序列为：每一次将树中编号最小的叶子删掉，将该节点编号加入到当前序列的最末端，最后只剩下一个节点时将该节点的编号加入到结尾。

例如对于上图中的树，它的删除序列为：2 4 3 1 5。

现在给出一棵$n$个节点的树，有$m$次操作：

1. up v：将$v$号节点的编号变为当前所有节点编号的$\max + 1$；
2. when v：查询$v$在当前树的删除序列中是第几号元素；
3. compare u v：查询$u$和$v$在当前树的删除序列中谁更靠前。

原题链接

有$n$个二次函数，第$i$个形如$f_i(x)=a_ix^2+b_ix+c_i$

你的总收益是$\sum_{i=1}^nf_i(x_i)$，但是有几个限制：

1. $x_i​$是$[l_i,r_i]​$中的一个整数
2. 还给了$m$条额外的限制，每条形如u v d，表示的是$x_u\leq x_v+d$

求最大的总收益。

$n\le 50; m\le 100; |a_i|\le 10;|b_i|,|c_i|\le1000;-100\le l_i\le r_i\le 100;|d_i|\le 200$。^[1]

有两个快递员，分别在$s_1, s_2(0\le s_1,s_2\le 10^9)$，现在有$n(1\le n\le 100000)$个任务，每个任务$x_i$表示要将货物送到$x_i$，让任何一个快递员到$x_i$都可以。由于快递员之间需要有对讲机联系，请你设计一种方案使得两个快递员之间的最长距离最短。