2021-team06-C210812

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==

[[Image(210812-standings.png,800px)]]

== submission ==

[[Image(210812-submission4.png,800px)]]
[[Image(210812-submission3.png,800px)]]
[[Image(210812-submission2.png,800px)]]
[[Image(210812-submission1.png,800px)]]


== 概述 ==

solved: 8/11  dirt: 66.7%

rank: 6



==  ==

== 总结 ==

whn:
通过K题建立起了一定优势但没有抓住。
今天算是感觉自己不停的在救火。。。一方面，认真推K的时候也要提醒队友正确跟榜，另一方面，面对不太擅长的题目需要有队友负责去研究……


== 题解 ==

A: 考虑排名的贡献分成“最终得分的累计贡献”加上“个人因为提分收到的贡献”。 记录scorecnt(x)表示得x分的累计贡献，scorerank(x)表示得x分目前的排名，则当一个得x分的人在第i轮提升了一分以后，
scorerank(x)++,scorecnt(x)+=(w(轮数)-i+1),而这个人得分需要加上之前没变成x+1分排名的差值，记(scorecnt(x+1)-scorerank(x+1)*(w-i+1))-(scorecnt(x)-scorerank(x)*(w-i+1))。最后结合两部分贡献输出答案即可。

B: 抄来的标程做法：

假如不需要维持avl，那么一定是沿着先序遍历选下去最好。所以按照先序遍历顺序枚举能否取每个位置。

又发现深度为d的avl树节点个数，在确定了哪些节点需要存在，哪些节点已经填放进去以后也是有下限的。

记f[x][i]表示根为x，节点深度为i的子树最少需要几个节点，has(x)表示节点x需要存在，got(x)表示节点x已经被取用（两者区别在于是否要被算进f里面去，如果只是需要存在但暂时还没填，那就不应该使它阻止顺序在它之前的转移过来），

每遍历一个节点后，对其所有的祖先按顺序结算；f[x][0]在has(x)==1时为INF（不存在），否则为0，其他f[x][i] 可以从f[ls][i-1]+f[rs][i-1]+!got(x),f[ls][i-1]+f[rs][i-2]+!got(x),f[ls][i-2]+f[rs][i-1]+!got(x)三种情况转移过来。遍历完以后如果至少有一个f[root][i]<m，表示节点可以插入，否则不可，再将has[x]和f[x]退回原样。

时间复杂度为带2倍左右常数的nlogn.

C：简单贪心题，似乎数据范围还开小了。

D：推式子发现cv绑定才有用，先计算出行走恰好k条边时边权意义的最短路，然后发现令k=边数，b=边权和，则y=kx+b有一段露在其他直线的外面表示它可以被用。想办法维护一下计算即可。yja WA8，待补。

E：模拟，以后尽量能花整数就化整数避免恶心数据。

F：模拟。。

G：距离i的位置对其后k个位置产生贡献当且仅当第i到第i+k-1个位置都被ban而第k个未被ban，推组合数以后求和算一下所有的贡献即可。

H：显然最优方案一定有一个端点开在整数坐标上，考虑二分答案，枚举每个整数端点看对应长度的线段斜率是否符合要求即可。实战在设定边界的时候白给了。

I：签到，排一边序后找出排序以后的数组和原数组最先和最后的不同的位置并翻转，看这样行不行即可。

J：离散化后从小到大枚举要花多少代价用于+1-1，然后对于只能删除的点需要扫一遍看一下需要删除几个。其他队表示可以使用链表或者线段树维护实现O(1)或者O(log)一次看出要多删多少个，待补。

K：和winter2021加油问题类似的题目，核心都是在贪心考虑怎么走可以覆盖所有最优决策并在此基础上设计转移。实战中设计的转移如下：

dp(x)表示位于位置x到达重点需要的答案。对x先求出jump表示下一步跳到的位置（d格后或者某个岛屿的左端点），id为下一个岛屿的编号

①前面有很多大空地：如果当前位置和下一个岛屿间隔2跳以上的距离，则贪心的直接跳到间隔2跳以内的地方.位置加d*倍数，时间也直接加min(d,t)*倍数。

②离一些岛屿间隔1跳以上2跳以下的距离，可以走一些距离然后跳一步到某个岛的右端点。需要枚举所有的右端点因为可能跳过若干个岛。位置变成右端点，时间加距离差+一步。

