@Apojacsleam
2018-11-09T04:45:47.000000Z
字数 150724
阅读 9322
模板 NOIP 2018 比赛 提高组
本文旨在用于NOIP2018考前复习。
时间原因,作者无法一一亲自调试其中的程序,也因如此,有一部分程序来自于互联网,如果您觉得这侵犯了您的合法权益,请联系Apojacsleam(QQ1729338463)删除。
对于给您造成的不便和困扰,我表示深深的歉意。
本文仅用于学习,禁止任何人或组织用于商业用途
本文中,标记*的为选学算法,在NOIP中较少涉及。
/*Coded by Apojacsleam*/#include<cstdio>#include<cctype>int readin(){int res=0;char ch=getchar();bool XX=false;for(;!isdigit(ch);ch=getchar())(ch=='-') && (XX=true);for(;isdigit(ch);ch=getchar())res=(res<<3)+(res<<1)+(ch^48);return XX?-res:res;}
/*Coded by Apojacsleam*/#include<cstdio>#include<cctype>inline char getcha(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}int readin(){int res=0;char ch=getcha();bool XX=false;for(;!isdigit(ch);ch=getcha())(ch=='-') && (XX=true);for(;isdigit(ch);ch=getcha())res=(res<<3)+(res<<1)+(ch^48);return XX?-res:res;}
/*Coded by Apojacsleam*/#include<cstdio>#include<cctype>inline double dbread(){double X=0,Y=1.0; int w=0; char ch=0;while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}while(isdigit(ch)) X=X*10+(ch^48),ch=getchar();ch=getchar();//读入小数点while(isdigit(ch)) X+=(Y/=10)*(ch^48),ch=getchar();return w?-X:X;}
/*Coded by Apojacsleam*/#include<cstdio>void writeout(int x){if(x<0) putchar('-'),x=-x;if(x>9) writeout(x/10);putchar(x%10+48);}
/*Coded by Apojacsleam*/#include<cstdio>char pbuf[100000],*pp=pbuf;void push(const char c) {if(pp-pbuf==100000) fwrite(pbuf,1,100000,stdout),pp=pbuf;*pp++=c;}void write(int x){static int sta[35];int top=0;do{sta[top++]=x%10,x/=10;}while(x);while(top) push(sta[--top]+'0');}//请大家在程序结束前加上一句fwrite(pbuf,1,pp-pbuf,stdout);pp=pbuf;//防止出现没输出完成的类似错误
欧几里德算法又称辗转相除法,是指用于计算两个正整数的最大公约数。应用领域有数学和计算机两个方面。计算公式。
/*Coded by Apojacsleam*///problemID:http://www.codevs.cn/problem/1212#include<cstdio>int gcd(int a,int b){return b?gcd(b,a%b):a;}int a,b;int main(){scanf("%d%d",&a,&b);printf("%d",gcd(a,b));}
复杂度
扩展欧几里德算法是用来在已知求解一组,使它们满足贝祖等式: (解一定存在,根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P1082#include<cstdio>int exgcd(int a,int b,int &x,int &y){if(!b){x=1,y=0;return a;}int gcd=exgcd(b,a%b,x,y),t=x;x=y,y=t-(a/b)*x;return gcd;}int a,b,x,y;int main(){scanf("%d%d",&a,&b);exgcd(a,b,x,y);printf("%d",(x%b+b)%b);return 0;}
复杂度
乘法逆元,是指数学领域群中任意一个元素,都在中有唯一的逆元,具有性质,其中为该群的单位元。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3811#include<cstdio>#define N 3000001long long a[N],f[N],g[N];int n,mod;long long ksm(long long a,long long b){long long res=1;while(b){if(b&1) res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}signed main(){scanf("%d%d",&n,&mod);f[0]=1;for(int i=1;i<=n;i++) f[i]=(f[i-1]*i)%mod;g[n]=ksm(f[n],mod-2);for(int i=n;i>=1;i--) g[i-1]=(g[i]*i)%mod;for(int i=1;i<=n;i++) a[i]=(f[i-1]*g[i])%mod;for(int i=1;i<=n;i++)printf("%lld\n",a[i]);return 0;}
复杂度,常数略大
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3811#include<cstdio>#define N 3000001int n,p;long long a[N];int main(){scanf("%d%d",&n,&p);a[1]=1;for(int i=2;i<=n;i++) a[i]=(p-(p/i))*a[p%i]%p;for(int i=1;i<=n;i++) printf("%lld\n",a[i]);return 0;}
复杂度
顾名思义,快速幂就是快速算底数的次幂。其时间复杂度为 ,与朴素的相比效率有了极大的提高。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P1226#include<cstdio>long long ksm(long long a,long long b,long long mod){int res=1;while(b){if(b&1) res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res%mod;}int main(){long long a,b,c;scanf("%lld%lld%lld",&a,&b,&c);printf("%lld^%lld mod %lld=%lld",a,b,c,ksm(a,b,c));return 0;}
复杂度
筛法是一种简单检定素数的算法。据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274~194年)发明的,又称埃拉托斯特尼筛法(sieve of Eratosthenes),后来扩展到利用筛法求积性函数。
积性函数:对于函数,若满足对任意互质的数字,且,那么称函数为积性函数。
狄利克雷卷积:对于函数,定义它们的卷积为。
两个积性函数的狄利克雷卷积仍为积性函数。
积性函数都可以用线性筛筛出来
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3383#sub#include<cstdio>#include<cstring>#define N 10000001bool vis[N];int n;void prime(){vis[0]=vis[1]=false;for(register int i=2;i<=n;i++)if(vis[i]){for(register int j=i+i;j<=n;j+=i)vis[j]=false;}return;}int q,x;int main(){memset(vis,true,sizeof(vis));scanf("%d%d",&n,&q);prime();for(int i=1;i<=q;i++){scanf("%d",&x);puts(vis[x]?"Yes":"No");}return 0;}
复杂度
#include<cstdio>#include<cstring>#define MAXN 100005#define MAXL 1299710int prime[MAXN];int check[MAXL];int tot = 0;memset(check, 0, sizeof(check));for (int i = 2; i < MAXL; ++i){if (!check[i]){prime[tot++] = i;}for (int j = 0; j < tot; ++j){if (i * prime[j] > MAXL) break;check[i*prime[j]] = 1;if (i % prime[j] == 0) break;}}
复杂度
复杂度
下面的isprime数组里,1表示不是素数,0表示是素数,请大家注意
isprime[1] = 1; mu[1] = 1;for(int i = 2; i < N; ++i){if(!isprime[i]){ prime[++num] = i; mu[i] = -1; }for(int j = 1; j <= num && i * prime[j] < N; ++j){isprime[i * prime[j]] = 1;if(i % prime[j]) mu[i * prime[j]] = -mu[i];else{ mu[i * prime[j]] = 0; break; }}}
isprime[1] = 1; phi[1] = 1;for(int i = 2; i < N; ++i){if(!isprime[i]){ prime[++num] = i; phi[i] = i - 1; }for(int j = 1; j <= num && i * prime[j] < N; ++j){isprime[i * prime[j]] = 1;if(i % prime[j]) phi[i*prime[j]] = phi[i] * (prime[j] - 1);else{ phi[i * prime[j]] = phi[i] * prime[j]; break; }}}
isprime[1]=1,d[1]=1;for(int i=2;i<N;++i){if(!isprime[i]){prime[++num]=i;d[i]=2;pred[i]=1;}for(int j=1;j<=num&&i*prime[j]<N;++j){isprime[i*prime[j]]=1;if(i%prime[j])d[i*prime[j]]=d[i]*d[prime[j]],pred[i*prime[j]]=1;else{pred[i*prime[j]]=pred[i]+1;d[i*prime[j]]=d[i]/(pred[i]+1)*(pred[i]+2);break;}}}
void Prepare(){isprime[1]=1;f[1]=mu[1]=1;for(int i=2;i<N;++i){if(!isprime[i]){prime[++num]=i;f[i]=i+1;mu[i]=-1;sumd[i]=1+i;powd[i]=i;}for(int j=1;j<=num&&i*prime[j]<N;++j){isprime[i*prime[j]]=1;if(i%prime[j]){sumd[i*prime[j]]=1+prime[j];powd[i*prime[j]]=prime[j];f[i*prime[j]]=f[i]*f[prime[j]];}else{powd[i*prime[j]]=powd[i]*prime[j];sumd[i*prime[j]]=sumd[i]+powd[i*prime[j]];f[i*prime[j]]=f[i]/sumd[i]*sumd[i*prime[j]];break;}}}}
中国剩余定理是中国古代求解一次同余式组的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期(公元5世纪)的数学著作《孙子算经》卷下第二十六题,叫做“物不知数”问题。
在OI中,中国剩余定理主要解决以下问题:
#include<cstdio>#define N 101int n,m[N],a[N],lcm=1,d;int exgcd(int a,int b,int &x,int &y){if(!b){x=1,y=0;return a;}int re=exgcd(b,a%b,x,y),tmp=x;x=y,y=tmp-(a/b)*y;return re;}int work(){int x,y,re=0;for(int i=1;i<=n;i++) lcm=lcm*m[i];for(int i=1;i<=n;i++){int kl=lcm/m[i];d=exgcd(kl,m[i],x,y);x=(x%m[i]+m[i])%m[i];re=(re+a[i]*x*kl)%lcm;}return re;}int main(){scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d%d",&m[i],&a[i]);;printf("%d",work());return 0;}
复杂度
大步小步法(Baby-Step-Giant-Step,简称BSGS),可以较高效的求解形如(是素数)的同余方程。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P4884#include<cstdio>#include<map>#include<cmath>using namespace std;__int128 FastPow(__int128 a,__int128 k,__int128 p){__int128 ans=1;while(k){if(k&1) (ans*=a)%=p;(a*=a)%=p;k>>=1;}return ans;}__int128 BSGS(__int128 a,__int128 b,__int128 p){map<__int128,__int128>hash;hash.clear();b%=p;__int128 t=(__int128)sqrt((double)p)+1;for(__int128 j=0;j<t;j++){__int128 val=b*FastPow(a,j,p)%p;hash[val]=j;}a=FastPow(a,t,p);if(!a)return(b==0)?1:-1;for(__int128 i=0;i<=t;i++){__int128 val=FastPow(a,i,p);__int128 j=hash.find(val)==hash.end()?-1:hash[val];if(j>=0&&i*t-j>=0) return i*t-j;}return -1;}__int128 k,m;int main(){scanf("%lld%lld",&k,&m);__int128 ans=BSGS(10,(9*k+1)%m,m);printf("%lld",ans);return 0;}
复杂度
求解类似于的算式。其中,应可以快速计算前缀和。
/*Coded by Apojacsleam*/#include<cstdio>#include<ctime>long long n,ans;int main(){scanf("%lld",&n);for(long long l=1,r;l<=n;l=r+1){r=n/(n/l);ans=(r-l+1)*(n/l);}printf("%lld",ans);return 0;}
复杂度
有一类问题,要求我们将一个正整数,分解为两个非平凡因子的乘积。
显然我们需要先检测是否为素数如果是素数将无解,可以使用Miller-Rabin算法来进行测试。
Pollard-Rho是一个非常玄学的方式,用于在的期望时间复杂度内计算合数的某个非平凡因子。事实上算法导论给出的是,是的某个最小因子,满足与互质。但是这些都是期望,未必符合实际。但事实上Pollard-Rho算法在实际环境中运行的相当不错。
#include <cstdio>#include <algorithm>#define rep(i, s, t) for(int i = s; i <= t; ++i)typedef long long ll;ll H;ll pls(ll a, ll b, ll p){ll res = 0;for(; b; b >>= 1, a = (a+a)%p)if(b & 1) res = (res+a)%p;return res%p;}ll pow(ll a, ll b, ll p){ll res = 1;for(; b; b >>= 1, a = pls(a, a, p))if(b & 1) res = pls(res, a, p)%p;return res % p;}bool M(ll p){ll x[60] = {0}, s = 20;ll rest = p-1, t = 0;while(!(rest%2)){t ++;rest >>= 1;}while(s--){ll a = rand()%(p-1)+1;x[0] = pow(a, rest, p);rep(i, 1, t){x[i] = pow(x[i-1], 2, p)%p;if(x[i] == 1)if((x[i-1] != 1) && (x[i-1] != p-1)) return false;}if(x[t] ^ 1) return false;}return true;}ll gcd(ll a, ll b){while(b){ll t = a%b;a = b;b = t;}return a;}ll P(ll p){ll c = rand()%(p-1)+1, x1 = rand()%(p-1)+1, x2 = x1;for(ll i = 2, k = 2; true; ++i){x1 = (pls(x1, x1, p) + c)%p;ll G = gcd(p, (x2-x1+p)%p);if(G > 1 && G < p) return G;if(x2 == x1) return p;if(i == k) x2 = x1, k <<= 1;}}void solve(long long n){if(n == 1) return;if(M(n)){H = std::min(H , n);return;}long long p = n;while(p == n) p = P(p);solve(p);solve(n/p);}int main(){int _;scanf("%d", &_);while(_--){ll p;H = 1LL << 54;scanf("%lld", &p);solve(p);if(H ^ p)printf("%lld\n", H);else puts("Prime");}return 0;}
复杂度
图是计算机内部一种常见的数据结构,分为无向图和有向图。
在无向图中,若图中任意一对顶点都是连通的,则称此图是连通图。
在有向图中,若任意一对顶点和间存在一条从到的路径和从到的路径,则称此图是强连通图。
无向图的一个极大连通子图称为该图的一个连通分量。
有向图的一个极大强连通子图称为该图的一个强连通分量。
在图的每条边上加上一个数字作权,也称代价,带权的图称为网。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3916#include<cstdio>#include<vector>using namespace std;#define N 1001bool vis[N];int n,m,ans[N],g[N][N];void dfs(int now,int start){vis[now]=true;ans[now]=start;for(int i=1;i<=n;i++)if(!vis[i]&&g[now][i]) dfs(i,start);}int main(){scanf("%d%d",&n,&m);int x,y;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);g[y][x]=1;}for(int i=n;i>=1;i--)if(!vis[i]) dfs(i,i);for(int i=1;i<=n;i++)printf("%d%c",ans[i],i==n?'\n':' ');return 0;}
复杂度
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3916#include<cstdio>#include<vector>using namespace std;#define N 100001vector<int> g[N];bool vis[N];int n,m,ans[N];void dfs(int now,int start){vis[now]=true;ans[now]=start;for(int i=0;i^g[now].size();i++)if(!vis[g[now][i]]) dfs(g[now][i],start);}int main(){scanf("%d%d",&n,&m);int x,y;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);g[y].push_back(x);}for(int i=n;i>=1;i--)if(!vis[i]) dfs(i,i);for(int i=1;i<=n;i++)printf("%d%c",ans[i],i==n?'\n':' ');return 0;}
复杂度,常数略大
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3916#include<cstdio>#define M 100001#define N 100001struct Edge{int nxt,to,val;}e[M];int n,m,head[N],tot;bool vis[N];void AddEdge(int u,int v){e[++tot].to=v,e[tot].nxt=head[u],head[u]=tot;}int ans[N];void dfs(int now,int start){vis[now]=true;ans[now]=start;for(int i=head[now];i;i=e[i].nxt)if(!vis[e[i].to]) dfs(e[i].to,start);}int main(){scanf("%d%d",&n,&m);int x,y;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);AddEdge(y,x);}for(int i=n;i>=1;i--)if(!vis[i]) dfs(i,i);for(int i=1;i<=n;i++)printf("%d%c",ans[i],i==n?'\n':' ');return 0;}
复杂度
如果一个图存在一笔画,则一笔画的路径叫做欧拉路,如果最后又回到起点,那这个路径叫做欧拉回路。
我们定义奇点是指跟这个点相连的边数目有奇数个的点。对于能够一笔画的图,我们有以下两个定理。
定理1:存在欧拉路的条件:图是连通的,有且只有2个奇点。
定理2:存在欧拉回路的条件:图是连通的,有0个奇点。
两个定理的正确性是显而易见的,既然每条边都要经过一次,那么对于欧拉路,除了起点和终点外,每个点如果进入了一次,显然一定要出去一次,显然是偶点。对于欧拉回路,每个点进入和出去次数一定都是相等的,显然没有奇点。
求欧拉路的算法很简单,使用深度优先遍历即可。
根据一笔画的两个定理,如果寻找欧拉回路,对任意一个点执行深度优先遍历;找欧拉路,则对一个奇点执行DFS。
#include<iostream>#include<cstring>using namespace std;#define maxn 101int g[maxn][maxn];//此图用邻接矩阵存储int du[maxn];//记录每个点的度,就是相连的边的数目int circuit[maxn];//用来记录找到的欧拉路的路径int n,e,circuitpos,i,j,x,y,start;void find_circuit(int i)//这个点深度优先遍历过程寻找欧拉路{int j;for(j=1;j<=n;j++)if(g[i][j]==1)//从任意一个与它相连的点出发{g[j][i]=g[i][j]=0;find_circuit(j);}circuit[++circuitpos]=i;//记录下路径}int main(){memset(g,0,sizeof(g));cin>>n>>e;for(i=1;i<=e;i++){cin>>x>>y;g[y][x]=g[x][y]=1;du[x]++;//统计每个点的度du[y]++;}start=1;//如果有奇点,就从奇点开始寻找,这样找到的就是for(i=1;i<=n;i++)//欧拉路。没有奇点就从任意点开始,if(du[i]%2==1)//这样找到的就是欧拉回路。(因为每一个点都是偶点)start=i;circuitpos=0;find_circuit(start);for(i=1;i<=circuitpos;i++)cout<<circuit[i]<<" ";cout<<endl;return 0;}
复杂度
欧拉回路是指不重复地走过所有路径的回路,而哈密尔顿环是指不重复地走过所有的点,并且最后还能回到起点的回路。
#include <queue>#include <cstdio>#include <set>#include <string>#include <stack>#include <cmath>#include <climits>#include <map>#include <cstdlib>#include <iostream>#include <vector>#include <algorithm>#include <cstring>#define max(a,b) (a>b?a:b)using namespace std;typedef long long(LL);typedef unsigned long long(ULL);const double eps(1e-8);char B[1<<15],*S=B,*T=B,ch;#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)int aa,bb; int F(){while(ch=getc(),(ch<'0'||ch>'9')&&ch!='-'); ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0'; return bb?aa:-aa;}#define N 100010int n,swp,cnt,z[N]; long long ans;#define swap(a,b) (swp=a,a=b,b=swp)#define abs(x) (x>0?x:-(x))#define max(a,b) (a>b?a:b)#define cmax(x) (ans<x?ans=x:1)struct P {int x,y,id,nx,ny;} p[N];bool operator<(const P&a,const P&b) {return a.nx<b.nx||a.nx==b.nx&&a.ny<b.ny;}class Graph{private:int et,la[N],ufs[N],tot;struct D{int x,y,v;bool operator<(const D&a)const {return v<a.v;}} d[N<<2];struct E {int to,v,nxt;} e[N<<1];int gf(int x) {return ufs[x]==x?x:ufs[x]=gf(ufs[x]);}void adde(int x,int y,int v){e[++et]=(E) {y,v,la[x]},la[x]=et;e[++et]=(E) {x,v,la[y]},la[y]=et;}public:Graph() {et=1;}void add(int x,int y,int v) {d[++tot]=(D) {x,y,v};}void make(){std::sort(d+1,d+1+tot);for(int i=1; i<=n; i++)ufs[i]=i; cnt=n;for(int i=1,x,y; i<=tot; i++)if((x=gf(d[i].x))!=(y=gf(d[i].y))){ufs[x]=y,cnt--,ans+=d[i].v,adde(d[i].x,d[i].y,d[i].v);}}} G;struct D {int x,n;} d[N];bool operator<(const D&a,const D&b) {return a.x<b.x;}#define dis(i,j) (abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y))void ins(int i){for(int t=p[i].ny; t<=cnt; t+=t&-t)if(z[t]==0||p[z[t]].x+p[z[t]].y<p[i].x+p[i].y)z[t]=i;}int query(int i){int f=0;for(int t=p[i].ny; t>0; t-=t&-t)if(z[t]&&(f==0||p[z[t]].x+p[z[t]].y>p[f].x+p[f].y))f=z[t];return f;}void work(){for(int i=1; i<=n; i++)p[i].nx=p[i].x-p[i].y,p[i].ny=p[i].y;std::sort(p+1,p+1+n);for(int i=1; i<=n; i++)d[i]=(D) {p[i].ny,i};std::sort(d+1,d+1+n); d[n+1].x=d[n].x; cnt=1;for(int i=1; i<=n; i++){p[d[i].n].ny=cnt;if(d[i].x!=d[i+1].x)cnt++;}memset(z,0,sizeof(z));for(int i=1,j; i<=n; ins(i++))if(j=query(i))G.add(p[i].id,p[j].id,dis(i,j));}int main(){n=F();for(int i=1; i<=n; i++)p[i]=(P) {F(),F(),i}; work();for(int i=1; i<=n; i++)swap(p[i].x,p[i].y); work();for(int i=1; i<=n; i++)p[i].y=-p[i].y; work();for(int i=1; i<=n; i++)swap(p[i].x,p[i].y); work(); G.make();printf("%lld\n",ans);}
如果一个系统由n个变量和m个约束条件组成,形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统(system of difference constraints)。亦即,差分约束系统是求解关于一组变量的特殊不等式组的方法。
//problemID:http://www.poj.org/problem?id=1201#include <cstdio>#include <cstring>#include <queue>#include <cctype>#include <algorithm>using namespace std;template<class T>inline void read(T &res) {char c; res = 0;while (!(isdigit(c = getchar())));while (isdigit(c)) res = res * 10 + c - '0', c = getchar();}const int N = 50005;const int INF = 0x3f3f3f3f;int head[N], vis[N], d[N];struct edge{int v, d, next;edge(int v = 0, int d = 0, int n = 0) : v(v), d(d), next(n){}}e[N<<2];int n, ma, mi = INF, k;queue<int> q;void add(int u, int v, int d) {e[k] = edge(v, d, head[u]);head[u] = k++;}int spfa() {fill(d+mi+1, d+ma+1, -INF);vis[mi] = 1;q.push(mi);while (!q.empty()) {int t = q.front(); q.pop();vis[t] = 0;for (int i = head[t]; i != -1; i = e[i].next) {int x = e[i].v;if (d[x] < d[t] + e[i].d) {d[x] = d[t] + e[i].d;if (!vis[x]) vis[x] = 1, q.push(x);}}}return d[ma];}int main() {int k = 0;memset(head, -1, sizeof(head));read(n);for (int i = 0; i < n; i++) {int a, b, c;read(a); read(b); read(c);add(a, b+1, c);ma = max(ma, b); mi = min(mi, a);}ma++;for (int i = mi; i < ma; i++) add(i, i+1, 0), add(i+1, i, -1);printf("%d\n", spfa());return 0;}
Prim算法,图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点,且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现;并在1957年由美国计算机科学家罗伯特·普里姆独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3366#include<cstdio>#include<algorithm>#define inf 2147483647#define maxn 5005#define maxm 200005struct edge{int v,w,next;}e[maxm<<1];//注意是无向图,开两倍数组int head[maxn],dis[maxn],cnt,n,m,tot,now=1,ans;//已经加入最小生成树的的点到没有加入的点的最短距离//比如说1和2号节点已经加入了最小生成树,那么dis[3]就等于min(1->3,2->3)bool vis[maxn];void add(int u,int v,int w){e[++cnt].v=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;}int prim(){//先把dis数组附为极大值for(int i=2;i<=n;++i){dis[i]=inf;}//这里要注意重边,所以要用到minfor(int i=head[1];i;i=e[i].next){dis[e[i].v]=std::min(dis[e[i].v],e[i].w);}while(++tot<n)//最小生成树边数等于点数-1{int minn=inf;//把minn置为极大值vis[now]=1;//标记点已经走过//枚举每一个没有使用的点//找出最小值作为新边//注意这里不是枚举now点的所有连边,而是1~nfor(int i=1;i<=n;++i){if(!vis[i]&&minn>dis[i]){minn=dis[i];now=i;}}ans+=minn;//枚举now的所有连边,更新dis数组for(int i=head[now];i;i=e[i].next){int v=e[i].v;if(dis[v]>e[i].w&&!vis[v]){dis[v]=e[i].w;}}}return ans;}int main(){scanf("%d%d",&n,&m);for(int i=1,u,v,w;i<=m;++i){scanf("%d%d%d",&u,&v,&w);add(u,v,w),add(v,u,w);}printf("%d",prim());return 0;}
复杂度
#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<cmath>#include<queue>#include<vector>#include<climits>using namespace std;#define maxn 99999999struct E{int next;int c;int zhi;}e[1005000];inline int read(){char ls=getchar();for (;ls<'0'||ls>'9';ls=getchar());int x=0;for (;ls>='0'&&ls<='9';ls=getchar()) x=x*10+ls-'0';return x;}int last[100500];int dis[100500];int n,m;int ans;int k;struct node{int num;node(){}node(int h){num=h;}bool operator <(const node & p)const{return dis[p.num]<dis[num];}};int located[100500];int heap[300500];int heap_size;inline void put(int d){int now,next;heap[++heap_size]=d;now=heap_size;located[d]=now;while(now>1){next=now>>1;if(dis[heap[now]]>=dis[heap[next]])break;located[d]=next;located[heap[next]]=now;swap(heap[now],heap[next]);now=next;}return;}inline void change(int d){int now,next;now=located[d];while(now>1){next=now>>1;if(dis[heap[now]]>=dis[heap[next]])break;located[d]=next;located[heap[next]]=now;swap(heap[now],heap[next]);now=next;}return;}inline int get(){int now,next,res;res=heap[1];heap[1]=heap[heap_size--];now=1;located[heap[1]]=1;located[res]=0;while(now*2<=heap_size){next=now*2;if(next<heap_size&&dis[heap[next+1]]<dis[heap[next]])++next;if(dis[heap[now]]<=dis[heap[next]])break;located[heap[now]]=next;located[heap[next]]=now;swap(heap[next],heap[now]);now=next;}return res;}int main(){n=read(),m=read();for(int i=1;i<=m;i++){int a1,b1,c1;a1=read();b1=read();c1=read();e[++k].next=b1;e[k].c=c1;e[k].zhi=last[a1];last[a1]=k;e[++k].next=a1;e[k].c=c1;e[k].zhi=last[b1];last[b1]=k;}for(int i=2;i<=n;i++)dis[i]=maxn;for(int j=last[1];j;j=e[j].zhi){int y=e[j].next;int c=e[j].c;if(c<dis[y])dis[y]=c;}for(int i=2;i<=n;++i)put(i);for(int i=1;i<=n-1;++i){int x=get();ans+=dis[x];for(int j=last[x];j;j=e[j].zhi){int y=e[j].next;int c=e[j].c;if(c<dis[y]){dis[y]=c;change(y);}}}cout<<ans<<endl;return 0;}
复杂度
求加权连通图的最小生成树的算法。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3366#include<cstdio>#include<cctype>#include<algorithm>inline char getcha(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}int readin(){char ch=getcha();int sum=0;while(!(ch>='0'&&ch<='9'))ch=getcha();while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=getcha();return sum;}int n,m,fa[5001],tot;struct EDGE{int x,y,val;}e[200001];bool cmp(EDGE A,EDGE B){return A.val<B.val;}int Find(int x){return ((x==fa[x])?(fa[x]):(fa[x]=Find(fa[x])));}long long ans=0;int main(){n=readin();m=readin();for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=m;i++){e[i].x=readin();e[i].y=readin();e[i].val=readin();}std::sort(e+1,e+m+1,cmp);int Root1,Root2;for(int i=1;i<=m;i++){Root1=Find(e[i].x);Root2=Find(e[i].y);if(Root1!=Root2){fa[Root1]=Root2;tot++;ans+=e[i].val;}if(tot==n-1){printf("%lld",ans);return 0;}}puts("orz");return 0;}
复杂度
#include<cstdio>#include<algorithm>using namespace std;#define maxm 300001#define inf 2147483647#define maxn 100001struct Edge{int u,v,w,next;}e[maxm<<1];struct qj{int ma,ma2;}q[maxn<<2];struct Edge1{int u,v,w;bool operator < (const Edge1 &x)const{return w<x.w;//按照边权排序}}edge[maxm];int n,m,vis[maxm],ans=inf,head[maxn],cnt,fa[maxn],mtree;void add(int u,int v,int w){e[++cnt].v=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;}//前向星加边namespace smallesttree{int find(int x){while(x!=fa[x]) x=fa[x]=fa[fa[x]];return x;}//并查集找祖先void init(){for(int i=1;i<=n;i++) fa[i]=i;//预处理并查集for(int i=0;i<m;i++) scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);}void kruskal(){init();sort(edge,edge+m);int T=0;for(int i=0;i<m;++i){int eu=find(edge[i].u),ev=find(edge[i].v);//寻找祖先if(eu!=ev){add(edge[i].u,edge[i].v,edge[i].w),add(edge[i].v,edge[i].u,edge[i].w);mtree+=edge[i].w;//记录子树大小fa[ev]=eu;//合并vis[i]=1;//标记该边为树边if(++T==n-1)break;//边数等于节点数+1即为一颗树}}}}//求出最小生成树namespace treecut{int dep[maxn],father[maxn],top[maxn],W[maxn],a[maxn],size[maxn],son[maxn],seg[maxn],col;//dep:深度father:父亲节点top:重链的顶端W:到根节点的距离a:点的权值//size:子树大小son:重儿子seg:在线段树中的序号(dfs序)void dfs1(int u,int fr){dep[u]=dep[fr]+1;size[u]=1;father[u]=fr;for(int i=head[u];i;i=e[i].next){int v=e[i].v;if(v!=fr){W[v]=W[u]+e[i].w;//W为每一个点到根节点的距离dfs1(v,u);size[u]+=size[v];if(size[v]>size[son[u]])son[u]=v;}}}//预处理出dep、size、father以及sonvoid dfs2(int now,int fi){top[now]=fi;seg[now]=++col;a[col]=W[now]-W[father[now]];//a为点的权值(它与之父亲节点边的权值)(相当于前缀和)if(!son[now])return;dfs2(son[now],fi);for(int i=head[now];i;i=e[i].next){int v=e[i].v;if(v!=son[now]&&v!=father[now])dfs2(v,v);}}//预处理出每个节点的top、seg以及权值//树剖模板就不解释了#define ls k<<1#define rs k<<1|1bool CMP(int a,int b){return a>b;}int getse(int x,int g,int z,int c){int a[4]={x,g,z,c};sort(a,a+4,CMP);for(int i=1;i<3;++i)if(a[i]!=a[0]) return a[i];return 0;}//找到两个区间的最大值和严格次大值(四个数)的最大值与严格次大值//就是合并两个区间的最大值和严格次大值void build(int k,int l,int r){if(l==r){q[k].ma=a[l];return;}int mid=(l+r)>>1;build(ls,l,mid),build(rs,mid+1,r);q[k].ma=max(q[ls].ma,q[rs].ma);q[k].ma2=getse(q[ls].ma,q[rs].ma,q[ls].ma2,q[rs].ma2);}//预处理出区间最大值与次大值qj query(int k,int l,int r,int ll,int rr){if(ll>r||rr<l)return(qj){-inf,-inf};if(ll<=l&&rr>=r)return(qj){q[k].ma,q[k].ma2};int mid=(l+r)>>1;qj t1=query(ls,l,mid,ll,rr),t2=query(rs,mid+1,r,ll,rr);return(qj){max(t1.ma,t2.ma),getse(t1.ma,t2.ma,t1.ma2,t2.ma2)};}//查询区间的区间的最大值与次小值int LCA(int u,int v,int d){int need=-inf;while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]])swap(u,v);qj temp=query(1,1,n,seg[top[u]],seg[u]);u=father[top[u]];need=max(need,(temp.ma==d)?temp.ma2:temp.ma);//严格次小边(如果temp.ma==k就是非严格次小)}if(dep[u]<dep[v])swap(u,v);//找到LCAqj temp=query(1,1,n,seg[v]+1,seg[u]);return max(need,(temp.ma==d)?temp.ma2:temp.ma);//同上}void init(){dfs1(1,0),dfs2(1,1),build(1,1,n);}}//树链剖分int main(){scanf("%d%d",&n,&m);smallesttree::kruskal();//求出最小生成树treecut::init();//预处理for(int i=0;i<m;++i){if(vis[i])continue;//枚举所有非树边(没有在最小生成树的边)int temp=mtree+edge[i].w-treecut::LCA(edge[i].u,edge[i].v,edge[i].w);if(ans>temp&&temp!=mtree+e[i].w&&temp>mtree)ans=temp;}printf("%d",ans);return 0;}
复杂度
#include<iostream>#include<math.h>#include<stdio.h>#include<string.h>using namespace std;#define zero(x) ((x>0? x:-x)<1e-15)int const MAXN = 100;double a[MAXN][MAXN];double b[MAXN][MAXN];int g[53][53];int n,m;double det(double a[MAXN][MAXN],int n){int i, j, k, sign = 0;double ret = 1, t;for (i = 0; i < n; i++)for (j = 0; j < n; j++)b[i][j] = a[i][j];for (i = 0; i < n; i++){if (zero(b[i][i])){for (j = i + 1; j < n; j++)if (!zero(b[j][i]))break;if (j == n)return 0;for (k = i; k < n; k++)t = b[i][k], b[i][k] = b[j][k], b[j][k] = t;sign++;}ret *= b[i][i];for (k = i + 1; k < n; k++)b[i][k] /= b[i][i];for (j = i + 1; j < n; j++)for (k = i + 1; k < n; k++)b[j][k] -= b[j][i] * b[i][k];}if (sign & 1)ret = -ret;return ret;}void build(){while (m--){int a, b;scanf("%d%d", &a, &b);g[a-1][b-1]=g[b-1][a-1]=1;}}int main(){int cas;scanf("%d", &cas);while (cas--){scanf("%d%d", &n, &m);memset(g,0,sizeof(g));build();memset(a,0,sizeof(a));for (int i=0; i<n; i++){int d=0;for (int j=0; j<n; j++)if (g[i][j])d++;a[i][i]=d;}for (int i=0; i<n; i++)for (int j=0; j<n; j++)if (g[i][j])a[i][j]=-1;double ans = det(a, n-1);printf("%0.0lf\n", ans);}return 0;}
复杂度
Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
/*Coded by Apojacsleam*///problemID:http://codevs.cn/problem/2602/#include<cstdio>#include<cmath>#include<cstring>struct Node{double x,y;}a[101];double f[101][101];int n,m;double calc(int b,int c){return sqrt((a[b].x-a[c].x)*(a[b].x-a[c].x)+(a[b].y-a[c].y)*(a[b].y-a[c].y));}int main(){memset(f,127,sizeof(f));scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);scanf("%d",&m);int b,c;for(int i=1;i<=m;i++){scanf("%d%d",&b,&c);f[b][c]=f[c][b]=calc(b,c);}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)(f[i][k]+f[k][j]<f[i][j])&&(f[i][j]=f[i][k]+f[k][j]);scanf("%d%d",&b,&c);printf("%.2lf",f[b][c]);return 0;}
复杂度
迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
/*Coded by Apojacsleam*/#include<iostream>#define inf 2147483647using namespace std;int e[1001][1001],dis[1001],visit[1001];int n,m;int main(){int t1,t2,t3;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)(i==j)?(e[i][j]=0):(e[i][j]=inf);for(int i=1;i<=m;i++) cin>>t1>>t2>>t3,e[t1][t2]=t3;//初始化dis数组,1号顶点到其余各个顶点的初始距离for(int i=1;i<=n;i++) dis[i]=e[1][i];//初始化visit数组for(int i=1;i<=n;i++) visit[i]=0;visit[1]=1;int u,min;for(int i=1;i<=n-1;i++){//找离1号顶点最近的顶点min=inf;for(int j=1;j<=n;j++) if(visit[j]==0&&dis[j]<min) min=dis[j],u=j;visit[u]=1;for(int v=1;v<=n;v++){if(e[u][v]<inf){if(visit[v]==0&&dis[v]>dis[u]+e[u][v]) dis[v]=dis[u]+e[u][v];}}}for(int i=1;i<=n;i++) cout<<dis[i]<<endl;return 0;}
复杂度
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P4779#include<cstdio>#include<queue>using namespace std;#define N 100001#define M 200001struct Edge{int nxt,to,val;}e[M<<1];int n,m,tot,head[N],dis[N],S;bool vis[N];priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;void AddEdge(int u,int v,int w){e[++tot].to=v;e[tot].val=w;e[tot].nxt=head[u];head[u]=tot;}void Dijkstra(){dis[S]=0;q.push(make_pair(0,S));while(!q.empty()){int x=q.top().second;q.pop();if(vis[x]) continue;vis[x]=true;for(int i=head[x];i;i=e[i].nxt)if(dis[e[i].to]>dis[x]+e[i].val){dis[e[i].to]=dis[x]+e[i].val;q.push(make_pair(dis[e[i].to],e[i].to));}}}int main(){scanf("%d%d%d",&n,&m,&S);for(int i=1;i<=n;i++) dis[i]=1e9;int x,y,z;for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);AddEdge(x,y,z);}Dijkstra();for(int i=1;i<=n;i++) printf("%d%c",dis[i],i==n?'\n':' ');}
复杂度
Bellman-Ford算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就完成。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P4779#include<cstdio>#include<cstring>#include<algorithm>int dis[10010];int origin[10010],destination[10010],value[10010],S;int n,m;int main(){scanf("%d%d%d",&n,&m,&S);for(int i=1;i<=m;i++)scanf("%d%d%d",&origin[i],&destination[i],&value[i]);memset(dis,0x7f,sizeof(dis));dis[1]=0;for(int i=1;i<=n-1;i++)for(int j=1;j<=m;j++)dis[destination[j]]=std::min(dis[destination[j]],dis[origin[j]]+value[j]);for(int i=1;i<=n;i++) printf("%d ",dis[i]);return 0;}
复杂度
SPFA 算法是 Bellman-Ford算法的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3371#include<cstdio>#include<vector>using namespace std;const int maxn=10001,inf=1000000000;struct node{int to,z;};int p[maxn],d[maxn];vector<node>e[maxn];int q[maxn*100];int main(){int m,n,s;scanf("%d%d%d",&n,&m,&s);for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);node t;t.to=y;t.z=z;e[x].push_back(t);}for(int i=1;i<=n;i++)d[i]=inf;d[s]=0,q[1]=s,p[s]=1;int f=0,l=1;while(f<l){f++;int x=q[f];for(int i=0;i<e[x].size();i++){int u=e[x][i].to,v=e[x][i].z;if(d[u]>d[x]+v){d[u]=d[x]+v;if(!p[u]) q[++l]=u,p[u]=1;}}p[x]=0;}for(int i=1;i<=n;i++) printf("%d ",d[i]<inf?d[i]:2147483647);return 0;}
SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同,为。
Johnson算法可以求解每对顶点之间的最短路径。对于稀疏图,该算法在要好于Floyd算法。算法与Floyd算法类似,每对顶点之间的最短距离用二维数组D表示;如果图中存在负环,算法将输出警告信息。Johnson算法把Bellman-Ford算法和Dijkstra算法作为其子函数。
public class JohnsonAlgo {double D[][];int P[][];GraphLnk G;/*** 构造函数*/public JohnsonAlgo(GraphLnk G) {this.G = G;D = new double[G.get_nv()][G.get_nv()];P = new int[G.get_nv()][G.get_nv()];}public boolean Johnson(){// 创建一个图_GGraphLnk _G = new GraphLnk(G.get_nv() + 1);for(int i = 0; i < G.get_nv(); i++){for(Edge e = G.firstEdge(i);G.isEdge(e); e = G.nextEdge(e))_G.setEdgeWt(e.get_v1(), e.get_v2(), G.getEdgeWt(e));}// 在原图的基础上添加一个顶点adint ad = _G.get_nv() - 1;for(int i = 0; i < G.get_nv(); i++){_G.setEdgeWt(ad, i, 0);}// 首先调用Bellman-Ford算法,以ad为起始点MinusWeightGraph swg = new MinusWeightGraph(_G);swg.BellmanFord(ad);// h函数int h[] = new int[G.get_nv() + 1];System.out.println("Bellman-Ford算法结果:");for(int i = 0; i < _G.get_nv(); i++)System.out.print((h[i] = (int)swg.D[i]) + "\t");System.out.println();for(int i = 0; i < _G.get_nv() - 1; i++)for(Edge e = G.firstEdge(i);G.isEdge(e); e = G.nextEdge(e))// 检测有没有负环if(h[e.get_v2()] > h[e.get_v1()] + _G.getEdgeWt(e)){System.out.println("图中有负环。");return false;}// 如果没有则重赋权else{int u = G.edge_v1(e), v = G.edge_v2(e);int wt = (int) (G.getEdgeWt(e) +h[G.edge_v1(e)] - h[G.edge_v2(e)]);G.setEdgeWt(u, v, wt);}System.out.println("重赋权后的各条边的权值:");for(int u = 0; u < G.get_nv(); u++){for(Edge e = G.firstEdge(u);G.isEdge(e);e = G.nextEdge(e)){System.out.print(u + "-" + e.get_v2() +" " + G.getEdgeWt(e) + "\t");}System.out.println();}// Dijkstra 算法求解每一个顶点的最短路径树SingleSourceShortestPaths sssp = new SingleSourceShortestPaths(G);for(int i = 0; i < G.get_nv(); i++){sssp.Dijkstra(i);System.out.println("\n第" + i + "顶点Dijkstra结果:");for(int j = 0; j < G.get_nv(); j++){System.out.print(sssp.D[j] + "\t");D[i][j] = sssp.D[j] + h[j] - h[i];P[i][j] = sssp.V[j];}System.out.println();}return true;}}
复杂度
#include <cstdio>#include <cstring>#include <queue>#include <vector>#include <algorithm>using namespace std;const int maxn = 1000 + 5;const int INF = 0x3f3f3f3f;struct Node {int v, c, flag;Node (int _v = 0, int _c = 0, int _flag = 0) : v(_v), c(_c), flag(_flag) {}bool operator < (const Node &rhs) const {return c > rhs.c;}};struct Edge {int v, cost;Edge (int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}};vector<Edge>E[maxn];bool vis[maxn][2];int dist[maxn][2];void Dijkstra(int n, int s) {memset(vis, false, sizeof(vis));for (int i = 1; i <= n; i++) {dist[i][0] = INF;dist[i][1] = INF;}priority_queue<Node>que;dist[s][0] = 0;que.push(Node(s, 0, 0));while (!que.empty()) {Node tep = que.top(); que.pop();int u = tep.v;int flag = tep.flag;if (vis[u][flag]) continue;vis[u][flag] = true;for (int i = 0; i < (int)E[u].size(); i++) {int v = E[u][i].v;int cost = E[u][i].cost;if (!vis[v][0] && dist[v][0] > dist[u][flag] + cost) {dist[v][1] = dist[v][0];dist[v][0] = dist[u][flag] + cost;que.push(Node(v, dist[v][0], 0));que.push(Node(v, dist[v][1], 1));} else if (!vis[v][1] && dist[v][1] > dist[u][flag] + cost) {dist[v][1] = dist[u][flag] + cost;que.push(Node(v, dist[v][1], 1));}}}}void addedge(int u, int v, int w) {E[u].push_back(Edge(v, w));}int main() {int n, m, v, w;while (scanf("%d", &n) != EOF) {for (int i = 0; i <= n; i++) E[i].clear();for (int u = 1; u <= n; u++) {scanf("%d", &m);for (int j = 0; j < m; j++) {scanf("%d%d", &v, &w);addedge(u, v, w);}}Dijkstra(n, 1);printf("%d\n", dist[n][1]);}return 0;}
复杂度
#include<bits/stdc++.h>using namespace std;const int maxd=5010;int dis[maxd];bool vis[maxd];int n,m,e;struct sd {int num, len;bool operator < (const sd &other) const {return len > other.len;}};vector<sd> edge[maxd],redge[maxd];void spfa(){memset(dis,127,sizeof(dis));dis[e]=0;queue<int> q;q.push(e);vis[e]=true;while(!q.empty()){int now=q.front(); q.pop(); vis[now]=false;for(int i=redge[now].size()-1;i>=0;--i){if(dis[redge[now][i].num]>dis[now]+redge[now][i].len)dis[redge[now][i].num]=dis[now]+redge[now][i].len;if(!vis[redge[now][i].num]){vis[redge[now][i].num]=true;q.push(redge[now][i].num);}}}}int A_star(int cnt){int ccnt=0;priority_queue<sd> q;q.push((sd){1,dis[1]});//importantwhile(!q.empty()){sd now=q.top();q.pop();if(now.num==e){ccnt++;if(cnt==ccnt){return now.len;}continue;//important}for(int i=edge[now.num].size()-1;i>=0;--i){q.push((sd){edge[now.num][i].num,now.len-dis[now.num]+edge[now.num][i].len+dis[edge[now.num][i].num]});//important}}}int main(){int us;scanf("%d%d%d",&n,&m,&e);scanf("%d",&us);int a,b,c;for(int i=1;i<=m;++i){scanf("%d%d%d",&a,&b,&c);edge[a].push_back((sd){b,c});redge[b].push_back((sd){a,c});}spfa();if(us==1) goto flag;cout<<A_star(us); return 0;flag:printf("%d",dis[1]);return 0;}
利用二进制的思想,想办法使一步一步向上搜索变成以的向上跳。需要定义一个数组,使表示节点的倍祖先。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3379#include<cstdio>#include<algorithm>#define N 500001struct Edge{int nxt,to;}e[N<<1];int n,tot,q,root,f[N][20],deep[N],head[N];void AddEdge(int u,int v){e[++tot].to=v;e[tot].nxt=head[u];head[u]=tot;}void dfs(int now){for(int i=1;i<=19;i++)f[now][i]=f[f[now][i-1]][i-1];for(int i=head[now];i;i=e[i].nxt)if(!deep[e[i].to]){deep[e[i].to]=deep[now]+1;f[e[i].to][0]=now;dfs(e[i].to);}}int LCA(int x,int y){if(deep[x]<deep[y]) std::swap(x,y);for(int i=19;i>=0;i--)if(deep[f[x][i]]>deep[y]) x=f[x][i];if(deep[x]>deep[y]) x=f[x][0];if(x==y) return x;for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return f[x][0];}int main(){scanf("%d%d%d",&n,&q,&root);deep[root]=1;int x,y;for(int i=1;i^n;i++){scanf("%d%d",&x,&y);AddEdge(x,y),AddEdge(y,x);}dfs(root);for(int i=1;i<=q;i++){scanf("%d%d",&x,&y);printf("%d\n",LCA(x,y));}return 0;}
复杂度
树链剖分,计算机术语,指一种对树进行划分的算法,它先通过轻重边剖分将树分为多条链,保证每个点属于且只属于一条链,然后再通过数据结构来维护每一条链。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3379#include<cstring>#include<iostream>#include<cctype>#include<cstdio>#include<algorithm>#define writ(x,c) write(x),putchar(c);using namespace std;inline char nc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}inline int read(){char c=0;int x=0;bool f=0;for(;!isdigit(c);c=nc()) if(c=='-') f=1;for(;isdigit(c);c=nc()) x=(x<<1)+(x<<3)+c-48;return (f ? -x : x);}void write(int x){if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0');}const int N=5e5+1;struct edge{int v,next;}e[N<<1];int n,m,root,tot,head[N],dep[N],siz[N],son[N],top[N],f[N];void add(int u,int v){e[++tot].v=v,e[tot].next=head[u],head[u]=tot;}void dfs1(int x){siz[x]=1,dep[x]=dep[f[x]]+1;for(int i=head[x];i;i=e[i].next){if(e[i].v==f[x])continue;f[e[i].v]=x;dfs1(e[i].v);siz[x]+=siz[e[i].v];if(!son[x] || siz[son[x]]<siz[e[i].v])son[x]=e[i].v;}}void dfs2(int x,int tv){top[x]=tv;if(son[x]) dfs2(son[x],tv);for(int i=head[x];i;i=e[i].next)if(e[i].v!=f[x] && e[i].v!=son[x])dfs2(e[i].v,e[i].v);}int main(){n=read(),m=read(),root=read();register int x,y;for(int i=1;i<n;++i){x=read(),y=read();add(x,y);add(y,x);}dfs1(root);dfs2(root,root);for(int i=1;i<=m;++i){x=read(),y=read();while(top[x]!=top[y]){if(dep[top[x]]>=dep[top[y]])x=f[top[x]];else y=f[top[y]];}writ(dep[x]<dep[y] ? x : y,'\n');}}
复杂度
这种算法是基于DFS和并查集来实现的。设为的父亲,为节点到根节点的距离。首先从一号根节点(记为)开始访问他的每一个子节点(记为),并用根节点与当前访问的子节点的距离更新值,即,其中表示到的距离,然后将当前子节点当做根点用上述同样步骤递归下去,并在递归回溯后将其值更新,这样的目的是保证子节点的所有子树全部被访问过。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3379#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<algorithm>#include<queue>#include<vector>#include<cctype>#define add_qedge(x,y) {ql[++qnum]={i,y,qt[x]};qt[x]=qnum;}#define top 20000000#define add_edge(x,y) {l[++num]={y,t[x]};t[x]=num;}#define max_n 500001using namespace std;int f[max_n],t[max_n],qt[max_n],lca[max_n];bool b[max_n];int i,num,qnum;char ch[top];int now_r,now_w=-1;inline void read(int &x){while (ch[now_r]<48) ++now_r;for (x=ch[now_r]-48;ch[++now_r]>=48;)x=(x<<1)+(x<<3)+ch[now_r]-48;}int q2[max_n],tail2;void write(int x){for (;x;x/=10) q2[++tail2]=x%10;for (;tail2;--tail2) ch[++now_w]=q2[tail2]+48;ch[++now_w]='\n';}struct edge{int to,next;}l[max_n<<1];struct qedge{int id,to,next;}ql[max_n<<1];struct node {int f;}T[max_n];void dfs_lca(int &x){f[x]=x;b[x]=1;int y,i;for(i=t[x];i;i=l[i].next)if((y=l[i].to)!=T[x].f){T[y].f=x;dfs_lca(y);f[y]=x;}for(i=qt[x];i;i=ql[i].next)if(b[y=ql[i].to]){while (y!=f[y]){q2[++tail2]=y;y=f[y];}lca[ql[i].id]=y;while (tail2){f[q2[tail2]]=y;--tail2;}}}int main(){ch[fread(ch,1,top,stdin)]=0;int n,m,root,x,y;read(n);read(m);read(root);for (i=1;i<n;++i){read(x);read(y);add_edge(x,y);add_edge(y,x);}for (i=1;i<=m;++i){read(x);read(y);add_qedge(x,y);add_qedge(y,x);}dfs_lca(root);for (i=1;i<=m;++i) write(lca[i]);fwrite(ch,1,now_w,stdout);}
复杂度
在计算机科学中,Kosaraju的算法(也称为Kosaraju-Sharir算法)是线性时间的算法来找到一个有向图的强连通分量。
Aho, Hopcroft 和Ullman相信这个算法是由S.RaoKosaraju在1978在一个未发表的论文上提出的。
相同的算法还从MichaSharir1981年自己出版的书上被单独的发现,这个算法利用了一个事实,即转置图(同图中的每边的方向相反)具有和原图完全一样的强连通分量。
//problemID:https://www.luogu.org/problemnew/show/P3387#include<cstdio>#include<algorithm>#include<cstring>#define N 100001#define M 1000001int x[M],y[M],head[M],nxt[M],v[M],w[M],cnt;int rhead[M],rnxt[M],rv[M],rcnt;int a[N],c[N],dp[N],mark[N],stack[N],n,m,t,ans;bool vis[N];void addline(int x,int y){v[cnt]=y,nxt[cnt]=head[x],head[x]=cnt++;}void raddline(int x,int y){rv[rcnt]=y,rnxt[rcnt]=rhead[x],rhead[x]=rcnt++;}void dfs1(int x){vis[x]=true;for(int i=head[x];i!=-1;i=nxt[i])if(!vis[v[i]]) dfs1(v[i]);stack[++t]=x;return;}void dfs2(int x){mark[x]=t,c[t]+=a[x];for(int i=rhead[x];i!=-1;i=rnxt[i])if(!mark[rv[i]]) dfs2(rv[i]);return;}void dfs3(int x){if(dp[x]) return;for(int i=head[x];i!=-1;i=nxt[i]){if(!dp[v[i]]) dfs3(v[i]);dp[x]=std::max(dp[x],dp[v[i]]);}dp[x]+=c[x];return;}int main(){memset(head,-1,sizeof(head));memset(rhead,-1,sizeof(rhead));scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=m;i++){scanf("%d%d",&x[i],&y[i]);addline(x[i],y[i]);raddline(y[i],x[i]);}for(int i=1;i<=n;i++)if(!vis[i]) dfs1(i);t=0,cnt=0;for(int i=n;i>=1;i--)if(!mark[stack[i]]) t++,dfs2(stack[i]);memset(head,-1,sizeof(head));memset(nxt,-1,sizeof(nxt));memset(vis,0,sizeof(vis));for(int i=1;i<=m;i++)if(mark[x[i]]!=mark[y[i]])addline(mark[x[i]],mark[y[i]]);for(int i=1;i<=t;i++){if(!dp[i]) dfs3(i);ans=std::max(ans,dp[i]);}printf("%d\n",ans);return 0;}
复杂度
Tarjan算法是用来求有向图的强连通分量的。求有向图的强连通分量的Tarjan算法是以其发明者Robert·Tarjan命名的。Robert·Tarjan还发明了求双连通分量的Tarjan算法。
Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
//problemID:https://www.luogu.org/problemnew/show/P3387#include<cstdio>#include<stack>using namespace std;const int N=10001;bool used[N];int dfn[N],low[N],p1[N],p2[N],v[N],a[N],f[N],fa[N],num,ord,ans;struct edge1{int u,nxt;}e1[N*10];struct edge2{int u,nxt;}e2[N*10];stack<int>q;void add1(int y,int x){e1[++num]=(edge1){y,p1[x]};p1[x]=num;}void add2(int x,int y){e2[++num]=(edge2){y,p2[x]};p2[x]=num;}void dfs1(int s){low[s]=dfn[s]=++ord;q.push(s),used[s]=1;for(int i=p1[s];i;i=e1[i].nxt){int u=e1[i].u;if(!dfn[u])dfs1(u),low[s]=min(low[u],low[s]);else if(used[u])low[s]=min(low[s],dfn[u]);}if(dfn[s]==low[s]){while(q.top()!=s){v[s]+=v[q.top()];fa[q.top()]=s;used[q.top()]=0,q.pop();}q.pop(),used[s]=0,fa[s]=s;}}void dfs2(int s){f[s]+=v[s];ans=max(ans,f[s]);for(int i=p2[s];i;i=e2[i].nxt){int u=e2[i].u;a[u]--,f[u]=max(f[u],f[s]);if(!a[u]) dfs2(u);}}int main(){int n,m,x,y;scanf("%d%d",&n,&m);for(int i=1;i<=n;++i) scanf("%d",&v[i]);while(m--) scanf("%d%d",&x,&y),add1(x,y);num=0;for(int i=1;i<=n;++i)if(!dfn[i]) dfs1(i);for(int i=1;i<=n;++i)for(int j=p1[i];j;j=e1[j].nxt)if(fa[i]!=fa[e1[j].u]){add2(fa[i],fa[e1[j].u]);a[fa[e1[j].u]]++;}for(int i=1;i<=n;++i)if(!a[i]&&!f[i]&&fa[i]==i) dfs2(i);printf("%d",ans);return 0;}
复杂度
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3386#include<cstdio>#include<cstring>int n,m,e,gril[1001],ans;bool f[1001][1001],vis[1001];bool dfs(int now){for(int i=1;i<=m;i++){if(f[now][i]&&(!vis[i])){vis[i]=1;if(!gril[i]||dfs(gril[i])) {gril[i]=now;return true;}}}return false;}int main(){scanf("%d%d%d",&n,&m,&e);int x,y;for(int i=1;i<=e;i++){scanf("%d%d",&x,&y);f[x][y]=true;}for(int i=1;i<=n;i++){memset(vis,false,sizeof(vis));if(dfs(i)) ans++;}printf("%d\n",ans);return 0;}
复杂度
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3386#include<cstdio>#include<cstring>struct Edge{int nxt,to;}e[1000001];int n,m,tot,q,gril[1001],head[1001],ans;bool vis[1001];void AddEdge(int u,int v){e[++tot].to=v;e[tot].nxt=head[u];head[u]=tot;}bool dfs(int now){for(int i=head[now];i;i=e[i].nxt){if(!vis[e[i].to]){vis[e[i].to]=1;if(!gril[e[i].to]||dfs(gril[e[i].to])) {gril[e[i].to]=now;return true;}}}return false;}int main(){scanf("%d%d%d",&n,&m,&q);int x,y;for(int i=1;i<=q;i++){scanf("%d%d",&x,&y);if(y>m) continue;AddEdge(x,y);}for(int i=1;i<=n;i++){memset(vis,false,sizeof(vis));if(dfs(i)) ans++;}printf("%d\n",ans);return 0;}
复杂度
/*Coded by Avalon*///problemID:https://www.luogu.org/problemnew/show/P3386#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<queue>using namespace std;const int maxn=1e6,inf=1e9;inline int read(){register int X=0;register char ch=0;while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X;}inline void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}struct edge{int next,to,c,f;}e[maxn];int head[maxn],cur[maxn],lev[maxn],s,t,n,m,tot,ed;void add(int u,int v,int c){e[tot].next=head[u],e[tot].c=c,e[tot].f=0,e[tot].to=v,head[u]=tot++;e[tot].next=head[v],e[tot].c=0,e[tot].f=0,e[tot].to=u,head[v]=tot++;}bool bfs(){memset(lev,0,sizeof(lev));queue<int> q;q.push(s);lev[s]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].to;if(!lev[v]&&e[i].c>e[i].f){q.push(v);lev[v]=lev[u]+1;}}}return lev[t]!=0;}int dfs(int u,int cpf){if(u==t) return cpf;int adf=0;for(int i=(cur[u]!=0?cur[u]:head[u]);i!=-1&&adf<cpf;i=e[i].next){int v=e[i].to;if(lev[v]==lev[u]+1&&e[i].c>e[i].f){int tmp=dfs(v,min(e[i].c-e[i].f,cpf-adf));e[i].f+=tmp,e[i^1].f-=tmp;adf+=tmp;cur[u]=i;}}return adf;}int dinic(){int maxflow=0;while(bfs()){memset(cur,0,sizeof(cur));maxflow+=dfs(s,inf);}return maxflow;}int main(){n=read(),m=read(),ed=read(),s=n+m+3,t=n+m+4;memset(head,-1,sizeof(head));for(int i=1;i<=ed;i++){int u=read(),v=read();add(u,v+n,1);}for(int i=1;i<=n;i++) add(s,i,1);for(int i=n+1;i<=m+n;i++) add(i,t,1);write(dinic()),putchar('\n');}
复杂度:由于流量为1,Dinic算法在二分图上的复杂度为
//problemID:http://www.uoj.ac/problem/80#include<bits/stdc++.h>using namespace std;typedef int ll;const int maxn=407,inf=1e9;int nl,nr,m;struct KuhnMunkres{int n;//左边0~n-1个点,右边0~n-1个点int a[maxn+5][maxn+5];int lx[maxn+5],ly[maxn+5],sla[maxn+5];//hl是左边顶标 hr是右边顶标int fl[maxn+5],fr[maxn+5];//fl[i]表示左边第i个点匹配右边哪个点 fr[i]表示右边第i个点匹配哪个点int vx[maxn+5],vy[maxn+5],pre[maxn+5];int q[maxn+5],tp;void match(int x){while(x){fr[x]=pre[x];int y=fl[fr[x]];fl[fr[x]]=x;x=y;}}void find(int x){fill(vx,vx+n+1,0);fill(vy,vy+n+1,0);fill(sla,sla+n+1,inf);q[tp=1]=x;vx[x]=1;while(1){for(int i=1;i<=tp;i++){int x=q[i];for(int y=1;y<=n;y++){int t=lx[x]+ly[y]-a[x][y];if(vy[y]||t>sla[y])continue;pre[y]=x;if(t==0){if(!fr[y]){match(y);return;}q[++tp]=fr[y];vy[y]=1;vx[fr[y]]=1;}else sla[y]=t;}}int d=inf;tp=0;for(int i=1;i<=n;i++)if(!vy[i]&&d>sla[i])d=sla[i],x=i;for(int i=1;i<=n;i++){if(vx[i])lx[i]-=d;if(vy[i])ly[i]+=d;else sla[i]-=d;}if(!fr[x]){match(x);return;}q[++tp]=fr[x];vy[x]=vx[fr[x]]=1;}}void solve(){memset(lx,0,sizeof(lx));memset(ly,0,sizeof(ly));memset(fl,0,sizeof(fl));memset(fr,0,sizeof(fr));for(int i=1;i<=n;++i) lx[i]=*max_element(a[i]+1,a[i]+n+1);for(int i=1;i<=n;++i) find(i);}}km;int main(){scanf("%d%d%d",&nl,&nr,&m);while(m--){int u,v;scanf("%d%d",&u,&v);scanf("%d",&km.a[u][v]);}km.n=max(nl,nr);km.solve();long long ans=0;for(int i=1;i<=nl;++i)ans+=km.a[i][km.fl[i]];printf("%lld\n",ans);for(int i=1;i<=nl;++i)if(km.a[i][km.fl[i]]==0) printf("0 ");elseprintf("%d ",km.fl[i]);return 0;}
复杂度
EK算法基于一个基本的方法:Ford-Fulkerson方法 即增广路方法 简称FF方法。
增广路方法是很多网络流算法的基础一般都在残留网络中实现其思路是每次找出一条从源到汇的能够增加流的路径 调整流值和残留网络 不断调整直到没有增广路为止
//problemID:https://www.luogu.org/problemnew/show/P3376#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int INF=0x7ffffff;queue <int> q;int n,m,x,y,s,t,g[201][201],pre[201],flow[201],maxflow;//g邻接矩阵存图,pre增广路径中每个点的前驱,flow源点到这个点的流量inline int bfs(int s,int t){while (!q.empty()) q.pop();for (int i=1; i<=n; i++) pre[i]=-1;pre[s]=0;q.push(s);flow[s]=INF;while (!q.empty()){int x=q.front();q.pop();if (x==t) break;for (int i=1; i<=n; i++)//EK一次只找一个增广路if (g[x][i]>0 && pre[i]==-1){pre[i]=x;flow[i]=min(flow[x],g[x][i]);q.push(i);}}if (pre[t]==-1) return -1;else return flow[t];}//increase为增广的流量void EK(int s,int t){int increase=0;while ((increase=bfs(s,t))!=-1){//迭代int k=t;while (k!=s){int last=pre[k];//从后往前找路径g[last][k]-=increase;g[k][last]+=increase;k=last;}maxflow+=increase;}}int main(){scanf("%d%d",&m,&n);for (int i=1; i<=m; i++){int z;scanf("%d%d%d",&x,&y,&z);g[x][y]+=z;}EK(1,n);printf("%d",maxflow);return 0;}
复杂度
dinic算法在EK算法的基础上增加了分层图的概念,根据从到各个点的最短距离的不同,把整个图分层。寻找的增广路要求满足所有的点分别属于不同的层,且若增广路为,点在分层图中的所属的层记为,那么应满足
//problemID:https://www.luogu.org/problemnew/show/P3376#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int inf=1e9;int n,m,x,y,z,maxflow,deep[500];//deep深度struct Edge{int next,to,dis;}edge[500];int num_edge=-1,head[500],cur[500];//cur用于复制headqueue <int> q;void add_edge(int from,int to,int dis,bool flag){edge[++num_edge].next=head[from];edge[num_edge].to=to;if (flag) edge[num_edge].dis=dis;//反图的边权为 0head[from]=num_edge;}//bfs用来分层bool bfs(int s,int t){memset(deep,0x7f,sizeof(deep));while (!q.empty()) q.pop();for (int i=1; i<=n; i++) cur[i]=head[i];deep[s]=0;q.push(s);while (!q.empty()){int now=q.front(); q.pop();for (int i=head[now]; i!=-1; i=edge[i].next){if (deep[edge[i].to]>inf && edge[i].dis)//dis在此处用来做标记 是正图还是返图{deep[edge[i].to]=deep[now]+1;q.push(edge[i].to);}}}if (deep[t]<inf) return true;else return false;}//dfs找增加的流的量int dfs(int now,int t,int limit)//limit为源点到这个点的路径上的最小边权{if (!limit || now==t) return limit;int flow=0,f;for (int i=cur[now]; i!=-1; i=edge[i].next){cur[now]=i;if (deep[edge[i].to]==deep[now]+1 && (f=dfs(edge[i].to,t,min(limit,edge[i].dis)))){flow+=f;limit-=f;edge[i].dis-=f;edge[i^1].dis+=f;if (!limit) break;}}return flow;}void Dinic(int s,int t){while (bfs(s,t))maxflow+=dfs(s,t,inf);}int main(){// for (int i=0; i<=500; i++) edge[i].next=-1;memset(head,-1,sizeof(head));scanf("%d%d",&m,&n);for (int i=1; i<=m; i++){scanf("%d%d%d",&x,&y,&z);add_edge(x,y,z,1); add_edge(y,x,z,0);}Dinic(1,n);printf("%d",maxflow);return 0;}
复杂度
ISAP(Improved Shortest Augmenting Path)也是基于分层思想的最大流算法。所不同的是,它省去了Dinic每次增广后需要重新构建分层图的麻烦,而是在每次增广完成后自动更新每个点的『标号』(也就是所在的层)
最短增广路算法是一种运用距离标号使寻找增广路的时间复杂度下降的算法。所谓的距离标号就是某个点到汇点的最少的弧的数量(即当边权为1时某个点的最短路径长度). 设点的标号为, 那么如果将满足, 且增广时只走允许弧, 那么就可以达到"怎么走都是最短路"的效果. 每个点的初始标号可以在一开始用一次从汇点沿所有反向的BFS求出.
//problemID:https://www.luogu.org/problemnew/show/P3376#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<queue>using namespace std;const int inf=1e9;queue <int> q;int m,n,x,y,z,maxflow,head[5000],num_edge=-1;int cur[5000],deep[5000],last[5000],num[5000];//cur当前弧优化; last该点的上一条边; num桶 用来GAP优化struct Edge{int next,to,dis;}edge[500];void add_edge(int from,int to,int dis,bool flag){edge[++num_edge].next=head[from];edge[num_edge].to=to;edge[num_edge].dis=dis;head[from]=num_edge;}//bfs仅用于更新deepvoid bfs(int t){while (!q.empty()) q.pop();for (int i=0; i<=m; i++) cur[i]=head[i];for (int i=1; i<=n; i++) deep[i]=n;deep[t]=0;q.push(t);while (!q.empty()){int now=q.front(); q.pop();for (int i=head[now]; i!=-1; i=edge[i].next){if (deep[edge[i].to]==n && edge[i^1].dis)//i^1是为了找反边{deep[edge[i].to]=deep[now]+1;q.push(edge[i].to);}}}}int add_flow(int s,int t){int ans=inf,now=t;while (now!=s){ans=min(ans,edge[last[now]].dis);now=edge[last[now]^1].to;}now=t;while (now!=s){edge[last[now]].dis-=ans;edge[last[now]^1].dis+=ans;now=edge[last[now]^1].to;}return ans;}void isap(int s,int t){int now=s;bfs(t);//搜出一条增广路for (int i=1; i<=n; i++) num[deep[i]]++;while (deep[s]<n){if (now==t){//如果到达汇点就直接增广,重新回到源点进行下一轮增广maxflow+=add_flow(s,t);now=s;//回到源点}bool has_find=0;for (int i=cur[now]; i!=-1; i=edge[i].next){if (deep[now]==deep[edge[i].to]+1 && edge[i].dis)//找到一条增广路{has_find=true;cur[now]=i;//当前弧优化now=edge[i].to;last[edge[i].to]=i;break;}}if (!has_find)//没有找到出边,重新编号{int minn=n-1;for (int i=head[now]; i!=-1; i=edge[i].next)//回头找路径if (edge[i].dis)minn=min(minn,deep[edge[i].to]);if ((--num[deep[now]])==0) break;//GAP优化 出现了断层num[deep[now]=minn+1]++;cur[now]=head[now];if (now!=s)now=edge[last[now]^1].to;}}}int main(){memset(head,-1,sizeof(head));scanf("%d%d",&m,&n);for (int i=1; i<=m; i++){scanf("%d%d%d",&x,&y,&z);add_edge(x,y,z,1); add_edge(y,x,z,0);}isap(1,n);printf("%d",maxflow);return 0;}
复杂度,但在非二分图上表现得比Dinic要好。
//problemID:https://www.luogu.org/problemnew/show/P4722#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<queue>using namespace std;const int MAXN=2*1e3+10;const int INF=1e8+10;inline char nc(){static char buf[MAXN],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;}inline int read(){char c=nc();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}return x*f;}int N,M,S,T;int H[MAXN];//每个节点的高度int F[MAXN];//每个节点可以流出的流量int gap[MAXN];//每个高度的数量struct node{int u,v,flow,nxt;}edge[MAXN];int head[MAXN];int num=0;//注意这里num必须从0开始inline void add_edge(int x,int y,int z){edge[num].u=x;edge[num].v=y;edge[num].flow=z;edge[num].nxt=head[x];head[x]=num++;}inline void AddEdge(int x,int y,int z){add_edge(x,y,z);add_edge(y,x,0);//注意这里别忘了加反向边}struct comp{int pos,h;comp(int pos=0,int h=0):pos(pos),h(h) {}inline bool operator < (const comp &a) const {return h<a.h;}};priority_queue<comp>q;bool Work(int u,int v,int id){int val=min(F[u],edge[id].flow);edge[id].flow-=val;edge[id^1].flow+=val;F[u]-=val;F[v]+=val;return val;}inline int HLPP(){H[S]=N;F[S]=INF;q.push(comp(S,H[S]));while(q.size()!=0){int p=q.top().pos;q.pop();if(!F[p]) continue;for(int i=head[p];i!=-1;i=edge[i].nxt)if( (p==S||H[edge[i].v]+1==H[p]) && Work(p,edge[i].v,i) && edge[i].v!=S && edge[i].v!=T)q.push( comp(edge[i].v,H[edge[i].v]) );if(p!=S && p!=T && F[p]){if( (--gap[ H[p] ])==0 )//该高度不存在{for(int i=1;i<=N;i++)if( H[p]<H[i]&&H[i]<=N && p!=S && p!=T )H[i]=N+1;//设置为不可访问}++gap[ ++H[p] ];//高度+1q.push( comp(p,H[p]) );}}return F[T];}int main(){memset(head,-1,sizeof(head));N=read(),M=read(),S=read(),T=read();for(int i=1;i<=M;i++){int x=read(),y=read(),z=read();AddEdge(x,y,z);}printf("%d", HLPP() );return 0;}
复杂度
//problemID:https://www.luogu.org/problemnew/show/P3381#include <iostream>#include <algorithm>#include <map>#include <math.h>#include <stdio.h>#include <string.h>#include <algorithm>#define MAXN 50050#define MAXN_ 5050#define INF 0x3f3f3f3fusing namespace std;struct edge{ int to,cap,cost,rev;};int n,m,flow,s,t,cap,res,cost,from,to;std::vector<edge> G[MAXN_];int dist[MAXN_],prevv[MAXN_],preve[MAXN_]; // 最短路的前驱节点 和 对应的边inline void add(){//也许你看到这里会看不懂,为什么要存一个 size 进来, 那么别急,我们下边的存反边 会用到的!G[from].push_back((edge){to,cap,cost,(int)G[to].size()});G[to].push_back((edge){from,0,-cost,(int)G[from].size()-1});}inline int read(){int x=0;char c=getchar();bool flag=0;while(c<'0'||c>'9'){if(c=='-')flag=1; c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}return flag?-x:x;}inline void min_cost_flow(int s,int t,int f){while(f > 0){memset(dist,INF,sizeof dist);dist[s] = 0;bool update = true;while(update){update = false;for(int i=1;i<=n;i++){if(dist[i] == INF) continue;for(int j=0;j<(int)G[i].size(); ++j){edge &e = G[i][j];if(e.cap > 0 && dist[e.to] > dist[i] + e.cost){dist[e.to] = dist[i] + e.cost;prevv[e.to] = i;preve[e.to] = j;update = true;}}}}// 此时的 INF 表示再也没有 增广路径,于是就是最后的答案了!if(dist[t] == INF) break;int d = f;for(int v = t; v != s; v = prevv[v])d = min(d,G[prevv[v]][preve[v]].cap);// d 就是 增广路的 流量!f -= cap;flow += d;res += d * dist[t];for(int v=t;v!=s;v=prevv[v]){edge &e = G[prevv[v]][preve[v]];e.cap -= d;G[v][e.rev].cap += d; // 给 反边加上适当的边权!}}}int main(int argc,char const* argv[]){n = read(); m = read(); s = read(); t = read();for(int i=1;i<=m;++i){scanf("%d%d%d%d",&from,&to,&cap,&cost);add();}min_cost_flow(s,t,INF);printf("%d %d\n",flow,res);return 0;}
//problemID:https://www.luogu.org/problemnew/show/P3381#include <iostream>#include <algorithm>#include <queue>#include <math.h>#include <stdio.h>#include <string.h>#include <algorithm>#define MAXN_ 5050#define INF 0x3f3f3f3f#define P pair<int,int>using namespace std;struct edge{ int to,cap,cost,rev;};int n,m,flow,s,t,cap,res,cost,from,to,h[MAXN_];std::vector<edge> G[MAXN_];int dist[MAXN_],prevv[MAXN_],preve[MAXN_]; // 前驱节点和对应边inline void add(){G[from].push_back((edge){to,cap,cost,(int)G[to].size()});G[to].push_back((edge){from,0,-cost,(int)G[from].size()-1});} // 在vector 之中找到边的位置所在!inline int read(){int x=0;char c=getchar();bool flag=0;while(c<'0'||c>'9'){if(c=='-')flag=1; c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}return flag?-x:x;}inline void min_cost_flow(int s,int t,int f){fill(h+1,h+1+n,0);while(f > 0){priority_queue<P,vector<P>, greater<P> > D;memset(dist,INF,sizeof dist);dist[s] = 0; D.push(P(0,s));while(!D.empty()){P now = D.top(); D.pop();if(dist[now.second] < now.first) continue;int v = now.second;for(int i=0;i<(int)G[v].size();++i){edge &e = G[v][i];if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];prevv[e.to] = v;preve[e.to] = i;D.push(P(dist[e.to],e.to));}}}// 无法增广 , 就是找到了答案了!if(dist[t] == INF) break;for(int i=1;i<=n;++i) h[i] += dist[i];int d = f;for(int v = t; v != s; v = prevv[v])d = min(d,G[prevv[v]][preve[v]].cap);f -= d; flow += d;res += d * h[t];for(int v=t;v!=s;v=prevv[v]){edge &e = G[prevv[v]][preve[v]];e.cap -= d;G[v][e.rev].cap += d;}}}int main(int argc,char const* argv[]){n = read(); m = read(); s = read(); t = read();for(int i=1;i<=m;++i){from = read(); to = read(); cap = read(); cost = read();add();}min_cost_flow(s,t,INF);printf("%d %d\n",flow,res);return 0;}
#include<iostream>#include<string>#include<algorithm>#include<cstdlib>#include<cstdio>#include<set>#include<map>#include<vector>#include<cstring>#include<stack>#include<cmath>#include<queue>using namespace std;#define CL(x,v); memset(x,v,sizeof(x));#define INF 0x3f3f3f3f#define LL long long#define REP(i,r,n) for(int i=r;i<=n;i++)#define RREP(i,n,r) for(int i=n;i>=r;i--)const int MAXN=1500;struct Edge{int from,to,cap,flow;};bool cmp(const Edge& a,const Edge& b){return a.from < b.from || (a.from == b.from && a.to < b.to);}struct Dinic{int n,m,s,t;vector<Edge> edges;vector<int> G[MAXN];bool vis[MAXN];int d[MAXN];int cur[MAXN];void init(int n){this->n=n;for(int i=0;i<=n;i++)G[i].clear();edges.clear();}void AddEdge(int from,int to,int cap){edges.push_back((Edge){from,to,cap,0});edges.push_back((Edge){to,from,0,0});//当是无向图时,反向边容量也是cap,有向边时,反向边容量是0m=edges.size();G[from].push_back(m-2);G[to].push_back(m-1);}bool BFS(){CL(vis,0);queue<int> Q;Q.push(s);d[s]=0;vis[s]=1;while(!Q.empty()){int x=Q.front();Q.pop();for(int i=0;i<G[x].size();i++){Edge& e=edges[G[x][i]];if(!vis[e.to]&&e.cap>e.flow){vis[e.to]=1;d[e.to]=d[x]+1;Q.push(e.to);}}}return vis[t];}int DFS(int x,int a){if(x==t||a==0)return a;int flow=0,f;for(int& i=cur[x];i<G[x].size();i++){Edge& e=edges[G[x][i]];if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){e.flow+=f;edges[G[x][i]^1].flow-=f;flow+=f;a-=f;if(a==0)break;}}return flow;}//当所求流量大于need时就退出,降低时间int Maxflow(int s,int t,int need){this->s=s;this->t=t;int flow=0;while(BFS()){CL(cur,0);flow+=DFS(s,INF);if(flow>need)return flow;}return flow;}//最小割割边vector<int> Mincut(){BFS();vector<int> ans;for(int i=0;i<edges.size();i++){Edge& e=edges[i];if(vis[e.from]&&!vis[e.to]&&e.cap>0)ans.push_back(i);}return ans;}void Reduce(){for(int i = 0; i < edges.size(); i++) edges[i].cap -= edges[i].flow;}void ClearFlow(){for(int i = 0; i < edges.size(); i++) edges[i].flow = 0;}};int n,m;Dinic solver;int du[MAXN];int dn[MAXN][MAXN];int id[MAXN][MAXN];int main(){while(~scanf("%d%d",&n,&m)){int s=0,t=n+m+1;int ss=n+m+2,tt=n+m+3;int a,b,c;CL(du,0);CL(dn,0);CL(id,0);solver.init(n+m+5);REP(i,1,m){scanf("%d",&a);solver.AddEdge(n+i,t,INF-a);du[n+i]-=a;du[t]+=a;}int C,D;REP(i,1,n){scanf("%d%d",&C,&D);solver.AddEdge(s,i,D);REP(j,1,C){scanf("%d%d%d",&a,&b,&c);solver.AddEdge(i,a+n+1,c-b);du[i]-=b;du[a+n+1]+=b;dn[i][a]=b;id[i][a]=solver.edges.size()-2;}}solver.AddEdge(t,s,INF);int sum=0;REP(i,1,t){if(du[i]<0){solver.AddEdge(i,tt,-du[i]);}else if(du[i]>0){solver.AddEdge(ss,i,du[i]);sum+=du[i];}}int maxflow=solver.Maxflow(ss,tt,INF);if(maxflow==sum){int ans=solver.Maxflow(s,t,INF);printf("%d\n",ans);for(int i=1;i<=n;i++){for(int j=0;j<m;j++)if(id[i][j])printf("%d\n",solver.edges[id[i][j]].flow+dn[i][j]);}}else printf("-1\n");printf("\n");}return 0;}
最长上升子序列(Longest Increasing Subsequence,LIS),在计算机科学上是指一个序列中最长的单调递增的子序列。
/*Coded by Apojacsleam*///problemID:http://codevs.cn/problem/1576/#include<cstdio>#include<iostream>using namespace std;int n,a[5001],dp[5001],ans;int main(){scanf("%d",&n);dp[1]=1;for(int i=1;i<=n;i++) scanf("%d",&a[i]),dp[i]=1;for(int i=2;i<=n;i++)for(int j=1;j<i;j++)if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1),ans=max(ans,dp[i]);printf("%d",ans);return 0;}
复杂度
/*Coded by Apojacsleam*///problemID:http://codevs.cn/problem/3955/#include<cstdio>#include<algorithm>using namespace std;int n,f[1000001],len,x;int main(){scanf("%d%d",&n,&x);f[++len]=x;for(int i=2;i<=n;i++){scanf("%d",&x);if(x>f[len]) f[++len]=x;else f[lower_bound(f+1,f+len+1,x)-f]=x;}printf("%d",len);return 0;}
复杂度
LCS是Longest Common Subsequence的缩写,即最长公共子序列。一个序列,如果是两个或多个已知序列的子序列,且是所有子序列中最长的,则为最长公共子序列。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P1439#include<cstdio>#include<algorithm>using namespace std;int n,a[1001],b[1001],dp[1001][1001];int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) scanf("%d",&b[i]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(a[i]==b[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);printf("%d",dp[n][n]);return 0;}
复杂度
给定两个整数序列,求它们的最长上升公共子序列。
//problemID:http://acm.hdu.edu.cn/showproblem.php?pid=1423#include<cstdio>#include<cstdlib>#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))int lengthOfLCIS(int *a,int n,int *b,int m){int ans=0;int dp[2][505]= {0};for(int i=0;i<n;++i){int max_dp=0;for(int j=0;j<m;++j){dp[(i+1)%2][j+1]=dp[i%2][j+1];if(a[i]>b[j]&&max_dp<dp[(i+1)%2][j+1]) max_dp=dp[(i+1)%2][j+1];if(a[i]==b[j]) dp[(i+1)%2][j+1]=max_dp+1;ans=max(ans,dp[(i+1)%2][j+1]);}}return ans;}int main(){int n,m,T;int a[505],b[505];scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=0;i<n;++i) scanf("%d",&a[i]);scanf("%d",&m);for(int j=0;j<m;++j) scanf("%d",&b[j]);printf("%d\n",lengthOfLCIS(a,n,b,m));if(T) printf("\n");}return 0;}
复杂度
给定个整数(可能为负数)组成的序列求该序列如的子段和的最大值。当所给的整数均为负数时定义子段和为,依此定义,所求的最优值为:
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P1115#include<cstdio>#define max(x,y) (x)>(y)?(x):(y)#define min(x,y) (x)<(y)?(x):(y)int n,maxn,ans=-2147483647,pre,x;int main(){scanf("%d",&n);maxn=0;ans=-2147483647;for(int i=1;i<=n;i++){scanf("%d",&x);x+=pre;pre=x;ans=max(ans,x-maxn);maxn=min(maxn,x);}printf("%d",ans);return 0;}
复杂度
背包是在件物品取出若干件放在空间为的背包里,每件物品的体积为,与之相对应的价值为。背包是背包问题中最简单的问题。背包的约束条件是给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。在背包问题中,因为每种物品只有一个,对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中,则不需要处理。如果选择将其放入背包中,由于不清楚之前放入的物品占据了多大的空间,需要枚举将这个物品放入背包后可能占据背包空间的所有情况。
/*Coded by Apojacsleam*///problemID:http://codevs.cn/problem/5709/#include<cstdio>#define max(x,y) (x)>(y)?(x):(y)int n,f[5001],w[1001],k[1001],V;int main(){scanf("%d%d",&V,&n);for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&k[i]);for(int i=1;i<=n;i++)for(int j=V;j>=w[i];j--)f[j]=max(f[j],f[j-w[i]]+k[i]);printf("%d",f[V]);return 0;}
复杂度
有种物品和一个容量为的背包,每种物品都有无限件可用。
第种物品的体积是,价值是。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P1616#include<cstdio>#define max(x,y) (x)>(y)?(x):(y)int n,f[100001],w[10001],k[10001],V;int main(){scanf("%d%d",&V,&n);for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&k[i]);for(int i=1;i<=n;i++)for(int j=w[i];j<=V;j++)f[j]=max(f[j],f[j-w[i]]+k[i]);printf("%d",f[V]);return 0;}
复杂度
有种物品和一个容量为的背包。第种物品最多有件可用,每件耗费的空间是,价值是。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量,且价值总和最大。
/*Coded by Apojacsleam*///problemID:http://codevs.cn/problem/5429/#include<cstdio>#define max(x,y) (x)>(y)?(x):(y)int n,f[100001],w[7001],v[7001],c[7001],V;int main(){scanf("%d%d",&n,&V);for(int i=1;i<=n;i++) scanf("%d%d%d",&w[i],&v[i],&c[i]);for(int i=1;i<=n;i++)for(int j=1;j<=c[i];j++)for(int k=V;k>=w[i];k--)f[k]=max(f[k],f[k-w[i]]+v[i]);printf("%d",f[V]);return 0;}
复杂度
/*Coded by Apojacsleam*///problemID:http://codevs.cn/problem/5429/#include<cstdio>#define max(x,y) (x)>(y)?(x):(y)int f[7005],w,v,k,s,n;int main(){scanf("%d%d",&n,&s);while(n--){scanf("%d%d%d",&w,&v,&k);for(int d=1;d<k;k-=d,d<<=1)for(long long i=s;i>=w*d;i--)f[i]=max(f[i],f[i-w*d]+v*d);for(long long i=s;i>=k*w;i--)f[i]=max(f[i],f[i-k*w]+v*k);}printf("%d",f[s]);return 0;}
复杂度
/*Coded by Apojacsleam*///problemID:http://codevs.cn/problem/5429/#include<cstdio>int n,m,v[7001],w[7001],c[7001],dp[7001],queue[7001],front,rear,ind[7001];int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i],&w[i],&c[i]);for(int i=1;i<=n;i++){for(int d=0;d<v[i];d++){front=0,rear=-1;for(int j=d,r=0;j<=m;j+=v[i],r++){int g=dp[j]-w[i]*r;if(front<=rear&&ind[front]<j-c[i]*v[i]) front++;while(front<=rear&&queue[rear]<=g) rear--;queue[++rear]=g;ind[rear]=j;dp[j]=queue[front]+w[i]*r;}}}printf("%d",dp[m]);return 0;}
复杂度
有的物品只可以取一次(背包),有的物品可以取无限次(完全背包),有的物品可以取的次数有一个上限(多重背包)。应该怎么求解呢?
/*Coded by Apojacsleam*///problemID:http://codevs.cn/problem/3269/#include<cstdio>#define max(x,y) (x)>(y)?(x):(y)int n,V,f[200005],h,t;void pack1(int v,int w)//01背包{for(int i=V;i>=v;i--)f[i]=max(f[i],f[i-v]+w);}void pack2(int v,int w)//完全背包{for(int i=v;i<=V;i++)f[i]=max(f[i],f[i-v]+w);}void pack3(int v,int w,int num)//多重背包二进制优化(虽然没用还是写了){for(int k=1;k<num;num-=k,k<<=1) pack1(v*k,w*k);pack1(v*num,w*num);}struct node{int f,id;}q[200005];void pack4(int v,int w,int num)//多重背包单调队列优化{for(int i=0;i<v;i++){h=t=0;for(int j=i,id=0;j<=V;j+=v,id++){while(h!=t&&q[t-1].f<=f[j]-id*w) t--;q[t++]=(node){f[j]-id*w,id};while(h!=t&&id-q[h].id>num) h++;f[j]=q[h].f+id*w;}}}int main(){scanf("%d%d",&n,&V);for(int i=1,v,w,num;i<=n;i++){scanf("%d%d%d",&v,&w,&num);if(num==-1||V/v<=num) pack2(v,w);else if(num==1) pack1(v,w);else pack4(v,w,num);}printf("%d",f[V]);return 0;}
复杂度
二维费用的背包问题是指:对于每件物品,具有两种不同的费用,选择这件物品必须同时付出这两种费用。对于每种费用都有一个可付出的最大值(背包容量)。问怎样选择物品可以得到最大的价值。
设第件物品所需的两种费用分别为和。两种费用可付出的最大值(也即两种背包容量)分别为和。物品的价值为。
/*Coded by Apojacsleam*///problemID:http://acm.hdu.edu.cn/showproblem.php?pid=2159#include<cstdio>#include<cstring>int main(){int n,m,f[120][120],s,k,a[120],b[120];while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF){memset(f,0,sizeof(f));for(int i=0;i<k;i++) scanf("%d%d",&a[i],&b[i]);for(int i=0;i<k;i++)for(int j=1;j<=s;j++)//注意动物的开始数是1for(int z=b[i];z<=m;z++) f[j][z]=f[j][z]>(f[j-1][z-b[i]]+a[i])?f[j][z]:(f[j-1][z-b[i]]+a[i]);//注意要j-1if(f[s][m]>=n){for(int i=0;i<=m;++i)if(f[s][i]>=n){printf("%d\n",m-i);break;}}else puts("-1");}return 0;}
复杂度
有件物品和一个容量为的背包。第件物品的费用是,价值是。这些物品被划分为组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P1757#include<cstdio>#include<vector>using namespace std;struct Node{int weight,value;}cnt;vector<Node> t[101];int n,m,dp[1001],belong,p;int main(){scanf("%d%d",&m,&n);for(int i=1;i<=n;i++){scanf("%d%d%d",&cnt.weight,&cnt.value,&belong);t[belong].push_back(cnt);}for(int i=1;i<=100;i++)if(t[i].size()){p=t[i].size();for(int j=m;j>=0;j--)for(int k=0;k<p;k++)if(j>=t[i][k].weight) dp[j]=max(dp[j],dp[j-t[i][k].weight]+t[i][k].value);}printf("%d",dp[m]);return 0;}
复杂度
这种背包问题的物品间存在某种“依赖”的关系。也就是说,物品依赖于物品,表示若选物品,则必须选物品。为了简化起见,我们先设没有某个物品既依赖于别的物品,又被别的物品所依赖;另外,没有某件物品同时依赖多件物品。
//problemID:https://www.luogu.org/problemnew/show/P1064#include<cstdio>#include<cstring>#define max(x,y) (x)>(y)?(x):(y)struct cas{int v,p,q;}a[60],pat[60][60];int n,m,t[60],V[60][10],P[60][10],cnt[60],f[32000],ans;int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q);//正常的读入if(a[i].q)//如果这个物品是附件{t[a[i].q]++;pat[a[i].q][t[a[i].q]].v=a[i].v;pat[a[i].q][t[a[i].q]].p=a[i].p;pat[a[i].q][t[a[i].q]].q=a[i].q;//把它存在相应的主件的分组中}}for(int i=1;i<=m;i++)//01背包处理{if(t[i])//如果当前物品为主件{memset(f,-1,sizeof(f));//恰好背包的处理,-1表示不恰好取到此价值f[0]=0;//恰好背包的处理for(int j=1;j<=t[i];j++)for(int k=n-a[i].v;k>=pat[i][j].v;k--)if(f[k]<f[k-pat[i][j].v]+pat[i][j].v*pat[i][j].p&&f[k-pat[i][j].v]!=-1)//恰好背包的判断f[k]=f[k-pat[i][j].v]+pat[i][j].v*pat[i][j].p;//很平常的01状态转移for(int j=0;j<=n-a[i].v;j++)if(f[j]!=-1)//恰好背包的判断,这种附件组合满足题意{cnt[i]++;V[i][cnt[i]]=j+a[i].v;P[i][cnt[i]]=f[j]+a[i].v*a[i].p;//把此情况存在主件i的分组中,为分组背包做好处理}}if(!a[i].q)//只买主件{cnt[i]++;V[i][cnt[i]]=a[i].v;P[i][cnt[i]]=a[i].v*a[i].p;//存储}}memset(f,0,sizeof(f));for(int i=1;i<=m;i++)for(int j=n;j>=0;j--)for(int k=1;k<=cnt[i];k++)if(j>=V[i][k]) f[j]=max(f[j],f[j-V[i][k]]+P[i][k]);//分组背包的计算for(int i=0;i<=n;i++) ans=max(ans,f[i]);printf("%d",ans);//输出return 0;}
复杂度
某大学有个职员,编号为。他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数,但是呢,如果某个职员的上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P1352#sub#include<iostream>#include<cstdio>#include<cstring>using namespace std;struct node{int to,next;}e[6001];int f[6001][2];int head[6001],a[6001],r[6001];int cnt,n;void ins(int u,int v){e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}void dp(int x){f[x][0]=0;f[x][1]=a[x];for(int i=head[x];i;i=e[i].next){int v=e[i].to;dp(v);f[x][0]+=max(f[v][0],f[v][1]);f[x][1]+=f[v][0];}}int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int u=1,v=1;u&&v;){scanf("%d%d",&u,&v);ins(v,u);r[u]=1;}for(int i=1;i<=n;i++)if(!r[i]){dp(i);printf("%d",max(f[i][0],f[i][1]));break;}return 0;}
复杂度
有个矩形,每个矩形可以用来描述,表示长和宽。矩形可以嵌套在矩形中当且仅当或者(相当于旋转度)。你的任务是选出尽可能多的矩形排成一行,使得除最后一个外,每一个矩形都可以嵌套在下一个矩形内。
/*Coded by Apojacsleam*/#include<algorithm>#include<cstdio>#include<cstring>struct node{int x,y;}juxing[1005];int cmp(node a,node b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}int N,n,ans,maxx,sum[1005];int main(){scanf("%d",&N);while(N--){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d",&juxing[i].x,&juxing[i].y);if(juxing[i].x<juxing[i].y){int temp=juxing[i].x;juxing[i].x=juxing[i].y;juxing[i].y=temp;}sum[i]=1;}std::sort(juxing,juxing+n,cmp);maxx=1;for(int i=1;i<n;i++){ans=0;for(int j=0;j<i;j++)if(juxing[j].x<juxing[i].x&&juxing[j].y<juxing[i].y)ans=std::max(sum[j],ans);sum[i]=ans+1;maxx=std::max(sum[i],maxx);}printf("%d\n",maxx);}return 0;}
复杂度
杭州人称那些傻乎乎粘嗒嗒的人为(音:laoer)。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有或的号码。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int dp[10][3];void Init()//预处理,算出所有可能{memset(dp,0,sizeof(dp));dp[0][0]=1;for(int i=1;i<=8;i++){dp[i][0]=dp[i-1][0]*9-dp[i-1][1];//在不含不吉利数62和4的首位分别补除了4的9个数字,减去在2前面补6的个数dp[i][1]=dp[i-1][0];//在不含不吉利数在首位补2dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1];//各种出现不吉利数的情况}}int Solve(int x){int digit[15];int cnt=0,tmp=x;while(tmp){digit[++cnt]=tmp%10;tmp/=10;}digit[cnt+1]=0;int flag=0,ans=0;for(int i=cnt;i>0;i--){ans+=digit[i]*dp[i-1][2];//由上位所有非吉利数推导if(flag)//之前出现非吉利的数字ans+=digit[i]*dp[i-1][0];else{if(digit[i]>4)//出现4ans+=dp[i-1][0];if(digit[i]>6)//出现6ans+=dp[i-1][1];if(digit[i+1]==6&&digit[i]>2)//出现62ans+=dp[i][1];}if(digit[i]==4||(digit[i+1]==6&&digit[i]==2))flag=1;}return x-ans;//所有的数减去非吉利的数}int main(){int a,b;Init();while(~scanf("%d%d",&a,&b)){if(a==0&&b==0)break;printf("%d\n",Solve(b+1)-Solve(a));}return 0;}
复杂度
现有盏灯,以及个按钮。每个按钮可以同时控制这盏灯——按下了第个按钮,对于所有的灯都有一个效果。按下按钮对于第盏灯,是下面中效果之一:
如果为,那么当这盏灯开了的时候,把它关上,否则不管;
如果为的话,如果这盏灯是关的,那么把它打开,否则也不管;
如果是,无论这灯是否开,都不管。
现在这些灯都是开的,给出所有开关对所有灯的控制效果,求问最少要按几下按钮才能全部关掉。
#include<iostream>#include<vector>#include<queue>#include<cstdio>#include<cstring>using namespace std;int RD(){int out=0,flag=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}while(c>='0'&&c<='9'){out=out*10+c-'0';c=getchar();}return flag*out;}const int maxn=2048;int num,m,numd;struct Node{int dp,step;};int vis[maxn];int map[maxn][maxn];void BFS(int n){queue<Node>Q;Node fir;fir.step=0,fir.dp=n;//初始状态入队Q.push(fir);while(!Q.empty())//BFS{Node u=Q.front();Q.pop();int pre=u.dp;for(int i=1;i<=m;i++)//枚举每个操作{int now=pre;for(int j=1;j<=num;j++){if(map[i][j]==1){if((1<<(j-1))&now) now=now^(1<<(j-1));//对状态进行操作}else if(map[i][j]==-1) now=((1<<(j-1))|now);//对状态进行操作}fir.dp=now,fir.step=u.step+1;//记录步数if(vis[now]==true)continue;if(fir.dp==0)//达到目标状态{vis[0]=true;//相当于一个标记flagcout<<fir.step<<endl;//输出return;//退出函数}Q.push(fir);//新状态入队vis[now]=true;//表示这个状态操作过了(以后在有这个状态就不用试了)}}}int main(){num=RD();m=RD();int n=(1<<(num))-1;for(int i=1;i<=m;i++)for(int j=1;j<=num;j++)map[i][j]=RD();BFS(n);if(vis[0]==false) puts("-1");return 0;}
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
/*Coded by Apojacsleam*///problemID:http://codevs.cn/problem/3187/#include<cstdio>#include<queue>using namespace std;queue<int> q;int n,opt,k;int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&opt);if(opt==1) scanf("%d",&k),q.push(k);else if(opt==2) q.pop();else printf("%d\n",q.front());}return 0;}
复杂度(入队,出队,访问队首)
栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
/*Coded by Apojacsleam*///problemID:http://codevs.cn/problem/3139/#include<cstdio>#include<stack>using namespace std;int n,opt,k;stack<int> s;int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&opt);if(opt==1) scanf("%d",&k),s.push(k);else if(opt==2) s.pop();else printf("%d\n",s.top());}return 0;}
复杂度(入栈,出栈,访问栈顶)
堆(英语:heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3378#sub#include<cstdio>#include<queue>#include<cctype>using namespace std;priority_queue<int,vector<int>,greater<int> > q;int m,a,b;int readin(){int res=0;char ch=0;bool XX=false;for(;!isdigit(ch);ch=getchar())if(ch=='-') XX=true;for(;isdigit(ch);ch=getchar()) res=(res<<3)+(res<<1)+ch-'0';return (XX?-res:res);}void writeout(int res){if(res<0) {putchar('-');res=-res;}if(res>9) writeout(res/10);putchar(res%10+'0');}int main(){m=readin();for(int i=1;i<=m;i++){a=readin();if(a==1){b=readin();q.push(b);}else if(a==2) writeout(q.top()),putchar('\n');else q.pop();}return 0;}
/*** C++: 斐波那契堆** @author skywang* @date 2014/04/06*/#ifndef _FIBONACCI_TREE_HPP_#define _FIBONACCI_TREE_HPP_#include <iomanip>#include <iostream>#include <cstdlib>#include <cmath>using namespace std;template <class T>class FibNode {public:T key; // 关键字(键值)int degree; // 度数FibNode<T> *left; // 左兄弟FibNode<T> *right; // 右兄弟FibNode<T> *child; // 第一个孩子节点FibNode<T> *parent; // 父节点bool marked; // 是否被删除第一个孩子FibNode(T value):key(value), degree(0), marked(false),left(NULL),right(NULL),child(NULL),parent(NULL) {key = value;degree = 0;marked = false;left = this;right = this;parent = NULL;child = NULL;}};template <class T>class FibHeap {private:int keyNum; // 堆中节点的总数int maxDegree; // 最大度FibNode<T> *min; // 最小节点(某个最小堆的根节点)FibNode<T> **cons; // 最大度的内存区域public:FibHeap();~FibHeap();// 新建key对应的节点,并将其插入到斐波那契堆中void insert(T key);// 移除斐波那契堆中的最小节点void removeMin();// 将other合并到当前堆中void combine(FibHeap<T> *other);// 获取斐波那契堆中最小键值,并保存到pkey中;成功返回true,否则返回false。bool minimum(T *pkey);// 将斐波那契堆中键值oldkey更新为newkeyvoid update(T oldkey, T newkey);// 删除键值为key的节点void remove(T key);// 斐波那契堆中是否包含键值keybool contains(T key);// 打印斐波那契堆void print();// 销毁void destroy();private:// 将node从双链表移除void removeNode(FibNode<T> *node);// 将node堆结点加入root结点之前(循环链表中)void addNode(FibNode<T> *node, FibNode<T> *root);// 将双向链表b链接到双向链表a的后面void catList(FibNode<T> *a, FibNode<T> *b);// 将节点node插入到斐波那契堆中void insert(FibNode<T> *node);// 将"堆的最小结点"从根链表中移除,FibNode<T>* extractMin();// 将node链接到root根结点void link(FibNode<T>* node, FibNode<T>* root);// 创建consolidate所需空间void makeCons();// 合并斐波那契堆的根链表中左右相同度数的树void consolidate();// 修改度数void renewDegree(FibNode<T> *parent, int degree);// 将node从父节点parent的子链接中剥离出来,并使node成为"堆的根链表"中的一员。void cut(FibNode<T> *node, FibNode<T> *parent);// 对节点node进行"级联剪切"void cascadingCut(FibNode<T> *node) ;// 将斐波那契堆中节点node的值减少为keyvoid decrease(FibNode<T> *node, T key);// 将斐波那契堆中节点node的值增加为keyvoid increase(FibNode<T> *node, T key);// 更新斐波那契堆的节点node的键值为keyvoid update(FibNode<T> *node, T key);// 在最小堆root中查找键值为key的节点FibNode<T>* search(FibNode<T> *root, T key);// 在斐波那契堆中查找键值为key的节点FibNode<T>* search(T key);// 删除结点nodevoid remove(FibNode<T> *node);// 销毁斐波那契堆void destroyNode(FibNode<T> *node);// 打印"斐波那契堆"void print(FibNode<T> *node, FibNode<T> *prev, int direction);};/** 构造函数*/template <class T>FibHeap<T>::FibHeap(){keyNum = 0;maxDegree = 0;min = NULL;cons = NULL;}/** 析构函数*/template <class T>FibHeap<T>::~FibHeap(){}/** 将node从双链表移除*/template <class T>void FibHeap<T>::removeNode(FibNode<T> *node){node->left->right = node->right;node->right->left = node->left;}/** 将node堆结点加入root结点之前(循环链表中)* a …… root* a …… node …… root*/template <class T>void FibHeap<T>::addNode(FibNode<T> *node, FibNode<T> *root){node->left = root->left;root->left->right = node;node->right = root;root->left = node;}/** 将节点node插入到斐波那契堆中*/template <class T>void FibHeap<T>::insert(FibNode<T> *node){if (keyNum == 0)min = node;else{addNode(node, min);if (node->key < min->key)min = node;}keyNum++;}/** 新建键值为key的节点,并将其插入到斐波那契堆中*/template <class T>void FibHeap<T>::insert(T key){FibNode<T> *node;node = new FibNode<T>(key);if (node == NULL)return ;insert(node);}/** 将双向链表b链接到双向链表a的后面** 注意: 此处a和b都是双向链表*/template <class T>void FibHeap<T>::catList(FibNode<T> *a, FibNode<T> *b){FibNode<T> *tmp;tmp = a->right;a->right = b->right;b->right->left = a;b->right = tmp;tmp->left = b;}/** 将other合并到当前堆中*/template <class T>void FibHeap<T>::combine(FibHeap<T> *other){if (other==NULL)return ;if(other->maxDegree > this->maxDegree)swap(*this, *other);if((this->min) == NULL) // this无"最小节点"{this->min = other->min;this->keyNum = other->keyNum;free(other->cons);delete other;}else if((other->min) == NULL) // this有"最小节点" && other无"最小节点"{free(other->cons);delete other;} // this有"最小节点" && other有"最小节点"else{// 将"other中根链表"添加到"this"中catList(this->min, other->min);if (this->min->key > other->min->key)this->min = other->min;this->keyNum += other->keyNum;free(other->cons);delete other;}}/** 将"堆的最小结点"从根链表中移除,* 这意味着"将最小节点所属的树"从堆中移除!*/template <class T>FibNode<T>* FibHeap<T>::extractMin(){FibNode<T> *p = min;if (p == p->right)min = NULL;else{removeNode(p);min = p->right;}p->left = p->right = p;return p;}/** 将node链接到root根结点*/template <class T>void FibHeap<T>::link(FibNode<T>* node, FibNode<T>* root){// 将node从双链表中移除removeNode(node);// 将node设为root的孩子if (root->child == NULL)root->child = node;elseaddNode(node, root->child);node->parent = root;root->degree++;node->marked = false;}/** 创建consolidate所需空间*/template <class T>void FibHeap<T>::makeCons(){int old = maxDegree;// 计算log2(keyNum),"+1"意味着向上取整!// ex. log2(13) = 3,向上取整为3+1=4。maxDegree = (log(keyNum)/log(2.0)) + 1;if (old >= maxDegree)return ;// 因为度为maxDegree可能被合并,所以要maxDegree+1cons = (FibNode<T> **)realloc(cons,sizeof(FibHeap<T> *) * (maxDegree + 1));}/** 合并斐波那契堆的根链表中左右相同度数的树*/template <class T>void FibHeap<T>::consolidate(){int i, d, D;FibNode<T> *x, *y, *tmp;makeCons();//开辟哈希所用空间D = maxDegree + 1;for (i = 0; i < D; i++)cons[i] = NULL;// 合并相同度的根节点,使每个度数的树唯一while (min != NULL){x = extractMin(); // 取出堆中的最小树(最小节点所在的树)d = x->degree; // 获取最小树的度数// cons[d] != NULL,意味着有两棵树(x和y)的"度数"相同。while (cons[d] != NULL){y = cons[d]; // y是"与x的度数相同的树"if (x->key > y->key) // 保证x的键值比y小swap(x, y);link(y, x); // 将y链接到x中cons[d] = NULL;d++;}cons[d] = x;}min = NULL;// 将cons中的结点重新加到根表中for (i=0; i<D; i++){if (cons[i] != NULL){if (min == NULL)min = cons[i];else{addNode(cons[i], min);if ((cons[i])->key < min->key)min = cons[i];}}}}/** 移除最小节点*/template <class T>void FibHeap<T>::removeMin(){if (min==NULL)return ;FibNode<T> *child = NULL;FibNode<T> *m = min;// 将min每一个儿子(儿子和儿子的兄弟)都添加到"斐波那契堆的根链表"中while (m->child != NULL){child = m->child;removeNode(child);if (child->right == child)m->child = NULL;elsem->child = child->right;addNode(child, min);child->parent = NULL;}// 将m从根链表中移除removeNode(m);// 若m是堆中唯一节点,则设置堆的最小节点为NULL;// 否则,设置堆的最小节点为一个非空节点(m->right),然后再进行调节。if (m->right == m)min = NULL;else{min = m->right;consolidate();}keyNum--;delete m;}/** 获取斐波那契堆中最小键值,并保存到pkey中;成功返回true,否则返回false。*/template <class T>bool FibHeap<T>::minimum(T *pkey){if (min==NULL || pkey==NULL)return false;*pkey = min->key;return true;}/** 修改度数*/template <class T>void FibHeap<T>::renewDegree(FibNode<T> *parent, int degree){parent->degree -= degree;if (parent-> parent != NULL)renewDegree(parent->parent, degree);}/** 将node从父节点parent的子链接中剥离出来,* 并使node成为"堆的根链表"中的一员。*/template <class T>void FibHeap<T>::cut(FibNode<T> *node, FibNode<T> *parent){removeNode(node);renewDegree(parent, node->degree);// node没有兄弟if (node == node->right)parent->child = NULL;elseparent->child = node->right;node->parent = NULL;node->left = node->right = node;node->marked = false;// 将"node所在树"添加到"根链表"中addNode(node, min);}/** 对节点node进行"级联剪切"** 级联剪切:如果减小后的结点破坏了最小堆性质,* 则把它切下来(即从所在双向链表中删除,并将* 其插入到由最小树根节点形成的双向链表中),* 然后再从"被切节点的父节点"到所在树根节点递归执行级联剪枝*/template <class T>void FibHeap<T>::cascadingCut(FibNode<T> *node){FibNode<T> *parent = node->parent;if (parent != NULL){if (node->marked == false)node->marked = true;else{cut(node, parent);cascadingCut(parent);}}}/** 将斐波那契堆中节点node的值减少为key*/template <class T>void FibHeap<T>::decrease(FibNode<T> *node, T key){FibNode<T> *parent;if (min==NULL ||node==NULL)return ;if ( key>=node->key){cout << "decrease failed: the new key(" << key <<") "<< "is no smaller than current key(" << node->key <<")" << endl;return ;}node->key = key;parent = node->parent;if (parent!=NULL && node->key < parent->key){// 将node从父节点parent中剥离出来,并将node添加到根链表中cut(node, parent);cascadingCut(parent);}// 更新最小节点if (node->key < min->key)min = node;}/** 将斐波那契堆中节点node的值增加为key*/template <class T>void FibHeap<T>::increase(FibNode<T> *node, T key){FibNode<T> *child, *parent, *right;if (min==NULL ||node==NULL)return ;if (key <= node->key){cout << "increase failed: the new key(" << key <<") "<< "is no greater than current key(" << node->key <<")" << endl;return ;}// 将node每一个儿子(不包括孙子,重孙,...)都添加到"斐波那契堆的根链表"中while (node->child != NULL){child = node->child;removeNode(child); // 将child从node的子链表中删除if (child->right == child)node->child = NULL;elsenode->child = child->right;addNode(child, min); // 将child添加到根链表中child->parent = NULL;}node->degree = 0;node->key = key;// 如果node不在根链表中,// 则将node从父节点parent的子链接中剥离出来,// 并使node成为"堆的根链表"中的一员,// 然后进行"级联剪切"// 否则,则判断是否需要更新堆的最小节点parent = node->parent;if(parent != NULL){cut(node, parent);cascadingCut(parent);}else if(min == node){right = node->right;while(right != node){if(node->key > right->key)min = right;right = right->right;}}}/** 更新斐波那契堆的节点node的键值为key*/template <class T>void FibHeap<T>::update(FibNode<T> *node, T key){if(key < node->key)decrease(node, key);else if(key > node->key)increase(node, key);elsecout << "No need to update!!!" << endl;}template <class T>void FibHeap<T>::update(T oldkey, T newkey){FibNode<T> *node;node = search(oldkey);if (node!=NULL)update(node, newkey);}/** 在最小堆root中查找键值为key的节点*/template <class T>FibNode<T>* FibHeap<T>::search(FibNode<T> *root, T key){FibNode<T> *t = root; // 临时节点FibNode<T> *p = NULL; // 要查找的节点if (root==NULL)return root;do{if (t->key == key){p = t;break;}else{if ((p = search(t->child, key)) != NULL)break;}t = t->right;} while (t != root);return p;}/** 在斐波那契堆中查找键值为key的节点*/template <class T>FibNode<T>* FibHeap<T>::search(T key){if (min==NULL)return NULL;return search(min, key);}/** 在斐波那契堆中是否存在键值为key的节点。* 存在返回true,否则返回false。*/template <class T>bool FibHeap<T>::contains(T key){return search(key)!=NULL ? true: false;}/** 删除结点node*/template <class T>void FibHeap<T>::remove(FibNode<T> *node){T m = min->key-1;decrease(node, m-1);removeMin();}template <class T>void FibHeap<T>::remove(T key){FibNode<T> *node;if (min==NULL)return ;node = search(key);if (node==NULL)return ;remove(node);}/** 销毁斐波那契堆*/template <class T>void FibHeap<T>::destroyNode(FibNode<T> *node){FibNode<T> *start = node;if(node == NULL)return;do {destroyNode(node->child);// 销毁node,并将node指向下一个node = node->right;delete node->left;} while(node != start);}template <class T>void FibHeap<T>::destroy(){destroyNode(min);free(cons);}/** 打印"斐波那契堆"** 参数说明:* node -- 当前节点* prev -- 当前节点的前一个节点(父节点or兄弟节点)* direction -- 1,表示当前节点是一个左孩子;* 2,表示当前节点是一个兄弟节点。*/template <class T>void FibHeap<T>::print(FibNode<T> *node, FibNode<T> *prev, int direction){FibNode<T> *start=node;if (node==NULL)return ;do{if (direction == 1)cout << setw(8) << node->key << "(" << node->degree << ") is "<< setw(2) << prev->key << "'s child" << endl;elsecout << setw(8) << node->key << "(" << node->degree << ") is "<< setw(2) << prev->key << "'s next" << endl;if (node->child != NULL)print(node->child, node, 1);// 兄弟节点prev = node;node = node->right;direction = 2;} while(node != start);}template <class T>void FibHeap<T>::print(){int i=0;FibNode<T> *p;if (min==NULL)return ;cout << "== 斐波那契堆的详细信息: ==" << endl;p = min;do {i++;cout << setw(2) << i << ". " << setw(4) << p->key << "(" << p->degree << ") is root" << endl;print(p->child, p, 1);p = p->right;} while (p != min);cout << endl;}#endif
//problemID:https://www.lydsy.com/JudgeOnline/problem.php?id=1455#include <iostream>#include <cstdio>using namespace std;const int N=1000001;int n,m; int a[N]; bool die[N];int l[N],r[N],fa[N],dep[N];int readin(){int x=0,f=1; char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;}int find(int x){if (fa[x]!=x)fa[x]=find(fa[x]);return fa[x];}void read(){n=readin();for (int i=1;i<=n;i++)a[i]=readin(),fa[i]=i;m=readin();return;}int merge(int x,int y){if (!x) return y;if (!y) return x;if (a[x]>a[y]) swap(x,y);r[x]=merge(r[x],y);if (dep[r[x]]>dep[l[x]])swap(l[x],r[x]);dep[x]=dep[r[x]]+1;return x;}void work(){char ch[10]; int x,y;for (int i=1;i<=m;i++){scanf("%s",ch);if (ch[0]=='M') {x=readin(),y=readin();if (die[x]||die[y]) continue;int f1=find(x),f2=find(y);if (f1!=f2) {int t=merge(f1,f2);fa[f2]=fa[f1]=t;}}else {x=readin();if (die[x]) printf("0\n");else {int f1=find(x); die[f1]=1;printf("%d\n",a[f1]);fa[f1]=merge(l[f1],r[f1]);fa[fa[f1]]=fa[f1];}}}return;}int main(){read();work();return 0;}
//problemID:https://www.luogu.org/problemnew/show/P3371#include<bits/stdc++.h>using namespace std;const int M=2e6+5;int n,root,id,tot,top,val[M],head[M],nxt[M],to[M],dad[M];queue<int>dui;void add(int x,int y){nxt[++id]=head[x],head[x]=id,to[id]=y,dad[y]=x;}int _new(int x){val[++tot]=x;return tot;}int merge(int x,int y){if(!x||!y)return x+y;if(val[x]<val[y]){add(x,y);return x;}else{add(y,x);return y;}}void pop(){int t;for(int i=head[root]; i; i=nxt[i])if(dad[to[i]]==root)dui.push(to[i]),dad[to[i]]=0;while(dui.size()>1){t=dui.front();dui.pop();dui.push(merge(dui.front(),t));dui.pop();}if(dui.size())root=dui.front(),dui.pop();else root=0;}int main(){scanf("%d",&n);int op,x;for(int i=1; i<=n; ++i){scanf("%d",&op);if(op==1)scanf("%d",&x),root=merge(_new(x),root);else if(op==2)printf("%d\n",val[root]);else pop();}}
并查集,在一些有个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中
并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3367#include<cstdio>#define N 10001int n,fa[N],m;void init(){for(register int i=1;i<=n;i++) fa[i]=i;return;}int Find(int x){while(x!=fa[x]) x=fa[x];return x;}void MergeSet(int x,int y){int Root1=Find(x),Root2=Find(y);if(Root1!=Root2) fa[Root1]=Root2;return;}bool Query(int x,int y){return Find(x)==Find(y);}int main(){scanf("%d%d",&n,&m);init();int opt,x,y;for(int i=1;i<=m;i++){scanf("%d%d%d",&opt,&x,&y);if(opt==1) MergeSet(x,y);else puts(Query(x,y)?"Y":"N");}return 0;}/*路径压缩Find()函数:int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}随机合并版MergeSet()函数:void MergeSet(int x,int y){srand(time(NULL));int Root1=Find(x),Root2=Find(y);if(Root1!=Root2){if(rand()&1) fa[Root1]=Root2;else fa[Root2]=Root1;}return;}按秩合并版MergeSet()函数:void MergeSet(int x,int y){int Root1=Find(x),Root2=Find(y);if(Root1!=Root2){if(rank[Root1]<=rank[Root2]) fa[Root1]=y,rank[Root2]=max(rank[Root2],rank[Root1]+1);else fa[Root2]=Root1,rank[Root1]=max(rank[Root1],rank[Root2]+1);}}*/
复杂度:路径压缩+按秩合并:,其他:
//problemID:https://www.lydsy.com/JudgeOnline/problem.php?id=3674#include<iostream>#include<string>#include<cstring>#include<cmath>#include<cstdio>#include<cstdlib>#include<stdio.h>#include<algorithm>using namespace std;const int maxn=200100;const int maxl=20;struct data{int lson,rson,id,val,_Size;} tree[maxn+2*maxn*maxl];int Root[maxn];int cur;int w[maxn];int n,m,lt,nt,lans;void Build(int x){tree[x].id=x;tree[x].val=x;tree[x]._Size=1;int left=x<<1;if (left<=n){tree[x].lson=left;Build(left);}int right=left|1;if (right<=n){tree[x].rson=right;Build(right);}}data Query(int root,int L,int x){if (x==L) return tree[root];if (x&(1<<(w[x]-w[L]-1))) return Query(tree[root].rson,L*2+1,x);else return Query(tree[root].lson,L*2,x);}data Find_fa(int x){data y=Query(Root[lt],1,x);while (y.id!=y.val) y=Query(Root[lt],1,y.val);return y;}void Update(int root,int L,int x,int nid,int v){if (L==x){if (nid==0) tree[root].val=v;else tree[root]._Size=v;return;}if (x&(1<<(w[x]-w[L]-1))){data temp=tree[ tree[root].rson ];tree[root].rson=++cur;tree[cur]=temp;Update(cur,L*2+1,x,nid,v);}else{data temp=tree[ tree[root].lson ];tree[root].lson=++cur;tree[cur]=temp;Update(cur,L*2,x,nid,v);}}void Add(int x,int y){data fx=Find_fa(x);data fy=Find_fa(y);if (fx.val==fy.val){Root[nt]=Root[lt];return;}if (fx._Size>fy._Size) swap(fx,fy);Root[nt]=++cur;tree[cur]=tree[ Root[lt] ];Update(cur,1,fx.id,0,fy.id);tree[++cur]=tree[ Root[nt] ];Root[nt]=cur;Update(cur,1,fy.id,1,fx._Size+fy._Size);}int main(){freopen("c.in","r",stdin);freopen("c.out","w",stdout);scanf("%d%d",&n,&m);Build(1);Root[1]=1;cur=n;lt=1,nt=1;lans=0;w[1]=1;for (int i=2; i<maxn; i++) w[i]=w[i/2]+1;/*for (int i=1; i<=n; i++){data temp=Find_fa(i);printf("%d ",temp.val);}printf("\n");*/for (int i=1; i<=m; i++){int op;scanf("%d",&op);if (op==1){int a,b;scanf("%d%d",&a,&b);a=a^lans;b=b^lans;nt++;Add(a,b);lt=nt;}if (op==2){int k;scanf("%d",&k);k=k^lans;lt=k+1;nt++;Root[nt]=Root[lt];lt=nt;}if (op==3){int a,b;scanf("%d%d",&a,&b);a=a^lans;b=b^lans;//printf("%d %d\n",a,b);data fa=Find_fa(a);data fb=Find_fa(b);bool f=(fa.val==fb.val);printf("%d\n",f);lans=f;nt++;Root[nt]=Root[lt];lt=nt;}/*for (int i=1; i<=n; i++){data temp=Find_fa(i);printf("%d ",temp.val);}printf("\n");*/}return 0;}
单调队列,即单调递减或单调递增的队列。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P1886#include<cstdio>#include<deque>#include<cctype>using namespace std;inline char getcha(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}int readin(){int res=0;char ch=getcha();bool XX=false;for(;!isdigit(ch);ch=getcha())(ch=='-') && (XX=true);for(;isdigit(ch);ch=getcha())res=(res<<3)+(res<<1)+(ch^48);return XX?-res:res;}void writeout(int x){if(x<0) putchar('-'),x=-x;if(x>9) writeout(x/10);putchar(x%10+48);}#define N 1000001int a[N],n,k,head,tail;struct node{int x,p;node(){}node(int xx,int pp){x=xx;p=pp;}}list[N],List[N];int main(){n=readin();k=readin();for(int i=1;i<=n;i++) a[i]=readin();head=1,tail=0;for(int i=1;i<=n;i++){while(head<=tail&&List[tail].x>=a[i]) tail--;List[++tail]=node(a[i],i);while(i-List[head].p>=k) head++;if(i>=k) writeout(List[head].x),putchar(i==n?'\n':' ');}head=1,tail=0;for(int i=1;i<=n;i++){while(head<=tail&&list[tail].x<=a[i]) tail--;list[++tail]=node(a[i],i);while(i-list[head].p>=k) head++;if(i>=k) writeout(list[head].x),putchar(i==n?'\n':' ');}return 0;}
复杂度
单调递增或单调减的栈,跟单调队列差不多,但是只用到它的一端,利用它可以用来解决一些ACM/ICPC和OI的题目。
//problemID:http://poj.org/problem?id=3250#include<cstdio>#include<iostream>#include<stack>using namespace std;int main(){int i,n,top,a[80010]; //top指向栈顶元素long long ans; //存储最终结果stack<int> st; //st为栈,每次入栈的是每头牛的位置while(~scanf("%d",&n)){while(!st.empty()) st.pop(); //清空栈for(i=0;i<n;i++) scanf("%d",&a[i]);a[n]=2147483647; //将最后一个元素设为最大值ans=0;for(i=0;i<=n;i++){if(st.empty()||a[i]<a[st.top()]){ //如果栈为空或入栈元素小于栈顶元素,则入栈st.push(i);}else{while(!st.empty()&&a[i]>=a[st.top()]){ //如果栈不为空并且栈顶元素不大于入栈元素,则将栈顶元素出栈top=st.top(); //获取栈顶元素st.pop(); //栈顶元素出栈//这时候也就找到了第一个比栈顶元素大的元素//计算这之间牛的个数,为下标之差-1ans+=(i-top-1);}st.push(i); //当所有破坏栈的单调性的元素都出栈后,将当前元素入栈}}cout<<ans;}return 0;}
复杂度
线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为。而未优化的空间复杂度为,实际应用时一般还要开的数组以免越界,因此有时需要离散化让空间压缩。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3372#include<cstdio>#define int long long#define N 100001struct Tree{int lazy,sum;}tree[N<<2];int a[N],n,m,x,y,opt,k;void build(int l,int r,int node){if(l==r){tree[node].sum=a[l];return;}int mid=(l+r)>>1;build(l,mid,node<<1);build(mid+1,r,node<<1|1);tree[node].sum=tree[node<<1].sum+tree[node<<1|1].sum;}void pushdown(int node,int ln,int rn){if(tree[node].lazy){tree[node<<1].lazy+=tree[node].lazy;tree[node<<1|1].lazy+=tree[node].lazy;tree[node<<1].sum+=tree[node].lazy*ln;tree[node<<1|1].sum+=tree[node].lazy*rn;tree[node].lazy=0;}return;}void add(int L,int R,int num,int l,int r,int node){if(L<=l&&r<=R){tree[node].sum+=num*(r-l+1);tree[node].lazy+=num;return;}int mid=(l+r)>>1;pushdown(node,mid-l+1,r-mid);if(L<=mid) add(L,R,num,l,mid,node<<1);if(R>mid) add(L,R,num,mid+1,r,node<<1|1);tree[node].sum=tree[node<<1].sum+tree[node<<1|1].sum;}long long query(int L,int R,int l,int r,int node){if(L<=l&&R>=r) return tree[node].sum;int mid=(l+r)>>1;pushdown(node,mid-l+1,r-mid);long long ans=0;if(L<=mid) ans+=query(L,R,l,mid,node<<1);if(R>mid) ans+=query(L,R,mid+1,r,node<<1|1);return ans;}signed main(){scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);build(1,n,1);for(int i=1;i<=m;i++){scanf("%lld%lld%lld",&opt,&x,&y);if(opt==1) scanf("%lld",&k),add(x,y,k,1,n,1);else printf("%lld\n",query(x,y,1,n,1));}return 0;}
复杂度
#include<cstdio>#include<cstring>#define R register intconst int N=1000009,M=20000009;int P,rt[N],lc[M],rc[M],val[M];char I[M<<1],O[M],*fi=I,*fo=O;bool nega;inline void in(R&z){while(*fi<'-')++fi;if(*fi=='-')nega=1,++fi;z=*fi++&15;while(*fi>'-')z*=10,z+=*fi++&15;if(nega)nega=0,z=-z;}void oi(R z){if(z>9)oi(z/10);*fo++=z%10|'0';}inline void out(R z){z>0?oi(z):(*fo++='-',oi(-z));*fo++='\n';}//上面快读快写void build(R&t,R l,R r)//初始化建树,线段树基本操作{R m;t=++P;if(l!=r){m=(l+r)>>1;build(lc[t],l,m);build(rc[t],m+1,r);}else in(val[P]);}inline void insert(R*t,R u,R l,R r,R k)//更新,插入一个新路径{R m;while(l!=r){*t=++P;m=(l+r)>>1;if(k<=m)r=m,rc[*t]=rc[u],t=&lc[*t],u=lc[u];else l=m+1,lc[*t]=lc[u],t=&rc[*t],u=rc[u];}in(val[*t=++P]);}inline int ask(R t,R l,R r,R k)//询问{R m;while(l!=r){m=(l+r)>>1;if(k<=m)r=m,t=lc[t];else l=m+1,t=rc[t];}return val[t];}int main(){freopen("ct.in","r",stdin);freopen("ct.out","w",stdout);fread(I,1,sizeof(I),stdin);R n,m,i,v,op,loc;in(n);in(m);build(rt[0],1,n);for(i=1;i<=m;++i){in(v);in(op);in(loc);if(op&1)insert(&rt[i],rt[v],1,n,loc);else{out(ask(rt[v],1,n,loc));rt[i]=++P;//没错,这里的版本复制其实很简单lc[P]=lc[rt[v]];rc[P]=rc[rt[v]];}}fwrite(O,1,fo-O,stdout);fclose(stdin);fclose(stdout);return 0;}
//problemID:https://www.luogu.org/problemnew/show/P1801#include<bits/stdc++.h>#define N 200005using namespace std;int m,n,k;int a[N],b[N],u[N];struct MM{int l,r,s;}tree[N<<2];inline void build(int root,int L,int R){tree[root].l=L;tree[root].r=R;if(L==R) return;int mid=(L+R)>>1;build(root<<1,L,mid);build(root<<1|1,mid+1,R);}inline void update(int root,int t){if(tree[root].l==tree[root].r){tree[root].s++;//个数加一return;}int mid=(tree[root].l+tree[root].r)>>1;if(t<=mid) update(root<<1,t);else update(root<<1|1,t);tree[root].s=tree[root<<1].s+tree[root<<1|1].s;}inline int query(int root,int t){if(tree[root].l==tree[root].r)return tree[root].l;if(t<=tree[root<<1].s) return query(root<<1,t);else return query(root<<1|1,t-tree[root<<1].s);}int main(){cin>>m>>n;for(int i=1;i<=m;i++){cin>>a[i];b[i]=a[i];}for(int i=1;i<=n;i++)cin>>u[i];sort(b+1,b+m+1);int s=unique(b+1,b+m+1)-(b+1);//离散化(如果值域很大的话),s是数组b中不重复的数的个数build(1,1,s);//依s建树int h=0;while(n!=h){h++;for(int i=u[h-1]+1;i<=u[h];i++){int v=lower_bound(b+1,b+s+1,a[i])-b;//v是a[i]在数组b中所处的位置(注意之前数组b排了序)update(1,v);}cout<<b[query(1,++k)]<<endl;}return 0;}
//problemID:http://acm.hdu.edu.cn/showproblem.php?pid=6183#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#define clr(a,b) memset(a,b,sizeof a)#define rep(i,j,k) for(int i=j;i<=k;i++)using namespace std;const int maxn = 2e6+5e5+11;const int oo = 0x3f3f3f3f;int T[70];struct ST{int L[maxn<<2],R[maxn<<2],minx[maxn<<2];int tot;void init(){clr(T,0);tot=0;L[0]=R[0]=0;minx[0]=oo;}void pu(int o){minx[o]=min(minx[L[o]],minx[R[o]]);}void update(int &o,int l,int r,int y,int x){if(!o){o=++tot;L[o]=R[o]=0;minx[o]=x;}if(l==r){minx[o]=min(minx[o],x);return ;}int m=l+r>>1;if(y<=m) update(L[o],l,m,y,x);else update(R[o],m+1,r,y,x);pu(o);}int query(int &o,int l,int r,int LL,int RR){if(!o){return oo; //很重要!!!}if(LL<=l&&r<=RR){return minx[o];}int m=l+r>>1;int ans=oo;if(LL<=m) ans=min(ans,query(L[o],l,m,LL,RR));if(RR>m) ans=min(ans,query(R[o],m+1,r,LL,RR));return ans;}}st;const int n = 1e6;int main(){int op,x,y,yy1,yy2,c;st.init();while(scanf("%d",&op)!=EOF){if(op==3)break;else if(op==0) st.init();else if(op==1){scanf("%d%d%d",&x,&y,&c);st.update(T[c],1,n,y,x);}else if(op==2){scanf("%d%d%d",&x,&yy1,&yy2);int ans=0,tmp;rep(i,0,50){tmp=st.query(T[i],1,n,yy1,yy2);if(tmp<=x) ans++;}printf("%d\n",ans);}}return 0;}
树状数组(Binary Indexed Tree, Fenwick Tree)是一个查询和修改复杂度都为的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;经过简单修改可以在的复杂度下进行范围修改,但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。
//problemID:https://www.luogu.org/problemnew/show/P3374#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>using namespace std;int n,m,tree[2000010];int lowbit(int k){return k & -k;}void add(int x,int k){while(x<=n){tree[x]+=k;x+=lowbit(x);}}int sum(int x){int ans=0;while(x!=0){ans+=tree[x];x-=lowbit(x);}return ans;}int main(){cin>>n>>m;for(int i=1;i<=n;i++){int a;scanf("%d",&a);add(i,a);}for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);if(a==1)add(b,c);if(a==2)cout<<sum(c)-sum(b-1)<<endl;}return 0;}
复杂度
ST表类似树状数组,线段树这两种数据结构,是一种用于解决RMQ(Range Minimum/Maximum Query,即区间最值查询)问题的离线数据结构。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3865#include<cstdio>#include<cmath>#define max(x,y) (x)>(y)?(x):(y)#define N 100001int n,q,a[N],ST[N][20],l,r,p;int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++) scanf("%d",&a[i]),ST[i][0]=a[i];for(int k=1;k<=20;k++)for(int i=1;i<=n;i++)if(i+(1<<k)-1<=n) ST[i][k]=max(ST[i][k-1],ST[i+(1<<(k-1))][k-1]);for(int i=1;i<=q;i++){scanf("%d%d",&l,&r);p=log2(r-l+1);printf("%d\n",max(ST[l][p],ST[r-(1<<p)+1][p]));}return 0;}
复杂度
其基本定应用为:把一个长度为的串,分成约块,相邻两块的大小不小于根号,每一块的大小不超过。这样就可以在的时间内解决一个插入、询问、拆分、合并等等的操作。
//problemID:https://www.lydsy.com/JudgeOnline/problem.php?id=3337#include<cstring>#include<iostream>#include<cctype>#include<cstdio>#include<algorithm>#include<queue>#include<cmath>#define writ(x,c) write(x),putchar(c);typedef long long ll;const int N=10000,MAX=1<<29;using namespace std;inline int read(){char c;int x=0;bool f=0;for(;!isdigit(c);c=getchar()) if(c=='-') f=1;for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return (f ? -x : x);}template <class _T>void write(_T x){if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0');}int n,m,size;struct node{int d[1003],s[1003],rev,add,same,size,next;ll sum;}a[N];queue<int> q;void Init(){}int new_node(){int temp=q.front();q.pop();return temp;}void clear(int x){a[x].rev=a[x].add=a[x].same=a[x].size=a[x].rev=0;}void erase(int x){q.push(x);clear(x);}void find(int &pos,int &now){for(now=0;a[now].next!=-1&&pos>a[now].size;now=a[now].next)pos-=a[now].size;}void down(int now){int tot=a[now].size;if(a[now].rev){a[now].rev=false;int tt=(tot>>1);for(int u=1;u<=tt;u++) swap(a[now].d[u],a[now].d[tot-u+1]);}if(a[now].same!=0){for(int u=1;u<=tot;u++)a[now].d[u]=a[now].same;a[now].sum=a[now].same*tot,a[now].same=0;}if(a[now].add!=0){for(int u=1;u<=tot;u++)a[now].d[u]+=a[now].add;a[now].sum=a[now].sum+a[now].add*tot,a[now].add=0;}}void update(int x){a[x].sum=0;for(int u=1;u<=a[x].size;u++)a[x].sum+=a[x].d[u],a[x].s[u]=a[x].d[u];sort(a[x].s+1,a[x].s+a[x].size+1);}void spilt(int now,int pos){down(now);int t=new_node();for(int u=pos;u<=a[now].size;u++)a[t].d[++a[t].size]=a[now].d[u];a[t].next=a[now].next,a[now].next=t,a[now].size=max(pos-1,0);update(t);update(now);}void Merge(int now){int k=a[now].next;down(now);down(k);for(int u=1;u<=a[k].size;u++)a[now].d[++a[now].size]=a[k].d[u];a[now].next=a[k].next;erase(k);update(now);}void maintain(int now){for(;now!=-1;now=a[now].next)if(a[now].next!=-1&&a[now].size+a[a[now].next].size<=size)Merge(now);}void ins(int pos,int x){int now;pos++;find(pos,now);spilt(now,pos);a[now].d[++a[now].size]=x,a[now].sum+=x;int lalal;for(lalal=1;lalal<a[now].size;lalal++)if(a[now].s[lalal]>x) break;for(int u=a[now].size;u>lalal;u--)a[now].s[u]=a[now].s[u-1];a[now].s[lalal]=x;maintain(now);}void del(int pos){int now;find(pos,now);down(now);for(int u=pos+1;u<=a[now].size;u++)a[now].d[u-1]=a[now].d[u];a[now].size--;update(now);maintain(now);}void solve(int l,int r,int &lp,int &rp){int pos=l;find(pos,lp);spilt(lp,pos);pos=r+1;find(pos,rp);spilt(rp,pos);pos=r;find(pos,rp);}int st[N];void rverse(int l,int r){int lp,rp;solve(l,r,lp,rp);int now=lp,top=0;for(int u=a[lp].next;u!=a[rp].next;u=a[u].next)st[++top]=u,a[u].rev^=1;a[st[1]].next=a[rp].next;for(int u=top;u>1;u--)a[st[u]].next=st[u-1];a[lp].next=rp;maintain(lp);}void slip(int l,int r,int k){int lp,mp,rp,np;solve(l,r-k,lp,mp),solve(r-k+1,r,mp,rp);np=a[lp].next,a[lp].next=a[mp].next,a[mp].next=a[rp].next,a[rp].next=np;maintain(lp);}void add(int l,int r,int val){int lp,rp;solve(l,r,lp,rp);for(int now=a[lp].next;now!=a[rp].next;now=a[now].next)a[now].add+=val,a[now].sum=a[now].sum+a[now].size*val;maintain(lp);}void same(int l,int r,int val){int lp,rp;solve(l,r,lp,rp);for(int now=a[lp].next;now!=a[rp].next;now=a[now].next)a[now].add=0,a[now].same=val,a[now].sum=a[now].size*val;maintain(lp);}ll getsum(int l,int r){int lp,rp;solve(l,r,lp,rp);ll ans=0;for(int now=a[lp].next;now!=a[rp].next;now=a[now].next)ans=ans+a[now].sum;maintain(lp);return ans;}int getcha(int l,int r){int lp,rp;solve(l,r,lp,rp);int maxx=-MAX,minn=MAX;for(int now=a[lp].next;now!=a[rp].next;now=a[now].next)if(a[now].size!=0)if(a[now].same!=0)minn=min(minn,a[now].same+a[now].add),maxx=max(maxx,a[now].same+a[now].add);elseminn=min(minn,a[now].s[1]+a[now].add),maxx=max(maxx,a[now].s[a[now].size]+a[now].add);maintain(lp);return maxx-minn;}int near(int l,int r,int val){int lp,rp;solve(l,r,lp,rp);int ans=MAX;for(int now=a[lp].next;now!=a[rp].next;now=a[now].next){if(a[now].same)ans=min(ans,abs(val-a[now].same-a[now].add));else{int id=lower_bound(a[now].s+1,a[now].s+a[now].size+1,val-a[now].add)-a[now].s;if(id!=a[now].size+1)ans=min(ans,a[now].s[id]+a[now].add-val);if(id!=1)id--,ans=min(ans,val-a[now].s[id]-a[now].add);}}maintain(lp);return ans;}int rank(int l,int r,int k){int lp,rp;solve(l,r,lp,rp);int ll=0,rr=MAX;while(ll<rr){int mid=(ll+rr)/2+1,sum=1;for(int now=a[lp].next;now!=a[rp].next;now=a[now].next){if(a[now].same!=0){if(a[now].same+a[now].add<mid)sum=sum+a[now].size;}else{int id=upper_bound(a[now].s+1,a[now].s+a[now].size+1,mid-a[now].add-1)-a[now].s;sum=sum+max(0,id-1);}}if(k>=sum) ll=mid;else rr=mid-1;}maintain(lp);return ll;}int sec(int l,int r,int val){int lp,rp;solve(l,r,lp,rp);int ans=0;for(int now=a[lp].next;now!=a[rp].next;now=a[now].next){if(a[now].same!=0){if(a[now].same+a[now].add<val)ans=ans+a[now].size;}else{int it=upper_bound(a[now].s+1,a[now].s+a[now].size+1,val-a[now].add-1)-a[now].s;ans=ans+it-1;}}maintain(lp);return ans;}int main(){n=read(),size=sqrt(n);for(int i=1;i<N;i++) q.push(i);a[0].next=-1;a[0].size=0;for(int u=1;u<=n;u++){int x=read();ins(u-1,x);}m=read();while(m--){register int op,x,y,z;op=read();switch(op){case 1:x=read();y=read();ins(x,y);break;case 2:x=read();del(x);break;case 3:x=read();y=read();rverse(x,y);break;case 4:x=read();y=read();z=read();slip(x,y,z);break;case 5:x=read();y=read();z=read();add(x,y,z);break;case 6:x=read();y=read();z=read();same(x,y,z);break;case 7:x=read();y=read();writ(getsum(x,y),'\n');break;case 8:x=read();y=read();writ(getcha(x,y),'\n');break;case 9:x=read();y=read();z=read();writ(near(x,y,z),'\n');break;case 10:x=read();y=read();z=read();writ(rank(x,y,z),'\n');break;case 11:x=read();y=read();z=read();writ(sec(x,y,z),'\n');break;}}return 0;}
复杂度
伸展树(Splay Tree),也叫分裂树,是一种二叉排序树,它能在内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造,后勃刚对其进行了改进。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。
//problemID:https://www.luogu.org/problemnew/show/P3391#include<bits/stdc++.h>#define N 100005using namespace std;int n,m;int fa[N],ch[N][2],size[N],rev[N],rt;inline void pushup(int x){size[x]=size[ch[x][0]]+size[ch[x][1]]+1;}void pushdown(int x){if(rev[x]){swap(ch[x][0],ch[x][1]);rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;rev[x]=0;}}void rotate(int x,int &k){int y=fa[x],z=fa[y],kind;if(ch[y][0]==x)kind=1;else kind=0;if(y==k)k=x;else{if(ch[z][0]==y)ch[z][0]=x;else ch[z][1]=x;}ch[y][kind^1]=ch[x][kind];fa[ch[y][kind^1]]=y;ch[x][kind]=y;fa[y]=x;fa[x]=z;pushup(x);pushup(y);}void splay(int x,int &k){while(x!=k){int y=fa[x],z=fa[y];if(y!=k){if((ch[y][0]==x)^(ch[z][0]==y))rotate(x,k);else rotate(y,k);}rotate(x,k);}}void build(int l,int r,int f){if(l>r)return;int mid=(l+r)/2;if(mid<f)ch[f][0]=mid;else ch[f][1]=mid;fa[mid]=f;size[mid]=1;if(l==r)return;build(l,mid-1,mid);build(mid+1,r,mid);pushup(mid);}int find(int x,int k){pushdown(x);int s=size[ch[x][0]];if(k==s+1)return x;if(k<=s)return find(ch[x][0],k);else return find(ch[x][1],k-s-1);}void rever(int l,int r){int x=find(rt,l),y=find(rt,r+2);splay(x,rt);splay(y,ch[x][1]);int z=ch[y][0];rev[z]^=1;}int main(){scanf("%d%d",&n,&m);rt=(n+3)/2;build(1,n+2,rt);for(int i=1;i<=m;i++){int L,R;scanf("%d%d",&L,&R);rever(L,R);}for(int i=2;i<=n+1;i++)printf("%d ",find(rt,i)-1);return 0;}
复杂度
树堆,在数据结构中也称Treap,是指有一个随机附加域满足堆的性质的二叉搜索树,其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为。
相对于其他的平衡二叉搜索树,Treap的特点是实现简单,且能基本实现随机平衡的结构。
#include<iostream>#include<cstdio>#include<queue>#include<cstring>#include<algorithm>#include<climits>typedef long long LL;using namespace std;int RD(){int out = 0,flag = 1;char c = getchar();while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}return flag * out;}//第一次打treap,不压行写注释XDconst int maxn = 1000019,INF = 1e9;//平衡树,利用BST性质查询和修改,利用随机和堆优先级来保持平衡,把树的深度控制在log N,保证了操作效率//基本平衡树有以下几个比较重要的函数:新建,插入,删除,旋转//节点的基本属性有val(值),dat(随机出来的优先级)//通过增加属性,结合BST的性质可以达到一些效果,如size(子树大小,查询排名),cnt(每个节点包含的副本数)等int na;int ch[maxn][2];//[i][0]代表i左儿子,[i][1]代表i右儿子int val[maxn],dat[maxn];int size[maxn],cnt[maxn];int tot,root;int New(int v){//新增节点,val[++tot] = v;//节点赋值dat[tot] = rand();//随机优先级size[tot] = 1;//目前是新建叶子节点,所以子树大小为1cnt[tot] = 1;//新建节点同理副本数为1return tot;}void pushup(int id){//和线段树的pushup更新一样size[id] = size[ch[id][0]] + size[ch[id][1]] + cnt[id];//本节点子树大小 = 左儿子子树大小 + 右儿子子树大小 + 本节点副本数}void build(){root = New(-INF),ch[root][1] = New(INF);//先加入正无穷和负无穷,便于之后操作(貌似不加也行)pushup(root);//因为INF > -INF,所以是右子树,}void Rotate(int &id,int d){//id是引用传递,d(irection)为旋转方向,0为左旋,1为右旋int temp = ch[id][d ^ 1];//旋转理解:找个动图看一看就好(或参见其他OIer的blog)ch[id][d ^ 1] = ch[temp][d];//这里讲一个记忆技巧,这些数据都是被记录后马上修改ch[temp][d] = id;//所以像“Z”一样id = temp;//比如这个id,在上一行才被记录过,ch[temp][d]、ch[id][d ^ 1]也是一样的pushup(ch[id][d]),pushup(id);//旋转以后size会改变,看图就会发现只更新自己和转上来的点,pushup一下,注意先子节点再父节点}//旋转实质是({在满足BST的性质的基础上比较优先级}通过交换本节点和其某个叶子节点)把链叉开成二叉形状(从而控制深度),可以看图理解一下void insert(int &id,int v){//id依然是引用,在新建节点时可以体现if(!id){id = New(v);//若节点为空,则新建一个节点return ;}if(v == val[id])cnt[id]++;//若节点已存在,则副本数++;else{//要满足BST性质,小于插到左边,大于插到右边int d = v < val[id] ? 0 : 1;//这个d是方向的意思,按照BST的性质,小于本节点则向左,大于向右insert(ch[id][d],v);//递归实现if(dat[id] < dat[ch[id][d]])Rotate(id,d ^ 1);//(参考一下图)与左节点交换右旋,与右节点交换左旋}pushup(id);//现在更新一下本节点的信息}void Remove(int &id,int v){//最难de部分了if(!id)return ;//到这了发现查不到这个节点,该点不存在,直接返回if(v == val[id]){//检索到了这个值if(cnt[id] > 1){cnt[id]--,pushup(id);return ;}//若副本不止一个,减去一个就好if(ch[id][0] || ch[id][1]){//发现只有一个值,且有儿子节点,我们只能把值旋转到底部删除if(!ch[id][1] || dat[ch[id][0]] > dat[ch[id][1]]){//当前点被移走之后,会有一个新的点补上来(左儿子或右儿子),按照优先级,优先级大的补上来Rotate(id,1),Remove(ch[id][1],v);//我们会发现,右旋是与左儿子交换,当前点变成右节点;左旋则是与右儿子交换,当前点变为左节点}else Rotate(id,0),Remove(ch[id][0],v);pushup(id);}else id = 0;//发现本节点是叶子节点,直接删除return ;//这个return对应的是检索到值de所有情况}v < val[id] ? Remove(ch[id][0],v) : Remove(ch[id][1],v);//继续BST性质pushup(id);}int get_rank(int id,int v){if(!id)return 0;//若查询值不存在,返回if(v == val[id])return size[ch[id][0]] + 1;//查询到该值,由BST性质可知:该点左边值都比该点的值(查询值)小,故rank为左儿子大小 + 1else if(v < val[id])return get_rank(ch[id][0],v);//发现需查询的点在该点左边,往左边递归查询else return size[ch[id][0]] + cnt[id] + get_rank(ch[id][1],v);//若查询值大于该点值。说明询问点在当前点的右侧,且此点的值都小于查询值,所以要加上cnt[id]}int get_val(int id,int rank){if(!id)return INF;//一直向右找找不到,说明是正无穷if(rank <= size[ch[id][0]])return get_val(ch[id][0],rank);//左边排名已经大于rank了,说明rank对应的值在左儿子那里else if(rank <= size[ch[id][0]] + cnt[id])return val[id];//上一步排除了在左区间的情况,若是rank在左与中(目前节点)中,则直接返回目前节点(中区间)的值else return get_val(ch[id][1],rank - size[ch[id][0]] - cnt[id]);//剩下只能在右区间找了,rank减去左区间大小和中区间,继续递归}int get_pre(int v){int id = root,pre;//递归不好返回,以循环求解while(id){//查到节点不存在为止if(val[id] < v)pre = val[id],id = ch[id][1];//满足当前节点比目标小,往当前节点的右侧寻找最优值else id = ch[id][0];//无论是比目标节点大还是等于目标节点,都不满足前驱条件,应往更小处靠近}return pre;}int get_next(int v){int id = root,next;while(id){if(val[id] > v)next = val[id],id = ch[id][0];//同理,满足条件向左寻找更小解(也就是最优解)else id = ch[id][1];//与上方同理}return next;}int main(){build();//不要忘记初始化[运行build()会连同root一并初始化,所以很重要]na = RD();for(int i = 1;i <= na;i++){int cmd = RD(),x = RD();if(cmd == 1)insert(root,x);//函数都写好了,注意:需要递归的函数都从根开始,不需要递归的函数直接查询else if(cmd == 2)Remove(root,x);else if(cmd == 3)printf("%d\n",get_rank(root,x) - 1);//注意:因为初始化时插入了INF和-INF,所以查询排名时要减1(-INF不是第一小,是“第零小”)else if(cmd == 4)printf("%d\n",get_val(root,x + 1));//同理,用排名查询值得时候要查x + 1名,因为第一名(其实不是)是-INFelse if(cmd == 5)printf("%d\n",get_pre(x));else if(cmd == 6)printf("%d\n",get_next(x));}return 0;}
复杂度
//problemID:https://www.luogu.org/problemnew/show/P3369#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>using namespace std;struct node{int siz,val,key,lch,rch;}t[100005];int tot,seed=233,root=1;int Rand(){//随机key值return seed=int(seed*482711ll%2147483647);}int NEW(int val){//新建节点t[++tot].siz=1;t[tot].val=val;t[tot].key=Rand();t[tot].lch=t[tot].rch=0;return tot;}void update(int now){//维护子树大小t[now].siz=t[t[now].lch].siz+t[t[now].rch].siz+1;}void split(int now,int &a,int &b,int val){//拆分操作//now原Treap,a左树,b右树,val判定值//注意传地址符if(now==0){a=b=0;//若now=0分割完毕;return;}if(t[now].val<=val)//因为now左子树中的所有值都小于now的值,所以若now属于左树,那么他们都属于左树递归now的右子树;a=now,split(t[now].rch,t[a].rch,b,val);//a=now已经使a的右子树=now的右子树,不再递归a的右子树;else//同上now右子树也都属于左树,递归左子树;b=now,split(t[now].lch,a,t[b].lch,val);update(now);//因为后面会用到左(右)树的siz所以更新维护}void merge(int &now,int a,int b){//合并操作//now新树if(a==0||b==0){now=a+b;//若某个树已空,则将另一个树整体插入return;}//按照key值合并(堆性质)if(t[a].key<t[b].key)//若a树key值<b树,那么b树属于a树的后代,因为b树恒大于a树,那么b树一定属于a树的右后代,a的左子树不变,直接赋给now,递归合并a的右子树和bnow=a,merge(t[now].rch,t[a].rch,b);elsenow=b,merge(t[now].lch,a,t[b].lch);//同理,a树一定是b树的左儿子,递归合并b的左儿子和aupdate(now);}void find(int now,int rank){//找第k大while(t[t[now].lch].siz+1!=rank){if(t[t[now].lch].siz>=rank)now=t[now].lch;//若左子树大小大于rank,找左子树elserank-=(t[t[now].lch].siz+1),now=t[now].rch;//找右子树(rank-左子树大小-树根(大小为1))号的元素}printf("%d\n",t[now].val);}void insert(int val){int x=0,y=0,z;z=NEW(val);//新建节点z,作为z树split(root,x,y,val);//将树分为两部分,x树为<=待插入值,y树大于merge(x,x,z);//合并x树和新节点z(树),赋给x树merge(root,x,y);//合并新x树和y树,赋给根//就这么简单}void delet(int val){int x=0,y=0,z=0;split(root,x,y,val);//分为x树为<=待删除,y树大于split(x,x,z,val-1);//x树分为新x树<待删除,z树等于待删除merge(z,t[z].lch,t[z].rch);//合并z树左右儿子,赋给z树,即丢弃z树根节点(实现删除)merge(x,x,z);merge(root,x,y);//合并,不在重复}void get_rank(int val){int x=0,y=0;split(root,x,y,val-1);//分为小于待查找值的x树和大于等于的y树printf("%d\n",t[x].siz+1);//即为待查找值的编号merge(root,x,y);//合并}void get_val(int rank){find(root,rank);//find查找即可}void get_pre(int val){int x=0,y=0;split(root,x,y,val-1);//x树为<=val-1值即小于val值find(x,t[x].siz);//在小于val值中找最大的(编号为siz的)就是前驱merge(root,x,y);}void get_nxt(int val){int x=0,y=0;split(root,x,y,val);//x树小于等于val值,那么y树大于val值find(y,1);//在y树中找最小的,即为后继merge(root,x,y);//合并}int main(){int i,j,k,m;NEW(2147483627);//初始虚节点t[1].siz=0;//siz为0,不算虚节点的大小scanf("%d",&m);for(i=1;i<=m;i++){scanf("%d%d",&j,&k);if(j==1)insert(k);if(j==2)delet(k);if(j==3)get_rank(k);if(j==4)get_val(k);if(j==5)get_pre(k);if(j==6)get_nxt(k);}return 0;}
复杂度
替罪羊树是计算机科学中,一种基于部分重建的自平衡二叉搜索树。在替罪羊树上,插入或删除节点的平摊最坏时间复杂度是,搜索节点的最坏时间复杂度是。
//problemID:https://www.luogu.org/problemnew/show/P3369#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define alpha 0.8#define maxn 2000001#define ri register#define il inlineusing namespace std;struct scapegoat{int son[2], val, valid, total;bool exist;}e[maxn];int memory[maxn];int cur[maxn];int root, pool, poi, cnt, to_rebuild;il bool isbad(int now){if((double)e[now].valid*alpha <= (double)max(e[e[now].son[0]].valid, e[e[now].son[1]].valid)) return true;return false;}void dfs(int now){if(!now) return;dfs(e[now].son[0]);if(e[now].exist) cur[++poi] = now;else memory[++pool] = now;dfs(e[now].son[1]);}void build(int l, int r, int &now){int mid = l+r>>1;now = cur[mid];if(l == r){e[now].son[0] = e[now].son[1] = 0;e[now].total = e[now].valid = 1;return;}if(l < mid) build(l,mid-1,e[now].son[0]);else e[now].son[0] = 0;build(mid+1,r,e[now].son[1]);e[now].total = e[e[now].son[0]].total + e[e[now].son[1]].total + 1;e[now].valid = e[e[now].son[0]].valid + e[e[now].son[1]].valid + 1;}il void rebuild(int &now){poi = 0;dfs(now);if(poi) build(1,poi,now);else now = 0;}il int find_rank(int k){int now = root;int ans = 1;while(now){if(e[now].val >= k) now = e[now].son[0];else{ans += e[e[now].son[0]].valid + e[now].exist;now = e[now].son[1];}}return ans;}il int find_kth(int k){int now = root;while(now){if(e[now].exist&&e[e[now].son[0]].valid+1 == k) return e[now].val;else if(e[e[now].son[0]].valid >= k) now = e[now].son[0];else{k -= e[e[now].son[0]].valid + e[now].exist;now = e[now].son[1];}}}void insert(int &now, int val){if(!now){now = memory[pool--]; e[now].val = val;e[now].exist = e[now].total = e[now].valid = 1;e[now].son[0] = e[now].son[1] = 0;return;}e[now].total++, e[now].valid++;if(e[now].val >= val) insert(e[now].son[0], val);else insert(e[now].son[1], val);if(!isbad(now)){if(to_rebuild){if(e[now].son[0] == to_rebuild) rebuild(e[now].son[0]);else rebuild(e[now].son[1]);to_rebuild = 0;}}else to_rebuild = now;}il void delete_pos(int &now, int tar) //target(目标){if(e[now].exist&&e[e[now].son[0]].valid+ 1 == tar){e[now].exist = 0; e[now].valid--; return;}e[now].valid--;if(e[e[now].son[0]].valid + e[now].exist >= tar) delete_pos(e[now].son[0], tar);else delete_pos(e[now].son[1],tar-e[e[now].son[0]].valid-e[now].exist);}il void delete_val(int tar){delete_pos(root, find_rank(tar));if((double)e[root].total*alpha > e[root].valid) rebuild(root);}int main(){int opt, x, m;for(int i = 2000000; i >= 1; i--) memory[++pool] = i;scanf("%d",&m);while(m--){scanf("%d%d",&opt,&x);if(opt == 1) {insert(root, x);}if(opt == 2) {delete_val(x);}if(opt == 3) {printf("%d\n",find_rank(x));}if(opt == 4) {printf("%d\n",find_kth(x));}if(opt == 5) {printf("%d\n",find_kth(find_rank(x)-1));}if(opt == 6) {printf("%d\n",find_kth(find_rank(x+1)));}}return 0;}
复杂度
#include <algorithm>#include <iostream>#include <fstream>#include <cstring>#include <cstdlib>#include <complex>#include <string>#include <cstdio>#include <vector>#include <bitset>#include <cmath>#include <ctime>#include <queue>#include <stack>#include <map>#include <set>using namespace std;const int MAXN = 1e5 + 100;int n, m;int a[MAXN];namespace Treap{struct balanced{int w;int sz;int num;int fix;int ch[2];};int tot;balanced tree[MAXN * 20];int newnode(int w){++tot;tree[tot].w = w;tree[tot].fix = rand();tree[tot].num = 1;tree[tot].ch[0] = tree[tot].ch[1] = 0;tree[tot].sz = 1;return tot;}void pushup(int p){tree[p].sz = tree[tree[p].ch[0]].sz + tree[tree[p].ch[1]].sz + tree[p].num;}void rotate(int &p, int d){int y = tree[p].ch[d];tree[p].ch[d] = tree[y].ch[d ^ 1];tree[y].ch[d ^ 1] = p;pushup(p);pushup(y);p = y;}void insert(int &p, int w){if (!p)p = newnode(w);else if (tree[p].w == w)++tree[p].num;else{if (tree[p].w > w){insert(tree[p].ch[0], w);if (tree[tree[p].ch[0]].fix > tree[p].fix)rotate(p, 0);}else{insert(tree[p].ch[1], w);if (tree[tree[p].ch[1]].fix > tree[p].fix)rotate(p, 1);}}pushup(p);}void remove(int &p, int w){if (tree[p].w > w)remove(tree[p].ch[0], w);else if (tree[p].w < w)remove(tree[p].ch[1], w);else{if (tree[p].num > 1)--tree[p].num;else{if (!tree[p].ch[0] && !tree[p].ch[1])p = 0;else if (!tree[p].ch[0]){rotate(p, 1);remove(tree[p].ch[0], w);}else if (!tree[p].ch[1]){rotate(p, 0);remove(tree[p].ch[1], w);}else{if (tree[tree[p].ch[0]].fix > tree[tree[p].ch[1]].fix){rotate(p, 0);remove(tree[p].ch[1], w);}else{rotate(p, 1);remove(tree[p].ch[0], w);}}}}if (p)pushup(p);}int queryrank(int p, int k) // return the highest rank of value 'k'{if (!p)return 0;if (tree[p].w > k)return queryrank(tree[p].ch[0], k);else if (tree[p].w == k)return tree[tree[p].ch[0]].sz;elsereturn tree[tree[p].ch[0]].sz + tree[p].num + queryrank(tree[p].ch[1], k);}int querynum(int p, int k) // return the value of kth rank node{if (tree[tree[p].ch[0]].sz + 1 == k)return tree[p].w;else if (tree[tree[p].ch[0]].sz + 1 < k)return querynum(tree[p].ch[1], k - 1 - tree[tree[p].ch[0]].sz);elsereturn querynum(tree[p].ch[0], k);}int querypre(int p, int k) // return the prefix of value k{if (!p)return -2147483647;if (tree[p].w >= k)return querypre(tree[p].ch[0], k);elsereturn max(tree[p].w, querypre(tree[p].ch[1], k));}int querysuf(int p, int k) // return the suffix of value k{if (!p)return 2147483647;if (tree[p].w <= k)return querysuf(tree[p].ch[1], k);elsereturn min(tree[p].w, querysuf(tree[p].ch[0], k));}void listall(int p){if (tree[p].ch[0])listall(tree[p].ch[0]);cerr << tree[p].w << ",sz=" << tree[p].num << " ";if (tree[p].ch[1])listall(tree[p].ch[1]);}}using Treap::listall;namespace SEG{struct segment{int l;int r;int root;};segment tree[MAXN * 8];void build(int p, int l, int r){tree[p].l = l;tree[p].r = r;for (int i = l; i < r + 1; ++i)Treap::insert(tree[p].root, a[i]);if (l != r){int mid = (l + r) / 2;build(p * 2, l, mid);build(p * 2 + 1, mid + 1, r);}}void modify(int p, int x, int y){Treap::remove(tree[p].root, a[x]);Treap::insert(tree[p].root, y);if (tree[p].l == tree[p].r)return;int mid = (tree[p].l + tree[p].r) / 2;if (x > mid)modify(p * 2 + 1, x, y);elsemodify(p * 2, x, y);}int queryrank(int p, int l, int r, int k) // query the highest rank of value 'k'{if (tree[p].l > r || tree[p].r < l)return 0;if (tree[p].l >= l && tree[p].r <= r)return Treap::queryrank(tree[p].root, k);elsereturn queryrank(p * 2, l, r, k) + queryrank(p * 2 + 1, l, r, k);}int querynum(int u, int v, int k) // query the value of kth num{int l = 0, r = 1e8;while (l < r){int mid = (l + r + 1) / 2;if (queryrank(1, u, v, mid) < k)l = mid;elser = mid - 1;}return r;}int querypre(int p, int l, int r, int k){if (tree[p].l > r || tree[p].r < l)return -2147483647;if (tree[p].l >= l && tree[p].r <= r)return Treap::querypre(tree[p].root, k);elsereturn max(querypre(p * 2, l, r, k), querypre(p * 2 + 1, l, r, k));}int querysuf(int p, int l, int r, int k){if (tree[p].l > r || tree[p].r < l)return 2147483647;if (tree[p].l >= l && tree[p].r <= r)return Treap::querysuf(tree[p].root, k);elsereturn min(querysuf(p * 2, l, r, k), querysuf(p * 2 + 1, l, r, k));}}int read(){char ch = getchar();int x = 0, flag = 1;while (ch != '-' && (ch < '0' || ch > '9'))ch = getchar();if (ch == '-'){ch = getchar();flag = -1;}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * flag;}int main(){n = read();m = read();for (int i = 1; i < n + 1; ++i)a[i] = read();SEG::build(1, 1, n);for (int i = 0; i < m; ++i){int opt = read();if (opt == 3){int x = read(), y = read();SEG::modify(1, x, y);a[x] = y;}else{int l = read(), r = read(), k = read();if (opt == 1)printf("%d\n", SEG::queryrank(1, l, r, k) + 1);else if (opt == 2)printf("%d\n", SEG::querynum(l, r, k));else if (opt == 4)printf("%d\n", SEG::querypre(1, l, r, k));elseprintf("%d\n", SEG::querysuf(1, l, r, k));}}return 0;}
//problemID:https://www.luogu.org/problemnew/show/P3834#include<cstdio>#include<cstring>#include<algorithm>#define mid (l+r)/2using namespace std;const int N = 200010;int n, q, m, cnt = 0;int a[N], b[N], T[N];int sum[N<<5], L[N<<5], R[N<<5];inline int build(int l, int r){int rt = ++ cnt;sum[rt] = 0;if (l < r){L[rt] = build(l, mid);R[rt] = build(mid+1, r);}return rt;}inline int update(int pre, int l, int r, int x){int rt = ++ cnt;L[rt] = L[pre]; R[rt] = R[pre]; sum[rt] = sum[pre]+1;if (l < r){if (x <= mid) L[rt] = update(L[pre], l, mid, x);else R[rt] = update(R[pre], mid+1, r, x);}return rt;}inline int query(int u, int v, int l, int r, int k){if (l >= r) return l;int x = sum[L[v]] - sum[L[u]];if (x >= k) return query(L[u], L[v], l, mid, k);else return query(R[u], R[v], mid+1, r, k-x);}int main(){scanf("%d%d", &n, &q);for (int i = 1; i <= n; i ++){scanf("%d", &a[i]);b[i] = a[i];}sort(b+1, b+1+n);m = unique(b+1, b+1+n)-b-1;T[0] = build(1, m);for (int i = 1; i <= n; i ++){int t = lower_bound(b+1, b+1+m, a[i])-b;T[i] = update(T[i-1], 1, m, t);}while (q --){int x, y, z;scanf("%d%d%d", &x, &y, &z);int t = query(T[x-1], T[y], 1, m, z);printf("%d\n", b[t]);}return 0;}
LCT是一种解决动态树问题的方法,由tarjan~~(为什么又是他)~~在1982年提出,最原始的论文在这里,在论文中,tarjan除了介绍了均摊复杂度为的LCT之外,还介绍了一种严格的算法。
//problemID:https://www.luogu.org/problemnew/show/P3690#include<bits/stdc++.h>#define N 300005using namespace std;int n,m,val[N];struct Link_Cut_Tree{int top,c[N][2],fa[N],xr[N],q[N],rev[N];inline void pushup(int x){xr[x]=xr[c[x][0]]^xr[c[x][1]]^val[x];}inline void pushdown(int x){int l=c[x][0],r=c[x][1];if(rev[x]){rev[l]^=1;rev[r]^=1;rev[x]^=1;swap(c[x][0],c[x][1]);}}inline bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}void rotate(int x){int y=fa[x],z=fa[y],l,r;if(c[y][0]==x)l=0;else l=1;r=l^1;if(!isroot(y)){if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;}fa[x]=z;fa[y]=x;fa[c[x][r]]=y;c[y][l]=c[x][r];c[x][r]=y;pushup(y);pushup(x);}void splay(int x){top=1;q[top]=x;for(int i=x; !isroot(i); i=fa[i])q[++top]=fa[i];for(int i=top; i; i--)pushdown(q[i]);while(!isroot(x)){int y=fa[x],z=fa[y];if(!isroot(y)){if((c[y][0]==x)^(c[z][0]==y))rotate(x);else rotate(y);}rotate(x);}}void access(int x){for(int t=0; x; t=x,x=fa[x])splay(x),c[x][1]=t,pushup(x);}void makeroot(int x){access(x);splay(x);rev[x]^=1;}int find(int x){access(x);splay(x);while(c[x][0])x=c[x][0];return x;}void split(int x,int y){makeroot(x);access(y);splay(y);}void cut(int x,int y){split(x,y);if(c[y][0]==x)c[y][0]=0,fa[x]=0;}void link(int x,int y){makeroot(x);fa[x]=y;}} T;inline int read(){int f=1,x=0;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');return f*x;}int main(){n=read();m=read();for(int i=1; i<=n; i++)val[i]=read(),T.xr[i]=val[i];while(m--){int opt=read();if(opt==0){int x=read(),y=read();T.split(x,y);printf("%d\n",T.xr[y]);}if(opt==1){int x=read(),y=read(),xx=T.find(x),yy=T.find(y);if(xx!=yy)T.link(x,y);}if(opt==2){int x=read(),y=read(),xx=T.find(x),yy=T.find(y);if(xx==yy)T.cut(x,y);}if(opt==3){int x=read(),y=read();T.access(x);T.splay(x);val[x]=y;T.pushup(x);}}return 0;}
复杂度
/*Coded by Apojacsleam*///problemID:http://codevs.cn/problem/3187/#include<cstdio>#include<queue>using namespace std;queue<int> q;int n,opt,k;int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&opt);if(opt==1) scanf("%d",&k),q.push(k);else if(opt==2) q.pop();else printf("%d\n",q.front());}return 0;}
/*Coded by Apojacsleam*///problemID:http://codevs.cn/problem/3139/#include<cstdio>#include<stack>using namespace std;int n,opt,k;stack<int> s;int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&opt);if(opt==1) scanf("%d",&k),s.push(k);else if(opt==2) s.pop();else printf("%d\n",s.top());}return 0;}
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3378#sub#include<cstdio>#include<queue>#include<cctype>using namespace std;priority_queue<int,vector<int>,greater<int> > q;int m,a,b;int readin(){int res=0;char ch=0;bool XX=false;for(;!isdigit(ch);ch=getchar())if(ch=='-') XX=true;for(;isdigit(ch);ch=getchar()) res=(res<<3)+(res<<1)+ch-'0';return (XX?-res:res);}void writeout(int res){if(res<0) {putchar('-');res=-res;}if(res>9) writeout(res/10);putchar(res%10+'0');}int main(){m=readin();for(int i=1;i<=m;i++){a=readin();if(a==1){b=readin();q.push(b);}else if(a==2) writeout(q.top()),putchar('\n');else q.pop();}return 0;}
#include <iostream>#include<deque>using namespace std;int main(){deque<int> mydeque (7,6); // 初始化deque为7个int,每个int值为6mydeque.push_front(2); //插入头mydeque.push_back(3); //插入尾cout << "mydeque size: " << mydeque.size() << endl;cout << "mydeque contains:";for (unsigned i=0; i<mydeque.size();i++) cout << " " << mydeque[i];cout << endl;return 0;}
/*Coded by Apojacsleam*///problemID:http://codevs.cn/problem/1076/#include<cstdio>#include<algorithm>int n,a[100001];int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);std::sort(a+1,a+n+1);for(int i=1;i<=n;i++) printf("%d%c",a[i],i==n?'\n':' ');return 0;}
/*copy by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3370#include<iostream>#include<string>#include<map>using namespace std;map<string,int>p;int n;string s;int main(){cin>>n;for(int i=1;i<=n;i++){cin>>s;p[s]++;}cout<<p.size();return 0;}
#include <string.h>#include <iostream.h>void main(void){char sStr1[100],sStr2[100],sStr3[100];sStr1[0] = sStr2[0] = sStr3[0] = '\0';strcpy(sStr1,"Golden Global View");strcpy(sStr2,"bal");strcpy(sStr3,"Hell");char *p = strstr(sStr1,sStr2); //从sStr1中查找balchar *p2 = strstr(sStr1,sStr3); //从sStr1中查找Hellcout<<(p==NULL?"NULL":p)<<endl;cout<<(p2==NULL?"NULL":p2)<<endl;}
#include <iostream> // std::cout#include <algorithm> // std::find#include <vector> // std::vectorint main () {// using std::find with array and pointer:int myints[] = { 10, 20, 30, 40 };int * p;p = std::find (myints, myints+4, 30);if (p != myints+4)std::cout << "Element found in myints: " << *p << '\n';elsestd::cout << "Element not found in myints\n";// using std::find with vector and iterator:std::vector<int> myvector (myints,myints+4);std::vector<int>::iterator it;it = find (myvector.begin(), myvector.end(), 30);if (it != myvector.end())std::cout << "Element found in myvector: " << *it << '\n';elsestd::cout << "Element not found in myvector\n";return 0;}
#include <iostream>#include <set>using namespace std;int main(){/*type of the collection:*-no duplicates*-elements are integral values*-descending order*/typedef set<int,greater<int> > IntSet;IntSet coll1; // empty set container//insert elements in random ordercoll1.insert(4);coll1.insert(3);coll1.insert(5);coll1.insert(1);coll1.insert(6);coll1.insert(2);coll1.insert(5);//iterate over all elements and print themIntSet::iterator pos;for (pos = coll1.begin(); pos != coll1.end(); ++pos) {cout << *pos << ' ';}cout << endl;//insert 4 again and process return valuepair<IntSet::iterator,bool> status = coll1.insert(4);if (status.second) {cout << "4 inserted as element "<< distance (coll1.begin(),status. first) + 1<< endl;}else {cout << "4 already exists" << endl;}//assign elements to another set with ascending orderset<int> coll2(coll1.begin(),coll1.end());//print all elements of the copycopy (coll2.begin(), coll2.end(),ostream_iterator<int>(cout," "));cout << endl;//remove all elements up to element with value 3coll2.erase (coll2.begin(), coll2.find(3));//remove all elements with value 5int num;num = coll2.erase (5);cout << num << " element(s) removed" << endl;//print all elementscopy (coll2.begin(), coll2.end(),ostream_iterator<int>(cout," "));cout << endl;}
#include <iostream>#include <set>using namespace std;int main(){/*type of the collection:*-duplicates allowed*-elements are integral values*-descending order*/typedef multiset<int,greater<int> > IntSet;IntSet coll1, // empty multiset container//insert elements in random ordercoll1.insert(4);coll1.insert(3);coll1.insert(5);coll1.insert(l);coll1.insert(6);coll1.insert(2);coll1.insert(5);//iterate over all elements and print themIntSet::iterator pos;for (pos = coll1.begin(); pos != coll1.end(); ++pos) {cout << *pos << ' ';}cout << endl;//insert 4 again and process return valueIntSet::iterator ipos = coll1.insert(4);cout << "4 inserted as element "<< distance (coll1.begin(),ipos) + 1<< endl;//assign elements to another multiset with ascending ordermultiset<int> coll2(coll1.begin(),coll1.end());//print all elements of the copycopy (coll2.begin(), coll2.end(),ostream_iterator<int>(cout," "));cout << endl;//remove all elements up to element with value 3coll2.erase (coll2.begin(), coll2.find(3));//remove all elements with value 5int num;num = coll2.erase (5);cout << num << " element(s) removed" << endl;//print all elementscopy (coll2.begin(), coll2.end(),ostream_iterator<int>(cout," "));cout << endl;}
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<ext/pb_ds/priority_queue.hpp>#define pir pair<ll,int>using namespace std;typedef long long ll;//typedef std::priority_queue<pir,vector<pir>,greater<pir> > heap;//3840 mstypedef __gnu_pbds::priority_queue<pir,greater<pir> > heap;//默认是pairing_heap_tag//3304 msconst int N=1e6+5,M=1e7+5;const ll INF=1e15;inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;}int n,m,T,rxa,rxc,rya,ryc,rp,a,b;int x,y,z;struct node{int v,w,next;}e[M];int cnt,head[N];ll dis[N];bool vis[N];inline void add(int u,int v,int w){e[++cnt].v=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;}heap q;inline void dijkstra(){int S;for(int i=1;i<=n;i++) dis[i]=INF;dis[S=1]=0;q.push(make_pair(dis[S],S));while(!q.empty()){pir t=q.top();q.pop();int x=t.second;if(vis[x]) continue;vis[x]=1;for(int i=head[x];i;i=e[i].next){int v=e[i].v;if(!vis[v]&&dis[v]>dis[x]+e[i].w){dis[v]=dis[x]+e[i].w;q.push(make_pair(dis[v],v));}}}}int main(){n=read();m=read();T=read();rxa=read();rxc=read();rya=read();ryc=read();rp=read();m=m-T;x=rxc%rp;y=ryc%rp;a=min(x%n+1,y%n+1);b=max(y%n+1,y%n+1);while(T--) add(a,b,100000000-100*a);while(m--) x=read(),y=read(),z=read(),add(x,y,z);dijkstra();printf("%lld",dis[n]);return 0;}
#include<cstdio>#include<ext/pb_ds/assoc_container.hpp>//pb_ds库这次内置了红黑树(red-black tree)、伸展树(splay tree)和排序向量树(ordered-vector tree,没找到通用译名,故自行翻译)。//这些封装好的树都支持插入(insert)、删除(erase)、求kth(find_by_order)、求rank(order_of_key)操作,O(logn)内完成using namespace std;using namespace __gnu_pbds;int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}tree<int,null_mapped_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>bbt;//SPOJG++版本稍旧(4.3.2),需要写成null_mapped_type才可以(高级版本可以写null_type)char in(){for(char ch=getchar();;ch=getchar()) if(ch>='A'&&ch<='Z') return ch;}int main(){char c;int x;for(int T=read();T--;){c=in();x=read();if(c=='I'){bbt.insert(x);}else if(c=='D'){bbt.erase(x);}else if(c=='K'){if(x<=bbt.size())printf("%d\n",*bbt.find_by_order(x-1));elseputs("invalid");}else{printf("%d\n",bbt.order_of_key(x));}}return 0;}
#include<cstdio>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>#pragma GCC optimize("02")using namespace std;using namespace __gnu_pbds;typedef long long ll;ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}typedef __gnu_pbds::tree<ll,null_mapped_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> T;T bbt;ll ans;int main(){ll n=read();for(ll i=1,o,k;i<=n;i++){o=read();k=read();if(o==1) bbt.insert((k<<20)+i);elseif(o==2) bbt.erase(bbt.lower_bound(k<<20));elseif(o==3) printf("%d\n",bbt.order_of_key(k<<20)+1);else{if(o==4) ans=*bbt.find_by_order(k-1);elseif(o==5) ans=*--bbt.lower_bound(k<<20);elseif(o==6) ans=*bbt.lower_bound((k+1)<<20);printf("%lld\n",ans>>20);}}return 0;}
算法是一种改进的字符串匹配算法,由和同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称算法)。
算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
具体实现就是实现一个函数,函数本身包含了模式串的局部匹配信息。时间复杂度。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3375#include<cstdio>#include<cstring>#define N 1000001char str[N],s[N];int next[N],n,m;int main(){scanf("%s%s",str+1,s+1);//这里一定要用scanf,由于gets在Linux和Windows下换行符不同,用gets这里会WA掉(血的教训!!!)n=strlen(str+1);m=strlen(s+1);int j=0;for(int i=2;i<=m;i++){while(j&&s[i]!=s[j+1]) j=next[j];if(s[i]==s[j+1]) j++;next[i]=j;}j=0;for(int i=1;i<=n;i++){while(j&&s[j+1]!=str[i]) j=next[j];if(str[i]==s[j+1]) j++;if(j==m) printf("%d\n",i-m+1),j=next[j];}for(int i=1;i<=m;i++)printf("%d%c",next[i],i==m?'\n':' ');return 0;}
复杂度
Manachar算法主要是处理字符串中关于回文串的问题的,它可以在的时间处理出以字符串中每一个字符为中心的回文串半径,由于将原字符串处理成两倍长度的新串,在每两个字符之间加入一个特定的特殊字符,因此原本长度为偶数的回文串就成了以中间特殊字符为中心的奇数长度的回文串了。
/*Coded by Apojacsleam*///problemID:https://www.luogu.org/problemnew/show/P3805#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define N 11000010char str[N],changedstr[N<<1];int p[N<<1];int change(){int j=0,len=strlen(str+1);changedstr[j++]='$';changedstr[j++]='#';for(int i=1;i<=len;i++) changedstr[j++]=str[i],changedstr[j++]='#';changedstr[j]='%';return j;}int Manacher(){int n=change(),maxID=1,maxPOS=1,ans=1;for(int i=1;i<=n;i++){if(i<maxPOS) p[i]=min(maxPOS-i,p[maxID*2-i]);else p[i]=1;while(changedstr[i-p[i]]==changedstr[i+p[i]]) p[i]++;if(p[i]+i>maxPOS){maxID=i;maxPOS=p[i]+i;}ans=max(ans,p[i]-1);}return ans;}int main(){scanf("%s",str+1);printf("%d",Manacher());return 0;}
复杂度
Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef unsigned long long ull;ull base=131;struct data{ull x,y;}a[10010];char s[10010];int n,ans=1;ull mod1=19260817;ull mod2=19660813;ull hash1(char s[]){int len=strlen(s);ull ans=0;for (int i=0;i<len;i++)ans=(ans*base+(ull)s[i])%mod1;return ans;}ull hash2(char s[]){int len=strlen(s);ull ans=0;for (int i=0;i<len;i++)ans=(ans*base+(ull)s[i])%mod2;return ans;}bool comp(data a,data b){return a.x<b.x;}signed main(){scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%s",s);a[i].x=hash1(s);a[i].y=hash2(s);}sort(a+1,a+n+1,comp);for (int i=2;i<=n;i++)if (a[i].x!=a[i-1].x || a[i-1].y!=a[i].y)ans++;printf("%d\n",ans);}
//problemID:https://www.luogu.org/problemnew/show/P1601#include<cstdio>#include<cstring>#define max(x,y) (x)>(y)?(x):(y)char a1[1000],b1[1000];int a[1000],b[1000],c[1000];int main(){scanf("%s",a1);scanf("%s",b1);if(a1[0]==48&&b1[0]==48) return 0*puts("0");int lena=strlen(a1),lenb=strlen(b1);for(int i=0;i<lena;i++)a[lena-i-1]=int(a1[i]-48);for(int i=0;i<lenb;i++)b[lenb-i-1]=int(b1[i]-48);//倒序输入便于进位int m=max(lena,lenb);for(int i=0;i<m;i++){c[i]+=a[i]+b[i];//不能直接赋值,要加上前面的进位while(c[i]>=10){c[i+1]++;c[i]-=10;}}m++;while(c[m]==0) m--; //删除前导0for(int i=m;i>=0;i--) putchar(c[i]+48);return 0;}
复杂度
//problemID:https://www.luogu.org/problemnew/show/P2142#include <iostream>#include <cmath>#include <cstring>using namespace std;int main(){char a[100010],b[100010];//设两个字符串cin>>a>>b;//读入两个字符串int c[100010],d[100010],h[100010],n1,n2,i,f=0,l=0;n1=strlen(a);//求字符串长度n2=strlen(b);for(i=0;i<n1/2;i++) swap(a[i],a[n1-1-i]);for(i=0;i<n2/2;i++) swap(b[i],b[n2-1-i]);for(i=0;i<n1;i++) c[i]=a[i]-'0';//把字符串a的字符转化为数字存到数组c当中。其中“-‘0’”为转换方法for(i=0;i<n2;i++) d[i]=b[i]-'0';if(n2>n1)//这一步是判断那个数长,哪个就大,就用哪个做被减数存到数组c中,哪个小就存到d中{for(i=0;i<n2;i++) swap(c[i],d[i]);//把两数交换,swap为交换函数f=1;//设一个旗帜,以后如果f=1就说明这数被减数比减数小,是负数。}if(n1>n2) swap(n1,n2); //取长的做for循环条件for(i=0;i<n2;i++) h[i]=c[i]-d[i];for(i=0;i<n2;i++)//这部就是借位{if(h[i]<0){h[i]=10+h[i];h[i+1]--;}}if(f==1) cout<<"-";//如果f等于一也就是结果为负数,打印“-”for(i=n2-1;i>=0;i--)//这步很重要! 这是在输出时把首位的0都去掉{if(l==0)//设了一个l,如果l为0意味着还没有碰到非零数,也就是有0就要去掉的0{if(h[i]!=0) //如果这数不为零{l=1;//l=1表明碰到了非零数了以后的0有实际意义要打印出来cout<<h[i];//打印此数continue;//然后跳出本次循环}}if(l!=0)//如果l不等于0,就说明这时的0有实际意义,要打印出来{cout<<h[i];}}}
复杂度
#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int L=100005;int na[L];string mul(string a,int b) //高精度a乘单精度b{string ans;int La=a.size();fill(na,na+L,0);for(int i=La-1;i>=0;i--) na[La-i-1]=a[i]-'0';int w=0;for(int i=0;i<La;i++) na[i]=na[i]*b+w,w=na[i]/10,na[i]=na[i]%10;while(w) na[La++]=w%10,w/=10;La--;while(La>=0) ans+=na[La--]+'0';return ans;}int main(){string a;int b;while(cin>>a>>b) cout<<mul(a,b)<<endl;return 0;}
复杂度
//problemID:http://codevs.cn/problem/3117/#include<bits/stdc++.h>using namespace std;char num1[505],num2[505];int com1[505],com2[506],re[1005],ans[1005];int main(){scanf("%s",&num1);scanf("%s",&num2);int len1=strlen(num1),len2=strlen(num2);for(int i=len1-1;i>=0;i--){com1[len1-i-1]=num1[i]-48;}for(int i=len2-1;i>=0;i--){com2[len2-i-1]=num2[i]-48;}for(int i=0;i<=len1-1;i++){for(int j=0;j<=len2-1;j++){re[i+j]=com1[i]*com2[j];}for(int i=0;i<=1000;i++){int p=re[i]%10;if(re[i]>=10)re[i+1]+=re[i]/10;re[i]=p;}for(int j=0;j<=1000;j++){ans[j]+=re[j];}memset(re,0,sizeof(re));}for(int i=0;i<=1000;i++){int p=ans[i]%10;if(ans[i]>=10)ans[i+1]+=ans[i]/10;ans[i]=p;}int t;for(int i=1005;i>=0;i--){if(ans[i]!=0){t=i;break;}}for(int i=t;i>=0;i--){printf("%d",ans[i]);}return 0;}
复杂度
#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include<iostream>using namespace std;#define N (1<<18)struct cmpx{double r,i;cmpx operator + (const cmpx &a)const { return (cmpx){ r+a.r,i+a.i }; }cmpx operator - (const cmpx &a)const { return (cmpx){ r-a.r,i-a.i }; }cmpx operator * (const cmpx &a)const { return (cmpx){ r*a.r-i*a.i,r*a.i+i*a.r }; }};int rev[N];cmpx A[N],a[N],b[N],c[N];int L,n;void DFT(cmpx a[],int f){for(int i=0;i<L;i++) A[i]=a[rev[i]];for(int i=0;i<L;i++) a[i]=A[i];for(int i=2;i<=L;i<<=1){cmpx wi=(cmpx){ cos(2.0*M_PI/i),f*sin(2.0*M_PI/i) };for(int k=0;k<L;k+=i){cmpx w=(cmpx){ 1.0,0.0 },x,y;for(int j=0;j<i/2;j++){x=a[k+j],y=w*a[k+j+i/2];a[k+j]=x+y,a[k+j+i/2]=x-y;w=w*wi;}}}if(f==-1) for(int i=0;i<L;i++) a[i].r/=L;}void FFT(cmpx a[],cmpx b[],cmpx c[]){DFT(a,1),DFT(b,1);for(int i=0;i<L;i++) c[i]=a[i]*b[i];DFT(c,-1);}void init(int tmp){for(n=0,L=1;L<tmp;L<<=1,n++);n++,L<<=1;for(int i=0;i<L;i++) for(int t=i,j=0;j<n;j++) rev[i]<<=1,rev[i]|=t&1,t>>=1;}int ans[N];int main(){int l1=0,l2=0;char ch=getchar();while(ch>'9'||ch<'0') ch=getchar();while(ch>='0'&&ch<='9') a[l1].r=ch-'0',a[l1++].i=0.0,ch=getchar();while(ch>'9'||ch<'0') ch=getchar();while(ch>='0'&&ch<='9') b[l2].r=ch-'0',b[l2++].i=0.0,ch=getchar();reverse(a,a+l1),reverse(b,b+l2),init(max(l1,l2));FFT(a,b,c);for(int i=0;i<L;i++) ans[i]=c[i].r+0.5;for(int i=0;i<L;i++) ans[i+1]+=ans[i]/10,ans[i]%=10;L=l1+l2+1;while(!ans[L]&&L>0) L--;for(int i=L;~i;i--) putchar(ans[i]+'0');putchar('\n');return 0;}
复杂度
#include<iostream>#include<algorithm>using namespace std;string div(string a,int b)//高精度a除以单精度b{string r,ans;int d=0;if(a=="0") return a;//特判for(int i=0;i<a.size();i++){r+=(d*10+a[i]-'0')/b+'0';//求出商d=(d*10+(a[i]-'0'))%b;//求出余数}int p=0;for(int i=0;i<r.size();i++)if(r[i]!='0') {p=i;break;}return r.substr(p);}int main(){string a;int b;while(cin>>a>>b){cout<<div(a,b)<<endl;}return 0;}
复杂度
#include <iostream>#include <cstring>#define ref(i,x,y) for (int i=x; i<=y; i++)#define def(i,x,y) for (int i=x; i>=y; i--)#define chstr(a,x,lenx) lenx=strlen(a);ref(i,1,lenx)x[i]=a[lenx-i]-48#define tl(f) t[f][0]using namespace std;char a[501],b[501];int x[501],y[501],ans[501],t[10][501],lenx,leny;int main(){cin>>a>>b;chstr(a,x,lenx);chstr(b,y,leny);tl(1)=leny;ref(i,1,leny)t[1][i]=y[i];ref(i,2,9){tl(i)=tl(i-1);ref(j,1,tl(i))t[i][j]=t[i-1][j]+y[j];ref(j,1,tl(i))if(t[i][j]>9){t[i][j+1]++;t[i][j]-=10;}if(t[i][tl(i)+1]!=0)tl(i)++;}int lent=lenx,anslen=lenx;def(i,lenx,1){int an=0,len1=max(lent-i+1,0);def(j,9,0){bool bo=1;def(k,max(len1,tl(j)),1)if(t[j][k]>x[i+k-1]){bo=0;break;}else if(t[j][k]<x[i+k-1])break;if (bo){an=j;break;}}ans[i]=an;ref(j,1,tl(an))x[j+i-1]-=t[an][j];ref(j,i,i+tl(an)-1)if (x[j]<0){x[j]+=10;x[j+1]--;}while(x[lent]==0)lent--;}while((ans[anslen]==0)&&(anslen>1))anslen--;def(i,anslen,1)cout<<ans[i];}
复杂度
#include<iostream>using namespace std;#define MAX 1001struct NEW_NUM{int num[MAX];int start;int end;NEW_NUM(){for (int i = 0; i < MAX; i++){num[i] = 0;}}};void calculate(NEW_NUM &temp);void add(NEW_NUM &temp, int num);void sub(NEW_NUM &a, int a_start, int a_end, NEW_NUM b, int b_start, int b_end);bool comp(NEW_NUM a, int a_start, int a_end, NEW_NUM b, int b_start, int b_end);int main(){char ch[MAX];NEW_NUM a, b;cin >> ch;int i;a.start = 1;for (i = 0; i <= MAX-1; i++){if (ch[i] == '\0')break;a.num[a.start+i] = ch[i] - '0';}a.end = i;int xx, yy;xx = yy = 1;b.start = 1;if (a.end % 2 == 0){int te = a.num[xx] * 10 + a.num[xx + 1];for (int i = 0; i <= 10; i++){if (i*i > te){b.num[yy] = i - 1;a.num[xx + 1] += a.num[xx]*10-(i-1)*(i-1);a.num[xx] = 0;if (a.num[xx + 1]>= 10){a.num[xx] += a.num[xx + 1] / 10;a.num[xx+1] = a.num[xx+1] % 10;}yy++;break;}}xx = xx + 2;}else{int te = a.num[xx];for (int i = 0; i <= 10; i++){if (i*i > te){b.num[yy] = i - 1;a.num[xx] -= (i-1)*(i-1);yy++;break;}}xx = xx + 1;}b.end = 1;while (xx+1<=a.end){NEW_NUM temp;temp.start = 3;for (int i = 1; i < yy; i++){temp.num[temp.start+i-1] = b.num[i];}b.num[yy] = 0;b.end = yy;temp.end = temp.start+yy-1;calculate(temp);for (int i = 1; i < 10; i++){if (i == 1)add(temp, 1);else add(temp, 2);if (comp(a, a.start, xx+1, temp, temp.start, temp.end)){sub(a, a.start, xx+1, temp, temp.start, temp.end);b.num[yy]++;}else{break;}}yy++;xx += 2;}for (int i = b.start; i <= b.end; i++){cout << b.num[i];}cout << endl;return 0;}bool comp(NEW_NUM a, int a_start,int a_end, NEW_NUM b, int b_start,int b_end){int i = a_start;while (a.num[i] == 0)i++;a.start = i;int j = b_start;while (b.num[j] == 0)j++;if (a_end - i>b_end - j)return true;if (a_end - i < b_end - j) return false;int k = 0;while (k <= a_end - i){if (a.num[k + i] > b.num[k + j]) return true;if (a.num[k + i] < b.num[k + j]) return false;k++;}return true;}void sub(NEW_NUM &a, int a_start, int a_end, NEW_NUM b, int b_start, int b_end){int i = a_end;int j = b_end;while (j >= b_start){if (a.num[i] >= b.num[j]) a.num[i] -= b.num[j];else{a.num[i - 1]--;a.num[i] = 10 + a.num[i] - b.num[j];}i--;j--;}}void add(NEW_NUM &temp, int num){temp.num[temp.end] += num;int i = temp.end;while (temp.num[i]>=10){temp.num[i - 1] += temp.num[i] / 10;temp.num[i] = temp.num[i] % 10;i--;}if (i < temp.start) temp.start = i;}void calculate(NEW_NUM &temp){ //temp*2*ifor (int i = temp.end; i >= temp.start; i--){temp.num[i] = 2 * temp.num[i];}for (int i = temp.end; i >= temp.start; i--){if (temp.num[i] >= 10){temp.num[i - 1] += temp.num[i] / 10;temp.num[i] = temp.num[i] % 10;}}int i = 0;while (temp.num[i] == 0){i++;}temp.start = i;}
#include<bits/stdc++.h>using namespace std;int a[9999],b[9999],c[9999],ans[9999];void read(int *x) {string s;cin>>s;x[0]=s.length();for(int i=1; i<=x[0]; i++)x[i]=s[i-1]-48;reverse(x+1,x+x[0]+1);}void print(int *x) {for(int i=x[0]; i>=1; i--)cout<<x[i];cout<<endl;}bool pd() {if(c[0]>b[0])return 1;if(c[0]<b[0])return 0;for(int i=c[0]; i>=1; i--) {if(c[i]>b[i])return 1;if(c[i]<b[i])return 0;}return 1;}void js() {int d=0;for(int i=1; i<=c[0]; i++) {c[i]-=b[i]+d;if(c[i]<0) {c[i]+=10;d=1;} else d=0;}while(c[0]>1&&!c[c[0]])c[0]--;}int main() {read(a);read(b);c[0]=0;for(int i=a[0]; i>=1; i--) {for(int j=c[0]; j>=1; j--)c[j+1]=c[j];c[1]=a[i];c[0]++;// print(c);while(pd()) {js();ans[i]++;}}ans[0]=a[0];while(ans[0]>1&&!ans[ans[0]])ans[0]--;print(c);return 0;}
#include <bits/stdc++.h>using namespace std;const int MAXN = 1300; //100000^250有1250位int pt;struct Bign{int s[MAXN], len;Bign(int num = 0){memset(s, 0, sizeof(s));len = 1;s[1] = num;}Bign operator * (int b)const{Bign c;c.len = len + 10;for (int i = 1; i <= c.len; i++){c.s[i] += s[i] * b;c.s[i+1] = c.s[i] / 10;c.s[i] %= 10;}c.clean();return c;}void clean(){while (len > 1 && !s[len]) len--;}};ostream& operator << (ostream &out, const Bign &x){int i;for (i = x.len; i > 0 && i > pt; i--) //输出整数部分out << x.s[i];if (i){ //若i不为0,表示还有小数部分out << "."; //先输出"."for (i = pt; i > 0; i--) //再输出小数部分out << x.s[i];}return out;}int main(){double a;int n;while (cin >> a >> n){//求a的小数位数pt = 0; //pt记录a的小数位数while (fabs(a - round(a)) > 1e-6){ //若a不等于a的整数部分,表示a不是整数pt++; //小数位数加一位a *= 10;}pt *= n; //a^n的小数位数等于a的小数位数 ×n//求s = a ^ nBign s = 1;for (int i = 1; i <= n; i++)s = s * (int)round(a);cout << s << endl;}return 0;}
又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
#include<cstring>#include<iostream>#include<conio.h>using namespace std;namespace trie{template<classT,size_t CHILD_MAX>/*ParameterT:Typeofreserveddata.ParameterCHILD_MAX:Sizeofarryofpointerstochildnode.*/struct nod{Treserved;nod<T,CHILD_MAX>*child[CHILD_MAX];nod(){memset(this,0,sizeof*this);}~nod(){for(unsignedi=0; i<CHILD_MAX; i++)deletechild[i];}void Traversal(char*str,unsignedindex){unsignedi;for(i=0; i<index; i++)cout<<str[i];cout<<'\t'<<reserved<<endl;for(i=0; i<CHILD_MAX; i++){if(child[i]){str[index]=i;child[i]->Traversal(str,index+1);}}return;}};template<classT,size_t CHILD_MAX=127>/*ParameterT:Typeofreserveddata.ParameterCHILD_MAX:Sizeofarryofpointerstochildnode.*/classtrie{private:nod<T,CHILD_MAX>root;public:nod<T,CHILD_MAX>*AddStr(char*str);nod<T,CHILD_MAX>*FindStr(char*str);boolDeleteStr(char*str);void Traversal(){char str[100];root.Traversal(str,0);}};template<classT,size_tCHILD_MAX>nod<T,CHILD_MAX>*trie<T,CHILD_MAX>::AddStr(char*str){nod<T,CHILD_MAX>*now=&root;do{if(now->child[*str]==NULL)now->child[*str]=newnod<T,CHILD_MAX>;now=now->child[*str];}while(*(++str)!='\0');return now;}template<classT,size_tCHILD_MAX>nod<T,CHILD_MAX>*trie<T,CHILD_MAX>::FindStr(char*str){nod<T,CHILD_MAX>*now=&root;do{if(now->child[*str]==NULL)return NULL;now=now->child[*str];}while(*(++str)!='\0');returnnow;}template<classT,size_tCHILD_MAX>bool trie<T,CHILD_MAX>::DeleteStr(char*str){nod<T,CHILD_MAX>**nods=new nod<T,CHILD_MAX>*[strlen(str)];intsnods=1;nod<T,CHILD_MAX>*now=&root;nods[0]=&root;do{if(now->child[*str]==NULL)returnfalse;nods[snods++]=now=now->child[*str];}while(*(++str)!='\0');snods--;while(snods>0){for(unsigned i=0; i<CHILD_MAX; i++)if(nods[snods]->child[i]!=NULL)return true;delete nods[snods];nods[--snods]->child[*(--str)]=NULL;}return true;}}int main(){//TestProgramtrie::trie<int>tree;while(1){cout<<"1foraddastring"<<endl;cout<<"2forfindastring"<<endl;cout<<"3fordeleteastring"<<endl;cout<<"4fortraversal"<<endl;cout<<"5forexit"<<endl;charstr[100];switch(getch()){case '1':cin.getline(str,100);cout<<"Thisstinghasexistedfor"<<tree.AddStr(str)->reserved++<<"times."<<endl;break;case '2':cin.getline(str,100);trie::nod<int,127>*find;find=tree.FindStr(str);if(!find)cout<<"Nofound."<<endl;elsecout<<"Thisstinghasexistedfor"<<find->reserved<<"times."<<endl;break;case '3':cin.getline(str,100);cout<<"Theactionis"<<(tree.DeleteStr(str)?"Successful.":"Unsuccessful.")<<endl;break;case '4':tree.Traversal();break;case '5':return 0;}}return 0;}
在字符串处理当中,后缀树和后缀数组都是非常有力的工具。其实后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也不太逊色,并且,它比后缀树所占用的空间小很多。可以说,在信息学竞赛中后缀数组比后缀树要更为实用。
//problemID:https://www.luogu.org/problemnew/show/P3809#include<bits/stdc++.h>#define N 1000010using namespace std;int t1[N],t2[N],sa[N],h[N],rk[N],c[10*N],a[N];char s[N];int m,n;void calcsa(int n,int m){int *x=t1,*y=t2,p=0,f=0;for(int i=1;i<=m;i++)c[i]=0;for(int i=1;i<=n;i++)c[x[i]=a[i]]++;for(int i=1;i<=m;i++)c[i]+=c[i-1];for(int i=n;i;i--)sa[c[x[i]]--]=i;for(int i=1;i<=n&&p<=n;i<<=1){p=0;for(int j=n-i+1;j<=n;j++)y[++p]=j;for(int j=1;j<=n;j++)if(sa[j]>i)y[++p]=sa[j]-i;for(int j=1;j<=m;j++)c[j]=0;for(int j=1;j<=n;j++)c[x[y[j]]]++;for(int i=1;i<=m;i++)c[i]+=c[i-1];for(int j=n;j;j--)sa[c[x[y[j]]]--]=y[j];swap(x,y);x[sa[1]]=1;p=2;for(int j=2;j<=n;j++)x[sa[j]]=y[sa[j]]==y[sa[j-1]]&&y[sa[j]+i]==y[sa[j-1]+i]?p-1:p++;m=p;}for(int i=1;i<=n;i++)rk[sa[i]]=i;for(int i=1;i<=n;i++){int j=sa[rk[i]-1];if(f)f--;while(a[i+f]==a[j+f])f++;h[rk[i]]=f;}}int main(){scanf("%s",s);int len=strlen(s);for(int i=0;i<len;i++)a[++n]=s[i]-' ';calcsa(n,10000);for(int i=1;i<=n;i++)printf("%d ",sa[i]);return 0;}
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#define ll long longusing namespace std;const int N=2010000;char s[N];int fa[N],ch[N][26],len[N],siz[N];int lst=1,node=1,l,t[N],A[N];ll ans;void Extend(int c){/*2+2+2+3行,那么多while但是复杂度是O(n)*/int f=lst,p=++node;lst=p;len[p]=len[f]+1;siz[p]=1;/*f为以c结尾的前缀的倒数第二个节点,p为倒数第一个(新建)len[i] 表示i节点的longest,不用记录shortest(概念在hihocoder后缀自动机1上讲得十分详细)siz[i]表示以i所代表的endpos的集合元素大小,即所对应的字符串集出现的次数不用担心复制后的siz,在parent树上复制后的点的siz是它所有儿子siz之和,比1多*/while(f&&!ch[f][c]) ch[f][c]=p,f=fa[f];if(!f) {fa[p]=1;return;}/*把前面的一段没有c儿子的节点的c儿子指向pSituation 1 如果跳到最前面的根的时候,那么把p的parent树上的父亲置为1*/int x=ch[f][c],y=++node;if(len[f]+1==len[x]) {fa[p]=x;node--;return;}/*x表示从p一直跳parent树得到的第一个有c儿子的节点的c儿子Situation 2 如果节点x表示的endpos所对应的字符串集合只有一个字符串,那么把p的parent树父亲设置为xSituation 2 和 Situation 3 本质不同!!!与机房dalao们讨论两天才知道Situation 2 必须特判的原因!!!详见上方链接的博客*/len[y]=len[f]+1; fa[y]=fa[x]; fa[x]=fa[p]=y;memcpy(ch[y],ch[x],sizeof(ch[y]));while(f&&ch[f][c]==x) ch[f][c]=y,f=fa[f];/*Situation 3 否则把x点复制一遍(parent树父亲、儿子),同时len要更新(注意len[x]!=len[f]+1,因为通过加点会使x父亲改变)然后把x点和p点的父亲指向复制点y,再将前面所有本连x的点连向y*/}int main(){//Part 1 建立后缀自动机scanf("%s",s); l=strlen(s);for(int i=l;i>=1;i--) s[i]=s[i-1];s[0]=0;for(int i=1;i<=l;i++) Extend(s[i]-'a');//Part 2 按len从大到小排序(和SA好像啊)后计算答案for(int i=1;i<=node;i++) t[len[i]]++;for(int i=1;i<=node;i++) t[i]+=t[i-1];for(int i=1;i<=node;i++) A[t[len[i]]--]=i;for(int i=node;i>=1;i--){//从小到大枚举,实际上在模拟parent树的DFSint now=A[i];siz[fa[now]]+=siz[now];if(siz[now]>1) ans=max(ans,1ll*siz[now]*len[now]);}printf("%lld\n",ans);return 0;}
在计算机科学中,Aho–Corasick算法是由Alfred V. Aho和Margaret J.Corasick 发明的字符串搜索算法,用于在输入的一串字符串中匹配有限组“字典”中的子串 。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度,约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数,如果每个子串互相匹配(如字典为a,aa,aaa,aaaa,输入的字符串为aaaa),算法的时间复杂度会近似于匹配的二次函数。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<queue>#include<algorithm>using namespace std;struct Tree//字典树{int fail;//失配指针int vis[26];//子节点的位置int end;//标记以这个节点结尾的单词编号}AC[100000];//Trie树int cnt=0;//Trie的指针struct Result{int num;int pos;}Ans[100000];//所有单词的出现次数bool operator <(Result a,Result b){if(a.num!=b.num)return a.num>b.num;elsereturn a.pos<b.pos;}string s[100000];inline void Clean(int x){memset(AC[x].vis,0,sizeof(AC[x].vis));AC[x].fail=0;AC[x].end=0;}inline void Build(string s,int Num){int l=s.length();int now=0;//字典树的当前指针for(int i=0;i<l;++i)//构造Trie树{if(AC[now].vis[s[i]-'a']==0)//Trie树没有这个子节点{AC[now].vis[s[i]-'a']=++cnt;//构造出来Clean(cnt);}now=AC[now].vis[s[i]-'a'];//向下构造}AC[now].end=Num;//标记单词结尾}void Get_fail()//构造fail指针{queue<int> Q;//队列for(int i=0;i<26;++i)//第二层的fail指针提前处理一下{if(AC[0].vis[i]!=0){AC[AC[0].vis[i]].fail=0;//指向根节点Q.push(AC[0].vis[i]);//压入队列}}while(!Q.empty())//BFS求fail指针{int u=Q.front();Q.pop();for(int i=0;i<26;++i)//枚举所有子节点{if(AC[u].vis[i]!=0)//存在这个子节点{AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];//子节点的fail指针指向当前节点的//fail指针所指向的节点的相同子节点Q.push(AC[u].vis[i]);//压入队列}else//不存在这个子节点AC[u].vis[i]=AC[AC[u].fail].vis[i];//当前节点的这个子节点指向当//前节点fail指针的这个子节点}}}int AC_Query(string s)//AC自动机匹配{int l=s.length();int now=0,ans=0;for(int i=0;i<l;++i){now=AC[now].vis[s[i]-'a'];//向下一层for(int t=now;t;t=AC[t].fail)//循环求解Ans[AC[t].end].num++;}return ans;}int main(){int n;while(233){cin>>n;if(n==0)break;cnt=0;Clean(0);for(int i=1;i<=n;++i){cin>>s[i];Ans[i].num=0;Ans[i].pos=i;Build(s[i],i);}AC[0].fail=0;//结束标志Get_fail();//求出失配指针cin>>s[0];//文本串AC_Query(s[0]);sort(&Ans[1],&Ans[n+1]);cout<<Ans[1].num<<endl;cout<<s[Ans[1].pos]<<endl;for(int i=2;i<=n;++i){if(Ans[i].num==Ans[i-1].num)cout<<s[Ans[i].pos]<<endl;elsebreak;}}return 0;}
#include <iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<string>#include<map>const int maxn=1000000;const int mod=10000;#define me(a) memset(a,0,sizeof(a))#define ll long longusing namespace std;struct node{int a[2][2];node(){memset(a,0,sizeof(a));}};node jx(node a,node b){node s;for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)s.a[i][k]=(s.a[i][k]+a.a[i][j]*b.a[j][k])%mod;return s;}node qsort(node a,int n){node s;for(int i=0;i<2;i++) s.a[i][i]=1;while(n){if(n&1) s=jx(s,a);a=jx(a,a);n>>=1;}return s;}int main(){node a;int n;a.a[0][0]=a.a[1][0]=a.a[0][1]=1;while(cin>>n&&n!=-1){node s=qsort(a,n);cout<<s.a[1][0]<<endl;}return 0;}
复杂度,常数略大
//problemID:http://noi.openjudge.cn/ch0111/02/#include <iostream>#include <iomanip>#include <cmath>using namespace std;bool check(double mid){double f = pow(mid,5)-15.0*pow(mid,4)+85.0*pow(mid,3)-225.0*pow(mid,2)+274.0*mid-121.0;if(f > 0.0) return 1;return 0;}int main(){double l=1.5, r=2.4, mid;while(r-l > 0.00000001){mid = (l+r)/2.0;if (check(mid)) l = mid;else r = mid;}cout << fixed << setprecision(6) << mid << endl;return 0;}
//problemID:http://noi.openjudge.cn/ch0111/01/#include<cstdio>#include<cmath>#include<iostream>using namespace std;#define N 100005int n,m,x,l,r,mid;long long a[N];int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);scanf("%d",&m);while(m--){scanf("%d",&x);l=0,r=n+1;if(x<=a[1]) {printf("%d\n",a[1]);continue;}if(x>=a[n]) {printf("%d\n",a[n]);continue;}while(l<r){mid=(l+r)>>1;if(a[mid]<x)l=mid;else if(a[mid]>x)r=mid;else {l=mid;break;}if(l==r-1&&a[l]<x&&a[r]>x) break;}if(abs(a[l]-x)<=abs(a[r]-x))printf("%d\n",a[l]);else printf("%d\n",a[r]);}return 0;}
//problemID:https://www.luogu.org/problemnew/show/P3382#include<bits/stdc++.h>using namespace std;const int N = 20 + 5;#define double long doubledouble T = 0.92, delta = 0.99, tt = 1e-14;double a[N], l, r, eps = 1e-4, ans, num;int n;void input(){scanf("%d%llf%llf", &n, &l, &r);for(int i = 0; i <= n; i++)scanf("%llf", &a[i]);return ;}double get_ans(double x){double ans = 0, now = 1;for(int i = n; i >= 0; i--){ans = ans + a[i] * now;now = now * x;}return ans;}void SA(){double now = (l + r) / 2;double t = T;while(t > tt){double temp = now + (rand() * 2 - RAND_MAX) * t;//随机一个点,保证其为正负数—//(rand()*2 - RAND_MAX)if(temp < l) temp = l;if(temp > r) temp = r;double new_ans = get_ans(temp);double DE = new_ans - ans;if(DE > 0){//如果新答案更优ans = new_ans;num = temp;now = temp;}t *= delta;}}void solve(){ans = -999999999;//y一开始ans应该特别小int qwq = 12;//跑12次while(qwq--){SA();}double x = num;printf("%.5llf\n", num);}signed main(){input();solve();return 0;}
#include<bits/stdc++.h>using namespace std;struct thing{double x,y,w;}a[1001];int n;double ansx,ansy,t,ans;#define T 0.9978double calc(double x,double y){double res=0;for(int i=1;i<=n;i++){res+=sqrt((a[i].x-x)*(a[i].x-x)+(a[i].y-y)*(a[i].y-y))*a[i].w;}return res;}void fire(){double xx=ansx,yy=ansy;t=2270;for(;t>=1e-14;t*=T){double x=xx-(rand()*2-RAND_MAX)*t,y=yy-(rand()*2-RAND_MAX)*t;double tmp=calc(x,y),d=tmp-ans;if(d<0){ans=tmp;ansx=x,ansy=y,xx=x,yy=y;}else if( exp(-d/t)*RAND_MAX>rand())xx=x,yy=y;}}int main(){srand(20011115);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].w);ansx+=a[i].x,ansy+=a[i].y;}ansx/=(double)n,ansy/=(double)n;ans=calc(ansx,ansy);for(int i=1;i<=8;i++)fire();printf("%.3lf %.3lf",ansx,ansy);}
#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 200005double eps=1e-9;int dcmp(double x){if (x<=eps&&x>=-eps) return 0;return (x>0)?1:-1;}struct Vector{double x,y;Vector(double X=0,double Y=0){x=X,y=Y;}};typedef Vector Point;Vector operator + (Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}Vector operator - (Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}bool operator == (Vector a,Vector b){return a.x==b.x&&a.y==b.y;}double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}double Len(Vector a){return sqrt(a.x*a.x+a.y*a.y);}double DisTS(Point P,Point A,Point B){if (A==B) return Len(P-A);Vector v=B-A,w=P-A,u=P-B;if (dcmp(Dot(v,w))<0) return Len(w);else if (dcmp(Dot(v,u))>0) return Len(u);else return fabs(Cross(v,w)/Len(v));}int n,m,guncnt,d,r,t,T;struct ANT{int x,y,lastx,lasty;int age;int level;int startblood,blood;bool carry;}ant[10];struct GUN{int x,y;}gun[25];int antcnt,tot,cake;int mp[10][10];int infor[10][10];double mi[N];int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};bool flag;void AntBirth(){if (antcnt<6&&!mp[0][0]){++antcnt;++tot;ant[antcnt].x=ant[antcnt].y=ant[antcnt].lastx=ant[antcnt].lasty=0;ant[antcnt].age=1;ant[antcnt].level=(tot-1)/6+1;ant[antcnt].startblood=ant[antcnt].blood=floor(4*mi[ant[antcnt].level]);ant[antcnt].carry=0;++mp[0][0];}}void Information(){for (int i=1;i<=antcnt;++i){if (ant[i].carry) infor[ant[i].x][ant[i].y]+=5;else infor[ant[i].x][ant[i].y]+=2;}}void Move(){for (int i=1;i<=antcnt;++i){int x=ant[i].x,y=ant[i].y;int lastx=ant[i].lastx,lasty=ant[i].lasty;bool can[4];memset(can,0,sizeof(can));int Max=0,cancnt=0;for (int j=0;j<4;++j){int nxtx=x+dx[j],nxty=y+dy[j];if (nxtx>=0&&nxtx<=n&&nxty>=0&&nxty<=m&&mp[nxtx][nxty]==0&&(nxtx!=lastx||nxty!=lasty)){can[j]=1;++cancnt;Max=max(Max,infor[nxtx][nxty]);}}if (!cancnt){ant[i].lastx=x;ant[i].lasty=y;continue;}int dir=0;for (int j=3;j>=0;--j){int nxtx=x+dx[j],nxty=y+dy[j];if (can[j]&&infor[nxtx][nxty]==Max){dir=j;if (ant[i].age%5==0) break;--mp[x][y];++mp[nxtx][nxty];ant[i].lastx=x,ant[i].lasty=y;ant[i].x=nxtx,ant[i].y=nxty;break;}}if (ant[i].age%5==0){for (int j=0;j<4;++j){++dir;if (dir==4) dir=0;if (can[dir]){int nxtx=x+dx[dir],nxty=y+dy[dir];--mp[x][y];++mp[nxtx][nxty];ant[i].lastx=x,ant[i].lasty=y;ant[i].x=nxtx,ant[i].y=nxty;break;}}}}}void CarryCake(){if (cake) return;for (int i=1;i<=antcnt;++i)if (ant[i].x==n&&ant[i].y==m){ant[i].carry=1;cake=i;ant[i].blood+=ant[i].startblood/2;ant[i].blood=min(ant[i].blood,ant[i].startblood);break;}}int qr(int x){return x*x;}int length(ANT a,GUN b){return qr(a.x-b.x)+qr(a.y-b.y);}bool canhit(ANT a,GUN b,ANT c){Point A=Point(b.x,b.y);Point B=Point(c.x,c.y);Point P=Point(a.x,a.y);double dis=DisTS(P,A,B);if (dcmp(dis-0.5)<=0) return 1;else return 0;}void Attack(){for (int i=1;i<=guncnt;++i){int goal=0;if (cake&&length(ant[cake],gun[i])<=r*r) goal=cake;else{int Min=100000;for (int j=1;j<=antcnt;++j){int now=length(ant[j],gun[i]);if (now<=r*r&&now<Min){Min=now;goal=j;}}}if (!goal) continue;for (int j=1;j<=antcnt;++j)if (canhit(ant[j],gun[i],ant[goal])) ant[j].blood-=d;}}void CheckDeath(){int i=1;while (i<=antcnt){if (ant[i].blood<0){--mp[ant[i].x][ant[i].y];for (int j=i;j<antcnt;++j)ant[j]=ant[j+1];--antcnt;}else ++i;}cake=0;for (int i=1;i<=antcnt;++i)if (ant[i].carry) {cake=i;break;}}bool CheckGame(){if (!cake) return 0;for (int i=1;i<=antcnt;++i)if (!ant[i].x&&!ant[i].y&&ant[i].carry) return 1;return 0;}int main(){scanf("%d%d",&n,&m);scanf("%d%d%d",&guncnt,&d,&r);for (int i=1;i<=guncnt;++i){scanf("%d%d",&gun[i].x,&gun[i].y);mp[gun[i].x][gun[i].y]=-1;}scanf("%d",&t);mi[0]=1.0;for (int i=1;i<=t;++i) mi[i]=mi[i-1]*1.1;for (T=1;T<=t;++T){AntBirth();Information();Move();CarryCake();Attack();CheckDeath();flag=CheckGame();if (flag) break;for (int i=0;i<=n;++i)for (int j=0;j<=m;++j)if (infor[i][j]) --infor[i][j];for (int i=1;i<=antcnt;++i)++ant[i].age;}if (flag) printf("Game over after %d seconds\n",T);else puts("The game is going on");printf("%d\n",antcnt);for (int i=1;i<=antcnt;++i)printf("%d %d %d %d %d\n",ant[i].age-1,ant[i].level,ant[i].blood,ant[i].x,ant[i].y);}