我只会这么多
tarjan:codevs 1332
void tarjan(int u)
{
dfn[u]=low[u]=Time++; s.push(u);
for(int i=head[u];~i;i=nxt[i])
{
int v=to[i];
if(!dfn[v]) tarjan(v);
else if(dfn[v]!=-) low[u]=Min(low[u],low[v]);
}
if(dfn[u]==dfn[v])
{
while(!s.empty())
{
int x=s.top(); s.pop();
dfn[x]=-;
tot++;
if(x==u) break;
}
}
}
spfa codevs 2038
#include<iostream>
#include<queue>
#include<stdio.h>
#include<string.h>
using namespace std;
const int inf=0x3f3f3f3f;
int cnt=-,n,e,s,t,ans=inf,p;
int head[],to[],w[],nxt[],d[],used[],pos[];
int Min(int x,int y)
{
return x<y?x:y;
}
void Init()
{
memset(head,-,sizeof(head));
memset(nxt,-,sizeof(nxt));
}
void link(int u,int v,int l)
{
nxt[++cnt]=head[u];
head[u]=cnt;
to[cnt]=v;
w[cnt]=l;
}
void spfa(int s)
{
queue<int>q;
memset(d,inf,sizeof(d));
q.push(s); d[s]=; used[s]=;
while(!q.empty())
{
int u=q.front(); q.pop(); used[u]=;
for(int i=head[u];~i;i=nxt[i])
{
int v=to[i],val=w[i];
if(d[v]>d[u]+val)
{
d[v]=d[u]+val;
if(!used[v])
{
q.push(v);
used[v]=;
}
}
}
}
int tot=;
for(int i=;i<=n;i++)
{
tot+=d[pos[i]];
}
ans=Min(ans,tot);
}
int main()
{
scanf("%d%d%d",&n,&p,&e);
for(int i=;i<=n;i++)
{
int u; scanf("%d",&pos[i]);
}
Init();
for(int i=;i<=e;i++)
{
int u,v,c; scanf("%d%d%d",&u,&v,&c);
link(u,v,c); link(v,u,c);
}
for(int i=;i<=p;i++)
{
spfa(i);
}
printf("%d",ans);
return ;
}
lca 1787
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int n,m,u,v,a,b,c,ans,temp1,cnt=-;
int dep[],head[],to[],nxt[];
int fa[][];
void Init()
{
memset(head,-,sizeof(head));
memset(nxt,-,sizeof(nxt));
memset(fa,-,sizeof(fa));
}
int abs(int x)
{
return x>?x:-x;
}
void link(int u,int v)
{
nxt[++cnt]=head[u]; head[u]=cnt;
to[cnt]=v;
}
void dfs(int u,int d)
{
dep[u]=d;
for(int i=head[u];~i;i=nxt[i])
{
int v=to[i];
if(!dep[v])
{
fa[][v]=u;
dfs(v,d+);
}
}
}
int lca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
int deep=dep[u]-dep[v];
for(int i=;i>=;i--)
{
if(deep&(<<i)) u=fa[i][u];
}
if(u==v) return u;
for(int i=;i>=;i--)
{
if(fa[i][u]!=fa[i][v])
{
u=fa[i][u];
v=fa[i][v];
}
}
return fa[][u];
}
inline int calc(int x,int y)
{
int temp=lca(x,y);
return abs(dep[x]-dep[temp])+abs(dep[y]-dep[temp]);
}
int main()
{
scanf("%d%d",&n,&m);
Init();
for(int i=;i<n;i++)
{
int u,v; scanf("%d%d",&u,&v);
link(u,v); link(v,u);
}
dfs(,);
for(int i=;i<=;i++)
{
for(int j=;j<=n;j++)
{
if(fa[i-][j]!=-) fa[i][j]=fa[i-][fa[i-][j]];
}
}
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
int x=lca(a,b);
int y=lca(b,c);
int z=lca(c,a);
if(x==y)
temp1=z;
else
if(y==z)
temp1=x;
else
if(x==z)
temp1=y;
ans=calc(a,temp1)+calc(b,temp1)+calc(c,temp1);
printf("%d %d\n",temp1,ans);
}
return ;
}
二分 跳石头
#include<iostream>
#include<stdio.h>
using namespace std;
int n,m,ans,L;
int a[],mark[];
bool C(int x)
{
int last=,tot=;
for(int i=;i<=n;i++)
{
mark[i]=;
if(a[i]-a[last]<x)
{
tot++;
mark[i]=;
}
else last=i;
}
last=n+;
for(int i=n;i>=;i--)
{
if(a[last]-a[i]<x&&!mark[i]) tot++;
else if(a[last]-a[i]>=x) break;
}
return tot<=m;
}
int main()
{
scanf("%d%d%d",&L,&n,&m);
a[]=; a[n+]=L+;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
int l=,r=L+,mid;
while(r-l>)
{
mid=(l+r)/;
if(C(mid)) {l=mid;ans=mid;}
else r=mid;
}
if(C(ans+)) ans++;
printf("%d",ans);
return ;
}
线段树
1012
#include<iostream>
#include<cstdio>
using namespace std;
const int inf=<<;
int m,d,t,size;
int tree[];
int Max(int x,int y)
{
return x>y?x:y;
}
void update(int l,int r,int x,int pos,int num)
{
if(l==r)
{
tree[x]=num;
return;
}
if(pos>(l+r)/) update((l+r)/+,r,x*+,pos,num);
if(pos<=(l+r)/) update(l,(l+r)/,x*,pos,num);
tree[x]=Max(tree[x],Max(tree[x*],tree[x*+]));
}
int query(int l,int r,int x,int a,int b)
{
if(l>b||r<a) return -inf;
if(l>=a&&r<=b) return tree[x];
return Max(query(l,(l+r)/,x*,a,b),query((l+r)/+,r,x*+,a,b));
}
int main()
{
scanf("%d%d",&m,&d);
for(int i=;i<=m;i++)
{
char s[]; scanf("%s",s);
if(s[]=='A')
{
int n,num; scanf("%d",&n); size++;
num=(n+t)%d;
update(,m,,size,num);
}
else if(s[]=='Q')
{
int l; scanf("%d",&l);
t=query(,m,,size-l+,size);
printf("%d\n",t);
}
}
// for(int i=1;i<=3;i++) cout<<tree[i]<<" ";
return ;
}
快速幂：
#include<iostream>
using namespace std;
int n,m,k,x;
int power(int k)
{
int t=,ret=;
while(k>)
{
if(k%==) ret*=t;
t*=t; k/=;
}
return ret;
}
int main()
{
cin>>k;
cout<<power(k);
return ;
}
高精度 3116
#include<iostream>
#include<cstdio>
using namespace std;
string A,B;
struct bigint
{
int d[];
int len;
}a,b,c;
int Max(int x,int y)
{
return x>y?x:y;
}
void add(bigint&a,bigint&b,bigint&c)
{
int x=,temp;
c.len=Max(a.len,b.len);
for(int i=;i<=c.len;i++)
{
temp=a.d[i]+b.d[i]+x;
c.d[i]=temp%; x=temp/;
}
if(x>) c.d[++c.len]=x;
for(int i=c.len;i>=;i--) cout<<c.d[i];
}
int main()
{
cin>>A>>B;
a.len=A.length();
for(int i=;i<A.length();i++)
{
a.d[A.length()-i]=A[i]-'';
}
b.len=B.length();
for(int i=;i<B.length();i++)
{
b.d[B.length()-i]=B[i]-'';
}
add(a,b,c);
return ;
}