A

不解释

B

不解释

C

随便状压

D

差分即可

E

考虑一对位置 $(i,j)$ ,假如 $a_i \leq a_j$ ,那么 $j-i$ 之间的都可以合法的选或不选,贡献为 $2^{j-i-1}$

然后就类似树状数组求逆序对的做法,每次统计前面有多少个位置,把它们的二次幂的逆元丢到树状数组里,因为 $\frac{2^j-1}{2^i} = 2^{j-i-1}$

记得离散化

for (int i = 1; i <= n; ++ i) a[i].first = read(), a[i].second = i;
std::sort(a.begin(), a.end());
int ans = 0;
for (int i = 1; i <= n; ++ i) {
    PII it = a[i];
    ans = (ans + (pw[it.second] * query(it.second) % mod) % mod) % mod;
    modify(it.second, qPow(pw[it.second + 1], mod - 2ll));
}

F

按照直径长度的奇偶性分类讨论。

以长度为奇数为例,说明直径的中心是一个点,那么从这个中心点往两边走,走了 $k$ 步到达的点下面挂的子树,若是存在深度恰好为 $k$ 的点,那么这个点就可以加加入一条直径。

偶数的情况类似讨论就可以了。

最好统计有多少个这样的点,乘起来就可以了。

Code: submissions

G

首先它给的四种走的方法里面, $x, y$ 方向上只有一个在动。我们首先把坐标系逆时针旋转 $45°$ ,这样坐标系就是 $(x+y, x- y)$ 了。

那么每次在 $x$ 或 $y$ 方向上的 $\pm D$ 就可以在两维上独立考虑。即:

$$ \sum\limits_{i=1}^{n} s_iD_i = A+B, \sum\limits_{i=1}^{n} s'_iD_i = A-B $$

其中 $s_i = \pm 1$

发现上面的式子中,$\sum\limits_{i=1}^{n} D_i$ (记做 $S$ )是一个定值。那么设 $t_i = 0/1$ 表示在这一维上 $D_i$ 到底走没走出去,那么:

$$ \sum\limits_{i=1}^{n} t_iD_i = \frac{S+A+B}{2},\sum_{i=1}^{n} \limits t'_iD_i = \frac{S+A-B}{2} $$

那么如果 rhs 是个负数或者比 $S$ 要大那么肯定就无解了。rhs 实际就是在某一个方向上总共走了多少。

然后通过一个 DP,设 $f_{x,y}$ 表示若 $\sum\limits_{i=1}^{x} t_iD_i = y$ 则为 $1$ ,否则为 $0$ 。实际上也可以解方程,参考 mals 的提交。

Code:submissions

H

不更,鸽了

最后修改:2021 年 10 月 19 日
如果觉得我的文章对你有用,请随意赞赏