T1.树上求和
题目大意：给出一棵n个点的树，一个点的等级定义为他到根节点的距离，对每个i求有多少个子树满足子树内等级为i的点不少于ai个。（n<=500,000）
思路：对每种等级统计答案，子树内等级为i的点的个数只有在dfs序相邻的两个点的lca处才会发生变化，把这些lca按深度排序后依次合并相邻子树即可，总复杂度O(nlogn)。
#include<cstdio> #include<vector> #include<algorithm> using namespace std; inline int read() { int x;char c; while((c=getchar())<'0'||c>'9'); for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0'; return x; } #define MN 500000 #define K 19 struct edge{int nx,t;}e[MN+5]; int h[MN+5],en,a[MN+5],d[MN+5],fa[K][MN+5],f[MN+5],s[MN+5],w[MN+5]; vector<int> v[MN+5]; struct node{int x,f;}p[MN+5]; bool cmp(node a,node b){return d[a.f]>d[b.f];} inline void ins(int x,int y){e[++en]=(edge){h[x],y};h[x]=en;} void dfs(int x) { v[d[x]].push_back(x); for(int i=h[x];i;i=e[i].nx) fa[0][e[i].t]=x,d[e[i].t]=d[x]+1,dfs(e[i].t); } int lca(int x,int y) { int dx=d[x]-d[y],i; if(dx<0)swap(x,y),dx=-dx; for(i=0;dx;++i,dx>>=1)if(dx&1)x=fa[i][x]; if(x==y)return x; for(i=K;i--;)if(fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y]; return fa[0][x]; } int gf(int k){return f[k]?f[k]=gf(f[k]):k;} int main() { freopen("summing.in","r",stdin); freopen("summing.out","w",stdout); int n,h,i,j,fx,fy;long long ans=0; n=read();h=read(); for(i=1;i<n;++i)ins(read(),i); for(i=0;i<=h;++i)a[i]=read(); dfs(0); for(i=1;i<K;++i)for(j=1;j<n;++j)fa[i][j]=fa[i-1][fa[i-1][j]]; for(i=0;i<=h;++i) { if(!a[i]){ans+=n;continue;} for(j=0;j<v[i].size();++j)f[j]=0,s[j]=1,w[j]=d[v[i][j]]; for(j=1;j<v[i].size();++j)p[j]=(node){j,lca(v[i][j-1],v[i][j])}; sort(p+1,p+v[i].size(),cmp); for(j=1;j<v[i].size();++j) { fx=gf(p[j].x);fy=gf(p[j].x-1); if(s[fx]>=a[i])ans+=w[fx]-d[p[j].f]; if(s[fy]>=a[i])ans+=w[fy]-d[p[j].f]; s[fx]+=s[fy];w[fx]=d[p[j].f];f[fy]=fx; } if(s[fx=gf(0)]>=a[i])ans+=w[fx]+1; } printf("%I64d",ans); fclose(stdin);fclose(stdout);return 0; }
T2.三角形规划
题解见这里的T3
T3.完美数对
题目大意：给定一个长度为n的数列a，求有多少对i<j满足ai*aj<=max(ai~aj)。（n<=100,000）
思路：枚举ak=max(ai~aj)，二分在哪个区间内ak为最大值，取[l,k]和[k,r]中较小的那一段，枚举这一段中的数，另一段中用主席树统计答案，由于每个ak对应的区间只有包含和不交两种关系，不会相交，我们枚举小的那一段的复杂度相当于启发式合并的复杂度，加上主席树，总复杂度O(nlogn^2)。
#include<cstdio> #include<algorithm> using namespace std; inline int read() { int x;char c; while((c=getchar())<'0'||c>'9'); for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0'; return x; } #define MN 100000 #define ND 3100000 #define K 17 #define INF 1000000000 struct node{int l,r,s;}t[ND+5]; int a[MN+5],rt[MN+5],tn,f[K][MN+5],d[MN+5]; int ins(int k,int l,int r,int x) { int p=++tn,mid=l+r>>1; t[p].s=t[k].s+1; if(l<r)if(x>mid)t[p].l=t[k].l,t[p].r=ins(t[k].r,mid+1,r,x); else t[p].l=ins(t[k].l,l,mid,x),t[p].r=t[k].r; return p; } int query(int kr,int kl,int l,int r,int x) { if(r==x)return t[kr].s-t[kl].s; int mid=l+r>>1; return x<=mid?query(t[kr].l,t[kl].l,l,mid,x): t[t[kr].l].s-t[t[kl].l].s+query(t[kr].r,t[kl].r,mid+1,r,x); } int query(int l,int r) { int s=d[r-l+1]; return s<0?0:max(f[s][l],f[s][r-(1<<s)+1]); } int main() { freopen("pair.in","r",stdin); freopen("pair.out","w",stdout); int n=read(),i,j,l,r,mid,ll,rr;long long ans=0; for(i=1;i<=n;++i)rt[i]=ins(rt[i-1],1,INF,f[0][i]=a[i]=read()); for(d[0]=-1,i=1;i<=n;++i)d[i]=d[i>>1]+1; for(i=1;i<K;++i)for(j=1;j+(1<<i)-1<=n;++j) f[i][j]=max(f[i-1][j],f[i-1][j+(1<<i-1)]); for(i=1;i<=n;++i) { for(ll=0,l=1,r=i;l<=r;) if(query(mid=l+r>>1,i-1)<a[i])r=mid-1; else ll=mid,l=mid+1; for(rr=n+1,l=i,r=n;l<=r;) if(query(i,mid=l+r>>1)>a[i])rr=mid,r=mid-1; else l=mid+1; ans+=query(rt[i-1],rt[ll],1,INF,1)+query(rt[rr-1],rt[i],1,INF,1); if(i-ll<rr-i)for(j=i;--j>ll;)ans+=query(rt[rr-1],rt[i],1,INF,a[i]/a[j]); else for(j=i;++j<rr;)ans+=query(rt[i-1],rt[ll],1,INF,a[i]/a[j]); } printf("%I64d",ans); fclose(stdin);fclose(stdout);return 0; }
T4.最小直径
题目大意：有一个n个点的图，要求给每个点构造m条出边，使图为强联通图且最大的两点间距离尽可能小，不超过最小加一则判为正确。（n<=1000，m<=5）
思路：看代码
#include<cstdio> int main() { freopen("diameter.in","r",stdin); freopen("diameter.out","w",stdout); int n,m,i,j; scanf("%d%d",&n,&m); for(i=0,j=1;j<n;++i,j*=m); printf("%d ",i); for(i=0;i<n;++i,puts(""))for(j=0;j<m;++j)printf("%d ",(i*m+j)%n); fclose(stdin);fclose(stdout);return 0; }