2020-team12-034

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(2021-W8standing.png, 1000px)]]
[[Image(2020-W8standing.2.png, 1000px)]]




== 问题 ==

D题由于交流问题未能完成。 队伍的计数能力有待提高，

== 题解 == 

A:签到。

B:核心是发现由于密率=355/113,所以710非常接近是2pi的113倍，在找一个很接近-1/2pi的数然后每次跳710即可。 如果发现不了可以打表发现。

C:“存在特殊条件会大幅简化题目”的系列。由于十字一定8联通且边可以来回走，发现画一条斜接着画一条竖是最优的，且从十字的一划到另一划可以走竖也可以走横，因此考虑只走树和横，发现这样建图可以直接得到一个“全都是偶点的需要一笔画的图”。于是就这样建好图跑一个欧拉回路即可。
注意输出方案是先dfs(v,u)再ans.pb(u)， 先pb(v)在dfs(v,u)会莫名wa.

D:核心：如果一个双回文串存在多个分割，那么它只能是双回文串循环而成(将双回文串表示为AB后不难证明）。因此一开始可以简单用f[i] = (j=0到i-1)f[j]*f[i-j]算出简单拼凑而成的双回文串，然后令g[i]表示双回文且不可分割的数目，那么一个长为i的双回文串会对f[i*j]贡献j次（例：ababab生成(1,5)(3,3)(5,1)三种分割，abaabaaba生成(0,9),(3,6),(6,3)三种分割），容斥掉即可。这样最后每个i对答案的贡献是g[i]*(n/i)。

E: 签到；先枚举一个点到另外所有点的路，取最长路（否则会lca)，就可以找出可能中点然后验证即可。

F: PHP？

G: 不会打高尔夫

H: ctc，根据调和级数性质，

I: 二分，把区间

J: 数位dp，已知前面位数和为k，则后面一个数对f(x)的贡献可以直接算，且对x的贡献也可以预处理10的幂直接算；dp[i][0/1][j][k]维护做到第i位，前面数和为j，f(x)与x模意义下的差值k即可。
由于不知道longlong和int差4倍常数考场上磨了一年。

K: ctc

L：转化成lcp(i,j)/(i-j)+1， 

M：签到，ctc

[/wiki/2020-team12 返回]

问题

D题由于交流问题未能完成。 队伍的计数能力有待提高，

题解

A:签到。

B:核心是发现由于密率=355/113,所以710非常接近是2pi的113倍，在找一个很接近-1/2pi的数然后每次跳710即可。 如果发现不了可以打表发现。

C:“存在特殊条件会大幅简化题目”的系列。由于十字一定8联通且边可以来回走，发现画一条斜接着画一条竖是最优的，且从十字的一划到另一划可以走竖也可以走横，因此考虑只走树和横，发现这样建图可以直接得到一个“全都是偶点的需要一笔画的图”。于是就这样建好图跑一个欧拉回路即可。

注意输出方案是先dfs(v,u)再ans.pb(u)， 先pb(v)在dfs(v,u)会莫名wa.

D:核心：如果一个双回文串存在多个分割，那么它只能是双回文串循环而成(将双回文串表示为AB后不难证明）。因此一开始可以简单用f[i] = (j=0到i-1)f[j]*f[i-j]算出简单拼凑而成的双回文串，然后令g[i]表示双回文且不可分割的数目，那么一个长为i的双回文串会对f[i*j]贡献j次（例：ababab生成(1,5)(3,3)(5,1)三种分割，abaabaaba生成(0,9),(3,6),(6,3)三种分割），容斥掉即可。这样最后每个i对答案的贡献是g[i]*(n/i)。

E: 签到；先枚举一个点到另外所有点的路，取最长路（否则会lca)，就可以找出可能中点然后验证即可。

F: PHP？

G: 不会打高尔夫

H: ctc，根据调和级数性质，

I: 二分，把区间

J: 数位dp，已知前面位数和为k，则后面一个数对f(x)的贡献可以直接算，且对x的贡献也可以预处理10的幂直接算；dp[i][0/1][j][k]维护做到第i位，前面数和为j，f(x)与x模意义下的差值k即可。

由于不知道longlong和int差4倍常数考场上磨了一年。

K: ctc

L：转化成lcp(i,j)/(i-j)+1，

M：签到，ctc

附加文件