数树
题意:
U 为所有 $n$个点的树的集合
对于给定的两棵树 $S, T$, 定义 $F(S, T) = y^{公共的边数}$
Question1:给定 $n, S$,求 $\sum_{T\in U}F(S, T)$
Question2:给定 $n$, 求 $\sum_{S \in U, T\in U}F(S, T)$
做法:
我们可以把 $y^k$贡献拆掉,$y^k = (y-1+1) ^ k = \sum_{i=0}^{k} \binom{k}{i} (y-1)^i$
就转换成了选择一些边同时属于两棵树,贡献是 $y^{边数}$
对于 Question1,如果这些边把 S 划分成了 $m$个联通块,每个联通块大小是 $a_i$,利用 prufer 定理可以得到这个划分的数量是 $n^{m-2}\prod_{i=1}^{m} a_i$,考虑一下组合意义,相当于找到树上若干个联通块,然后每一个联通块选一个根,这部分写一个树形 dp 就好了
对于 Question2 也是类似的想法,也是先枚举一下边集,计算两棵树都包含这个边集的方案数
$$
\begin{split}
ans &= \sum_{m=0}^{n-1}y^{n-m}\sum_{\sum_{i=1}^{m}a_i=n}\frac{n!\prod_{i=1}^{m}\frac{a_i^{a_i-2}}{a_i!}}{m!}\times (n^{m-2}\prod_{i=1}^{m}a_i)^2 \\
&= n! \frac{y^n}{n^4} [x^n]\sum_{m=0}^{n-1} \frac {\left(\frac{n^2}{y} \sum_{j=1}^{n}\frac{j^j}{j!}x_j \right) ^m} {m!}
\end{split}
$$
写一个 exp 就好了(细节省略掉啦)


远古计算机
subtask1 题意理解点
subtask2 打表用 jmp 代替 if
subtask3 bfs 一下
subtask4 把图建出来网络流啊
subtask5 人类智慧易得他是一张网格图,所以构造一下就好了


I 君的商店
题意:
交互题
给定长度为 $n$的 0/1 序列 ${a}$,至少有一个 1,已知 1 个数的奇偶性, 定义一个集合 $S$的 value 为 $\sum_{i \in S} a_i$ ,每次可以问交互库两个集合,交互库会返回 value 大小关系,如果两个集合 value 相等,那么交互库就会自己返回一个数,目标为确定整个序列。
做法:
先介绍一个 7N 的做法。
2N 确定最大值 a,然后每一次找两个还没有确定的 x,y,询问 x+y 和 a 的关系,然后再询问 x 和 y,代价为 5N 确定 x,y 中的一个数。
前面的 2N 并不是必要的,subtask3 告诉我们,可以二分确定一条递增的链。
优化一下之前7N的做法,先随便找一个a,然后找两个还没有确定的x,y,询问x+y和a以及x和y,假设 $x \leq y$,如果 $x+y \leq a$,那么 $x = 0$,否则 $y \geq a$,这样 $y->a$就是找到的一条链。最后在这条链沿用 subtask3 的做法就好了。

分类: 文章

7 条评论

Zepto · 2019年2月3日 4:57 下午

远古计算机的 Subtask 4 不是被出题人点名不是网络流嘛。

    foreverpiano · 2019年2月4日 7:51 下午

    类似于 CTSC 一道叫做家园的题目的建图。
    枚举一下答案(周期数)记为 d,把一个点拆成 d 个点排成 d 层,第 i 层向第 i+1 层练边,然后如果满流了就好了啊。
    简要题解是不是过于简要了啊 qwq。

      litble · 2019年2月11日 7:24 下午

      大神求教 QAQ
      这个网络流做法是保证求出最优解,还是只是构造一种较优的方案?
      为什么我这么做还是要 8 个周期才能出解啊?

        foreverpiano · 2019年2月14日 7:11 下午

        非常抱歉回复晚了。。
        这个做法是我同学在考场中写的,他 A 了 subtask4,我实现了一下好像是要 8 个周期,7 个周期是 49 个数。
        好像还有另外一种做法可以在 7 个周期出解,看起来很玄学的样子。差不多是先跑多源(51~100) 最短路,然后反过来 bfs,如果同一时刻有多个冲突了,开一个队列存一下,每一次传队首未传递的。
        我怎么感觉网络流 hack 不掉啊,不知道发生了什么。(明天我去问问他考场怎么做的

          litble · 2019年2月14日 7:29 下午

          我在洛谷看到题解里有个人用了你说的玄学做法,我发现 TA 的构造代码跑出来的答案一个 node 用了多次,运行 checker 可以 7 个周期出解。修复一个 node 用多次后却无法 7 个周期出解了(可能是我修复的方法不对)。
          我有点怀疑这题是不是有锅,它没说一个 node 用多次会记零分而是说用多次会出现未知错误,我怀疑这个未知错误可能反而导致错误的构造方案 AC。

      litble · 2019年2月12日 3:43 下午

      T2 能不能稍微讲仔细点啊 QAQ

        Remmina · 2019年2月13日 9:49 上午

        估计 foreverpiano 正在

        • 高高兴兴过大年
        • 欢欢喜喜迎新春

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注