ThreeWater--CSDN博客

原创可持久化trie树

https://www.nowcoder.com/acm/contest/104/H 就是区间里找一个值和x异或起来最大，多次查询#include <bits/stdc++.h>using namespace std;typedef double ll;const int N=1e5+5;struct node{ int c[2],val;}tree[N*40...

2018-04-26 19:18:04 435

原创主席树poj2104

主席树：其实就是开了n个前缀线段树，但是每次只更新logn个节点信息，达到可以利用历史信息来求得所需答案其最简单的应用就是区间第k大以下是大致的建树过程 #include<cstdio>#include<algorithm>#include <iostream>using namespace std;const int N=1e5+10;...

2018-04-26 10:37:15 282

原创划分树（数第几大）

#include <bits/stdc++.h>using namespace std;const int N=1e5+10;int tree[30][N];//表示每层每个位置的值int sorted[N];//已经排序好的数int toleft[30][N];//表示第i层从1到i有数分入左边void build(int l,int r,int dep){ if(l==r)

2017-11-07 19:52:53 686

原创线性基+树链剖分（bzoj4568）

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=20005;const int m_base=60;ll read(){ long long x=0,f=1; char ch=getchar(); while (ch<'0' || ch>'9') {if (ch=

2017-11-03 22:49:41 247

原创矩阵快速幂（new 模板

第一种ju jumul(ju a,ju b){//矩阵乘法 int i,j,k; ju c; c.CSH(); for(i=0;i<n;i++) for(j=0;j<n;j++) if(a.a[i][j]) for(k=0;k<n;k++) c.a[i]

2017-10-20 20:06:22 264

转载 2-sat模版（转自acm再见）

//2-sat模版const int maxn=10005*3;int n,m;int a[maxn],b[maxn];struct note{ int to; int nxt;}edge[maxn*2];int head[maxn];int ip;int dfn[maxn],low[maxn],sccno[maxn],cnt,scc,instack[maxn];

2017-10-18 21:25:50 228

原创线段树模板

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define ls l,mid,rt<<1#define rs mid+1,r,rt<<1|1inline int MAX(int a,int b) {return a>b?a:b;}const int N=50005;int sum[N<<2];voi

2017-10-10 18:30:33 576

原创 hdu6184 (过题全靠抖

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=1e5+5;int vis[N];vector<int> q[N],low,up;unordered_set<ll> mp;unordered_map<ll,int> cnt;int main(){ int n,m;

2017-09-06 16:08:12 490

原创三元环的个数

#include<bits:stdc++.h>using namespace std;typedef long long ll;const int N=1e5+5;int vis[N];vector<int> q[N],low,up;set<ll> mp;int main(){ int n,m; while(~scanf("%d%d",&n,&m)) {

2017-09-06 15:20:35 701

原创 hdu6191（字典树合并）

字典树合并，记得释放内存#include <bits/stdc++.h>using namespace std;typedef long long ll;int a[100005];vector<pair<int,int> > que[100005];vector<int> qq[100005];int ans[100005];struct node{ struct node

2017-09-05 17:39:12 482

原创线性序列模版

typedef long long ll;// 线性序列求第n项const ll mod=1000000007;ll quick_pow(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}const int N=10010;ll res[N],base[N],_c[N]

2017-08-26 14:41:05 586

原创异或的应用

从一堆其他数都出现偶数次，只有一个数出现奇数次，O(n)求这个数异或一遍即可。从一堆其他数都出现偶数次，只有两个数出现奇数次，O(n)求这两个数。先异或一遍，得a^b的值，然后找到一位为1的位置，则a位置上为1，b位置为0（或反之）这样就能将所有数，分成两组，该位为0和该位为1的情况，分别异或一遍，得a,b

2017-08-17 09:42:31 250

原创 1~n的异或和

ll xor_n(ll n){ ll t=n&3; if (t&1) return t/2ull^1; return t/2ull^n;}

2017-08-17 09:39:13 2046

很多语言都提供了 lambda 表达式，如 Python，Java 8。lambda 表达式可以方便地构造匿名函数，如果你的代码里面存在大量的小函数，而这些函数一般只被调用一次，那么不妨将他们重构成 lambda 表达式。C++11 的 lambda 表达式规范如下：[ capture ] ( params ) mutable exception attribute -> ret { body }

2017-08-15 09:42:07 193

原创 hdu6069

先枚举素因子，再枚举区间，每次跨越素数长度#include<bits/stdc++.h>using namespace std;typedef long long ll;int INF=0x3f3f3f3f;ll p[200005],cn=0,d[1000005];ll aa[1000005],bb[1000005];int main(){ for(ll i=2; i<=100

2017-08-06 14:07:35 282

原创 HDU4609 NTT||FFT

先用NTT求出两两组合的方案数然后就能o(n) 求出能组成三角形的方案数 NTT:#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=4e5+10;const ll mod=( 1ll << 47 ) * 7 * 4451 + 1 ;const ll g=3;ll mul( ll

2017-08-02 22:20:14 287

原创 51nod扒下来的蜜汁大数乘法

#include<iostream>#include<stdio.h>#include<string.h>#include<math.h>#include<algorithm>#include<iomanip>#include<stdlib.h>#include <time.h>using namespace std;typedef long long ll;typedef un

2017-08-02 15:23:00 417

原创 FFT&&FWT&&NTT

FFT是计算卷积的，就是 FFT大数乘法模版：#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>using namespace std;const int N = 500005;const double pi = acos(-1.0);char s1[N],s2[N];int len,res[N]

2017-08-02 15:22:00 721

原创 hdu6059 字典树维护数位统计异或对数

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=5e5+5;void read(int &ret){ret=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();for(;ch>='0'&&ch<='9';ch=getchar())

2017-08-02 14:53:24 342

原创 HDU 6058 维护最近k个比本身大的数

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=5e5+5;int read(){ int ret=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); for(; ch>='0'&&ch<=

2017-08-01 21:08:57 834 1

原创 hdu2586 lca+rmq

#include<bits/stdc++.h>using namespace std;const int N=40010;const int M=20;int s;struct node{ int v,w; node() {} node(int vv,int ww) { v=vv; w=ww; }};vector

2017-07-19 11:56:34 237

原创 codeforces 830B 树状数组

#include <bits/stdc++.h>using namespace std;typedef long long ll;int read(){int ret=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';retur

2017-07-18 10:05:18 295

原创最大三角形

#include <bits/stdc++.h>using namespace std;typedef long long ll;ll read(){ ll ret=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); for(; ch>='0'&&ch<='9'; ch=getchar()) re

2017-07-15 21:45:28 375

原创 codeforces 830A

第一眼看到就觉得是二分答案，但是没有仔细去想，就放弃了。#include <bits/stdc++.h>using namespace std;typedef long long ll;ll read(){ ll ret=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); for(; ch>='0

2017-07-14 22:28:52 370

原创区间最多约数

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=1e7+5,M=3200;vector<int> prime;int pri[M]={0};int mx,ans;int pricnt;int li,ri;void f(){ pri[0]=pri[1]=1; f

2017-07-08 11:04:31 328

原创 rmq(区间最值)

RMQ是英文Range Maximum(Minimum) Query的缩写，即区间最值。其预处理为O(nlogn) ,查询为Ｏ(１), 不支持修改。 RMQ的原理实际上是动态规划，我们用A[1..N]表示一组数，用[Li,Ri]表示题目中所涉及到询问区间。设F[i,j]表示从a[i]到a[i+2^j-1]这个范围内的最大值，也就是以a[i]为起点连续个数的最大值，由于元素个数为2^j个，所以从

2017-07-05 16:40:21 1288

原创第k长边的最小值

二分答案res，如果权值<=res,为0，否则为1，跑dij，如果dis>=k ,则说明res还能再大一点#include <bits/stdc++.h>using namespace std;typedef long long ll;int n,m,k;int edge[10005],cnt;int g[105][105],vis[105],dis[105];int mp[105][1

2017-07-04 15:24:49 260

原创 1021区间dp-51nod

#include<bits/stdc++.h>using namespace std;#define pb push_backtypedef long long ll;ll dp[105][105],a[105];ll sum[105];int main(){ int n; scanf("%d",&n); for(int i=0;i<=n;i++)

2017-05-10 22:23:25 144

转载 KM算法

转至 http://www.cnblogs.com/wenruo/p/5264235.html现在有N男N女，男生和女生每两个人之间有好感度，我们希望把他们两两配对，并且最后希望好感度和最大。怎么选择最优的配对方法呢？首先，每个妹子会有一个期望值，就是与她有好感度的男生中最大的好感度。男生呢，期望值为0，就是，，，只要有一个妹子就可以啦，不挑~~这样，我们把每个人的期望值标出来。然后，开始配对。配对

2017-04-06 21:50:37 366

原创二分图无权匹配之匈牙利算法

hdu：2063 有n个男生,m个女生，然后有k个爱慕关系，然后让你找出最大的匹配数。#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;int k,m,n,ans,a[505][505],used[505],to[50

2017-03-28 22:11:23 202

原创二分图匹配基本概念

最大匹配数：最大匹配的匹配边的数目最小点覆盖数：选取最少的点，使任意一条边至少有一个端点被选择最大独立数：选取最多的点，使任意所选两点均不相连最小路径覆盖数：对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。定理1：最大匹配数 = 最小点覆盖数（这是 Konig 定理）定理2：最大匹配数 = 最大独立数定理3：最小

2017-03-28 11:16:40 4137

原创 pta basin 1002

#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <queue>#include <map>#include <cmath>#include <iostream>#include <set>#include <vector>#define INF 0x3f3f3f3f

2017-03-12 18:11:52 330

原创 pta basin 1001

#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <queue>#include <map>#include <cmath>#include <iostream>#include <set>#include <vector>#define INF 0x3f3f3f3f

2017-03-12 18:05:16 187

原创 PAT（basin）

1001：

2017-03-12 18:04:55 351

原创多维最短路。

注意点：看代码注释#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <queue>#include <map>#include <cmath>#include <iostream>#include <set>#include <vector>#define INF

2017-03-12 18:00:54 309

原创堆判断

#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <queue>#include <map>#include <cmath>#include <iostream>#include <set>#include <vector>#define INF 0x3f3f3f3f

2017-03-11 10:32:56 314

原创 hdu2586 lca

lca裸题#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <queue>#include <map>#include <cmath>#include <iostream>#define INF 0x3f3f3f3fusing namespace std;const i

2017-03-09 21:06:42 185

原创 LCA离线 hiho1067

dfs(u)//marge和find为并查集合并函数和查找函数{ for each(u,v) //访问所有u子节点v { dfs(v); //继续往下遍历 marge(u,v); //合并v到u上标记v被访问过; } for each(u,e) //访问所有和u有询问关系的e

2017-03-09 19:05:33 203

原创 poj1986 (树链剖分+线段树或者LCA+RMQ)

求树上任意两点的距离#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <iostream>#include <queue>#define INF 0x3f3f3f3fusing namespace std;int n,m;#include <vector>const i

2017-03-07 08:58:29 321

原创 hiho#1181 欧拉路2

在这个例子中：L1: 1-2-6-5-1 L2: 2-3-7-2 L3: 3-4-8-3 第一步时我们将L1压入栈S，同时我们用一个数组Path来记录我们出栈的顺序：S: [1 2 6 5 1] Path: 然后出栈到节点2时我们发现了2有其他路径，于是我们把2的另一条路径加入：S: 1 [2 3 7 2] Path: 1 5 6 此时L2已经走完，然后再开始弹出元素，直到我们发现3有

2017-03-06 19:00:39 216

umlstar5.0.2版本

空空如也