running_in_dark-CSDN博客

原创 bzoj1195(最短母串)

1：练习了string类，string中查找，找不到的话会返回 s.npos一个变量，而不是返回一般的s.end();2：这题还可以，ac自动机上状压bfs，找最短路，实际上是dp，但是转移都是加1，所以可以抽象为边长为一从起始状态到最终状态的最短路，因为为边长1，又可以转为bfs。3： #include#include#include#include#include

2017-04-16 16:49:07 530

原创 bzoj4820

表示高斯消元总写错。。。注意，概率和期望高斯消元，我们消的时候，取一个fabs最大的就好，别用eps判了，re惨了。。 #include#include#include#include#include#includeusing namespace std;const int N=305; int n,m,pos[N]; int head[N*N],tot,

2017-04-13 19:53:41 531

原创 hdu3340（线段树+几何）

给定N个多边形，然后每次查询一段坐标内图形的面积。我们可以将多边形拆解为多个梯形，转化为每一次在一个区间加一个等差数列，注意这个等差数列是实数的，其实就是一个区间加一个梯形面积，而梯形面积我们只需要知道左右端点的高就好，这样打标记，累加左右的高，是可以维护的。这里线段树是要离散化的，所以下传标记找mid高度时，要注意不是线段树区间的中点，而是实际区间的中点，#inclu

2017-04-10 11:51:13 504

原创计算几何模板

poj1113（凸包）#include#include#include#includeusing namespace std;const double eps=1e-8;const double pi=acos(-1.0);inline int dcmp(double x) { if (fabs(x)<eps) return 0; return x<0 ? -1:1;}

2017-04-04 11:09:55 338

原创 cf311B（斜率优化）

很好的dp #include#include#include#include#includeusing namespace std;typedef long long ll;const int N=500005;int now,n,m,p;ll dp[2][N],f[N],d[N],sum[N];int q[N],head,tail;ll getup(int j,

2017-04-03 16:20:58 1473

原创 cf547c 容斥原理

互质问题，特别注意1的处理！！！构建了容斥和莫比乌斯函数的对应关系详见zyf2000的博客 #include#include#include#include#include#includeusing namespace std;typedef long long ll;const int N=200005;int n,q,vis[N];vector

2017-04-02 22:47:27 563

原创 bzoj1492(cdq分治+凸包+优化dp)

我们会发现dp不满足单调性，但是可以构建凸包，其中点的表示方法很巧妙要对一些问题转化成凸包敏感一点，尝试找出表示凸包的点，看看是否可以用斜率来表示答案。一定要写eps，wa到死。。。在cdp分治如果预先，处理了某一维信息相对的顺序，那么在分治中千万不能打破这个顺序！！！！ #include#include#include#include#include

2017-04-01 20:18:30 790

