CVBB ACM Team

题意:求$x + \left\lceil \frac{d}{x + 1} \right\rceil(x \ge 0)$的最小值。

题解:有$x + \left\lceil \frac{d}{x + 1} \right\rceil = \left\lceil x + \frac{d}{x + 1} \right\rceil$，因此可以化为对勾函数$x + \frac{d}{x + 1} = (x + 1) + \frac{d}{(x + 1)} - 1$，因此最小值在$\left\lfloor \sqrt{d} -1\right\rfloor$处或$\left\lceil \sqrt{d} - 1 \right\rceil$处取得。

题意:求$a \cdot b + a + b = conc(a, b)$且$1 \le a \le A,1 \le b \le B$的$(a, b)$对数，$conc(a, b)$表示将$b$放在$a$右边形成一个新的数字。$(1 \le A, B \le 10^9)$

题解:等式化为$a(b+1)=a*10^x$，其中$x$是$b$的位数，因此$b$只能是形如$10^x-1$数，$a$可以任意取，统计即可。

题意:两个数组$a$和$b$，满足长度均为$m$，元素均为$1$到$n$的整数，$a_i \le b_i$，$a$不降，$b$不升，求方案数。$(1 \le n \le 1000, 1 \le m \le 10)$

题解:我拿dp+前缀和优化写的，又慢又复杂，只需要将$a$和逆序的$b$拼到一起就成了$2m$个数在$1$到$n$里选数组成一个不降序列，答案为${n+2m-1 \choose 2m}$。

题意:给定$n$个长度为$m$的数组，选出两个（可以相同）的数组$a_i$和$a_j$，有如下定义$k \in [1, m], b_k = \max(a_{i, k}, a_{j, k})$，求$\min \limits_{k = 1}^{m} b_k$的最大值。$(1 \le n \le 3 \cdot 10^5, 1 \le m \le 8)$

题解:最大的最小，二分答案。发现$m$很小，因此对于一个要判断的值$x$，令$a_{i, j} = (a_{i, j} \ge x)$，则每个数组变成了一个子集，$x$合法的条件是有两个数组的并集为全集，只需要遍历每一个数组，枚举该集合的所有子集进行标记即可。复杂度为$O(2^mn\log n)$，$2^m$是子集数上界跑不满，而且时间给了五秒，可以过。

题意:给定$n$个元素，一开始的顺序为$1$到$n$，$m$次操作把一个元素移动到第一个，问整个过程中每个元素所在位置下标的最大值和最小值分别是多少。

题解:平衡树裸题。只需要模拟这个过程，然后把某个元素放到第一个的时候记录一下即可。但寒假写的时候用的是记录父亲的fhqtreap，这次用splay写的时候极度不熟练竟然没调出来。。最后操作完忘记splay还tle了。

题意:给出一个$m$条边的二分图，左边有$n_1$个点，右边有$n_2$个点。每个点给定颜色，可能是红色、蓝色、或者无色。每条边颜色不定，涂红色需要耗费$r$元，涂蓝色需要耗费$b$元，不涂色不要钱。要求与红点相连的边中红边数量的要严格大于蓝边数量，与蓝点相连的边中蓝边数量要严格大于红边数量，求最小代价并输出方案，或判断无解。$(1 \le n_1, n_2, m, r, b \le 200)$

题解:考虑上下界费用流。对于每条边，左连右一条边表示这条边涂红，费用为$r$流量为$1$，右连左一条边表示这条边涂蓝，费用为$b$流量为$1$。对于左边的红色点（右边对称一下），要求红边数量大于蓝边，因此不算源点的话流出的流量大于流入的流量，需要从源点向该点连一条费用为$0$下界为$1$上界无穷的边；同理对于左边的蓝色点（右边对称一下），要求蓝边数量大于红边，因此不算汇点的话流入的流量大于流出的流量，需要从该点向汇点连一条费用为$0$下界为$1$上界无穷的边；对于无色的边，没有流量限制，因此和源点和汇点都相连且下界为$0$。最后跑上下界费用流板子即可。