NanoApe's Blog

既是咸鱼又是辣鸡

【Plan M】51Nod Marathon

NanoApe posted @ 2016年5月31日 21:30 in 蒟蒻不做题提前退役 , 293 阅读

国家队爷的竞(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 非波那契树


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter