[考试反思]1109csp-s模拟测试106：撞词
（撞哈希了用了模拟测试28的词，所以这次就叫撞词吧）
蓝色的0。。。
蓝色的0。。。
都该联赛了还能CE呢。。。
考试结束前15分钟左右，期望得分300
然后对拍发现T2伪了写了一个能拿90分的垃圾随机化
然后很着急，想再写一个部分分，结果没编译就交了。。。
不管在多么紧急的情况下，都要检查，编译。
。。。还不如不对拍拿一个伪的20。。。
然后T3少考虑一种情况。挂了。
T1：合并集合merge
区间dp板子。
1 #include<cstdio> 2 #include<bitset> 3 #include<iostream> 4 using namespace std; 5 bitset<303>B[603][603]; 6 int n,x[603],dp[603][603],sz[603][603],ans; 7 int main(){ 8 freopen("merge.in","r",stdin);freopen("merge.out","w",stdout); 9 scanf("%d",&n); 10 for(int i=1;i<=n;++i)scanf("%d",&x[i]),x[i+n]=x[i]; 11 for(int l=1;l<=n<<1;++l){ 12 B[l][l][x[l]]=1; 13 for(int r=l+1;r<l+n&&r<=n<<1;++r)B[l][r]=B[l][r-1],B[l][r][x[r]]=1; 14 } 15 for(int l=1;l<=n<<1;++l)for(int r=l;r<l+n&&r<=n<<1;++r)sz[l][r]=B[l][r].count(); 16 #define r l+len-1 17 for(int len=2;len<=n;++len)for(int l=1;r<=n<<1;++l)for(int m=l;m<r;++m) 18 dp[l][r]=max(dp[l][r],dp[l][m]+dp[m+1][r]+sz[l][m]*sz[m+1][r]); 19 for(int i=1;i<=n;++i)ans=max(ans,dp[i][i+n-1]); 20 printf("%d ",ans); 21 }
T2：爬climb
除了最后一步以外，每一步一定用A-B最大的。
枚举用的最后一个，考虑如何$O(logn)$进行$check$
发现其实只是i后面的药丸后错了一位，也可以理解为水位在i以后晚了一天才上涨。
预处理错位前后的两个$sum A-B$与水位的差值，$ST$查询。
复杂度$O(nlogn)$
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 struct P{ 5 int a,b; 6 friend bool operator<(P x,P y){ 7 return x.a-x.b>y.a-y.b; 8 } 9 }p[100005]; 10 int hb[100005],ans,n,lim; 11 long long L,sum[100005],h1[100005],h2[100005],wt[100005],st1[18][100005],st2[18][100005]; 12 long long mn1(int l,int r){ 13 if(r<l)return 123456789012345; 14 int B=hb[r-l+1]; 15 return min(st1[B][l],st1[B][r-(1<<B)+1]); 16 } 17 long long mn2(int l,int r){ 18 if(r<l)return 123456789012345; 19 int B=hb[r-l+1]; 20 return min(st2[B][l],st2[B][r-(1<<B)+1]); 21 } 22 int main(){freopen("climb.in","r",stdin);freopen("climb.out","w",stdout); 23 scanf("%d%lld",&n,&L);ans=lim=n+1;//printf("n=") 24 for(int i=1;i<=n;++i)scanf("%d%d",&p[i].a,&p[i].b); 25 sort(p+1,p+1+n); 26 for(int i=1;i<=n;++i)scanf("%lld",&wt[i]),wt[i]+=wt[i-1]; 27 for(int i=1;i<=n;++i)sum[i]=sum[i-1]+p[i].a-p[i].b;//,printf("%lld ",sum[i]); 28 for(int i=1;i<=n;++i)if(sum[i]<sum[i-1]){lim=i;break;} 29 for(int i=1;i<=n;++i)h1[i]=h2[i]=sum[i]; 30 for(int i=1;i<=n;++i)h1[i]-=wt[i],h2[i]-=wt[i-1]; 31 for(int i=1;i<=n;++i)st1[0][i]=h1[i],st2[0][i]=h2[i]; 32 for(int j=1;j<18;++j)for(int i=1;i+(1<<j)-1<=n;++i)st1[j][i]=min(st1[j-1][i],st1[j-1][i+(1<<j-1)]); 33 for(int j=1;j<18;++j)for(int i=1;i+(1<<j)-1<=n;++i)st2[j][i]=min(st2[j-1][i],st2[j-1][i+(1<<j-1)]); 34 for(int i=0;i<=18;++i)for(int j=1<<i;j<1<<i+1&&j<=n;++j)hb[j]=i; 35 for(int i=1;i<=n;++i){//printf("%d/%d:%d %d ",i,n,p[i].a,p[i].b); 36 int out1=lower_bound(sum,sum+lim,L-p[i].a)-sum,out2=lower_bound(sum,sum+lim,L-p[i].b)-sum;//printf("%d %d %d ",out1,out2,lim); 37 if(out1==lim&&out2==lim)continue; 38 if(out1<i&&out1!=lim){//printf("%lld ",mn1(1,out)); 39 if(mn1(1,out1)<=0)continue; 40 ans=min(ans,out1+1);//printf("1:%d %d ",i,out1); 41 }else if(out2>=i&&out2!=lim){//printf("%lld %lld ",mn1(1,i-1),mn2(i+1,out)); 42 if(mn1(1,i-1)<=0)continue; 43 if(mn2(i+1,out2)<=p[i].a-p[i].b)continue; 44 ans=min(ans,out2);//printf("2:%d %d ",i,out2); 45 } 46 }printf("%d ",ans==n+1?-1:ans);//printf("%lld %lld ",mn1(1,5),mn2(7,8)); 47 }