肝了两题...
T1一眼题，分解质因数，找出2的个数和5的个数取min输出
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=1000010,inf=1e9; int n,m,T; int fac2[maxn],fac5[maxn]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } int main() { freopen("zero.in","r",stdin); freopen("zero.out","w",stdout); read(T); for(int i=1;i<=1000000;i++) { int x=i;fac2[i]=fac2[i-1];fac5[i]=fac5[i-1]; for(;(x&1)==0;x>>=1)fac2[i]++; for(;x%5==0;x/=5)fac5[i]++; } while(T--) { read(m);read(n); int cnt2=fac2[m]-fac2[n]-fac2[m-n]; int cnt5=fac5[m]-fac5[n]-fac5[m-n]; printf("%d ",min(cnt2,cnt5)); } return 0; }
T2是个环套树题
分三类：①两个点都在同个树上，求直径，两次bfs或者树形DP即可
②一个点在环上一个点在树上，答案为最大深度dep+len/2
③两个点在不同的树上，即求max(depi+depj+dis(i,j))，而dis(i,j)显然是<=len/2且递增的，用单调队列维护max(depj+dis(i,j))，队头与i距离超过len/2就出队，走一圈之后就可以算出这种情况的答案
三类取max
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=500010,inf=1e9; struct poi{int too,pre;}e[maxn]; int n,m,x,y,z,tot,ans,st,ed,cnt,len; int mx1[maxn],mx2[maxn],d[maxn],last[maxn],isrt[maxn],rt[maxn],q[maxn]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } inline void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;} void dfs(int x,int fa) { d[x]=d[fa]+1;mx1[x]=d[x];mx2[x]=0; for(int i=last[x];i;i=e[i].pre) if(e[i].too!=fa&&!isrt[e[i].too]) { dfs(e[i].too,x); if(mx1[e[i].too]>mx1[x])mx2[x]=mx1[x],mx1[x]=mx1[e[i].too]; else if(mx1[e[i].too]>mx2[x])mx2[x]=mx1[e[i].too]; } ans=max(ans,mx1[x]+mx2[x]-(d[x]<<1)); } int dfs2(int x,int fa) { if(x==ed)return len++,1; for(int i=last[x];i;i=e[i].pre) if(e[i].too!=fa)if(dfs2(e[i].too,x)) return rt[++cnt]=x,isrt[x]=1,len++,1; return 0; } inline int dis(int x,int y){if(x>=y)return x-y;return len-(y-x);} inline void work() { int l=1,r=0; for(int i=(len>>1);i;q[++r]=i,i--) while(l<=r&&mx1[rt[q[r]]]+dis(q[r],cnt)<=mx1[rt[i]]+dis(i,cnt))r--; for(int i=cnt;i;i--) { while(l<=r&&(dis(q[l],i)>(len>>1)||q[l]==i))l++; ans=max(ans,mx1[rt[i]]+mx1[rt[q[l]]]+dis(q[l],i)); while(l<=r&&mx1[rt[q[r]]]+dis(q[r],i)<=mx1[rt[i]])r--; q[++r]=i; } } int main() { freopen("road.in","r",stdin); freopen("road.out","w",stdout); read(n);read(m); for(int i=1;i<n;i++)read(x),read(y),add(x,y),add(y,x); for(int i=1;i<=m;i++) { read(st);read(ed);ans=len=cnt=0; memset(isrt,0,sizeof(isrt));d[0]=-1; rt[++cnt]=ed;isrt[ed]=1;dfs2(st,0); for(int j=1;j<=cnt;j++)dfs(rt[j],0),ans=max(ans,mx1[rt[j]]+(len>>1)); work();printf("%d ",ans); } return 0; }