• 等级
  • 11472 访问
  • 172 原创
  • 15 转发
  • 33193 排名
  • 7 评论
  • 11 获赞

牛客练习赛34 F 主席树

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

2018-12-14 22:30:32

BZOJ5301 莫队

#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int block,pos[N],A[N],k,ans,B[N],ANS[N]; struct Query{ int l,r,id; bool operator <(const Query a) const{ ret...

2018-12-13 21:37:35

HDU5528 迪利克雷卷积

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

2018-12-13 14:15:12

BZOJ4260 Trie

字典树完美解决 #include<bits/stdc++.h> using namespace std; const int N=4e5+10; int T[N<<5][2],A[N],B[N],C[N],tot; void insert(int x){ int p=1; for(int i=1<<30;i;i>>=1){ int y=(...

2018-12-13 09:31:20

BZOJ3732 LCA

倍增同时维护链上最大 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int head[N],Next[N],ver[N],edge[N],mf[N][20],f[N][20],d[N],fa[N],tot,t; queue<int> q; struct P{ int x,y,z; }A...

2018-12-12 14:42:57

BZOJ3631 LCA

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

2018-12-10 19:05:34

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

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

2018-12-09 12:02:08

POJ1180 斜率优化

#include<iostream> using namespace std; typedef long long ll; const int N=1e5+10; ll T[N],F[N],ANS[N],S[N],s; int main(){ int n,s; cin>>n>>s; for(int i=1;i<=n;++i)cin...

2018-12-09 11:48:34

BZOJ3437 斜率优化

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10; ll A[N],B[N],F[N],P[N],S[N],DP[N]; int main(){ //freopen("1.in","r",stdin); int n; scanf("%d",&n); ...

2018-12-09 11:38:42

BZOJ3524 主席树

大水题 本来这个主席树写的是bzoj2489,结果发现是个假算法 然后顺手改了改把这道题A了 最近写主席树越来越6了呢 #include<bits/stdc++.h> using namespace std; const int N=5e5; int A[N+10],tot,R[N+10]; struct HisTree{ int l,r,sum; #define l(x...

2018-12-09 11:37:07

牛客练习赛33

这题WildCow学长出的 C不想写结果最后中奖了2333 A:水题 #include<bits/stdc++.h> using namespace std; typedef long long ll; ll l,r,x; ll F(ll y){ return y/x; } int main(){ int T; cin>>T; whi...

2018-12-07 22:29:57

Python 版线段树

class Tree(object): def __init__(self,l,r): self.l=l self.r=r self.value=0 mid=(l+r)/2 if(l<r): self.left=Tree(l,mid); self.righ...

2018-12-05 22:29:53

好像是时候该退役了

自己太垃圾了 学物理去了

2018-12-05 11:36:54

BZOJ 4553 CDQ

本质是对时间的分治  #include<bits/stdc++.h> using namespace std; const int N=1e5+10; struct P{ int l,r,val,id; }A[N]; bool cmp1(P a,P b){return a.l<b.l;} bool cmp2(P a,P b){return a.val<b.val...

2018-12-02 10:49:22

Codeforces Round 522C

 DP加指针反向找 #include<bits/stdc++.h> using namespace std; const int N=2e5+10; int B[N][6],A[N],n; void OUT(int x){ vector<int> V; V.push_back(x); for(int i=n;i>1;--i){ V.push_back(B...

2018-11-28 15:47:30

Codeforce Round 524 F 可持久化线段树

好题  #include<bits/stdc++.h> using namespace std; const int N=3e5+10; struct SegmentTree{ int p,l,r,Max; }T[N*20]; int cnt,R[N],n,m,k; void insert(int &root,int l,int r,int x,int val){ ...

2018-11-25 19:38:35

11.22 样程

A: 求最小生成树 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int tot=0; struct P{ int x,y,z; }A[N]; int fa[N]; int get(int x){ if(x==fa[x])return x; return fa[x]=get(fa[x]); ...

2018-11-22 19:06:12

11.16 作业样程

DFS  Order #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int head[N],Next[N],ver[N],tot; void add(int x,int y){ ver[++tot]=y,Next[tot]=head[x],head[x]=tot; } void dfs(int x...

2018-11-18 19:10:59

只是出于我对ACM的热爱,以及不想让他们有我去年的遗憾罢了

无奈

2018-11-14 21:32:37

训练赛题解

A: #include<bits/stdc++.h> using namespace std; int n; int A[20],V[20]; bool P(int x){ for(int i=2;i*i<=x;++i){ if(x%i==0)return 0; } return 1; } void dfs(int x){ if...

2018-11-12 21:08:31

Gipsy_Danger

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