题意:给你一张纸,纸上有一些单词和相片,给你一些限制条件,求要占的最小行数
题解：
倍增
乍一看是一个模拟题，但是N和Q的范围很大，所以需要搞点事情
设f1[i][j]表示从第i个单词连续1<<j行不经过相片所能填的单词数，f2[i][j]表示从第i个单词开始经过相片所能填的单词数
这样就很容易用倍增转移了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #define ll long long 8 using namespace std; 9 10 const int N = 100010; 11 12 int T,n,m,w,pw,dw; 13 int a[N],f1[N][22],f2[N][22]; 14 15 int gi() { 16 int x=0,o=1; char ch=getchar(); 17 while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); 18 if(ch=='-') o=-1,ch=getchar(); 19 while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); 20 return o*x; 21 } 22 23 void get_st() { 24 for(int i=1; i<=n; i++) { 25 int sum=a[i],j=i+1; 26 while(sum+a[j]+1<=w && j<=n) sum+=a[j++]+1; 27 f1[i][0]=j-i; 28 } 29 for(int j=1; j<=20; j++) 30 for(int i=1; i<=n; i++) 31 f1[i][j]=f1[i][j-1]+f1[i+f1[i][j-1]][j-1]; 32 for(int i=1; i<=n; i++) { 33 int sum=0,flg=0,j=i; 34 while(sum+a[j]+flg<=dw) sum+=a[j++]+flg,flg=1; 35 sum=flg=0; 36 while(sum+a[j]+flg<=w-pw-dw) sum+=a[j++]+flg,flg=1; 37 f2[i][0]=j-i; 38 } 39 for(int j=1; j<=20; j++) 40 for(int i=1; i<=n; i++) 41 f2[i][j]=f2[i][j-1]+f2[i+f2[i][j-1]][j-1]; 42 } 43 44 int query1(int i, int x) { 45 if(x==0) return i; 46 while(x && i<=n) { 47 int j=0; 48 while(1<<(j+1)<=x) j++; 49 i+=f1[i][j]; 50 x-=1<<j; 51 } 52 return i; 53 } 54 55 int query2(int i, int x) { 56 if(x==0) return i; 57 while(x && i<=n) { 58 int j=0; 59 while(1<<(j+1)<=x) j++; 60 i+=f2[i][j]; 61 x-=1<<j; 62 } 63 return i; 64 } 65 66 int query3(int i) { 67 int ret=0; 68 while(i<=n) { 69 int j=0; 70 while(i+f1[i][j+1]<=n) j++; 71 i+=f1[i][j]; 72 ret+=1<<j; 73 } 74 return ret; 75 } 76 77 int main() { 78 T=gi(); 79 while(T--) { 80 n=gi(),w=gi(),pw=gi(),dw=gi(); 81 for(int i=1; i<=n; i++) a[i]=gi(); 82 m=gi(),get_st(); 83 for(int i=1; i<=m; i++) { 84 int x=gi(),h=gi(),tmp,ans,t; 85 tmp=query3(1); 86 if(tmp<=x-1) { 87 printf("%d ", tmp+h); 88 continue; 89 } 90 ans=(x+h-1); 91 t=query1(1,x-1); 92 t=query2(t,h); 93 if(t<=n) ans+=query3(t); 94 printf("%d ", ans); 95 } 96 } 97 }