2016 ICPC 沈阳站

排名	当场过题数	至今过题数	总题数
25/?	6	8	13

A

solved by 2sozx

题意

签到题

题解

签到题

B

solved by 2sozx

题意

签到题

题解

签到题

C

solved by 2sozx

题意

\(f(1) = a, f(2) = b, f(i) = 2f(i - 2) + f(i - 1) + i^4\) 求 \(f(n)\)。\(n,a,b < 2^{31}\)

题解

矩阵快速幂模板题，注意爆 \(int\)

D

upsolved by vjudge

题意

之前练到过，有毒题，爬。

题解

爬。

E

upsolved by

题意

题解

F

upsolved by

题意

题解

G

upsolved by 2sozx

题意

给一个圆柱体容器，底面半径为 \(1\) ，高为 \(2\) ，现向其中倒入高度为 \(d\) 的水，将容器倾斜，问水刚好不洒出容器时液面的面积是多少。

题解

参考链接

H

upsolved by JJLeo

题意

题解

I

solved by JJLeo

题意

树上斜率优化，要用单调队列，每个节点从所有祖先那里转移。

题解

考虑使用可撤销的单调队列，对于队首 \(l\)，只会进行 \(l++\)，因此将它复原到原本的 \(l\) 即可。对于队尾 \(r\)，和可撤销的单调栈一样，每次将新插入元素直接放在队尾，然后将它和本该被弹出的最后一个元素互换，将此时的下标记录为该节点的队尾下标，回溯时进行撤销，将儿子队首位置的元素和自己 \(r+1\) 位置的元素交换即可。

J

upsolved by JJLeo

题意

给定一棵节点数为 \(n\) 基环树，\(q\) 次操作，分为两种：将所有距离点 \(x\) 不超过 \(d\) 的点加上一个值，或询问所有距离点 \(x\) 不超过 \(d\) 的点的权值之和。\((n, q \le 10^5, d \le 2)\)

题解

如果是一棵树，那么对于一个节点，需要考虑的就只有它的父亲，它的爷爷，它的兄弟，它的儿子和它的孙子。考虑对树进行bfs，那么上述的bfs序各自构成一个连续的区间，使用线段树维护即可。

本题是基环树，因此需要讨论一波，对于环上的点，考虑对于环上临近的1个或2个点即可，注意去重，以及当 \(d=2\) 时且选中点为环上点时，要考虑环上临近点的所有儿子。

记录

总结

• ZYF：J题分类讨论完全正确，但是算法完全想错了，\(O(n)\) 维护不太可能，太想当然了。