2019-team666-0044

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]

== 概述 ==

solved:7/11 645  dirt:46% 

rank:44/133

[[Image(Standings.jpg,800px)]]



== 流水账 ==

前40分钟光速过了C、D、K、L、M。之后三人轮流想A、E、F、J四个题，机位空的时候tjc试了一下F的15个贪心取最优，竟然过了，'''F1y167'''. 2小时左右hyw和yyc讨论出了A，后来交了一次wa了，经过多次修改后hyw征询了一下tjc的意见，tjc发现yyc的题意转化有误，得到正确题意后众人想到了一个很容易的fix，fix之后'''A5y205'''。最后tjc给出了J的状态定义方法，hyw推完转移方程上机，没有调完，赛后5分钟才过。yyc想E无果。

== 总结 ==

=== yyc ===

=== tjc  ===

=== hyw  ===

这个E想不出来真的不应该啊……

J这个状态的定义以前应该是碰过的啊。orz得好好提升一下个人实力了。

=== 题解 ===

A：去掉那些在该位置之前有比它大的数的点，得到一个单调不减的序列。考虑题意相当于有若干个点(nx[i],b[i])，其中nx[i]是i之前有多少个合法的点，查询为选一个点，满足这个点与最后一个点组成的向量和查询的向量叉积最大。考虑以i开始的后缀的这个值就是f(最后一个点)-f(i)，那么只要找到f的最小值就行了，维护一个下凸包在上面三分即可。

B：

C：三分圆心取半径最小

D：把图黑白染色，求黑格与白格的较小值

E：线段树，每次转移相当于一堆区间的dp值的求和，维护区间出现次数最少的数出现的次数，如果变为0，需要将这个区间删除，并加上一个区间，由于区间总数只有2000所以复杂度是对的。维护的时候顺带维护区间里dp值的和。

F：15次贪心取最优乱搞@tjc

G：

H：

I：

J：首先可以将所有路径的上端点下移一格，这样就变成有若干个区间，每个区间里至少要有一条边和它父亲的那条边颜色不同，我们称这样的边为被标记的边。设dp[i][j]表示当前考虑第i个点，以i的子树里的点为区间下端点的区间
、且内部还没有已经被标记的边、这样的区间的上端点的深度最大为j时，有多少种方案数。dp[i][0]表示不存在这样的区间时的方案数，即以i的子树里的点为区间下端点的区间内部至少有一条边被标记了。转移有一些细节要注意，dp[i][0]的转移需要分开考虑。

K、L、M：签到

[/wiki/2019-team666 返回]

概述

solved:7/11 645 dirt:46%

rank:44/133

流水账

前40分钟光速过了C、D、K、L、M。之后三人轮流想A、E、F、J四个题，机位空的时候tjc试了一下F的15个贪心取最优，竟然过了，F1y167. 2小时左右hyw和yyc讨论出了A，后来交了一次wa了，经过多次修改后hyw征询了一下tjc的意见，tjc发现yyc的题意转化有误，得到正确题意后众人想到了一个很容易的fix，fix之后A5y205。最后tjc给出了J的状态定义方法，hyw推完转移方程上机，没有调完，赛后5分钟才过。yyc想E无果。

总结

yyc

tjc

hyw

这个E想不出来真的不应该啊……

J这个状态的定义以前应该是碰过的啊。orz得好好提升一下个人实力了。

题解

A：去掉那些在该位置之前有比它大的数的点，得到一个单调不减的序列。考虑题意相当于有若干个点(nx[i],b[i])，其中nx[i]是i之前有多少个合法的点，查询为选一个点，满足这个点与最后一个点组成的向量和查询的向量叉积最大。考虑以i开始的后缀的这个值就是f(最后一个点)-f(i)，那么只要找到f的最小值就行了，维护一个下凸包在上面三分即可。

B：

C：三分圆心取半径最小

D：把图黑白染色，求黑格与白格的较小值

E：线段树，每次转移相当于一堆区间的dp值的求和，维护区间出现次数最少的数出现的次数，如果变为0，需要将这个区间删除，并加上一个区间，由于区间总数只有2000所以复杂度是对的。维护的时候顺带维护区间里dp值的和。

F：15次贪心取最优乱搞@tjc

G：

H：

I：

J：首先可以将所有路径的上端点下移一格，这样就变成有若干个区间，每个区间里至少要有一条边和它父亲的那条边颜色不同，我们称这样的边为被标记的边。设dp[i][j]表示当前考虑第i个点，以i的子树里的点为区间下端点的区间

、且内部还没有已经被标记的边、这样的区间的上端点的深度最大为j时，有多少种方案数。dp[i][0]表示不存在这样的区间时的方案数，即以i的子树里的点为区间下端点的区间内部至少有一条边被标记了。转移有一些细节要注意，dp[i][0]的转移需要分开考虑。

K、L、M：签到

附加文件