题目：链接: https://pan.baidu.com/s/1ef_9hGBhczW0B4dz5IUKmw 密码: qgjy
T1:
hash后直接二分查询即可
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; inline long long read() { long long f=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return ans*f; } char str[100001]; long long sum[100001]; long long b[100001]; long long bb=27; long long maxn=0; long long l,r,mid; long long u,v; bool check(long long x) { long long x1=sum[u+x-1]-sum[u-1]*b[x]; // cout<<sum[u+x-1]<<" "<<sum[u-1]<<" "<<b[x]<<" "<<x1<<endl; long long x2=sum[v+x-1]-sum[v-1]*b[x]; // cout<<sum[v+x-1]<<" "<<sum[v-1]<<" "<<b[x]<<" "<<x2<<endl; return x1==x2; } int main() { b[0]=1; for(int i=1;i<=100000;i++) b[i]=b[i-1]*bb; scanf("%s",str+1); long long len=strlen(str+1); for(long long i=1;i<=len;i++) sum[i]=sum[i-1]*bb+(str[i]-'a'+1); long long n=read(); for(long long i=1;i<=n;i++) { u=read(),v=read(); l=1,r=len-max(u,v)+1; maxn=0; while(l<=r) { mid=(l+r)/2; if(check(mid)) { maxn=max(maxn,mid); l=mid+1; }else r=mid-1; } printf("%d ",maxn); } } /* aabaabab 1 2 7 */
T2:
因为作者能力有限，数学技巧过于高深，所以先给std，学完以后再重新补写
#include<iostream> #include<cstring> #include<cstdio> using namespace std; inline int read() { int x=0,t=1,c; while(!isdigit(c=getchar()))if(c=='-')t=-1; while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*t; } int sig(long long x) { if(x<0)return -1; else if(!x)return 0; return 1; } long long gcd(long long a,long long b){return b?gcd(b,a%b):a;} class Vector { public: long long x,y; Vector(long long _x=0,long long _y=0) { x=_x; y=_y; } Vector operator + (const Vector &b) const { return Vector(x+b.x,y+b.y); } Vector operator - (const Vector &b) const { return Vector(x-b.x,y-b.y); } long long operator * (const Vector &b) const { return x*b.x+y*b.y; } }; class Line { public: long long a,b,c; Line(Vector v0,Vector v1) { a=v0.x-v1.x; b=v0.y-v1.y; swap(a,b); a=-a; c=gcd(a,b); a/=c; b/=c; c=a*v0.x+b*v0.y; } Line(long long _a=0,long long _b=1,long long _c=0) { a=_a; b=_b; c=_c; } int side(Vector v) { return sig(v*Vector(a,b)-c); } }l1,l2; void Solve() { int n=read(); Vector v0,v1,u0,u1; v0.x=read();v0.y=read();v1.x=read();v1.y=read(); l1=Line(v0,v1); bool res=0; while(n--) { u0.x=read();u0.y=read();u1.x=read();u1.y=read(); l2=Line(u0,u1); if(l1.a*l2.b==l1.b*l2.a) { if(l1.c*l2.b==l2.c*l1.b) { long long l0=0,r0=(v1-v0)*(v1-v0),l1=(u0-v0)*(v1-v0),r1=(u1-v0)*(v1-v0); if(l0<=r1&&l1<=r0)res=1; } } else { if(l1.side(u0)!=l1.side(u1)&&l2.side(v0)!=l2.side(v1))res=1; } } if(res)puts("YES"); else puts("NO"); } int main() { freopen("intersect.in","r",stdin); freopen("intersect.out","w",stdout); int T=read(); while(T--)Solve(); }
T3:
dijkstra倒推，加优先队列优化，设dis[n]=0,dis[i]=min{dis[i],max（最大限制，dis[x(i为起点的终点)]+所对应需要的能量）}
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> using namespace std; inline long long read() { long long f=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return ans*f; } priority_queue<pair<long long,long long > > que; long long n,m,cnt=1; struct node{ long long a,b,c,m,nex; }x[2000110]; long long head[1000010]; long long vis[1000010]; long long dis[1000010]; void add(long long u,long long v,long long c,long long m) { x[cnt].a=u,x[cnt].b=v,x[cnt].c=c,x[cnt].m=m; x[cnt].nex=head[u],head[u]=cnt++; } long long inf; int main() { memset(head,-1,sizeof(head)); memset(dis,127/3,sizeof(dis)); inf=dis[1]; n=read(),m=read(); for(long long i=1;i<=m;i++) { long long u=read(),v=read(),c=read(),m=read(); add(u,v,c,m); add(v,u,c,m); } dis[n]=0; que.push(make_pair(0,n)); while(!que.empty()) { long long xx=que.top().second;que.pop(); if(vis[xx]==1) continue; vis[xx]=1; for(long long i=head[xx];i!=-1;i=x[i].nex) { if(dis[x[i].b]>max(x[i].m,dis[xx]+x[i].c)) { dis[x[i].b]=max(x[i].m,dis[xx]+x[i].c); que.push(make_pair(-dis[x[i].b],x[i].b)); } } } if(dis[1]!=inf) cout<<dis[1]; else cout<<-1; }