状压DP算法笔记

Created2025-05-04|Updated2025-05-04|笔记

|Post Views:

啊哈起床了来写一个状压dp八

状态压缩

状态压缩DP，简称状压DP。顾名思义，状态压缩

Author: hsl-beat

Link: http://hsl-beat.github.io/2025/05/04/%E7%8A%B6%E5%8E%8BDP%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0/

Copyright Notice: All articles on this blog are licensed under CC BY-NC-SA 4.0 unless otherwise stated.

Related Articles

RMQ的三种奇妙方法

这是2025年3月29号的截图痛苦的一天前言用于记录不幸挂掉的某学校比赛的文章。。。 RMQ是什么 Range Max/Min Query，中文就是区间最大/最小值查询，简称RMQ，这篇文章主要探讨RMQ的3种解决方法。题面给你一个长度为NNN的正整数数组A=(A1,A2,...AN)A=(A_1,A_2,...A_N)A=(A1,A2,...AN)。然后给你MMM个查询，每次查询给你左端点lll和右端点rrr，回答AAA的第lll个元素到第rrr个元素之间的这个区间中的元素的最大值。 1≤N≤1000001 \leq N \leq 1000001≤N≤100000 解题思路首先你应该想到的我都把这个看似很简单的题单独拎出来了，你如果还想着BF的话可以选择去往生堂把自己埋了，啊没错这个问题有几种奇妙的方法可以让程序跑的快多了！！！ ST表思路 Sparse...

Tarjan算法笔记

今天是2025年2月12日，这是洛谷的占卜结果：显然适合学习新算法，今天早上正好学了tarjan，来稍微写一写。 tarjan tarjan求SCC SCC是什么度娘说了：有向图强连通分量：在有向图G中，如果两个顶点ViV_iVi,VjV_jVj间（Vi>VjV_i>V_jVi>Vj）有一条从ViV_iVi到VjV_jVj的有向路径，同时还有一条从VjV_jVj到ViV_iVi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图GGG的每两个顶点都强连通，称GGG是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected...

对拍，但是构造题

对拍是什么？对拍是一种校验程序正确性的方法，通过比较两个程序的同一个测试样例的输出结果，就可以做到判断正确性。想必各位dalao们都会对拍吧，在oi这种shabi赛制中，对拍就显得尤为重要。但是，如果你哪天运气不好，遇到了构造题，应该怎么办呢？其实说的高大上，这个玩意其实不难，营养并不多，比赛的时候动动小聪明其实也能想到 ...

差分约束算法笔记但是只有板子因为为了应付今晚的G题所以匆匆学的

标题长，别怪我没啥好说的，因为只有板子，直接上板子题（小黄油美式害得我根本睡不着，浅浅写一下，哪里有问题欢迎喷我，脑子可能今晚有点不好使） P5960 【模板】差分约束题目描述给出一组包含 mmm 个不等式，有 nnn 个未知数的形如： {xc1−xc1′≤y1xc2−xc2′≤y2⋯xcm−xcm′≤ym\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧xc1−xc1′≤y1xc2−xc2′≤y2⋯xcm−xcm′≤ym 的不等式组，求任意一组满足这个不等式组的解。对于 100%100\%100% 的数据，1≤n,m≤5×1031\leq n,m \leq 5\times 10^31≤n,m≤5×103，−104≤y≤104-10^4\leq y\leq 10^4−104≤y≤104，1≤c,c′≤n1\leq c,c'\leq...

树状数组学习笔记

树状数组是什么本质上就是一个长得像树的数组，长得很像一个二叉树，like下面的图：我们拿它干嘛呢？我们可以拿它来单点修改，区间查询。那就有人说：欸，那线段树功能性比树状数组多，你怎么不用线段树？你这么认这个功能性干嘛啊，它会把其他方面给异化掉的懂吗，知不知道什么叫异化跟具体化？赛场上可能同一个问题树状数组要写10min，但是线段树要30min，你说你写那个？怎么实现树状数组好奇树状数组是怎么被人想出来的 lowbit 树状数组是通过这个叫lowbit的函数实现的，它主要用来求一个二进制数最低的一位111以及它后面的一堆000组成的数。说具体点，比如说114114114这个数，它就等于(1110010)2(1110010)_2(1110010)2，那求lowbit后就会变成(10)2(10)_2(10)2，也就是2 那想要求出lowbit函数的值，我们只需要让它返回xxx andandand (−x)(-x)(−x)就可以了结构还是那张图片，我们把数组从前往后编号，你会发现深度相同的位置二进制下末尾0的个数是相同的！ ...

ABC388游记（A~E）

Atcoder ABC388个人游记（A~E）比赛链接 A. ?UPC 题面给你一个字符串 SSS 。在这里， SSS 的第一个字符是大写英文字母，第二个和后面的字符是小写英文字母。打印由 SSS 的第一个字符和 UPC 按此顺序连接而成的字符串。思路 a题难度稳定依旧炒鸡简单，按题意模拟即可。代码 123456789#include<bits/stdc++.h>using namespace std;int main(){ char s; cin >> s; cout << s << "UPC"; return 0;} B.Heavy Snake 题面有 NNN 条蛇。最初， iii (条)蛇的厚度是 TiT_iTi ，长度是 LiL_iLi 。蛇的重量定义为其厚度和长度的乘积。对于满足 1≤k≤D1 \leq k \leq D1≤k≤D 的每个整数 kkk ，求每条蛇的长度增加 kkk 时最重的蛇的重量。 1≤N,D≤1001 \leq N, D \leq...

Comments