图论
Linux驱动开发
并发编程
JUC
random
执行系统命令
虚拟设备
HID
rust
科研绘图
网站安全防护
语法
kingbase
lstm
opengl
移动端
知识计算
语音读写播放
无痕模式
证件照
状压dp
2024/4/12 17:26:50
【GDOI2017模拟8.15】Game
Description
给出一个n*m的网格图。 你可以决定每个格子是0还是1. 给出nm个限制，每个限制限制每行或每列有且只有多少块连续的1. 一块连续的1指的就是一块连续的1（呵呵 两块连续的1就像这样：1…101…1 求方案数。 n<5,m<20
Sol…
[ZJOI2015]地震后的幻想乡
Description
给出一张n个点m条边的无向图，第i条边有一个在[0,1]内独立随机的权值ei 问这张图的最小生成树的最大边权的期望 n<10,m<n*(n-1)/2
Solution
设f(x)表示只用边权<x的边，图不连通的概率 可以发现，f(k)P(x>k)…
[51nod1920]空间统计学
Description
给出m维平面上的n个点，每个点的每维坐标在[0,3]范围内 对于i0~3m，求曼哈顿距离为i的点对数量 n<200000,m<9
Solution
被鞋垫教做题QwQ我真是太菜了 才不是什么FWT呢 考虑状压Dp，压4进制m位 Fi,j,s表示考虑完前i为&…
acwing 327 玉米田
题面 题解(棋盘模型) 这题是要求我们不能在数字是0的地方中玉米，还有就是上下左右相邻的位置不能种玉米，还是一样，每一行的状态只取决于上一行的状态，用二进制表示放置的状态，然后从第一行开始向下更新 对于不能种玉米…
[codeforces107C][51nod1579]席位安排
Description
一个长度为n的排列，要满足m条限制 第i条限制形如(ai,bi)，表示排列的第ai个位置一定要比第bi个位置小 求满足条件的，字典序第k小的排列 n<16,m<100,k<1e18
Solution
考虑一位一位确定答案，我只需要知道…
[51nod1447]好记的字符串
Description
给出n个字符串，每个字符串长度均为m 一个字符串为好记的当且仅当它存在一个位置，使得这个位置上它的字符和其他所有串不一样 你每次可以修改某一个字符串中的某一个位置，代价为ai,j 求把所有串变成好记的的最小代价 n,m<…
备战蓝桥杯---状态压缩DP基础2之TSP问题
先来一个题衔接一下： 与上一题的思路差不多，不过这里有几点需要注意：
1.因为某一列的状态还与上上一行有关，因此我们令f[i][j][k]表示第i行状态为j,第i-1行状态为k的最大炮兵数。
因此，我们可以得到状态转移方程&…
状压DP——蒙德里安的梦想/最短hamilton路径
状压DP简单来说就是用二进制的方式来压缩状态 具体的题目会有不同的表示方法
蒙德里安的梦想
首先分析这个问题，我们现在行上放小方格，在行上放完之后，那么纵向的小方格就只有一种放的方式。因此！只需要求出横向放的方式就可以了…
蓝桥杯系列 - 2019国赛 - 矩阵计数
矩阵的每个位置只有两种可能的状态，加上 N, M 的范围这么小，很容易想到要用到二进制，往这个思路想下去就想到了状压 DP。 大致思路如下：
输入 N, M，矩阵每行的状态就有 numState 2M 个。假设 1 代表题中的 ‘X’&…
bzoj 2669: [cqoi2012]局部极小值
Description 有一个n行m列的整数矩阵，其中1到nm之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。给出所有局部极小值的位置，你的任务是判断有多…
【NOIP2017提高A组冲刺11.1】荒诞
Description
给出一张n个点m条边的图，保证图中不存在长度大于10的简单路径 选择某一个点需要付出Ci的代价，求最小代价使得每个点都被选择，或者它相邻的点被选择
Solution
原题似乎是POI2012的某道题(夕立：poi？) 而…
acwing 292 炮兵阵地
题面 题解(状压DP棋盘模型) 状压DP棋盘模型题，对于H 山丘是不能放置意大利炮的，那么我们就可以提前预处理出山丘的位置，把山丘的位置设为二进制中的1，在最后和合法的状态进行&判断，假设01011(山丘的位置) …
POJ3254，Corn Fields（状压DP）
题意:农夫有一块地，被划分为m行n列大小相等的格子，其中一些格子是可以种植作物的（用1标记），其他格子则不能种植（用0标记），并且要求相邻格子不能同时都有种植作物。现在输入数据给出这…
[AGC020F]Arcs on a Circle
Description
用n个长度为L[i]的圆弧随机覆盖长度为c的圆环，问圆环被完全覆盖的概率 n<6,c<50
Solution
我还以为是一道niubi积分题_(:з」∠)_ 考虑把圆环在L最大的圆弧的左端点处断开，我们可以把环上的问题变成链上的问题 然后，每个…
【CF424E】Colored Jenga
Description
Tomsk 寒冷的冬季傍晚非常无聊——没人想要在这个时间点儿上在街上晃。居住在Tomsk 的市民都坐在温暖的公寓里玩游戏打发时间。他们玩的其中一个游戏唤作“有色积木” 。
这个游戏需要三种不同颜色的木块：红色，绿色及蓝色。接着࿰…
acwing 291 蒙德里安的梦想（状压DP）
题面 题解 我们发现，只要确定了横向小方格的位置（蓝色），其余位置都是纵向的小方格，就已经确定了一种方案，所以我们只需要枚举合法的横向小方格，那么就相当于枚举了方案数。 先给出 f[i] [j] 的定…
Leetcode.1125 最小的必要团队
题目链接 Leetcode.1125 最小的必要团队 Rating ： 2251 题目描述
作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people中选出些人组成一个「必要团队」（ 编号为 i 的备选人员 people[i]含有一份该备…
acwing 524 愤怒的小鸟
题面 题解 一般的抛物线方程 y ax2 bx c ,但是题中是要求我们从原点射出一个开口向下的抛物线，所以就要求a<0,过（0，0），把(0,0)点带入就可以得出c0 ；因此抛物线方程为：yax2bx，有…
【GDOI2018模拟8.11】决战
Description N<2500
Solution
听说暴力状压可以过？然而我常数不好只有90分 考虑普通的状压，F[i][s][j]表示当前填到第i行，第i行的状态为s，用了j个哲学♂家的方案数 我们把最后一维看做多项式，用x^j的系数表示答…
bzoj 2073: [POI2004]PRZ
Description 一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥. 桥已经很旧了, 所以它不能承受太重的东西. 任何时候队伍在桥上的人都不能超过一定的限制. 所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过. 队伍里每个人过桥都需要特定…
洛谷P1171 售货员的难题（状压DP）
题目描述： 某乡有n个村庄(1<n≤20)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0<s<1000)是已知的，且A村到B村与B村到A村的路大多不同。为了提高效率，他从商店出发到每个村庄一次&…
[SCOI2005]互不侵犯（状压DP）
题意：给定一个N * N的棋盘，放置K个国王，使他们互相攻击不到对方，共有多少种方案。国王可以攻击上下左右，左上左下，右上右下附近的一格，共8格。 数据范围：1<N<9, 0<K<N *…
CF580D，Kefa and Dishes（状压DP）
题意：有n道菜，每道菜一个权值，有k个条件，表示第y道菜在第x道后马上吃有c的附加值。求从中吃m道菜的最大权值。
本题详解可看： https://www.cnblogs.com/real-l/p/8597827.html 作为还在入门状压DP的萌新，这…
acwing 1064 小国王
题面 题解(状压DP棋盘模型) 我们可以知道图中蓝色部分为国王，它的周围一圈是不能放其他国王的，那么它所影响的位置就是与他相邻的位置，我们放到每行来看，影响下一行的就是上一行国王的位置 我们用二进制来表示每行的状态 …
备战蓝桥杯---状态压缩DP进阶题1
我们来看一看一道比较难的问题（十分十分的巧妙）： 显然我们应该一行一行放，又竖的会对下一行产生影响，我们令横着放为0，竖着放的上方为1.
对于下一行，前一行放1的下面为0，但是会出现…
CodeForces - 906C Party 【状压dp】
我们通过状态压缩，然后判断转移的情况，然后主要通过| 的运算，将不是联通块中的人的朋友加入到联通块中的操作
#include <bits/stdc.h>
#define cl(a) memset(a,0,sizeof(a))
#define ll long long
#define pb(i) push_back(i)
#define…
Leetcode.2172 数组的最大与和
题目链接 Leetcode.2172 数组的最大与和 rating : 2392 题目描述
给你一个长度为 n n n 的整数数组 n u m s nums nums 和一个整数 n u m S l o t s numSlots numSlots ，满足 2 ∗ n u m S l o t s ≥ n 2 * numSlots \geq n 2∗numSlots≥n 。总共有 n u m S …
1011 - Marriage Ceremonies （状压DP（dfs））
题目连接
Time Limit: 2 second(s) Memory Limit: 32 MB You work in a company which organizes marriages. Marriages are not that easy to be made, so, the job is quite hard for you.
The job gets more difficult when people come here and give their bio-data wi…
状压dp：Gym - 102832J
https://vjudge.net/contest/587311#problem/G
认真读题，然后发现就是让区间不交，要么包含要么相离，长度为偶数，直接状压
状压就状压10位就行。转移发现长度为偶数，所以可能填法只有 2 5 2^5 25。总复杂度 O ( n 2…
【AC自动机+状压dp】HDU2825 Wireless Password
题意 : 输入n(1<n<25)、m(0<m<10)、k，意思就是给你 m 个模式串，问你构建长度为 n 至少包含 k 个模式串的方案有多少种 mod20090717 直接进行计数一定是比较麻烦的，又发现m比较小，所以我们可以进行一下状态压缩再继续进…