labrother-CSDN博客

cdoj 1159 不知道为什么这么水的题目我都花了好久来思考，（真的比较水），n=20,很明显是状压dp,但是k=10^9,这个的确有点吓人，但是转换一下思想，把k中的每个数分开考虑，然后状压，就可以了，用快速幂优化一下就可以了。bzoj 3812 这题还是比较神的，dp[i]表示i状态时，至少有n个不联通的情况种数，注意是至少n个不联通（这个n包括了所有可能），容斥的时候注意要反一下，把d

2017-02-11 21:11:03 360

原创 kmp模板

#include #include #include #include #include #include #include #include #define maxn 100009#define inf 0x3f3f3f3f#define mod 1000000007#define Mat_size 11using namespace std;char s[maxn];

2016-05-16 16:49:50 228

原创 hdu 4612 tarjian求桥双连通分量缩点+树直径

感觉hdu上数据有点水，但不知道哪组数据可以cha掉我的代码，求告知>-感觉以后树的直径代码还是统一规范一下，即兴写的。//hdu 4612 tarjian边双连通缩点+树的直径#include #include #include #include #include #include #define inf 0x3f3f3f3f#define lowbit(x) ((x)&

2016-01-25 14:57:55 364

原创 LA 3523 tarjian求双连通分量+二分判奇圈

白书上有详细解说代码与书上有些不同，但核心是相通的//LA 3523 点双连通+二分判奇圈#include #include #include #include #include #include#include #define inf 0x3f3f3f3f#define lowbit(x) ((x)&(-x))#define maxn 1050using names

2016-01-25 14:53:59 553

原创 hdu 4738 tarjian求桥

//hdu 4738 tarjian求桥#include #include #include #include #include #define inf 0x3f3f3f3f#define lowbit(x) ((x)&(-x))#define maxn 1000005using namespace std;int dfn[maxn],low[maxn],n,m,ans,hea

2016-01-25 14:50:50 353

原创 hdu 4587 tarjian求割点数目

看注释就好了，我写的还是比较仔细的。//hdu 4587 tarjian 求割点#include #include #include #include #include #define inf 0x3f3f3f3f#define lowbit(x) ((x)&(-x))#define maxn 20005using namespace std;int dfn[maxn],l

2016-01-25 14:49:13 339

原创 hdu 4399 树形dp

题意比较难理解>-//hdu 4799 树形dp#include #include #include #include #include #define inf 0x3f3f3f3f#define lowbit(x) ((x)&(-x))#define maxn 50055using namespace std;int dp[maxn][5],val[maxn],sta[max

2016-01-25 14:45:29 594

原创 hdu 3966 树链剖分（坑内存）

//hdu 3966 树链剖分+树状数组(节点)#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #define lowbit(x) ((x)&(-x))#define LL long long#define maxn 50005

2016-01-21 19:50:42 287

原创 hdu 5593 树形dp

//hdu 5593 树形dp#include #include #include #include #include #define LL long long#define maxn 500005using namespace std;int dp[maxn][15];int k,n;vector g[maxn];void dfs(int a){ dp[a][

2016-01-21 19:47:36 324

原创 hdu 5592 线段树

//hdu 5592 线段树(傻逼题)#include #include #include #include #define maxn 50005using namespace std;struct Tree{ int l,r,len;}tree[maxn*6];int a[maxn],b[maxn];void build(int a,int l,int r){

2016-01-21 19:45:37 316

原创 spoj 375 树链剖分（裸模板）

看来以后树链剖分要用这个模板了。具体效果怎么样，还要看看，机场wifi太TM慢了。寒假估计要是有史以来最辛苦的了。寒假疯狂AC万岁。//树链剖分模板/*记siz[v]表示以v为根的子树的节点数，dep[v]表示v的深度(根深度为1)，top[v]表示v所在的链的顶端节点，fa[v]表示v的父亲，son[v]表示与v在同一重链上的v的儿子节点（姑且称为重儿子），w[v]表示v与其父亲节

2016-01-18 14:48:37 286

原创 Codeforces Round #338 (Div. 2) C. Running Track (dp)

由于这题目要求输出的时候序号要尽量小，没看到，所以呵呵了。属于dp，注释都在代码中间了。貌似自己面对这种要输出答案解，并且要求序号小的题目很是蛋疼。//Codeforces Round #338 (Div. 2) C. Running Track (dp)#include#include#include#include#include#include#define mod 1

2016-01-09 23:26:28 325

