T1 lcp
题目大意：
q次询问一个字符串两个后缀的最长公共前缀
思路：
可以二分长度hash判断
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #define MAXN 10010011 #define ll long long12 #define inf 213906214313 using namespace std;14 inline int read()15 {16 int x=0,f=1;char ch=getchar();17 while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}18 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}19 return x*f;20 }21 const int mod1=19260817,mod2=998244353,bas1=137,bas2=233;22 ll hsh1[MAXN],hsh2[MAXN],pw1[MAXN],pw2[MAXN];23 int n,ans,a,b;24 char c[MAXN];25 int Check(int x)26 {27 int va1=(hsh1[a+x-1]-(hsh1[a]*pw1[x-1])%mod1+mod1)%mod1,va2=(hsh2[a+x-1]-(hsh2[a]*pw2[x-1])%mod2+mod2)%mod2;28 int vb1=(hsh1[b+x-1]-(hsh1[b]*pw1[x-1])%mod1+mod1)%mod1,vb2=(hsh2[b+x-1]-(hsh2[b]*pw2[x-1])%mod2+mod2)%mod2;29 if(va1==vb1&&va2==vb2) return 1;30 return 0;31 }32 int main()33 {34 freopen("lcp.in","r",stdin);35 freopen("lcp.out","w",stdout);36 scanf("%s",c+1);n=strlen(c+1);37 for(int i=pw1[0]=pw2[0]=1;i<=n;i++)38 pw1[i]=(pw1[i-1]*bas1)%mod1,hsh1[i]=((hsh1[i-1]*bas1)%mod1+c[i]-'a'+1)%mod1,39 pw2[i]=(pw2[i-1]*bas2)%mod2,hsh2[i]=((hsh2[i-1]*bas2)%mod2+c[i]-'a'+1)%mod2;40 int q=read(),l,r,mid;41 while(q--)42 {43 a=read(),b=read(),l=ans=1,r=n-max(a,b)+1;44 if(c[a]!=c[b]) {puts("0");continue;}45 while(r>=l)46 {47 mid=(l+r)>>1;48 if(Check(mid)) ans=mid,l=mid+1;49 else r=mid-1;50 }51 printf("%d\n",ans);52 }53 }
T2 线段求交
题目大意：
求两个线段的交点
思路：
使用计算几何
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #define MAXN 11 #define ll long long12 #define inf 213906214313 using namespace std;14 inline int read()15 {16 int x=0,f=1;char ch=getchar();17 while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}18 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}19 return x*f;20 }21 int n,ans;22 struct Point23 {24 double x,y;25 Point operator - (const Point &a) const26 {27 return (Point){x-a.x,y-a.y};28 }29 double operator ^ (const Point &a) const30 {31 return x*a.y-y*a.x;32 }33 };34 struct Segment{Point st,ed;}g,h;35 double Area(Point a,Point b,Point c){ return (b-a)^(c-a);}36 bool Intersec(Point a,Point b,Point c,Point d)37 {38 if(max(a.x,b.x)
T3 spaceship
题目大意：
你在点1处可以带一些油，每条道路有一个额外的权值c，表示当你剩余至少c的油的时候才能走这条路，每条路需要费不同的油
求1到n至少要带多少油
思路：
反跑dij 每次修改dis数组的时候dis[to[i]与max(dis[x]+val[i],limit[i])取min即可
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #define MAXN 10010011 #define ll long long12 #define inf 213906214313 using namespace std;14 inline int read()15 {16 int x=0,f=1;char ch=getchar();17 while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}18 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}19 return x*f;20 }21 int n,m,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],val[MAXN<<1],lmt[MAXN<<1],cnt;22 void add(int u,int v,int w,int c){nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w,lmt[cnt]=c;}23 struct node24 {25 int x,dis;26 bool operator < (const node &a) const27 {28 return dis>a.dis;29 }30 };31 int dis[MAXN],vis[MAXN];32 priority_queue q; 33 void dij()34 {35 memset(dis,127,sizeof(dis));36 dis[n]=0;q.push((node){n,0});int x,d;37 while(!q.empty())38 {39 x=q.top().x,d=q.top().dis;q.pop();40 if(vis[x]) continue;41 vis[x]=1;42 for(int i=fst[x];i;i=nxt[i])43 if(dis[to[i]]>max(d+val[i],lmt[i])){dis[to[i]]=max(d+val[i],lmt[i]);q.push((node){to[i],dis[to[i]]});}44 }45 if(dis[1]>=inf) puts("-1");46 else printf("%d",dis[1]);47 }48 int main()49 {50 freopen("spaceship.in","r",stdin);51 freopen("spaceship.out","w",stdout);52 n=read(),m=read();int a,b,c,d;53 while(m--){a=read(),b=read(),c=read(),d=read();add(a,b,c,d);add(b,a,c,d);}54 dij();55 }