xkaxingz

分类

算法(1) 题解(3) 题解a(15)

/ 注册

全部文章（共17篇）

111A

https://ac.nowcoder.com/acm/contest/111/A （好像经常会忽略加粗字体）其实看到加粗字体，知道形成方式后就很显然了。不一定知道是树形dp，但肯定知道要递归，高度和宽度就会操作了。由于相接的两部分反色，于是要算和当前同色的面积，只要当前总面积减去一层递归下的面...

C++ 动态规划树形dp

2026-02-28

1 16

1655. 分配重复整数

很小，不难想到状压dp，且应该把状态压缩，依次枚举。有一个需要注意的地方：有时我们设置搜索状态为，表示进入到第个数，顾客的满足状态为，第个数剩余个。这样显然爆空间，无法实现记忆化，因而时间复杂度直接爆炸。解决这个问题有一个新思路：就是新增状态时，枚举当前状态的补集。因为：显然新增状态不能和现有状...

C++ 状压dp 记忆化搜索动态规划

2026-02-22

0 17

1434. 每个人戴不同帽子的方案数

套路：枚举一个变量（或者说按顺序搜索），另一个变量根据搜索路线状态压缩+记忆化处理。注意到帽子颜色很多，枚举每个帽子是否被选择不现实（共有种情况）。但同样注意到人数很少，转换一下思路：状态中表示这个人是否选好了帽子，总共种情况，从开始依次枚举帽子即可。同时结合记忆化：表示从第个帽子，状态开始选...

状压dp 动态规划记忆化搜索

2026-02-22

0 17

1994. 好子集的数目

注意到，而其中符合条件的整数只有个，显然可以考虑状压，直接枚举所有情况即可。注意的处理，对于每一个状态，每个都是可取可不取，故有种情况。枚举所有子集：初始为，那么为：。代码： class Solution { public: int a[22]={2,3,5,6,7,10,11,13,14,...

状压dp

2026-02-22

1 14

P1171 售货员的难题

状压dp+记忆化搜索 TSP问题：要求从出发经过所有点之后回到的最短路径。看数据量容易想到状压dp。因为要经过所有点，所以定义状态，二进制上为则表示已经过。定义为状态为，当前在点，从出发到当前状态后，达到最终状态（在点，状态为）的最短路径。于是显然有转移：。同时由于最终状态锁死，排除一些不合法...

状压dp 动态规划记忆化搜索

2026-02-21

1 24

120561I

https://ac.nowcoder.com/acm/contest/120561/I （同样诡异的🔑）主要是找规律。令为的二进制最高位，令，则 1.若，则显然答案为。 2.若，则答案为，因为区间中含有到的所有数，通过和做与操作能得到到间的所有数字。 3.若，那么同2，一定可以得到到的所有数...

构造找规律

2026-02-17

0 32

120561H

https://ac.nowcoder.com/acm/contest/120561/H 先给一个结论：对一个确定数列（），以开头/结尾的前缀/后缀或和最多只有个。那么就很好做了：定义为以结尾，后缀或和为的符合题目的数量。显然有转移：令数列储存当前下以为结尾的后缀或和。则有：由于一个有的...

动态规划

2026-02-17

1 21

120565C

https://ac.nowcoder.com/acm/contest/120565/C 显然二分答案。主要是全覆盖，那么圆的有效面积高度一定要达到，那么就是：能否选出条高度达到的线段使它们覆盖轴的。做一个简单贪心即可。贪心：在所有左端点小于当前的线段中选出右端点最大的更新，同时线段计数，得到最...

二分

2026-02-17

0 26

120565H

https://ac.nowcoder.com/acm/contest/120565/H 纯观察题，新增知识棋盘黑白染色。首先目标是所有数字一样，那么所有数字的和一定是的倍数。注意到黑色、白色位置的和永远不变，所以黑/白位置的和也一定是黑/白格子数量的倍数。注意到： 1 1 -1 -1 和 1 ...

2026-02-16

1 21

120565F

https://ac.nowcoder.com/acm/contest/120565/F （诡异的🔑）贪心+dp 因为种情况的最小公倍数是，所以前段暴力填充，贪心取最优，后续dp处理。但是如果最后只剩下的话，如果填的是的，那么后面再加凑成的情况处理不了，于是要多留出一段来处理这种情况。 #inc...

贪心动态规划

2026-02-13

1 27