2018-Reconquista-C3

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== Contest Information ==

''' The 35th Petrozavodsk Programming Camp - Contest 1: t.me/umnik_team Contest '''

[https://official.contest.yandex.com/ptz-summer-2018/contest/8780 Yandex]

== 流水账 ==

【jsb视角】[[br]]
出门猜了F状态数不多就过了。把D题的暴力积分丢给了威威。担心了好久爆精度（事实上底下1e18就是爆了），正思考着要不要上python，测了几组数据发现答案有规律>_<。之后机位空了会儿有点伤,C题的度数不会有点慌。后来我先去写B的数据结构，很久后lzw才提出了C题的prufer序列的解法。之后我和lsmll搞出了G的做法，层层嵌套的数据结构。进度慢还是硬伤，开始写已经只剩下1h40min了。封榜后交了一发WA3，换lsmll上机敲板子线性递推板子，企图使过I。一通操作发现不是递推，溜了溜了。最后还有15min调G，一番魔改，1min时TLE6了，打出了GG……回去卡了卡常数就过去了，有点小郁闷。

== 总结 ==

=== lsmll ===
前期还不错，但是后面G题被卡常数了，而H题和I题的技术我们不太会，导致只有4题，虽然由于罚时不错勉强进了前10，但是我认为不够理想，应该要做出5题的。要好好学习不会的技术，好好提高水平。

=== jsb ===

C题其实挺显然的。但是prufer序列我基本忘了，看到度数相关竟然也没想到。C题做的有点久。[[br]]
B题虽然过得很顺利，但是其实是树剖强行维护的。其实更简单的dfs序做法，没仔细想。[[br]]
最伤的就是封榜后尝试莽I，其实想一想就会发现不是递推。[[br]]
G要对1kw的数据进行哈希，结束前最后1min才提交，TLE了，真的可惜。[[br]]
回去分析，发现我的模数只开了1e6，那冲撞概率也太大了>_<。随便乘了一个2^4^就秒过了。[[br]]

=== lzw ===
前期C题开的有些慢，H和I不会做是姿势水平不够，G题按理说应该要过的，因为浪费了机位的时间去抄I题的线性递推，其实理性分析一下这个显然是没法递推的。感受了一下感觉来参赛的队伍也不都是很牛的队伍，努力冲到前五吧。

== Solution ==

B：对于每一条边，维护一个二元组(a,b)，表示它子树/另一侧是否有黑点。树链剖分后，每次对连续区间的二元组某一维加减1，或者询问全局(a>=1,b>=1)的二元组边权和。容斥一下，两个维度独立，即是求某一维=0的数量。线段树维护区间最小值以及出现个数即可。 [[br]]
C: 化简之后发现一棵树的权值等于n * sum{i*(a_i-1)} + n * (n + 1) / 2.  发现sum{i*(a_i-1)}这个东西就是prufer序列的和。问题转化为求prufer序列和的期望。假设a全是-1，相当于有n-2个数，每个数在[1,n]随机，求它们和的期望。对于a不是-1的地方，相当于事先强制在这个序列里塞入了一些数，加上他们的贡献即可。 [[br]]
D：二分求出4个交点，暴力积分。发现答案有规律是4*a-1+2/3。 [[br]]
F：猜测状态数很小，暴力DP，map存状态。 [[br]]
G：将权值重新调整为原根的幂次。这样一个集合的阶就是(P-1)/gcd(S_i,P-1)。转化成区间加、区间gcd，线段树维护差分数组即可。 [[br]]
I: [[br]]
[https://www.cnblogs.com/jiangshibiao/p/9536185.html JSB's blog]

== 补题 ==
A [jsb]

E [jsb]

**F [](赛后被卡掉，有待fix)

G [jsb]

H [lzw，jsb]

I [lzw]

J []

Contest Information

The 35th Petrozavodsk Programming Camp - Contest 1: t.me/umnik_team Contest

Yandex

流水账

【jsb视角】[[br]]

出门猜了F状态数不多就过了。把D题的暴力积分丢给了威威。担心了好久爆精度（事实上底下1e18就是爆了），正思考着要不要上python，测了几组数据发现答案有规律>_<。之后机位空了会儿有点伤,C题的度数不会有点慌。后来我先去写B的数据结构，很久后lzw才提出了C题的prufer序列的解法。之后我和lsmll搞出了G的做法，层层嵌套的数据结构。进度慢还是硬伤，开始写已经只剩下1h40min了。封榜后交了一发WA3，换lsmll上机敲板子线性递推板子，企图使过I。一通操作发现不是递推，溜了溜了。最后还有15min调G，一番魔改，1min时TLE6了，打出了GG……回去卡了卡常数就过去了，有点小郁闷。

总结

lsmll

前期还不错，但是后面G题被卡常数了，而H题和I题的技术我们不太会，导致只有4题，虽然由于罚时不错勉强进了前10，但是我认为不够理想，应该要做出5题的。要好好学习不会的技术，好好提高水平。

jsb

C题其实挺显然的。但是prufer序列我基本忘了，看到度数相关竟然也没想到。C题做的有点久。[[br]]

B题虽然过得很顺利，但是其实是树剖强行维护的。其实更简单的dfs序做法，没仔细想。[[br]]

最伤的就是封榜后尝试莽I，其实想一想就会发现不是递推。[[br]]

G要对1kw的数据进行哈希，结束前最后1min才提交，TLE了，真的可惜。[[br]]

回去分析，发现我的模数只开了1e6，那冲撞概率也太大了>_<。随便乘了一个2⁴就秒过了。[[br]]

lzw

前期C题开的有些慢，H和I不会做是姿势水平不够，G题按理说应该要过的，因为浪费了机位的时间去抄I题的线性递推，其实理性分析一下这个显然是没法递推的。感受了一下感觉来参赛的队伍也不都是很牛的队伍，努力冲到前五吧。

Solution

B：对于每一条边，维护一个二元组(a,b)，表示它子树/另一侧是否有黑点。树链剖分后，每次对连续区间的二元组某一维加减1，或者询问全局(a>=1,b>=1)的二元组边权和。容斥一下，两个维度独立，即是求某一维=0的数量。线段树维护区间最小值以及出现个数即可。 [[br]]

C: 化简之后发现一棵树的权值等于n * sum{i*(a_i-1)} + n * (n + 1) / 2. 发现sum{i*(a_i-1)}这个东西就是prufer序列的和。问题转化为求prufer序列和的期望。假设a全是-1，相当于有n-2个数，每个数在[1,n]随机，求它们和的期望。对于a不是-1的地方，相当于事先强制在这个序列里塞入了一些数，加上他们的贡献即可。 [[br]]

D：二分求出4个交点，暴力积分。发现答案有规律是4*a-1+2/3。 [[br]]

F：猜测状态数很小，暴力DP，map存状态。 [[br]]

G：将权值重新调整为原根的幂次。这样一个集合的阶就是(P-1)/gcd(S_i,P-1)。转化成区间加、区间gcd，线段树维护差分数组即可。 [[br]]

I: [[br]]

JSB's blog

补题

A [jsb]

E [jsb]

**F [](赛后被卡掉，有待fix)

G [jsb]

H [lzw，jsb]

I [lzw]

J []