③一步可以越过某些岛，则向前跳一步。位置到达jump，时间加上跳一步的距离。
④如果已经到达终点，可以直接走过去。

[/wiki/2021-team6 返回]

Ranklist

submission

概述

solved: 8/11 dirt: 66.7%

rank: 6

总结

whn:

通过K题建立起了一定优势但没有抓住。

今天算是感觉自己不停的在救火。。。一方面，认真推K的时候也要提醒队友正确跟榜，另一方面，面对不太擅长的题目需要有队友负责去研究……

题解

A: 考虑排名的贡献分成“最终得分的累计贡献”加上“个人因为提分收到的贡献”。 记录scorecnt(x)表示得x分的累计贡献，scorerank(x)表示得x分目前的排名，则当一个得x分的人在第i轮提升了一分以后，

scorerank(x)++,scorecnt(x)+=(w(轮数)-i+1),而这个人得分需要加上之前没变成x+1分排名的差值，记(scorecnt(x+1)-scorerank(x+1)*(w-i+1))-(scorecnt(x)-scorerank(x)*(w-i+1))。最后结合两部分贡献输出答案即可。

B: 抄来的标程做法：

假如不需要维持avl，那么一定是沿着先序遍历选下去最好。所以按照先序遍历顺序枚举能否取每个位置。

又发现深度为d的avl树节点个数，在确定了哪些节点需要存在，哪些节点已经填放进去以后也是有下限的。

记f[x][i]表示根为x，节点深度为i的子树最少需要几个节点，has(x)表示节点x需要存在，got(x)表示节点x已经被取用（两者区别在于是否要被算进f里面去，如果只是需要存在但暂时还没填，那就不应该使它阻止顺序在它之前的转移过来），

每遍历一个节点后，对其所有的祖先按顺序结算；f[x][0]在has(x)==1时为INF（不存在），否则为0，其他f[x][i] 可以从f[ls][i-1]+f[rs][i-1]+!got(x),f[ls][i-1]+f[rs][i-2]+!got(x),f[ls][i-2]+f[rs][i-1]+!got(x)三种情况转移过来。遍历完以后如果至少有一个f[root][i]

时间复杂度为带2倍左右常数的nlogn.

C：简单贪心题，似乎数据范围还开小了。

D：推式子发现cv绑定才有用，先计算出行走恰好k条边时边权意义的最短路，然后发现令k=边数，b=边权和，则y=kx+b有一段露在其他直线的外面表示它可以被用。想办法维护一下计算即可。yja WA8，待补。

E：模拟，以后尽量能花整数就化整数避免恶心数据。

F：模拟。。

G：距离i的位置对其后k个位置产生贡献当且仅当第i到第i+k-1个位置都被ban而第k个未被ban，推组合数以后求和算一下所有的贡献即可。

H：显然最优方案一定有一个端点开在整数坐标上，考虑二分答案，枚举每个整数端点看对应长度的线段斜率是否符合要求即可。实战在设定边界的时候白给了。

I：签到，排一边序后找出排序以后的数组和原数组最先和最后的不同的位置并翻转，看这样行不行即可。

J：离散化后从小到大枚举要花多少代价用于+1-1，然后对于只能删除的点需要扫一遍看一下需要删除几个。其他队表示可以使用链表或者线段树维护实现O(1)或者O(log)一次看出要多删多少个，待补。

K：和winter2021加油问题类似的题目，核心都是在贪心考虑怎么走可以覆盖所有最优决策并在此基础上设计转移。实战中设计的转移如下：

dp(x)表示位于位置x到达重点需要的答案。对x先求出jump表示下一步跳到的位置（d格后或者某个岛屿的左端点），id为下一个岛屿的编号

①前面有很多大空地：如果当前位置和下一个岛屿间隔2跳以上的距离，则贪心的直接跳到间隔2跳以内的地方.位置加d*倍数，时间也直接加min(d,t)*倍数。

②离一些岛屿间隔1跳以上2跳以下的距离，可以走一些距离然后跳一步到某个岛的右端点。需要枚举所有的右端点因为可能跳过若干个岛。位置变成右端点，时间加距离差+一步。

③一步可以越过某些岛，则向前跳一步。位置到达jump，时间加上跳一步的距离。

④如果已经到达终点，可以直接走过去。

附加文件