2021-team06-C210924

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==

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

== submission ==

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


== 概述 ==

solved: 6/12  dirt: 50%

rank: 54



==  ==

== 总结 ==

whn:
状态尚可，不过还有许多进步空间。
本场比较重大的失手点在于1：48后有两个小时没有提交，yja的G和lxy的J都在机上写但没能开出。决策上的失误主要是可能应该尽早让whn去做一个真的博弈题（而不是I这种只有壳的），yja去做C；能力上的不足还是在lxy的J（可能还有B？）上。


== 题解 ==

A: 求出生成函数\prod(x+a[i])以后计算答案即可，用一类分治NTT可以做两个Log复杂度。

B: 一个显然的做法是建出 T1,T2,⋯,Tn 的 AC 自动机，则题目相当于在 AC 自动机上随机游走，问走到叶结点之一的期望次数。设 E(x[i]) 表示从 AC 自动机上第 i 个点出发，期望多少次能走到一个叶结点。观察方程 E(x[u])=1+∑p[c]*E(x[next[u,c]])。（next[u,c] 表示从点 u 走 c 的转移边到的结点）中，next[u,c] 要么是 Trie 树上 u 的儿子，要么深度不超过 u 的深度。考虑树剖：对每个点 u 任选一个儿子 v 作为偏爱儿子进行树链剖分。那这个方程就可以看作把 v 用 u 的其他儿子和深度不超过 u 的深度的结点表示出来。那么我们发现经过代入，每个结点的答案都可以通过一些链顶结点的答案来表示。怎么做呢？我们按从浅到深的顺序来做。注意到对一个方程 E(x[u])=1+∑p[c]*E(x[next[u,c]])，它所涉及到的最深层的结点是 u 的全部儿子，而它们除了偏爱儿子 v 以外全是链顶结点。而对于所涉及到的深度不超过 u 的深度的结点，由于我们是按从浅到深的顺序，所以一定已经被表出，代入即可。由于叶子结点不超过 n 个，所以剖出链的个数 O(n)，未知数个数 O(n)，总时间复杂度 O(n3+n2mk+|R|)，可以通过。

C: 待yja补

D：签到，按题意模拟。遇到需要读行的情况最老实的办法还是getchar循环。

E：注意到W<=5的意义在于，会产生重叠的矩形的间隔距离最多为9.于是考虑dp[i][j][MASK]表示前i个位置，拍了j张照，第i-9到第i个位置是否被拍照的转移。预处理每个位置在前9个位置被取了mask后如果拍照可以多覆盖的面积，一共有n * (2^9^)种矩形面积和三角形面积并需要求，使用set维护每个坐标被覆盖的区间位置然后暴力计算即可（切记不要上界下界）；转移复杂度也是O(n^2^ 2^9^)的。 还需要注意小心分类讨论求矩形和梯形的面积并。

F：待yja写题解

G：单独考虑考虑一种数，显然前面所有的数都可以到最后一个数及从最后一个数出发的所有位置。因此对于每次询问，如果所问位置的数不是这种数最后一个位置，则先手必胜（对应的最后一个位置必败则去那，否则去最后一个位置能转移到的必败点即可），否则单独算一下sg值即可，算一次复杂度是O(256)的。

H：令ways[i][j]表示从(0,0)到(i,j),无视障碍点情况下的方案数，则如果能求出ways数组，剩下令f[i]表示从0出发到达第i个故障点且不经过其他故障点的方案数，那么f[i] = ways[x[i]][y[i]] - \sum(f[j] * ways[x[i]-x[j]][y[i]-y[j]])(x[i]>=x[j],y[i]>=y[j])。而求ways[i][j]，我们需要根据已知构造系数为所有从(0,0)到(i,j)的方案数G(x,y) = \sum a_ijx^i^y^j^，然后求1/(1-G)以获得G^0^+G^1^+...+G^n^的方案和。标程使用了高科技NTT求这一步，可当板子来用？

I：发现询问是一棵树，对于每个节点需要知道从树根到它的路径上所有数的答案，暴力转移是时空复杂度均(O(nmaxa))的。因此需要考虑轻重链DP，定义dp[i][j]表示经过i条轻边，得到异或值j的方案数，每次转移先枚举轻儿子，直接从dp[pos+1][i] = min(dp[pos][i],dp[pos][i xor a[v]]+w[v]]然后递归；再对重儿子转移一次并将dp[pos+1][i]更新到dp[pos][i]中即可。

J: 区间重复出现的颜色有一个经典做法，记pre[i]为上一个跟i颜色相同的位置，统计pre大于等于s的数目。操作一可以set维护，操作二考虑暴力分块，每一个块开一个优先队列维护pre值，复杂度是m（klog+根号n）。（其实可以线段树直接找下一个pre大于等于s）

K: 视情况补

L: 签到，对于每个排列正好有n!种序列，所以答案就是(n!)^2^/n^n^

