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 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