hihoCoder #27
2024-09-05 02:11:02
A
QvQ
B
题目：http://hihocoder.com/problemset/problem/1470
分析：dfs序+栈+数学
可以发现，对于每组询问，树上是有很多点都只能等于0的
对于每个节点求出dfs序得到进来的时间和出去的时间
对于询问的限制，可以用括号序列表示：((()()))()()
然后根据各种情况讨论结果
唯一需要计算的是两颗子树，大小分别为n,m，求C(n,0)*C(m,0)+C(n,1)*C(n,m)+....+C(n,n)*C(n,m)
这个实际上等于C(n+m,m)，因为对于n中有i个1，m中有i个1的情况，如果把m中的颜色全部取反，那么总共就有m个1，问题等价于从(n+m)中取出m个作为1，其它作为0
C
题目：http://hihocoder.com/problemset/problem/1470
分析：树形dp
很套路的树形dp
套路在状态表示里没有那个限制要求k
f(uxi)表示以u为根的子树，有x条路线向u的上方延伸的答案数
对于从儿子v上来的路线，有三种可能：两条线在u点汇聚成一条、直接在u点结束、继续沿着u上去
在不断合并子树的过程中：
f(u,i+j-k)+=f(u,i)*f(v,j)*C(i,k)*C(j,k)*k!(i、j分别表示伸上来的路线数，k表示各取k条合并成一条线路）
注意每条边只能被经过<=k次
所以对于每个u，f(u,x)(x>k)都是0
D
不会啊TAT
最新文章
- 如何同时打开两个excel
- 实现tableview的下拉刷新
- 参数化命令相关知识点之==================防止SQl的注入
- MySQL外键使用需要注意的几点
- php ceil() 函数向上舍入为最接近的整数。
- HTML5 – 1.基础
- SQL数据类型大全 《转自网络》
- jfinal的ajax例子
- 问题解决：引入com.sun.management.OperatingSystemMXBean 出错
- 如何将可执行文件打包至APK并运行（转）
- 《wc》-linux命令五分钟系列之十七
- Linux 环境下 Lua 安装(转)
- Angular2 Service实践
- 利用UiWatchers 监听解决安卓自动化各种自动化各种非期待弹窗，弹层，升级，广告，对话框，来电等问题
- 记OI退役
- gdb调试动态链接so
- Jfinal集成Spring
- 初始if..else 条件语句
- eclipse中ant打war包
- C语言中二维字符数组的定义和初始化