主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
abc243做题笔记
最后更新于 2025-07-31 14:56:46
作者
EasonTao
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
## **前言** $at$终于上黄啦！ 希望下周不要掉回来。 ## **C** 先对坐标排序，再检查有没有同一行内先出现R再出现L。 ## **D** 刚开始看到题时，我想：“欸？这题不直接模拟就好了嘛！” 然后， ### **WA**! 我一看,这题目只保证答案在 $long$ $long$ 范围内，没保证过程中不溢出。又发现，$U$和$L,R$是可以抵消的，这样就不会溢出了。 ## **E** 我们可以发现，如果一条边不能删，当且仅当删了这条边后这条边的两个端点之间的距离变了。否则一定能删。 因为其他经过这两个点的路径也可以走这两点间的最短路而不走这条边。 用 $floyd$ 处理出最短路和有没有多条路径就行了。 ## **F** 这道题考虑 $dp$ 。 我们令 $dp(i,j,k)$ 表示目前考虑到第 $i$ 种奖品，抽到 $j$ 个不同的奖品，一共抽了 $k$ 个奖品的概率。 答案是 $dp(N,M,K)$ 。 考虑插板转移。 枚举当前这个奖品抽到多少个。 如果抽到0个，那么转移方程就是： $$ dp(i,j,k) \rightarrow dp(i+1,j,k) $$ 如果抽到d个，那么转移方程是： $$ \dbinom{k+d}{d} \times dp(i,j,k)\times \frac{{w_i}^d}{(\sum w)^d} \rightarrow dp(i+1,j+1,k+d) $$ ## **G** 我们先预处理出一个 $dp$ 数组和其前缀和，只要预处理 $10^5 $ 位。 $dp_i$ 表示当 $x=i$ 时有多少序列。 有一个十分重要的性质，就是当 $\sqrt x =\sqrt y$（都下取整） 时，$x$ 与 $y$ 的方案数相同。这时我们可以从 $1$ 枚举到 $ \sqrt { \sqrt x}$，求有多少数的根号下取整等于它，再将dp预处理出的前缀和加到答案里。
正在渲染内容...
点赞
2
收藏
0
