LightOJ1021 Painful Bases（状压DP）
容易想到状态dp[n][S][m]（S是数字出现的集合），表示前n位用了数字集S且模k余数是m的方案数。利用(xy)base%k=(x*base+y)%k=((x%k ) *base+y)%k，进行状态第三维的转移。不过d[16][216][20]有2000多W的状态数，且不说超时的问题，内存早已超...
HDU4623 CRIME 【状压DP】【同类项合并】
题目大意:求相邻元素互质的排列个数。题目分析:由于互质只与质因数有关，所以我们对于质因数种类相同的数合并为一类，特殊的，1,17,19,23是一类，因为没有数与他们不互质。那么我们做各个位进制不同的状压DP。转移就是在末尾添加哪个数。代码:#include<cstdio>#include...
HDU5418.Victor and World（状压DP）
#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<algorithm>usingnamespacestd;typedeflonglongll...
【BZOJ-2732】集合选数 状压DP （思路题）
2734:[HNOI2012]集合选数TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 1070 Solved: 623[Submit][Status][Discuss]Description《集合论与图论》这门课程有一道作业题，要求同学们求出{1,2,3,4...
POJ1038 Bugs Integrated, Inc 状压DP+优化
(1) 最简单的4^10*N的枚举（理论上20%）(2) 优化优化200^3*N的枚举（理论上至少50%）(3) Dfs优化状压dpO（我不知道，反正过不了，需要再优化）（理论上80%）(4) 再剩下的，卡常数+卡常数+一个小优化（自己想吧，有可能被卡一个点）(5) 如果还没有过，dfs中可能有重复...
吃奶酪 状压dp
题目描述房间里放着n块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在(0,0)点处。输入输出格式输入格式：第一行一个数n(n<=15)接下来每行2个实数，表示第i块奶酪的坐标。两点之间的距离公式=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))输出格...
【62测试】【状压dp】【dfs序】【线段树】
第一题：给出一个长度不超过100只包含'B'和'R'的字符串，将其无限重复下去。比如，BBRB则会形成BBRBBBRBBBRB现在给出一个区间[l,r]询问该区间内有多少个字符'B'(区间下标从1开始) [1<=l,r<=1e18]解： 没想到第一题这么水。直接前缀和+mod就可以了，再...
[NOI2001]炮兵阵地 状压DP
题面：司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H”表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：如果...
SGU 131. Hardwood floor 状压dp 难度:2
131.Hardwoodfloortimelimitpertest:0.25sec. memorylimitpertest:4096KBThebanquethallofComputerScientists'PalacehasarectangularformofthesizeMxN(1<=M&l...
poj2686-Traveling by Stagecoach（状压dp）
题意：n张马票，m个城市，马票上有马数（决定速度），一张只能用一次，给出地图，求从城市a到b的最短时间。分析：n值很小状态压缩#include<map>#include<set>#include<list>#include<cmath>#include...
bzoj2669 [cqoi2012]局部极小值 状压DP+容斥
题目传送门https://lydsy.com/JudgeOnline/problem.php?id=2669题解可以发现一个\(4\times7\)的矩阵中，有局部最小值的点最多有\(2\times4=8\)个，所以我们可以状压一下每个局部最小值的位置有没有被选。从小到大填入每一个格子，那么如果一个...
hdu 4057--Rescue the Rabbit(AC自动机+状压DP)
题目链接ProblemDescriptionDr.Xisabiologist,wholikesrabbitsverymuchandcandoeverythingforthem.2012iscoming,andDr.XwantstotakesomerabbitstoNoah'sArk,ortherea...
BZOJ1072 排列perm 【状压dp】
Description给一个数字串s和正整数d,统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能被2整除，其中末位为2的有30种，末位为4的有60种。Input输入第一行是一个整数T，表示测试数据的个数，以下每行一组s和d，中间用空格隔开。s保证只包含数字0,1,2...
POJ 3254 状压DP
题目大意：一个农民有一片n行m列的农场 n和m范围[1,12] 对于每一块土地，1代表可以种地，0代表不能种。因为农夫要种草喂牛，牛吃草不能挨着，所以农夫种菜的每一块都不能有公共边。告诉你n，m和那些地方能种菜哪些地方不能种菜，求农夫一共有多少种方案种菜解法：基本思想是状压也就是用一个int型的数代...
HDU 4539 郑厂长系列故事——排兵布阵 —— 状压DP
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4539郑厂长系列故事——排兵布阵TimeLimit:10000/5000MS(Java/Others) MemoryLimit:65535/32768K(Java/Others)TotalSubmi...
hdu4778：状压dp+博弈
题目大意：有g种不同颜色的小球，b个袋子，每个袋子里面有若干个每种小球两人轮流取袋子，当袋子里面的同色小球有s个时，会合并成一个魔法球，并被此次取袋子的人获得成功获得魔法球的人可以再次取求二者都进行最优策略之后两人所得魔法球个数差分析：博弈，数据很小，自然想到了可以搜索所有状态然后从每一步的子状态中...
HDU 3001 Traveling（状压DP）
题目大意：10个点的TSP问题，但是要求每个点最多走两边，不是只可以走一次，所以要用三进制的状态压缩解决这个问题。可以预处理每个状态的第k位是什么。原代码链接：http://blog.csdn.net/accry/article/details/66077033进制，代表走过这个点的次数#inclu...
nefu1109 游戏争霸赛（状压dp）
题目链接：http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id=1109//我们校赛的一个题，状压dp，还在的人用1表示，被淘汰的人用0表示。倒着循环即可。//比赛的时候我用的是二维dp数组表示状态，一直是WA的，搞不懂原因。。。...
HDU 4778 状压DP
一看就是状压，由于是类似博弈的游戏。游戏里的两人都是绝对聪明，那么先手的选择是能够确定最终局面的。实际上是枚举最终局面情况，0代表是被Bob拿走的，1为Alice拿走的，当时Alice拿走且满足变换成魔法石，那么相当于是Alice完成了该次操作，增加上次状态值，否则相当于先后手交换，该状态下减去上个...
AGC 016 F - Games on DAG(状压dp)
题意给你一个有\(n\)个点\(m\)条边DAG图，点的标号和拓扑序一致。现在有两个人进行博弈，有两个棋子分别在\(1,2\)号点上，需要不断移动到它指向的点上。如果当前两个点都无法移动，那么就视为当前操作的人失败。问有多少边集满足先手必胜。\(\displaystyle2\len\le15,m\l...