2020-team12-026

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(2021-W5standings.png, 1000px)]]
[[Image(2021-W5status.png, 1000px)]]

==  ==

szb一人带飞狂砍5+1（赛后）题场。

== 题解 == 

A:核心是FWT..

B:较难计数dp.
考虑先用dp[x][y]表示长为x，元素为1-y的完美序列数。

直接统计很难，考虑求出不完美序列然后容斥；又发现每个不完美序列需要记录最远的那个位置来分类。

记t为最后一个满足prefix_max(i) = suffix_min(i+1)的位置，发现：① suffix(i+1)是完美序列；②后半段需要>=前半段。 因此，后半段由m到y组成的完美序列，前半段由1-m组成的任意序列，且两段均至少有一个m.

于是对于枚举的t和m,对应的方案数是([x-t][y-(m-1)]-[x-t][y-m])*(m^t-(m-1)^t).

之后进行两轮计算：第一轮dp[x][y] - sum(t=1..y-1) dp[x][y-1]*C(y,t)以算出长为x，正好有y个元素的方案数；然后再统计ans = sum(y=1..x) dp[x][y]*C(k,y)。

为了将复杂度优化到O(n^3)^， 需要拆开上面方案数的式子为四项，观察到m^t^=m^x^*m^(t-x)^，于是进行前缀和优化：（以第一项为例）presum[y][m] = sum(i=1..x-1)f[i][y-(m-1)]*m^t^，直接从前往后加可以不需要记录i，但是需要记录y和m两个字母。


难点：①想到不需要k的状态

 ②想到dp[x][y]表示离散化的y个数是可以由dp[x][y]表示1-y任意取推算出来的。（瓶颈，因为如果停留在离散化的状态就不可能有比大小）

 ③ 大胆往容斥方向想，并想到可以绕回去。

 ④ 正确推出猎奇的前缀和。

C:数位dp或找规律。必须导致做。

D:简单题。

E:先拆位，然后whn想着前缀后缀后卡死了...正解是讨论：先把各种&起来=1的地方处理掉，然后一个一个处理0区间，对所有区间是否有交进行分类讨论。

F:分治后处理合并'['和']'的情况。先预处理每个位置向四个方向延伸的距离，然后两重枚举上边界i和下边界j，每个i边界上，做一个区间加【i,下边界】，到j边界时要做一个单点查询，按照延伸的长度排序以后离线处理。
细节1：注意分治是要横竖分治，在横向长时左右分，竖向长时上下分。。
细节2：区间加清理树状数组时注意不能直接for(i,l,r) c[i]=0，这样修改时大于r的那些i+lowbit(i)的位置会无法清空。


G:签到

H:重点是观察式子，消去三次项并找到合适的路线：在y=x线上或线下都是一个L，接近中间爬阶梯。

I: 签到

J: 签到

K: 猎奇

L：大坑，难读题+无解题，题解一页半的论文题。没什么意思

M：签到。

N：本质是建树的分治：考虑一个区间的最大值（之一）肯定会杀掉所有区间，然后按照区间左右分治找区间的最大值，其必须满足杀完左/右半区间的人后大于区间最大值，且杀完整个区间以后要大于上一层的最大值。（看似要一层层合并实际上只要两层就够了，其实很类似于笛卡尔树）

[/wiki/2020-team12 返回]

szb一人带飞狂砍5+1（赛后）题场。

题解

A:核心是FWT..

B:较难计数dp.

考虑先用dp[x][y]表示长为x，元素为1-y的完美序列数。

直接统计很难，考虑求出不完美序列然后容斥；又发现每个不完美序列需要记录最远的那个位置来分类。

记t为最后一个满足prefix_max(i) = suffix_min(i+1)的位置，发现：① suffix(i+1)是完美序列；②后半段需要>=前半段。 因此，后半段由m到y组成的完美序列，前半段由1-m组成的任意序列，且两段均至少有一个m.

于是对于枚举的t和m,对应的方案数是([x-t][y-(m-1)]-[x-t][y-m])*(mt-(m-1)t).

之后进行两轮计算：第一轮dp[x][y] - sum(t=1..y-1) dp[x][y-1]*C(y,t)以算出长为x，正好有y个元素的方案数；然后再统计ans = sum(y=1..x) dp[x][y]*C(k,y)。

为了将复杂度优化到O(n3)， 需要拆开上面方案数的式子为四项，观察到mt=mx*m(t-x)，于是进行前缀和优化：（以第一项为例）presum[y][m] = sum(i=1..x-1)f[i][y-(m-1)]*mt，直接从前往后加可以不需要记录i，但是需要记录y和m两个字母。

难点：①想到不需要k的状态

②想到dp[x][y]表示离散化的y个数是可以由dp[x][y]表示1-y任意取推算出来的。（瓶颈，因为如果停留在离散化的状态就不可能有比大小）

③ 大胆往容斥方向想，并想到可以绕回去。

④ 正确推出猎奇的前缀和。

C:数位dp或找规律。必须导致做。

D:简单题。

E:先拆位，然后whn想着前缀后缀后卡死了...正解是讨论：先把各种&起来=1的地方处理掉，然后一个一个处理0区间，对所有区间是否有交进行分类讨论。

F:分治后处理合并'['和']'的情况。先预处理每个位置向四个方向延伸的距离，然后两重枚举上边界i和下边界j，每个i边界上，做一个区间加【i,下边界】，到j边界时要做一个单点查询，按照延伸的长度排序以后离线处理。

细节1：注意分治是要横竖分治，在横向长时左右分，竖向长时上下分。。

细节2：区间加清理树状数组时注意不能直接for(i,l,r) c[i]=0，这样修改时大于r的那些i+lowbit(i)的位置会无法清空。

G:签到

H:重点是观察式子，消去三次项并找到合适的路线：在y=x线上或线下都是一个L，接近中间爬阶梯。

I: 签到

J: 签到

K: 猎奇

L：大坑，难读题+无解题，题解一页半的论文题。没什么意思

M：签到。

N：本质是建树的分治：考虑一个区间的最大值（之一）肯定会杀掉所有区间，然后按照区间左右分治找区间的最大值，其必须满足杀完左/右半区间的人后大于区间最大值，且杀完整个区间以后要大于上一层的最大值。（看似要一层层合并实际上只要两层就够了，其实很类似于笛卡尔树）

附加文件