真的是下定了巨大的决心来搞这一讲，果不其然耗了一晚上
开车旅行（真的是NOIP的题吗怎么这么恐怖）
首先，先用set把小A和小B从城市i出发，到达的下一个城市预处理出来。
f[i][j][k]表示走了2^i天，j城市出发，k表示谁开车，到达那个城市。
转移就是f[i][j][k]=f[i-1][f[i-1][j][k]][k] 相信很好理解
特别的i-1==0时，因为k是奇数，开车的人是变化的，所以f[i][j][k]=f[i-1][f[i-1][j][k]][k^1]
令da[i][j][k],db[i][j][k]，分别表示小A和小B这个状态下走的路程
对于询问1，枚举所有的城市作为起点，然后基于二进制划分的思想，倒着for一步步在满足走的总路程<=x0的情况下前进，这样可以计算出小A走的路程和小B走的路程。找最大比值即可。
询问二就直接询问小A走的路程和小B走的路程了。同理可求。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<set> using namespace std; typedef long long LL; int h[110000]; struct snode { int id,h; snode(){} snode(int ID,int H){id=ID;h=H;} friend bool operator <(snode s1,snode s2){return s1.h<s2.h;} }; set<snode>S; set<snode>::iterator it,lt,rt; int g[110000],I; bool cmp(int g1,int g2){return (abs(h[g1]-h[I])<abs(h[g2]-h[I]))||(abs(h[g1]-h[I])==abs(h[g2]-h[I])&&h[g1]<h[g2]);} int Ago[110000],Bgo[110000]; int f[22][110000][2]; LL da[22][110000][2],db[22][110000][2]; LL A,B; void solve(int now,int x0) { A=B=0; int k=0; for(int i=20;i>=0;i--) if(f[i][now][k]!=0&&da[i][now][k]+db[i][now][k]<=x0) { x0-=da[i][now][k]+db[i][now][k]; A+=da[i][now][k],B+=db[i][now][k]; if(i==0)k^=1; now=f[i][now][k]; } } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&h[i]); memset(Ago,0,sizeof(Ago)); memset(Bgo,0,sizeof(Bgo)); for(int i=n;i>=1;i--) { S.insert(snode(i,h[i])); it=lt=rt=S.find(snode(i,h[i])); int m=0; if(lt!=S.begin()) { lt--,g[++m]=(*lt).id; if(lt!=S.begin())lt--,g[++m]=(*lt).id; } rt++; if(rt!=S.end()) { g[++m]=(*rt).id; rt++;if(rt!=S.end())g[++m]=(*rt).id; } I=i;sort(g+1,g+m+1,cmp); if(m>1)Ago[i]=g[2]; if(m>0)Bgo[i]=g[1]; } memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) { if(Ago[i]!=0) f[0][i][0]=Ago[i], da[0][i][0]=abs(h[Ago[i]]-h[i]), db[0][i][0]=0; if(Bgo[i]!=0) f[0][i][1]=Bgo[i], da[0][i][1]=0, db[0][i][1]=abs(h[Bgo[i]]-h[i]); } for(int i=1;i<=20;i++) for(int j=1;j<=n;j++) for(int k=0;k<=1;k++) { int l=k;if(i==1)l=k^1; if(f[i-1][j][k]>0)f[i][j][k]=f[i-1][f[i-1][j][k]][l]; if(f[i][j][k]>0) { da[i][j][k]=da[i-1][j][k]+da[i-1][f[i-1][j][k]][l]; db[i][j][k]=db[i-1][j][k]+db[i-1][f[i-1][j][k]][l]; } } int x0,ans;LL ansA=1,ansB=0; scanf("%d",&x0); for(int i=1;i<=n;i++) { solve(i,x0); if(B==0)A=1; if(A*ansB<ansA*B||(A*ansB==ansA*B&&h[i]>h[ans]))ansA=A,ansB=B,ans=i; } printf("%d ",ans); int Q,x,y; scanf("%d",&Q); while(Q--) { scanf("%d%d",&x,&y); solve(x,y); printf("%lld %lld ",A,B); } return 0; }
Count The Repetitions
f[j][i]表示从s1第i个字符开始，能够表示出s2 2^j最少需要多少字符。
就有f[j][i]=f[j-1][i]+f[j-1][((i+f[j-1][i])-1)%s1len+1]
最后就枚举匹配的起始点，同样在不超过s1len*n1的情况下用二进制一步步跳，记录当前起始点的最优解更新答案就好了。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; char s1[110],s2[110]; LL f[40][110]; int main() { freopen("2.in","r",stdin); freopen("2.out","w",stdout); while(1) { int n2,n1; scanf("%s",s2+1);if(s2[1]=='}')break; scanf("%d%s%d",&n2,s1+1,&n1); int s2len=strlen(s2+1),s1len=strlen(s1+1); bool bk=false; for(int i=1;i<=s1len;i++) { int p=i;f[0][i]=0; for(int j=1;j<=s2len;j++) { int cc=0; while(s1[p]!=s2[j]) { p=p%s1len+1; cc++;if(cc>=s1len){printf("0 ");bk=true;break;} } p=p%s1len+1; f[0][i]+=cc+1; if(bk==true)break; } if(bk==true)break; } if(bk==true)continue; for(int j=1;j<=30;j++) for(int i=1;i<=s1len;i++) f[j][i]=f[j-1][i]+f[j-1][((i+f[j-1][i])-1)%s1len+1]; LL m=0; for(int i=1;i<=s1len;i++) { int x=i;LL ans=0; for(int j=30;j>=0;j--) if(x+f[j][(x-1)%s1len+1]-1<=s1len*n1) x+=f[j][(x-1)%s1len+1], ans+=(1<<j); m=max(m,ans); } printf("%lld ",m/n2); } return 0; }
好像都是先预处理出下一步的状态，然后二进制划分啊