9-18-模拟赛-20

title: 9.18 模拟赛#20
date: 2023-09-18 15:11:52
categories: 
 - 题解
top: #114

T1

手玩后发现第一个人的最后个数最多，易证。

然后考虑别人给了他多少贡献，应为 \(\frac{m}{3}+\frac{\frac{m}{3} }{3}+\frac{a_n}{3}\)。其中 \(a_n\) 为 \(n\) 开始分前的数量。

发现 \(\forall \ 2 \le i \le n,a_i=\frac{\frac{ {\frac{a_1}{3}+a_2} }{3}\dots +a_n}{3}\)，只有部分数字对它有贡献，\(O(log_3 n)\) 即可。

tips：向下取整时 \(\frac{\frac{x}{3} }{3} \neq \frac{x}{9}\)。

code

T2

通过不算一个数的值想到容斥，于是考虑每个值要不算几次。

首先把每个限制按照 \(y\) 分类，然后根据 \(x,y\) 的大小关系算情况，然后减去同时以两个关键点为两个端点的情况。

特别注意的是，当 \(x=y\) 时，情况要加上 \(n\)；减去的值为 \(sum(x < n)+sum(x > n)+[x=n] \times (sum(x < n)+sum(x > n))\)

code

T4

先上结论：\(a\) 树（权值为 \(a\) 的树）与 \(b\) 树的数量相等。

证明：

设树的大小为 \(n\) 。

对于 \(a\) 树，