憕

题解

/ 注册

全部文章 / 题解（共4篇）

题解 | #D明七暗七数位dp+二分#

D 明七暗七 +数位dp+二分转变一下题意可以变为求区间内所有满足含有7或者是7的倍数的数，第一个条件数位dp容易枚举，第二个条件需要记录好每位数对7取模的余数，如果余数为0即为倍数。如14，第一位数位10，对7取模的余数维3，第二位为4对7取模余数为4，两者之和对7取模余数为0，故为7的倍数。故...

二分查找记忆化搜索

2022-11-16

1 519

题解 | #I题给给#

线性期望dp 因为是求最终被染色的节点数，对于每个节点分开考虑如果第i个节点被在k次操作里染色的概率为p，则它的对期望的贡献为 pi*1；所以总的期望E = 所有节点被选的的概率之和。对于第i个节点被选的概率不好求，但是可以求它的对立事件，在k次操作里面都不被选的概率q，所以p = 1-q；一次...

2022-11-10

1 377

题解 | #勘测#

H-游戏矩阵快速幂考点是邻接矩阵的n次方的意义考虑矩阵乘法的定义：令 C=A×B C=A×B Cij=∑k=1nAik×Bkj Cij=∑k=1nAik×Bkj 那么 A2ij=∑k=1nAik×Akj Aij2=∑k=1nAik×Akj 邻接矩阵A中的元素都是用0,1来表示是否联通的，或者...

C++ 矩阵位运算

2022-11-08

3 362

题解 | #点权#

//对于每个节点来说它的最小消费肯定是以他文根节点，所有子节点传递过来的最小的两个；如果每个节点都跑一遍树形dp是O（n方）会t；我们先固定一个根节点跑一遍dfs，确定它的最小消费；然后对于剩下的节点，他们的消费已经是除根结点外的所有子节点的最小消费，因此，我们只是需要判断根节点更新它需要的...

深度优先搜索

2022-03-20

2 508