首页 > 代码库 > 线段树什么的最讨厌了
线段树什么的最讨厌了
线段树什么的最讨厌了
这一题当然不能去枚举n,而是要去扩展构造.
假设当前区间为[L,R].我们要将这个区间扩展为[0,?](当然是在可行的情况下)
由于被扩展出的区间与当前区间的长度最多相差一(而且在左边的区间长度不小于右边,可证),所以有四种方向扩展(设区间长度为len):
1.由区间[L,R]扩展出[L-len-1,L-1],区间变为[L-len-1,R];
2.由区间[L,R]扩展出[L-len,L-1],区间变为[L-len,R];
3.由区间[L,R]扩展出[R+1,R+len],区间变为[L,R+len];
4.由区间[L,R]扩展出[R+1,R+len-1],区间变为[L,R+len-1];
当然,我们还要加一点剪枝,然后就A了,总复杂度应该是4*log2(R-L+1),稳.
1 #include<cstdio> 2 #include<iostream> 3 int L,R,limitn,ans; 4 using namespace std; 5 void B(int L,int R){ 6 if (L<0||R>=ans||L>R) return; 7 if (L==0){ans=R; return;} 8 int len=R-L+1; if (R-L+1>L) return; 9 B(L-len,R); B(L-len-1,R); B(L,R+len-1); B(L,R+len);10 }11 int main(){12 int T; scanf("%d",&T);13 for (; T; T--){14 cin>>L>>R>>limitn,ans=limitn+1;15 B(L,R); if (ans==limitn+1) ans=-1;16 printf("%d\n",ans);17 }18 return 0;19 }
线段树什么的最讨厌了
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。