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}\)。
T2
通过不算一个数的值想到容斥，于是考虑每个值要不算几次。
首先把每个限制按照 \(y\) 分类，然后根据 \(x,y\) 的大小关系算情况，然后减去同时以两个关键点为两个端点的情况。
特别注意的是，当 \(x=y\) 时，情况要加上 \(n\)；减去的值为 \(sum(x < n)+sum(x > n)+[x=n] \times (sum(x < n)+sum(x > n))\)
T4
先上结论：\(a\) 树（权值为 \(a\) 的树）与 \(b\) 树的数量相等。
证明：
设树的大小为 \(n\) 。
对于 \(a\) 树，