2016-C03-team3

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(2016-08-03 15-08-09屏幕截图.png)]]
'''by shb'''
{{{
今天的我也是一如既往地划水啊！其实还要糟糕一点= =因为没有一题是我亲手写完A掉的。开局我负责看ABC。A题（看起来）思路很简单，随机加表达式计算就好了，先放着。
B题的思路也很简单，DFS序套树状数组，但看了一下范围，发现最多有5000W个操作，顿时就很虚。于是就转向了看起来最简单的C题，结果特么是个坑。当我在坑里游来游去的
时候，xian学长发现I是个签到题，但没有注意到空间上限只有4M，用了map结果MLE了。fengsuiyan学长想了个位运算的优化，用了4kb就A了，orzorz。然后进入了长时间的卡题。
我们写了一下D，发现不停地WA，于是就暂时搁置了。
过了很久，fengsuiyan学长在数学手册上找到了F题的重要性质——所有最高次系数为1的多项式方程的有理根都是整数。于是就轻松过了。后面我写了个A的框架，就剩下（大雾）
表达式的计算了。这是我发现自己对单目运算符和括号的理解并不是很深，于是甩锅给了fengsuiyan学长，过了一会儿他就写出来了（赛后发现其实随机是非常容易卡掉的，今天
难得欧了一次），真是太强辣！这段时间我和xian学长讨论了一下H的题意，YY了一下发现其实十分简单，让xian学长上去写了。之后，我们开始死磕D，换了各种写法，枚举了各种
题意，但就是WA。终于在比赛还剩半个小时的时候，我发现一直没仔细看的主循环里少了一个对答案的更新，交上去WA在了后面的点，然后把最小的自然数换成了1就过了，欧洲人的
数学真是难以理解啊！这大概是我本场做的最有价值的事情了吧。之后看了一下E，fengsuiyan学长想到了一个状压，但来不及了，就这样结束了。
今天没怎么动手写代码，靠学长们carry。躺赢的感觉还是很棒的2333。感觉自己的数学很需要加强，还有阅读能力，J题到最后都没有很理解。
}}}
'''by fengsuiyan'''
{{{
看到I mle后，记得在编程之美上看到过类似的就写了一发按位统计。过了I。发现有人过了F，就去看，感觉并不会，也没啥题写，我在那边翻了翻数学手册，然后发现数学手册
好强，然后过了F。背一个D的锅，写的时候有一个判断没有更新最值，wa了好多次不应该。E和C都有想，然而写不完了。
}}}
'''by imxian'''
{{{
I题没想到竟然会卡空间，空间限制只有4M，MLE了。
H题，shb学长跟我讲的时候说要去掉互相包含的线段，我觉得不用，结果wa了一次，以后搞不清楚的地方还是要多和学长们沟通。
D题wa得太多次了，当时应该两个人一起检查，逐行解释代码。
}}}

== '''未完成题目''' ==
   B C E G J
'''嘴巴AC一下B题'''
题意：有一棵树，两种操作，一种是选定至多1000个点，给它们加权值。第二种是询问两给定点路径上权值之和。Q<=50000
很显然QK已经5000w了，再套个数据结构的复杂度肯定要T。所以考虑牺牲第第二种操作的时间来加速修改。我们考虑分块。对于某个询问，令S(x)表示根到x路径的权值和，则Query(A,B)
=S(A)+S(B)-S(LCA(A,B))-S(Fa(LCA(A,B))),我们只要可以快速地修改查询S(x)即可。在树的DFS序上，如果每个点出现两次，将第一次出现的位置赋值为其权值，第二次出现的位置赋值
为权值的相反数，则对于x第一次出现的位置L[x],V[1]+V[2]……+V[L[x]]就是我们要求的S[x]。我们将DFS序分块，维护每块的和，这样就可以O(1)修改，查询的时候只要前面整块查，
最后不完整的一块暴力，就可以做到O(sqrt(N))。总复杂度O(Q(K+sqrt(N)))。

by shb

今天的我也是一如既往地划水啊！其实还要糟糕一点= =因为没有一题是我亲手写完A掉的。开局我负责看ABC。A题（看起来）思路很简单，随机加表达式计算就好了，先放着。
B题的思路也很简单，DFS序套树状数组，但看了一下范围，发现最多有5000W个操作，顿时就很虚。于是就转向了看起来最简单的C题，结果特么是个坑。当我在坑里游来游去的
时候，xian学长发现I是个签到题，但没有注意到空间上限只有4M，用了map结果MLE了。fengsuiyan学长想了个位运算的优化，用了4kb就A了，orzorz。然后进入了长时间的卡题。
我们写了一下D，发现不停地WA，于是就暂时搁置了。
过了很久，fengsuiyan学长在数学手册上找到了F题的重要性质——所有最高次系数为1的多项式方程的有理根都是整数。于是就轻松过了。后面我写了个A的框架，就剩下（大雾）
表达式的计算了。这是我发现自己对单目运算符和括号的理解并不是很深，于是甩锅给了fengsuiyan学长，过了一会儿他就写出来了（赛后发现其实随机是非常容易卡掉的，今天
难得欧了一次），真是太强辣！这段时间我和xian学长讨论了一下H的题意，YY了一下发现其实十分简单，让xian学长上去写了。之后，我们开始死磕D，换了各种写法，枚举了各种
题意，但就是WA。终于在比赛还剩半个小时的时候，我发现一直没仔细看的主循环里少了一个对答案的更新，交上去WA在了后面的点，然后把最小的自然数换成了1就过了，欧洲人的
数学真是难以理解啊！这大概是我本场做的最有价值的事情了吧。之后看了一下E，fengsuiyan学长想到了一个状压，但来不及了，就这样结束了。
今天没怎么动手写代码，靠学长们carry。躺赢的感觉还是很棒的2333。感觉自己的数学很需要加强，还有阅读能力，J题到最后都没有很理解。

by fengsuiyan

看到I mle后，记得在编程之美上看到过类似的就写了一发按位统计。过了I。发现有人过了F，就去看，感觉并不会，也没啥题写，我在那边翻了翻数学手册，然后发现数学手册
好强，然后过了F。背一个D的锅，写的时候有一个判断没有更新最值，wa了好多次不应该。E和C都有想，然而写不完了。

by imxian

I题没想到竟然会卡空间，空间限制只有4M，MLE了。
H题，shb学长跟我讲的时候说要去掉互相包含的线段，我觉得不用，结果wa了一次，以后搞不清楚的地方还是要多和学长们沟通。
D题wa得太多次了，当时应该两个人一起检查，逐行解释代码。

未完成题目

B C E G J

嘴巴AC一下B题

题意：有一棵树，两种操作，一种是选定至多1000个点，给它们加权值。第二种是询问两给定点路径上权值之和。Q<=50000

很显然QK已经5000w了，再套个数据结构的复杂度肯定要T。所以考虑牺牲第第二种操作的时间来加速修改。我们考虑分块。对于某个询问，令S(x)表示根到x路径的权值和，则Query(A,B)

=S(A)+S(B)-S(LCA(A,B))-S(Fa(LCA(A,B))),我们只要可以快速地修改查询S(x)即可。在树的DFS序上，如果每个点出现两次，将第一次出现的位置赋值为其权值，第二次出现的位置赋值

为权值的相反数，则对于x第一次出现的位置L[x],V[1]+V[2]……+V[L[x]]就是我们要求的S[x]。我们将DFS序分块，维护每块的和，这样就可以O(1)修改，查询的时候只要前面整块查，

最后不完整的一块暴力，就可以做到O(sqrt(N))。总复杂度O(Q(K+sqrt(N)))。

附加文件