摸🐟🐭

分类

数据结构专题班(2) 题解(2)

/ 注册

全部文章（共4篇）

牛牛的猜球游戏

https://ac.nowcoder.com/acm/contest/19483/F 这道题乍一看像是个找规律或者模拟题，实质上其每次操作都是固定的那么这样的题目要如何带入前缀和来思考呢我们将每一次的操作的序列状态的改变看作一个量然后拿这个量形成的数组做前缀和为什么可以这么转化呢，因为前...

前缀和构造

2021-08-17

2 673

智乃酱的区间乘积（线段树or前缀积+乘法逆元）

https://ac.nowcoder.com/acm/contest/19483/A 一个前缀积的问题，但是由于自己一开始不会逆元（数论0基础QAQ）自然在取模时出了错于是先用线段树冲了一发线段树： #include <bits/stdc++.h> using namespace ...

前缀和逆元

2021-08-17

1 822

题解 | #送外卖2#

20个点的数据，基本上可以判断是状态压缩，所以就直接开始上手了。基本思路还是很好想，构建出图之后用floyd构建全图联通，再用状压dp求解答案。而难点在于，定义dp数组的含义。我们回忆一下状压dp求解哈密顿路径的例题：dp数组的两个维度表示的是当前状态和落脚点，值表示最短路径当前状态包含了所有的已遍...

构造最短路状压dp

2021-07-20

9 913

牛牛与跷跷板（附详细注释代码）

牛牛与跷跷板抓住题目中：相邻则可以跳跃，目的是寻求1号块到n号的最小跳跃次数可以确定这道题的基本解法是：最短路然后在题目的思考过程中发现，这道题的图并没有给你构造出来那就需要从零开始构建边与边之间的关系第一发想到的当然是暴力构建，N^2 的复杂度果然超了…… 随后发现，这题居然可以贪一贪！...

构造最短路贪心

2021-02-04

5 630