原创 bzoj4134 (sg函数，线段树合并（trie））

trie合并，加sg函数。。。 #include#include#include#include#include#includeusing namespace std;const int N=100005;const int D=19;int n;int c[N];int head[N],tot,pre[N*2],to[N*2];void addedge(int

2017-03-26 11:29:35 441

原创 bzoj3132(二维树状数组+公式化简处理)

树状数组处理区间需要化公式。。。 #include#include#include#include#includeusing namespace std;int n,m;struct aa{ int t[2050][2050]; void add(int x,int y,int tmp) { for (int i=x;i<=n;i+=i&-i) for

2017-03-19 17:19:05 535

原创 bzoj1823（2 sat）

the first 2 sat #include#include#include#include#include#includeusing namespace std;const int N=205;int n,m;int head[N],to[N*N],pre[N*N],tot;void addedge(int u,int v) {to[++tot]=v;pre[

2017-03-09 16:22:51 189

原创 bzoj2286 虚树第一道

据说虚树问题总是要套dp的。主要的巧妙之处在于，可以在等同于数据大小的复杂度内建好虚树，关键是利用了dfs序的性质。 #include#include#include#include#include#include#include#includeusing namespace std;const int N=250005;typedef l

2017-03-01 11:35:34 221

原创 bzoj2115( maxize xor)

how amazing the problem is! #include#include#include#include#include#includeusing namespace std;typedef long long ll;const int N=100005;int n,m;int head[N],tot;struct aa

2017-03-01 11:22:28 247

原创 bzoj2460（xor线性基）

拟阵证明，线性基性质，线性基中任意子集异或和不为0，所以从大到小加入就好 /************************************************************** Problem: 2460 User: zhhx Language: C++ Result: Accepted Time:24 m

2017-02-27 15:51:36 863

原创 vjudge： spoj--to the moon（主席树区间修改）

题目大意：题目大意：给定一些数字，有以下几个操作 a、[L,R]区间的数字变化D的数值。并且时间向前推进 b、询问某个时间的[L,R]区间的数字之和，这不花费时间 c、回到X时间。可持久话线段树裸题。其实区间修改就体现了，只要主席树更新的节点，就要重建。就本题而言，区间加我可以搞成标记永久化，防止p

2017-02-26 12:25:25 1640

原创 bzoj2212(线段树合并第一道)

话说像这样的，维护的东西需要数据结构且需要合并的问题，就可以考虑合并。例如本题，我们所需要从叶子节点把维护的数据不断递推上来，所以就需要线段树合并。肯定是动态开节点 #include#include#include#include#include#include#include#include#define fi first#define se second#def

2017-02-26 09:36:45 613

原创 bzoj4031 （矩阵树定理，行列式基础）

行列式再回顾！手机上图片 /************************************************************** Problem: 4031 User: zhhx Language: C++ Result: Accepted Time:20 ms Memory:1048 kb*************

2017-02-25 21:09:18 370

原创 bzoj1023（仙人掌直径，圆方树）

一般仙人掌问题，都要分情况，树上一种处理方式，环上另一种处理方式。 /************************************************************** Problem: 1023 User: zhhx Language: C++ Result: Accepted Time:744 ms Memory

2017-02-25 21:06:51 1125

原创 bzoj4066(kd_tree 维护权值)

话说本来想写替罪羊重构，可是后来发现狂T不止。 /************************************************************** Problem: 4066 User: zhhx Language: C++ Result: Accepted Time:49076 ms Memory:12468 k

2017-02-25 21:01:55 435

原创 bzoj1486(dfs版spfa判环)

01分数规划，注意这里是用dfs版的spfa判环，我们只需要判断是否可以进行一个圈的松弛操作就好。 #include#include#include#include#include#includeusing namespace std;const int N=10005; int n,rt,m,flag; struct aa{ int u,v; do

2017-02-25 07:35:24 725

原创 poj3693后缀数组（插点）

确是够坑 #include#include#include#include#includeusing namespace std;const int N=100005*2;int n,len;char ch[N];int s[N],sa[N],height[N],c[N],rank[N],t1[N],t2[N];int f[N][20],tmp[N],kk[N];

2017-02-16 23:06:18 243

原创 bzoj2179（fft模板）

大整数乘法 #include#include#include#include#include#include#includeusing namespace std;typedef complex E;const double pi=acos(-1.0);const int N=150005;int n,m,L,c[N],R[N];E

2017-02-12 20:32:35 232

原创 bzoj2179 bigint * fft

hzwer , not easy understand #include#include#include#include#include#include#includeusing namespace std;const double pi=acos(-1.0);typedef complex E;char ch[60005];int n,m

2017-02-12 17:45:28 179

原创 bzoj2565(manacher)

利用了manacher的整个思想#include#include#include#include#includeusing namespace std;const int N=200005;int n,m,len,f[N*2],front[N*2],back[N*2];char ch[N],s[N*2];int main(){ scanf("%s",ch);n=str

2017-02-10 10:06:16 185

原创 bzoj3881(ac自动机)

又是数组开小。。。。。 #include#include#include#include#include#include#includeusing namespace std;const int N=100005; int n,m;int ans[2000005];int ch[2000005][30],tot,fail[2000005],last[2000005]

2017-02-10 09:10:27 367 1

原创 bzoj2527(整体二分)

第一道整体二分，实际上就是锻炼分治思想 #include#include#include#include#include#includeusing namespace std;typedef long long ll;const int N=300005;const ll inf=1e9+10;int n,m,k;struct aa{ ll p;int ans;

2017-02-10 08:53:10 334

原创 bzoj3531（树链剖分+动态开点线段树）

每一个颜色建一个线段树神方法，用主席树的计算方法，因为一个点在线段树中只会产生log个点，所以总的点数是在n log n的级别内的所以均摊下来不会MLE #include#include#include#include#include#includeusing namespace std;const int N=100005;int n,C,Q;int w[N]

2017-02-09 12:46:48 322

原创 bzoj4012(动态点分治+卡常数)

这是一种类型的动态点分治动态点分治，关键还是要在均摊n的空间复杂度内存下所有东西。这个就要充分利用stl，比如vector每一个点存以这个点为根点分治的信息。对于询问一个点的路径时，就是沿着点分治树，不断朝fa走，每走一层统计一下，因为分治树可以保证在log层内，时间复杂度同阶 #include#include#include#include#incl

2017-02-08 23:06:10 578

原创 bzoj2653(可持久化线段树)

新姿势注意区间的合并问题，比如最大前缀和最大后缀的合并，表示被这里卡了好长时间 #include#include#include#include#include#include#define fi first#define se second#define MK(a,b) make_pair((a),(b))#define pii pairusing namespa

2017-02-08 11:47:11 295

原创 poj2528(动态开点线段树——过不了)

#include#include#include#include#includeusing namespace std;const int N=80005;int n,l[N],r[N],tot=0,rt=1;struct aa{ int lc,rc;bool pan;}a[N*28];void up(int i){ int l=a[i].lc,r=a[i].rc;

2017-02-07 11:37:36 398

原创 bzoj2120(带修改莫队或树状数组套主席树)

带修改莫队模板第一关键字：左端点的块第二：右端点块第三：前面的修改次数，这里称time#include#include#include#include#includeusing namespace std;const int N=10005;int n,m;int block,pos[N],col[N];int query_num;struct aa{

2017-02-07 10:25:29 1580

原创 bzoj2160(manacher)

manacher复习可以按照自己思路来写#include#include#include#include#includeusing namespace std;typedef long long ll;const ll mod=19930726;int n,m,p[1000005];ll k,f[1000005];char s[1000005];ll aa(ll

2017-02-06 17:19:57 313

原创 bzoj2957(线段树应用)

线段树维护区间上升子序序列长度，其中在up的时候是通过递归在深度log的时间内合并的。也就是说线段树可能可以干更多的事。 #include#include#include#include#includeusing namespace std;const int N=100005;struct aa{ int l,r; int len;double mx;}a[N*4

2017-02-06 15:38:40 220

原创 bzoj1833数位dp（据说是模板）

woc，恶心了我半天，对于1--9还好处理，但是0这个东西总是要特殊处理，很烦人。最后想到0也一样处理，然后减去不合法的就是前导0的数量就好据说是模板，我都费这么大劲，好弱啊#include#include#include#include#includeusing namespace std;typedef long long ll;ll f[15],A,B,g[

2017-02-06 08:37:43 582

原创 bzoj3053

k维最近点对。要求输出前m近点对，用priority_queue存前几名就好，注意估价函数剪枝 #include#include#include#include#include#include#define fi first#define se second#define pii pair#define MK(a,b) make_pair((a),(b))#defi

2017-02-05 14:59:34 323

原创 bzoj2628 kdtree 模板

#include#include#include#include#includeusing namespace std;const int N=1000005;int ans,n,m,t,x,y;int rt,D;struct aaa{ int d[2]; int mx[2],mi[2]; int l,r;}a[N];bool cmp(aaa a,aaa b)

2017-02-05 10:53:40 1172

原创 bzoj1246（树状数组）

树状数组的灵活运用，维护的是最大值，因为整个数组就是一个前缀最大值，所以可以用实现，求一个前缀最大值，和更新pos之后的最大值。很好的运用，多回顾思考 #include#include#include#include#includeusing namespace std;const int N=20005;int n;int pos[N][6];int t[N*5

2017-02-04 16:25:45 615

原创 cf_13E (分块水lct)

同bzoj2002 弹飞绵羊基本思想还是，均衡修改和询问的复杂度，降到n sqrt n的 #include#include#include#include#includeusing namespace std;const int N=200005;int n,m,block;int end[N],pos[N],cnt[N],next[N],a[N];void

2017-02-03 13:01:55 257

原创 bzoj3122(bsgs)

被取模卡了一天............... #include#include#include#include#include#includeusing namespace std;typedef long long ll;void exgcd(ll a,ll b,ll &g,ll &x,ll &y) {if(!b) g=a,x=1,y=0;else exgcd(b,a

2017-01-31 23:16:00 289

原创 bzoj2209(splay)

debug很爽，表示细节错误一个有一个。注意：1：在更新打标记时，要把原始数据和维护数据一起更新！！2：在序列问题中，查找一个数只能用size找排名来找，因为，序列可能翻转！！#include#include#include#include#include#includeusing namespace std;const int N=100005;int n,m,a[

2017-01-30 13:33:26 191

原创 vjudge 数据结构刷题记录

hdu4010#include#include#include#include#include#includeusing namespace std;const int N=300005;int n,q;int u[N],v[N];int fa[N],ch[N][2],w[N],rev[N],add[N],mx[N];stack s;bool isroot(int u

2017-01-29 09:10:36 596

空空如也

空空如也