2021-team06-C210818

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==

[[Image(210818-standing.png,800px)]]

== submission ==

[[Image(210818-submission.png,800px)]]


== 概述 ==

solved: 9/10  dirt: 30.77%

rank: 3



==  ==

== 总结 ==

whn:
被lxy带了，I和J一个概率期望题一个数据结构题都做的很稳，反而自己出了一些比较低级的错误
目前的专精安排： whn: 博弈&计算几何&斜率优化， lxy：数据结构&期望？ yja:字符串？


== 题解 ==

A: 联系wythoff游戏，打表意识到每个点只能转移到一个必败点，两重for循环枚举到sg值等于0的点就把能到他的点置1，O(n^2^)预处理即可

B: 若b>2r则Drop，否则Stuck，距离用初中几何知识计算即可

C: 线段树合并求出原树中最长上升子序列。提出这个子序列，以两端点为根各求出所有子树中最长上升子序列。显然删除的点必定在该子序列对应的链上，枚举这个点，易通过两端点求子树LIS的结果O(1)计算出删除该点的结果。复杂度O(nlogn)。

D：签到，预处理前缀和枚举每个位置即可。

E：bfs，0-3号管道和4-5号管道可以认为是一种，可以走一步转一步，对于每个格子从四个方向分别只会经过一次，搜索即可，输出方案需要手玩讨论。

F：签到，看似数位DP，其实三位数以上一定是答案，所以暴力一下两位数一位数的情况即可。

G：先考虑没有限制的情况，那么肯定是要让2n个数里面每一组都构成前一半和后一半的配对；接下来考虑交换一对的贡献，设ai,bi是两个属于小一半的数，aj,bj是两个属于大一半的数，则交换的收益是2*min(aj,bj)-2*max(ai,bi)。 对于这样的数对排序然后贪心即可。

H：命题等价于所有的两个数的差不能整除M。所以把原集合S的所有a构成一个生成函数，-a构成另一个生成函数，做一次FFT即可。需要设置一个偏移值来处理负系数。

I：考虑从后往前dp。设f[i][j]表示最后一个人选择了i（值为i），前一个人选择了j的情况下，到达终止状态的期望步数。设值为i的数在排列中的位置位pp[i]，转移方程为f[i][j]=(sum(f[k][i])/合法的k个数)+1,(k>i,pp[k]>pp[j])，可以对每一个i开一个树状数组维护，时间复杂度(n^2logn)(人下人复杂度)

J: 考虑线段树维护。对于每个wi，将所有j>i的uj和vj减去wi。最底层的节点记录该下标对应的u（记为val1）和下一个下标对应的v（记为val2）。对于操作0，若一个区间[l,r]合法，即能从l开到r+1，则对于任意i属于[l,r]皆满足ui<=任意vj，j属于[i+1,r+1]，可以在每个区间中维护，记为flag。对于操作2，开一个树状数组记录wi前缀和计算出减掉后u和v的值，单点修改。对于操作1，要求区间修改[i+1,n-1]的val1和[i,n-1]的val2，但修改区间的val1和val2时会对flag造成影响，这时注意到[i+1,n-1]的val1和val2修改值相等，对flag无影响，因此具体操作为在[i+1,n-1]同时修改val1和val2，再对[i,i]单点修改val2。时间复杂度O(nlogn)

[/wiki/2021-team6 返回]

Ranklist

submission

概述

solved: 9/10 dirt: 30.77%

rank: 3

总结

whn:

被lxy带了，I和J一个概率期望题一个数据结构题都做的很稳，反而自己出了一些比较低级的错误

目前的专精安排： whn: 博弈&计算几何&斜率优化， lxy：数据结构&期望？ yja:字符串？

题解

A: 联系wythoff游戏，打表意识到每个点只能转移到一个必败点，两重for循环枚举到sg值等于0的点就把能到他的点置1，O(n2)预处理即可

B: 若b>2r则Drop，否则Stuck，距离用初中几何知识计算即可

C: 线段树合并求出原树中最长上升子序列。提出这个子序列，以两端点为根各求出所有子树中最长上升子序列。显然删除的点必定在该子序列对应的链上，枚举这个点，易通过两端点求子树LIS的结果O(1)计算出删除该点的结果。复杂度O(nlogn)。

D：签到，预处理前缀和枚举每个位置即可。

E：bfs，0-3号管道和4-5号管道可以认为是一种，可以走一步转一步，对于每个格子从四个方向分别只会经过一次，搜索即可，输出方案需要手玩讨论。

F：签到，看似数位DP，其实三位数以上一定是答案，所以暴力一下两位数一位数的情况即可。

G：先考虑没有限制的情况，那么肯定是要让2n个数里面每一组都构成前一半和后一半的配对；接下来考虑交换一对的贡献，设ai,bi是两个属于小一半的数，aj,bj是两个属于大一半的数，则交换的收益是2*min(aj,bj)-2*max(ai,bi)。 对于这样的数对排序然后贪心即可。

H：命题等价于所有的两个数的差不能整除M。所以把原集合S的所有a构成一个生成函数，-a构成另一个生成函数，做一次FFT即可。需要设置一个偏移值来处理负系数。

I：考虑从后往前dp。设f[i][j]表示最后一个人选择了i（值为i），前一个人选择了j的情况下，到达终止状态的期望步数。设值为i的数在排列中的位置位pp[i]，转移方程为f[i][j]=(sum(f[k][i])/合法的k个数)+1,(k>i,pp[k]>pp[j])，可以对每一个i开一个树状数组维护，时间复杂度(n^2logn)(人下人复杂度)

J: 考虑线段树维护。对于每个wi，将所有j>i的uj和vj减去wi。最底层的节点记录该下标对应的u（记为val1）和下一个下标对应的v（记为val2）。对于操作0，若一个区间[l,r]合法，即能从l开到r+1，则对于任意i属于[l,r]皆满足ui<=任意vj，j属于[i+1,r+1]，可以在每个区间中维护，记为flag。对于操作2，开一个树状数组记录wi前缀和计算出减掉后u和v的值，单点修改。对于操作1，要求区间修改[i+1,n-1]的val1和[i,n-1]的val2，但修改区间的val1和val2时会对flag造成影响，这时注意到[i+1,n-1]的val1和val2修改值相等，对flag无影响，因此具体操作为在[i+1,n-1]同时修改val1和val2，再对[i,i]单点修改val2。时间复杂度O(nlogn)

附加文件