【Nov+Dec】Problem
NanoApe
posted @ 2015年11月17日 18:27
in 蒟蒻不比赛何来学费
, 341 阅读
NOIP考了595，期中考上升了200+名次，预计此月人品即将跌落谷底
完成度：
3/7
[BestCoder 62 Div.1 D]
★给定一棵树，N个节点，每个节点上有一个字符串。M次询问，每次询问给定两点和字符串S，求两点间路径上字符串为S子串的节点最长长度
先树链剖分，得到dfs序；然后对所有name建立AC自动机。对于自动机上的每一个结点，建立一个可持久化线段树$T(x)=T(fail(x))+w(x)$。T(x)对应的是dfs序，维护的是的maxlen。每一次查询一个串，我们只需要将这个串在自动机经过的点中查询主席树中对应的树剖区间即可。复杂度$O(|S|log^2n)$
[BestCoder 63 Div.1 C]
有n个球，共有m种颜色，第i个球的颜色为j的概率已知。对于第i种颜色，若有x个球，对答案的贡献为$x^2$。问答案的期望。
突破口：$x^2$的贡献可以看成是两球颜色相同的对数。然后就计算两两球之间颜色相同的概率。
[BestCoder 66 Div.1 B]
设$f(x)=\sum_{k=0}^x (-1)^k 2^{2x-2k} C_{2x-k+1}^k,f_0(x)=f(x),f_n(x)=f(f_{n-1}(x))(n \ge 1)$
求$\phi(f_n(x))$
这题假如放在比赛来给你打，就是让你打表找规律。。。
求证：$f_n(x)=n+x+1$
证明：见BC官方题解
[BestCoder 63 Div.1 D]
[BestCoder 66 Div.1 D]
[CF 609F]
[TC SRM 667 Div.1 A]
[TC SRM 667 Div.1 B]
评论 (0)
NanoApe
ENE>.<~
计数器
152787
分类
搜索
听听看？
最新留言
最新评论
链接
RSS
