• 等级
  • 15039 访问
  • 183 原创
  • 15 转发
  • 31527 排名
  • 10 评论
  • 11 获赞

BZOJ4894 矩阵外向树&&辗转相除消元

外向树需要把度数矩阵改成入度因为取模,高斯消元要在整数下进行有一种辗转相除消元法,可以不用求逆元,而且非常好写,复杂度最后求代数余子式的时候去掉的应该是根的那一行和那一列#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constllN=310,M=1000000007;lla...

2019-02-10 11:26:00

BZOJ3534 矩阵树

#include<bits/stdc++.h>usingnamespacestd;constintN=55;doublea[N][N],A[N][N];voidgauss(intn){ for(inti=1;i<=n;++i){ for(intj=i;j<=n;++j){ if(fabs(a[j][i])>1e-8){ ...

2019-02-09 16:39:09

BZOJ3436 差分约束

#include<bits/stdc++.h>usingnamespacestd;constintN=2e4+10;intNext[N],head[N],ver[N],edge[N],d[N],tot,v[N];voidadd(intx,inty,intz){ ver[++tot]=y,Next[tot]=head[x],head[x]=tot,edge[...

2019-02-09 13:28:56

BZOJ3309 线性筛

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e7;intp[N+10],cnt,v[N+10],u[N+10];llg[N+10];voidinit(){ u[1]=1; for(inti=2;i<=N;++i){ if(!v[i]){ ...

2019-02-09 11:14:48

BZOJ3211 线段树

一道很早之前就见过的题,一直没写过暴力更新打标记就ok#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e5+10;llA[N];structSegmenTree{ structsegmenttree{ intl,r;llval;boolover...

2019-02-08 18:31:15

BZOJ3173 Rope&&BIT

突然发现有rope这样一个神奇的东西实现原理好像是块状链表然后套BIT就好#include<bits/stdc++.h>#include<ext/rope>#definerope__gnu_cxx::ropeusingnamespacestd;constintN=1e5+10;intans[N];structBIT{ intT[...

2019-02-08 17:08:13

BZOJ 3172 HASH&&FIND

看见网上题解全是AC自动机HASH应该也可以吧洛谷上HASH过了bzoj交后不到1s告诉我超时,你的时限可是10s啊(雾后来想了一下,应该是空间开太大了HASH代码:#include<bits/stdc++.h>usingnamespacestd;typedefunsignedlonglongll;constintN=1e6;llp[...

2019-02-08 15:40:29

BZOJ3144 DINIC

神奇的建图!!#include<bits/stdc++.h>usingnamespacestd;constintN=45*45*45+10,M=300010,inf=1<<30;constintdx[]={1,0,-1,0,0};constintdy[]={0,-1,0,1,0};intP,Q,R,D,Next[M],d[N],head[N...

2019-02-08 14:53:17

BZOJ2957 线段树

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e5+10;structSegmentTree{ intl,r,ans;doubleval; #definel(x)Tree[x].l #definer(x)Tree[x].r #defineans(...

2019-02-08 11:11:09

BZOJ3122 BSGS

高中数学+BSGS#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;llPow(llx,lly,llmod){ llans=1; for(;y;y>>=1){ if(y%2==1)ans=ans*x%mod; x=x*x%mod; } returnans;...

2019-02-08 11:10:09

海洋学知识点整理

海洋学预习01绪论海洋学的研究内容:​ 既有海水的运动规律,海洋中的物理、化学、生物、地质的过程及其相互作用的基础理论。02地球海洋概观科氏力的特点:​ 只有运动的物体才会受到科氏力的影响,科氏力不影响物体运动的速度,只影响物体运动的方向,北半球科氏力为运动方向的右侧,南半球为左侧。地球的圈层结构:内圈:地壳、地幔、地核外圈:水圈、大气圈、生物圈海洋固有的形态特...

2019-01-01 18:58:11

西安赛记

这次西安赛,,额,,,周六:考完四级去流亭坐飞机,下了飞机又做了三个小时的车到了酒店,告诉我们下午六点没来的自动取消预定,现在一间房间都没了?????无语然后打算五个人挤一间房????之后找了一家附近的唯一有房间的,三个人在高架路上走了一公里,还没走到,发现那个地方巨阴森,为了安全,果断撤然后找了他们会务组,他们说沟通有问题,又给我们找了个地方,快十点才住进去之后打了两...

2018-12-17 21:40:02

牛客练习赛34 F 主席树

这题和我之前做的mex原理等价比赛的时候虚树开的太长了爆内存的时候返回的wa我一直以为是代码写的有问题其实权值线段树的长开n+1就够了代码只有39行#include<bits/stdc++.h>usingnamespacestd;constintN=3e5+10;structContinueTree{intl,r,Min,sum;...

2018-12-14 22:30:32

BZOJ5301 莫队

#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+10;intblock,pos[N],A[N],k,ans,B[N],ANS[N];structQuery{intl,r,id;booloperator<(constQuerya)const{ret...

2018-12-13 21:37:35

HDU5528 迪利克雷卷积

被卡常了wuwuwu,这道题最后也没过,本机测试随机满数据不到2s,20000个1e94s这种做法比较奇葩,我估计没人会这么做这道题的本质是左边那个希腊符号是欧拉函数,右边的是因子之和,都是积性函数,数论卷积后还是积性函数所以n因式分解,化成答案变成几个积性函数的积总复杂度 啊,计蒜客上A了详细的写下这道题的题解:容易的看出,答案是:       等...

2018-12-13 14:15:12

BZOJ4260 Trie

字典树完美解决#include<bits/stdc++.h>usingnamespacestd;constintN=4e5+10;intT[N<<5][2],A[N],B[N],C[N],tot;voidinsert(intx){ intp=1; for(inti=1<<30;i;i>>=1){ inty=(...

2018-12-13 09:31:20

BZOJ3732 LCA

倍增同时维护链上最大#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;inthead[N],Next[N],ver[N],edge[N],mf[N][20],f[N][20],d[N],fa[N],tot,t;queue<int>q;structP{ intx,y,z;}A...

2018-12-12 14:42:57

BZOJ3631 LCA

根本不用树链剖分直接类似数组加个标记dfs就行#include<bits/stdc++.h>usingnamespacestd;constintN=3e5+10;intA[N],ver[N*2],Next[N*2],head[N],d[N],DP[N],f[N][20],t,tot;queue<int>q;voidadd(intx,int...

2018-12-10 19:05:34

解决斜率优化问题的一个玄学奇葩方法

这是一个最坏情况n^2,但本机各种随机数据测试都接近o(n)的时间,HDU,POJ,BZOJ上运行时间也只是该题最短时间的两三倍,而且1e6数据还没开读入挂。但是只是随机数据下接近线性,但是如果故意造数据,随便卡。BZOJ3437:时限10sPOJ1180:时限1sHDU3507:时限1s这样写的前提是,x变量随着r单调递增。以后这类题可以前莽一发试试...

2018-12-09 12:02:08

POJ1180 斜率优化

#include<iostream>usingnamespacestd;typedeflonglongll;constintN=1e5+10;llT[N],F[N],ANS[N],S[N],s;intmain(){intn,s;cin>>n>>s;for(inti=1;i<=n;++i)cin...

2018-12-09 11:48:34

Gipsy_Danger

关注
  • 中国 山东省 青岛市
奖章
  • 持之以恒
  • 1024勋章