原创 poj 1038 状态压缩

这道题还是比较基础的状态压缩dp,但有几个点还是要去注意一下，注意点代码的注释中已经给出来了。//poj 1038 状态压缩dp#include#include#include#include#include#include#define mod 105225319#define maxn 100000using namespace std;int dp[3][maxn];

2016-01-09 17:21:45 415

原创 hdu 5555 状态压缩dp

这题目还是比较隐蔽的，不知道如何进行dp。其实往简单的方面去想也是可以的，当最左边的青蛙确定好位置之后，再考虑他之后的一个青蛙状态。注意一下，由于bad位置有10个，我们可以运用状态压缩来解决，之后的其他膜肯定覆盖了全部位置，因此其他膜可以随便去挑位置。//hdu 5555 状态压缩dp#include#include#include#include#include#def

2016-01-09 17:09:10 461

原创 LA 4794 状态压缩dp

//LA 4794 状压dp//据说是当年2010年全球总决赛最简单的一道题目#define _CRT_SECURE_NO_WARNINGS#pragma warning(disable:4996)#include#include#include#include#include#include#include#include#define mod 10000009#def

2015-12-12 03:32:01 272

原创 hdu 1074 状态压缩dp

//hdu 1074 状态压缩dp#include#include#include#include#include#include#include#include#define mod 10000009#define maxn 9999999999#define long long llusing namespace std;struct Job{ char name

2015-12-12 02:22:56 285

原创 hdu 4628 状态压缩dp

字符串最多只有16位直接暴力。//hdu 4628 状态压缩dp#define _CRT_SECURE_NO_WARNINGS#include#include#include#include#include#include#include#define mod 10000009#define long long llusing namespace std;char s[

2015-12-11 00:39:03 290

原创 hdu 5564 快速矩阵幂+数位dp

hdu5564这道题一看就知道用数位dp,但是在状态转移时，发现不可能转移成功，10^9,但是发现转移可以用矩阵来进行表示，因此……但是要注意矩阵最后一列用来计算结果。代码看看就好了，毕竟卡着时间过的，2500ms左右，标程3000ms.//hdu 5564 快速矩阵幂+数位dp#include#include#include#define mod 1000000007#de

2015-12-10 20:42:47 294

原创 hdu 4630 线段树+在线操作

2015-12-10 18:28:06 268

原创 hdu 5438 +hdu 4786 并查集

hdu 5438先拓扑排序一下，注意后面要进行并查集合并。//hdu 5438 并查集+拓扑排序#include #include #include #include #include #include #include #include #include #define maxn 110005using namespace std;int link[maxn],n,m

2015-12-09 23:45:22 265

原创 cdoj1259 线段树+bitset

感觉题目简单，就看你的bitset怎么用了。#include #include #include #include #include #include #include #include #define maxn 160005using namespace std;struct ee{ int l,r,lazy; bitset s;}tree[maxn*

2015-12-08 22:10:44 286

原创 hdu 4614 线段树+二分

这题感觉有点坑，数组越界了，看来以后数组要尽可能的开大一些了。#include #include #include #include #include using namespace std;#define maxn 60005struct ee{int l,r,flag,length;}tree[maxn*4];int n,m;void build(int a,int

2015-12-05 20:11:38 244

原创 hdu 4616 树形dp

这是一道比较特别的树形dp题目。。。。。。。或许只是我自己这样认为的吧。1.假如u为根节点，v1,v2,v3是其子节点，v1与v2可以连成一条链，不仅仅只是父节点与子节点可以连成一条链（其实就是可以任意选取点开始）。2。题目要求中了几个陷阱就要停止，与“最多能中的陷阱不超过n”这个条件有较大不同，要考虑所选取链头尾是否有陷阱（当链的总陷阱数达到n时）。#include #includ

2015-12-05 02:12:31 276

原创 hdu 5106 hdu 5435 数位dp

hdu 5106真的好累，就不解释代码了。#include #include #include #include long long int dp[1002][1002],dpl[1002][1002];//dpl[i][j]用来计算前i位j个1的个数，dp[i][j]用来计算前i位，有j个1的数的个数。int bit[1003],n,c[1001];char r[1003];

2015-12-03 20:56:21 520

原创 hdu 4666 线段树+最大曼哈顿距离

