2016-S02-team1

从 Trac 迁移的文章

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

原文章内容如下：

||Run Id||Time||Problem||Language||Status||
||26||2||A||GNU C++||Yes||
||166||5||B||GNU C++||Yes||
||416||21||C||GNU C++||Yes||
||517||54||E||GNU C++||No - Time Limit Exceeded||
||635||83||I||GNU C++||No - Time Limit Exceeded||
||674||94||I||GNU C++||Yes||
||720||103||E||GNU C++||No - Time Limit Exceeded||
||1035||178||H||GNU C++||No - Wrong Answer||
||1047||181||E||GNU C++||Yes||
||1070||185||H||GNU C++||Yes||
||1769||290||G||GNU C++||No - Wrong Answer||
||1904||296||J||GNU C++||Yes||
||1927||297||G||GNU C++||No - Wrong Answer||
||1949||297||G||GNU C++||No - Wrong Answer||
||1968||298||G||GNU C++||Yes||

比赛链接:

== 流水账 ==

[http://www.cc98.org/dispbbs.asp?Boardid=329&ID=4661478 2016 沈阳赛区小结 by sfiction @Siunaus]

== 总结 ==


== 题解 ==

ABC 略去不表。

=== H. Guessing the Dice Roll [sfiction] ===

AC自动机建图后即为马尔可夫链，且无振荡，用高斯消元解或者矩阵快速幂拼精度。

比赛时高斯消元对应矩阵有误，转移矩阵不能有“流量”的泄露，可以给起始点加上常数1或者所有吸收态向起始点连权值为1边。

=== I. The Elder [sfiction] ===

树上斜率优化，将普通斜率优化所用单调栈可撤销化即可。O(nlogn)。

树分治后用根方向到重心路径更新其余点，可以做到O(nlogn^2^)，本质是将每个点的决策点拆分为log个凸包。

=== J. Query on a graph [sfiction] ===

设环上点深度为0，所有操作按k=0,1,2和depth分为6种，每种都可以拆分为常数个对同深度点的区间操作，用线段树或树状数组维护即可。

== 补题 ==

~~D~~FK~~L~~M
Run IdTimeProblemLanguageStatus
262AGNU C++Yes
1665BGNU C++Yes
41621CGNU C++Yes
51754EGNU C++No - Time Limit Exceeded
63583IGNU C++No - Time Limit Exceeded
67494IGNU C++Yes
720103EGNU C++No - Time Limit Exceeded
1035178HGNU C++No - Wrong Answer
1047181EGNU C++Yes
1070185HGNU C++Yes
1769290GGNU C++No - Wrong Answer
1904296JGNU C++Yes
1927297GGNU C++No - Wrong Answer
1949297GGNU C++No - Wrong Answer
1968298GGNU C++Yes

比赛链接:

流水账

2016 沈阳赛区小结 by sfiction @Siunaus

总结

题解

ABC 略去不表。

H. Guessing the Dice Roll [sfiction]

AC自动机建图后即为马尔可夫链，且无振荡，用高斯消元解或者矩阵快速幂拼精度。

比赛时高斯消元对应矩阵有误，转移矩阵不能有“流量”的泄露，可以给起始点加上常数1或者所有吸收态向起始点连权值为1边。

I. The Elder [sfiction]

树上斜率优化，将普通斜率优化所用单调栈可撤销化即可。O(nlogn)。

树分治后用根方向到重心路径更新其余点，可以做到O(nlogn2)，本质是将每个点的决策点拆分为log个凸包。

J. Query on a graph [sfiction]

设环上点深度为0，所有操作按k=0,1,2和depth分为6种，每种都可以拆分为常数个对同深度点的区间操作，用线段树或树状数组维护即可。

补题

DFKLM