国家队爷的竞（na）技（qian）平台

update:16.07.08

51Nod Marathon 9

A 打怪兽

维护打败怪个数+当前方案数+可选个数，然后推一遍

B 中国好区间

把每种数归类为$\ge T$和$<T$，然后枚举结尾位置求方案数

★C 连通率

一棵树，每个点有$\frac{1}{2}$的概率毁坏，求期望相连点对数

树DP，每个数原先为$1$，往上移动统计时乘上$\frac{1}{2}$，这个逆元可以做到，最后再乘上方案数$2^n$

D B君的梦境

求用1*1*1*2填满2*2*3*n的方案数（四维）

将前三维压成一个状态，然后可以矩阵连乘；但是状态数为4096，通过三维旋转去重，再去掉不可能到达的状态，减少到96

△E 赫拉迪克之杖

F 棋盘游戏

给一个黑白棋盘和四种操作，问能否使得棋盘变成全白

试着缩小局面，会发现四种操作可以让一个n*m的棋盘变成3*3

然后由实践（爆搜）可得当n和m都小于4时有16种局面能恢复纯白，其余的n和m有32种（前面16种和其取反）

51Nod Marathon 10

A 树的距离之和

对于一棵无根树中每个点，求所有节点到其的距离之和

树DP一遍

B 公共祖先

给两棵树，n个点，定义$F(a,b)$表示点a与点b在两棵树上的公共祖先的交集的大小，求$\sum F(a,b)$

首先，一个点所做贡献，等于其在两棵树所截的子树的交集大小所包含的对数

然后一棵树（A）求dfs序，一棵树（B）跑dfs，然后对于某个点的B子树全部打标记，然后区间询问其A子树有多少打了标记，就得到了子树交集大小

C 子集价值

一个计算得到的值$x$对答案的贡献是$x^2$，我们把它拆开，会发现只要在单二进制位的分解上多加个两个相邻位的分解，还是能分解完单独算贡献的

D 锁屏密码

锁屏密码求方案数

$n=1$时方案数为$2^(m-1)$

$n>1$时可以发现任选三点共线的概率不是很大，答案大概是(n*m)!的级别，由于答案小于2^63，可知总点数最大在20左右（逗我呢

然后就可以状压了

△E 联通？联通！

△F Tree and Permutation

51Nod Marathon 15

A B君的游戏

SG 函数只与 1 的个数有关，暴力打表 SG 即可

B 完美消除

数位 DP，设状态为 $F(i,S,k)$ 表示此时 i 位波动状态为 S 需要 k 次删除的方案数

C lyk与gcd

莫比乌斯反演一发

D LIS Counting

搜索，状态消去无用信息然后去重

E Danganronpa

搞出AC自动机，然后操作相当于每次给 Fail 子树的每个点在原树中的每个儿子 +1 然后单点查询

拆成每次给 Fail 子树的每个点 +1，询问每次找原树到根的路径和

前半部分弄 dfs 序，后半部分弄括号序列，用 KDtree 维护

△F 非波那契树

51Nod Marathon 14

A 棋盘问题

我们会发现每次操作只能修改奇数个1，所以变成奇偶性问题了

B 约数和

卡常数差评

由于数据随机，所以可以直接暴力维护b数组，均摊 $O(nlogn)$

（当然枚举约数的姿势要够好，例如预处理出所有数的质因数，然后就可以用个队列快速求得所有约数）

C 平均数

二分答案，然后将序列差分，那么就转成求区间和为负的个数，我们可以用个权值线段树或者树状数组解决，复杂度 $O(nlog^2n)$

（注意前缀0的存在）

D 小Q的家庭作业

首先证明一发 $G(x)=x*约数个数$ 然后就变成分解质因数了

△待填坑

△E Gcd and Lcm

△F 非波那契树