【cf718X】Codeforces Round #373 (Div. 1)

2016年11月7日7700

A. Efim and Strange Grade

给一个长为n的小数,有t次操作,每次可以让小数点后的某一位向前四舍五入

问能最终能得到的最大的数

题解

考虑找到最前的一个大等于5的数字,从其开始考虑四舍五入

如果四舍五入到小数点,将小数点去掉

最后再处理一下整数位的进位问题

C. Sasha and Array

给定一个长度为n的数列an,有两种操作

1、将L到R的加上X

2、询问\(\sum_{L \leq i \leq R} F(a_i)\)

题解

考虑在线段树的每个结点维护一个斐波那契数列的转移矩阵
区间加法:就是将区间乘上v次的转移矩阵,标记下传同理
信息合并就是两个矩阵直接相加

D. Andrew and Chemistry

给定一棵树,每个结点的度数小等于4

要在树上加一个结点,加完后度数依然小于4

问有多少不同构的加法

\(1\leq n\leq 10^5\)

题解

树的同构有经典的哈希做法,我们设法通过预处理,快速求得『在每个结点上加上一个结点后,新树的哈希值』

在树形递推的时候加上记忆化,mp(x,y)表示y的子树x的哈希值

由于树的度数很小,可以直接把每个结点x的儿子的哈希值一起放在vector里排好序,再把vector放到map里编x的哈希值

E. Matvey’s Birthday

给一个长为n的字符串,两个位置有连边当它们相邻或为相同字母,边权都为1

求图的直径以及直径的数量

\(2\leq n\leq 10^5\)

题解

定义\(dis(i,c)\)为第i个位置到一个字符为c的位置的最短距离

定义\(d(c1,c2)\)为字符为c2的位置到字符为c2的位置的最短距离

以上枚举所有字母为起点广搜可得

(每个位置向【相邻位置】和【相邻位置】的字母连边,每个字母与【该字母的所有位置】连边)

我们发现两个位置的距离为

\(dis(i,j)=min(|i-j|,min\{dis(i,c)+1+dis(j,c)\})\)

注意到\(d(s_j,c)\leq dis(j,c)\leq d(s_j,c)+1\),而\(d(c1,c2)\)通过预处理求得

\(dis(j,c)\)就可以由一个8位二进制数加上\(s_j\)复原

也就是说,当我们枚举 i 来计算\(dis(i,j)\)的时候,对于小于\(i-15\)的 j,就只需用\(c(s,st)\)记录字母为s,状态为st的 j 的数量