由于要求n个点的最大曼哈顿距离，并且要执行插入，删去操作，如果对距离公式什么都不做的话，会发现复杂度太高了，tle肯定。再来看一下二维式子，无非有四种方式：(x1-x2)+(y1-y2),(-x1+x2)+(y1-y2),(x1-x2)+(y2-y1),(x2-x1)+(y2-y1).毫无规律再变化一下。（x1+y1）-(x2+y2),(-x1+y1)-(-x2+y2),(x1-y1)

2015-12-03 20:46:40 1121

原创 uva10529 概率dp+区间dp

这道题有点绕，至少思考过程还是比较复杂的。1.题意是要求寻找一个最优的期望，一想到最优，就会联想到枚举，但怎么枚举？由题意可以发现可以枚举最后放的那个牌，为什么？因为这样对两边影响最小，只有当你两边都完成后才可以去计算中间那个值，这一步是区间dp的核心思想，将所有情况都归类到枚举的牌位置左右都有区间的情况去计算。2.如何计算？这个也是比较麻烦的。首先这个不像一般的概率dp直接用dp

2015-11-28 04:28:08 520

原创 uva10859 树形dp

这道题太让我恶心了，用别人ac的代码和自己的答案进行对拍，没错，但就是ac不了，希望大神可以帮我一下（按道理这题提交不成功是因为没有用记忆花搜索，应该是tle,但却是wa，懒得改为记忆花搜索了，毕竟答案都是错的，那就没必要去纠结超时的问题了但我好像知道wa在哪里了）#include #include #include using namespace std;#include #def

2015-11-26 00:55:14 275

原创 uva 11825 集合动态规划

鉴于区域赛的题目刷不动以及基础弱的特点，来刷刷白书。。。。。黑书还完全没看过#include #include using namespace std;#include int k[20],cover[(1<<16)+1],f[(1<<16)+1];int main(){ //freopen("d:\\in.txt","r",stdin); int n,t,fla

2015-11-25 14:29:32 270

转载 hdu 4035 概率dp

这道题很具有典型性的。值得看看。/*HDU 4035 dp求期望的题。题意：有n个房间，由n-1条隧道连通起来，实际上就形成了一棵树，从结点1出发，开始走，在每个结点i都有3种可能： 1.被杀死，回到结点1处（概率为ki） 2.找到出口，走出迷宫（概率为ei） 3.和该点相连有m条边，随机走一条

2015-11-12 20:40:58 281

原创概率dp hdu 5236

说好听一点又一次的涨姿势了，说难听一点又被虐的体无完肤。感觉这道题难，首先连题目样例都没读懂。算了直接上代码。#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;#define l

2015-11-10 20:34:55 307

原创 hdu5282 最长公共子序列

这道题不错，怎么说呢，又是一到让我涨姿势的题（因为不会做）#include #include #include #include #include #include #include using namespace std; #define ll long long const int mod = 1e9+7;

2015-10-23 22:30:23 249

原创 hdu 1664如此爽的一道bfs+数论

这道题真的是要靠第三感觉，首先题目没有给定数字答案的大小限制，应该想到有条件可以限制这个数字的大小。囧。。。。。。。。毕竟菜鸟，完全没想法。ps：一个数论中的结论：对于任意的整数n，必然存在一个由不多于两个的数来组成的一个倍数。因为a，aa，aaa……取n+1个，则必有两个模n余数相同，相减即得n的倍数m。而m只由a、0组成。先用一个数来搜答案，9种情况，已经搜到答案就输出

2015-10-21 00:03:56 793

翻译 hdu 5481 区间离散+组合

第二个样例解释：集合中含有2个区间：一个是[0,2],编号为1，一个是[1,3]，编号为2。集合的子集有4个：1、空集，集合中区间的并的长度为02、{区间1}，集合中区间的并的长度为23、{区间2}，集合中区间的并的长度为24、{区间1、区间2}，集合中区间的并为[0,3]，长度为3考虑某一个区间对于答案的贡献：若某个区间

2015-10-19 10:21:44 357

原创 hdu 3333 线段树离线操作

这道题不同于一般普通的线段树，如果用在线算法的话会失败，以我的理解的话，是因为每个节点所要保存的信息都与前面位置的数据有关。不像通常的线段树，只与子节点的信息有关。首先按照查询区间的右值进行排序。然后进行数据插入，把每个数放进线段树的时候，先判断再之前他有没有在线段树，如果在，则删除它，并把他的位置更新到当前点。#include #include #include #inclu

2015-10-18 13:22:40 625

操作系统线程编程

沙坑里打开

空空如也