【NOIP模拟题】[状压dp][线段树]
T1 给出一个长度不超过100只包含’B’和’R’的字符串，将其无限重复下去。 比如，BBRB则会形成BBRBBBRBBBRB。现在给出一个区间[l,r]询问该区间内有多少个字符’B’(区间下标从1开始) 思路： 写起走就行了…考试的时候脑抽写了高精度…结果wa完了TAT 主...
HDU-4352 XHXJ's LIS(数位dp+状压)
B - XHXJ's LIS HDU - 4352 题意：给定一个区间[l,r]，问区间内有多少个数满足：它的每一位上的数字所组成的序列的最长上升子序列的长度恰好是k题解：数位dp,考虑到最长上升子序列的O(nlogn)的解法，因为只有0~9共10种数...
SPOJ Balanced Numbers （数位DP+3进制状压）【模板】
BALNUM - Balanced Numbers no tags Balanced numbers have been used by mathematicians for centuries. A positive integer is considered a balanced numbe...
hdu4352——XHXJ's LIS(数位DP+状压)
引用：最长上升子序列nlogn算法 在川大oj上遇到一道题无法用n^2过于是，各种纠结，最后习得nlogn的算法 最长递增子序列，Longest Increasing Subsequence 下面我们简记为 LIS。排序+LCS算法 以及 DP算法就忽略了，这两个太容易理解了。 假设存在一个序列d...
HDU 4352 XHXJ's LIS(数位DP+状压)
Problem Description #define xhxj (Xin Hang senior sister(学姐)) If you do not know xhxj, then carefully reading the entire description is very important...
洛谷 P2622 关灯问题II【状压DP;隐式图搜索】
题目描述现有n盏灯，以及m个按钮。每个按钮可以同时控制这n盏灯——按下了第i个按钮，对于所有的灯都有一个效果。按下i按钮对于第j盏灯，是下面3中效果之一：如果a[i][j]为1，那么当这盏灯开了的时候，把它关上，否则不管；如果为-1的话，如果这盏灯是关的，那么把它打开，否则也不管；如果是0，无论这灯...
BZOJ 1097: [POI2007]旅游景点atr( 最短路 + 状压dp )
先最短路预处理, 然后状压就行了--------------------------------------------------------------------------#include<cstdio>#include<cstring>#include<alg...
BZOJ 4000: [TJOI2015]棋盘( 状压dp + 矩阵快速幂 )
状压dp, 然后转移都是一样的, 矩阵乘法+快速幂就行啦. O(logN*2^(3m))---------------------------------------------------------------------------------------------#include<c...
【洛谷】P1052 过河（状压dp）
题目描述在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终...
【BZOJ-1097】旅游景点atr SPFA + 状压DP
1097: [POI2007]旅游景点atrTime Limit: 30 Sec Memory Limit: 357 MBSubmit: 1531 Solved: 352[Submit][Status][Discuss]DescriptionFGD想从成都去上海旅游。在旅途中他希望经过一些城市并...
2018.08.19 NOIP模拟 dp（二分+状压dp）
Dp题目背景SOURCE：NOIP2015-SHY-10题目描述一块土地有 n 个连续的部分，用 H[1]，H[2]，…，H[n] 表示每个部分的最初高度。有 n 种泥土可用，他们都能覆盖连续的 k 个部分，第 i 种泥土的价格为 C[i]，可以使 i，i+1，…，i+k-1 部分的高度增加 E[i...
hdu3001（状压dp，三进制）
TravellingTime Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5896 Accepted Submission(s): 1908...
【BZOJ1725】[Usaco2006 Nov]Corn Fields牧场的安排 状压DP
【BZOJ1725】[Usaco2006 Nov]Corn Fields牧场的安排DescriptionFarmer John新买了一块长方形的牧场，这块牧场被划分成M列N行(1<=M<=12; 1<=N<=12)，每一格都是一块正方形的土地。FJ打算在牧场上的某几格土地里种...
poj炮兵阵地（状压）（25+10+20=55）
http://poj.org/problem?id=1185刚开始思路就错了 想着用保存这一行的状态 然后再去枚举前面两行的状态 这样不能保证前面两行的状态同时满足要求正解：保存两行的状态 再依次枚举前面的各种小错误不断啊 改的一个纠结。。 #include <iostream> #in...
BZOJ.3058.四叶草魔杖(Kruskal 状压DP)
题目链接\(2^{16}=65536\)，可以想到状压DP。但是又有\(\sum A_i\neq 0\)的问题。。但是\(2^n\)这么小，完全可以枚举所有子集找到\(\sum A_i=0\)的，先使这整个子集内满足平衡，求一棵最小生成树就一定可以了。这样可能会不最优，我们可以用更小的子集(小的话还...
HDU 4906 Our happy ending (状压DP)
HDU 4906 Our happy endingpid=4906" style="">题目链接题意：给定n个数字，每一个数字能够是0-l,要选当中一些数字。然后使得和为k，问方案思路：状压dp。滚动数组，状态表示第i个数字。能组成的数字状态为s的状态，然后每次一个数字，循环枚举它要选取1 -...
HDU 1074 Doing Homework （状压dp）
题意：给你N（<=15）个作业，每个作业有最晚提交时间与需要做的时间，每次只能做一个作业，每个作业超出最晚提交时间一天扣一分求出扣的最小分数，并输出做作业的顺序。如果有多个最小分数一样的话，则按照作业字典序输出（注意：输入也是按照字典序输入的）题解：首先想到的是暴力dfs，但是会超时。接着我们...
bzoj3380: [Usaco2004 Open]Cave Cows 1 洞穴里的牛之一(spfa+状压DP)
数据最多14个有宝藏的地方，所以可以想到用状压dp可以先预处理出每个i到j的路径中最小权值的最大值dis[i][j]本来想用Floyd写，无奈太弱调不出来。。后来改用spfa然后进行dp，这基本是货郎担问题(TSP)，状压中挺常出现的问题f[s][i]表示状态s下到第i个有宝藏的地方，是否能拿到所有...
BZOJ 3870: Our happy ending( 状压dp )
dp(i, s)表示考虑了前i个数后, 能取到的数的集合为s时的方案数.对于1~min(L, K)枚举更新, 剩下的直接乘就好了. 复杂度O(T*K*2^N)。。。好像有点大, 但是可以AC。。。。---------------------------------------------------...
SPOJ BALNUM Balanced Numbers 平衡数（数位DP，状压）
题意：平衡树定义为“一个整数的某个数位若是奇数，则该奇数必定出现偶数次；偶数位则必须出现奇数次”，比如 222，数位为偶数2，共出现3次，是奇数次，所以合法。给一个区间[L,R]，问有多少个平衡数？思路：这题比较好解决，只有前导零问题需要解决。如果枚举到011，那么其前导零（偶数）出现了1次而已，而...