[/wiki/2021-team6 返回]

Ranklist

submission

概述

solved: 6/12 dirt: 50%

rank: 54

总结

whn:

状态尚可，不过还有许多进步空间。

本场比较重大的失手点在于1：48后有两个小时没有提交，yja的G和lxy的J都在机上写但没能开出。决策上的失误主要是可能应该尽早让whn去做一个真的博弈题（而不是I这种只有壳的），yja去做C；能力上的不足还是在lxy的J（可能还有B？）上。

题解

A: 求出生成函数\prod(x+a[i])以后计算答案即可，用一类分治NTT可以做两个Log复杂度。

B: 一个显然的做法是建出 T1,T2,⋯,Tn 的 AC 自动机，则题目相当于在 AC 自动机上随机游走，问走到叶结点之一的期望次数。设 E(x[i]) 表示从 AC 自动机上第 i 个点出发，期望多少次能走到一个叶结点。观察方程 E(x[u])=1+∑p[c]*E(x[next[u,c]])。（next[u,c] 表示从点 u 走 c 的转移边到的结点）中，next[u,c] 要么是 Trie 树上 u 的儿子，要么深度不超过 u 的深度。考虑树剖：对每个点 u 任选一个儿子 v 作为偏爱儿子进行树链剖分。那这个方程就可以看作把 v 用 u 的其他儿子和深度不超过 u 的深度的结点表示出来。那么我们发现经过代入，每个结点的答案都可以通过一些链顶结点的答案来表示。怎么做呢？我们按从浅到深的顺序来做。注意到对一个方程 E(x[u])=1+∑p[c]*E(x[next[u,c]])，它所涉及到的最深层的结点是 u 的全部儿子，而它们除了偏爱儿子 v 以外全是链顶结点。而对于所涉及到的深度不超过 u 的深度的结点，由于我们是按从浅到深的顺序，所以一定已经被表出，代入即可。由于叶子结点不超过 n 个，所以剖出链的个数 O(n)，未知数个数 O(n)，总时间复杂度 O(n3+n2mk+|R|)，可以通过。

C: 待yja补

D：签到，按题意模拟。遇到需要读行的情况最老实的办法还是getchar循环。

E：注意到W<=5的意义在于，会产生重叠的矩形的间隔距离最多为9.于是考虑dp[i][j][MASK]表示前i个位置，拍了j张照，第i-9到第i个位置是否被拍照的转移。预处理每个位置在前9个位置被取了mask后如果拍照可以多覆盖的面积，一共有n * (29)种矩形面积和三角形面积并需要求，使用set维护每个坐标被覆盖的区间位置然后暴力计算即可（切记不要上界下界）；转移复杂度也是O(n2 29)的。 还需要注意小心分类讨论求矩形和梯形的面积并。

F：待yja写题解

G：单独考虑考虑一种数，显然前面所有的数都可以到最后一个数及从最后一个数出发的所有位置。因此对于每次询问，如果所问位置的数不是这种数最后一个位置，则先手必胜（对应的最后一个位置必败则去那，否则去最后一个位置能转移到的必败点即可），否则单独算一下sg值即可，算一次复杂度是O(256)的。

H：令ways[i][j]表示从(0,0)到(i,j),无视障碍点情况下的方案数，则如果能求出ways数组，剩下令f[i]表示从0出发到达第i个故障点且不经过其他故障点的方案数，那么f[i] = ways[x[i]][y[i]] - \sum(f[j] * ways[x[i]-x[j]][y[i]-y[j]])(x[i]>=x[j],y[i]>=y[j])。而求ways[i][j]，我们需要根据已知构造系数为所有从(0,0)到(i,j)的方案数G(x,y) = \sum a_ijxiyj，然后求1/(1-G)以获得G0+G1+...+Gn的方案和。标程使用了高科技NTT求这一步，可当板子来用？

I：发现询问是一棵树，对于每个节点需要知道从树根到它的路径上所有数的答案，暴力转移是时空复杂度均(O(nmaxa))的。因此需要考虑轻重链DP，定义dp[i][j]表示经过i条轻边，得到异或值j的方案数，每次转移先枚举轻儿子，直接从dp[pos+1][i] = min(dp[pos][i],dp[pos][i xor a[v]]+w[v]]然后递归；再对重儿子转移一次并将dp[pos+1][i]更新到dp[pos][i]中即可。

J: 区间重复出现的颜色有一个经典做法，记pre[i]为上一个跟i颜色相同的位置，统计pre大于等于s的数目。操作一可以set维护，操作二考虑暴力分块，每一个块开一个优先队列维护pre值，复杂度是m（klog+根号n）。（其实可以线段树直接找下一个pre大于等于s）

K: 视情况补

L: 签到，对于每个排列正好有n!种序列，所以答案就是(n!)2/nn

附加文件