2020-2021:teams:namespace:牛客多校第六场
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:牛客多校第六场 [2020/07/29 17:32] great_designer [H] |
2020-2021:teams:namespace:牛客多校第六场 [2020/08/01 10:22] (当前版本) great_designer [I] |
||
|---|---|---|---|
| 行 165: | 行 165: | ||
| 以下是补题。 | 以下是补题。 | ||
| + | |||
| + | 本题用到了斐波那契数和卢卡斯数的结论。[[斐波那契和卢卡斯]] | ||
| <hidden> | <hidden> | ||
| - | <code C> | + | <code C++> |
| + | |||
| + | #include<stdio.h> | ||
| + | |||
| + | #include<algorithm> | ||
| + | #include<set> | ||
| + | |||
| + | using namespace std; | ||
| + | |||
| + | set<pair<int,int> > s; | ||
| + | |||
| + | long long L[44],ans; | ||
| + | |||
| + | void Sub(set<pair<int,int> >::iterator p) | ||
| + | { | ||
| + | set<pair<int,int> >::iterator pl=p,pr=p; | ||
| + | int l=(*p).second,r=(*p).first,last,plast; | ||
| + | if(p==s.begin()) | ||
| + | { | ||
| + | ans-=l>>1; | ||
| + | if(l<=3) | ||
| + | { | ||
| + | ans-=r-l>>1; | ||
| + | plast=r; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | ans-=r-l; | ||
| + | plast=r-1; | ||
| + | } | ||
| + | last=1; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | --pl; | ||
| + | last; | ||
| + | if((*pl).second<=3) | ||
| + | { | ||
| + | last=(*pl).first; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | last=(*pl).first-1; | ||
| + | } | ||
| + | ans-=(l-last+1)/2; | ||
| + | ans-=r-l; | ||
| + | plast=r-1; | ||
| + | } | ||
| + | ++pr; | ||
| + | if(pr==s.end()) | ||
| + | { | ||
| + | return; | ||
| + | } | ||
| + | ans+=((*pr).second-last+1)>>1; | ||
| + | ans-=((*pr).second-plast+1)>>1; | ||
| + | return; | ||
| + | } | ||
| + | |||
| + | void Add(set<pair<int,int> >::iterator p) | ||
| + | { | ||
| + | set<pair<int,int> >::iterator pl=p,pr=p; | ||
| + | int l=(*p).second,r=(*p).first,last,plast; | ||
| + | if(p==s.begin()) | ||
| + | { | ||
| + | ans+=l>>1; | ||
| + | if(l<=3) | ||
| + | { | ||
| + | ans+=r-l>>1; | ||
| + | plast=r; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | ans+=r-l; | ||
| + | plast=r-1; | ||
| + | } | ||
| + | last=1; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | --pl; | ||
| + | last; | ||
| + | if((*pl).second<=3) | ||
| + | { | ||
| + | last=(*pl).first; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | last=(*pl).first-1; | ||
| + | } | ||
| + | ans+=(l-last+1)/2; | ||
| + | ans+=r-l; | ||
| + | plast=r-1; | ||
| + | } | ||
| + | ++pr; | ||
| + | if(pr==s.end()) | ||
| + | { | ||
| + | return; | ||
| + | } | ||
| + | ans-=((*pr).second-last+1)>>1; | ||
| + | ans+=((*pr).second-plast+1)>>1; | ||
| + | return; | ||
| + | } | ||
| + | |||
| + | void add(int x) | ||
| + | { | ||
| + | if(!x) | ||
| + | { | ||
| + | return; | ||
| + | } | ||
| + | if(x==1) | ||
| + | { | ||
| + | x=2; | ||
| + | } | ||
| + | set<pair<int,int> >::iterator p=s.lower_bound(make_pair(x-1,-1)); | ||
| + | if(p==s.end()||(*p).second>x+1) | ||
| + | { | ||
| + | int l=(1ll<<31)-1,r; | ||
| + | if(p!=s.end()) | ||
| + | { | ||
| + | l=(*p).second; | ||
| + | r=(*p).first; | ||
| + | } | ||
| + | if(l==x+2) | ||
| + | { | ||
| + | Sub(p); | ||
| + | s.erase(p); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | r=x; | ||
| + | } | ||
| + | p=s.lower_bound(make_pair(x-2,-1)); | ||
| + | if(p!=s.end()&&(*p).first==x-2) | ||
| + | { | ||
| + | l=(*p).second; | ||
| + | Sub(p); | ||
| + | s.erase(p); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | l=x; | ||
| + | } | ||
| + | s.insert(make_pair(r,l)); | ||
| + | Add(s.lower_bound(make_pair(r,l))); | ||
| + | return; | ||
| + | } | ||
| + | if((*p).first==x-1) | ||
| + | { | ||
| + | int l=(*p).second; | ||
| + | Sub(p); | ||
| + | s.erase(p); | ||
| + | if(l<x-1) | ||
| + | { | ||
| + | s.insert(make_pair(x-3,l)); | ||
| + | Add(s.lower_bound(make_pair(x-3,l))); | ||
| + | } | ||
| + | add(x+1); | ||
| + | return; | ||
| + | } | ||
| + | if(((*p).first-x)&1) | ||
| + | { | ||
| + | int l=(*p).second,r=(*p).first; | ||
| + | Sub(p); | ||
| + | s.erase(p); | ||
| + | if(l<x) | ||
| + | { | ||
| + | s.insert(make_pair(x-1,l)); | ||
| + | Add(s.lower_bound(make_pair(x-1,l))); | ||
| + | } | ||
| + | l=r+1,r=r+1; | ||
| + | p=s.lower_bound(make_pair(r+2,-1)); | ||
| + | if(p!=s.end()&&(*p).second==r+2) | ||
| + | { | ||
| + | r=(*p).first; | ||
| + | Sub(p); | ||
| + | s.erase(p); | ||
| + | } | ||
| + | s.insert(make_pair(r,l)); | ||
| + | Add(s.lower_bound(make_pair(r,l))); | ||
| + | return; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | int l=(*p).second,r=(*p).first; | ||
| + | Sub(p); | ||
| + | s.erase(p); | ||
| + | if(l<x) | ||
| + | { | ||
| + | s.insert(make_pair(x-1,l+1)); | ||
| + | Add(s.lower_bound(make_pair(x-1,l+1))); | ||
| + | } | ||
| + | int nl=r+1; | ||
| + | r=r+1; | ||
| + | p=s.lower_bound(make_pair(r+2,-1)); | ||
| + | if(p!=s.end()&&(*p).second==r+2) | ||
| + | { | ||
| + | r=(*p).first; | ||
| + | Sub(p); | ||
| + | s.erase(p); | ||
| + | } | ||
| + | p=s.lower_bound(make_pair(nl-2,-1)); | ||
| + | if(p!=s.end()&&(*p).first==nl-2) | ||
| + | { | ||
| + | nl=(*p).second; | ||
| + | Sub(p); | ||
| + | s.erase(p); | ||
| + | } | ||
| + | s.insert(make_pair(r,nl)); | ||
| + | Add(s.lower_bound(make_pair(r,nl))); | ||
| + | add(l-2); | ||
| + | return; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | void del(int x) | ||
| + | { | ||
| + | if(!x) | ||
| + | { | ||
| + | return; | ||
| + | } | ||
| + | if(x==1) | ||
| + | { | ||
| + | x=2; | ||
| + | } | ||
| + | set<pair<int,int> >::iterator p=s.lower_bound(make_pair(x,-1)); | ||
| + | if((*p).second>x) | ||
| + | { | ||
| + | int r=(*p).first,l=(*p).second; | ||
| + | Sub(p); | ||
| + | s.erase(p); | ||
| + | if(l<r) | ||
| + | { | ||
| + | s.insert(make_pair(r,l+2)); | ||
| + | Add(s.lower_bound(make_pair(r,l+2))); | ||
| + | } | ||
| + | if((x-l)&1) | ||
| + | { | ||
| + | if(l-2>=x+1) | ||
| + | { | ||
| + | p=s.lower_bound(make_pair(x-1,-1)); | ||
| + | if(p==s.end()||(*p).first!=x-1) | ||
| + | { | ||
| + | s.insert(make_pair(l-2,x+1)); | ||
| + | Add(s.lower_bound(make_pair(l-2,x+1))); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | int nl=(*p).second; | ||
| + | Sub(p); | ||
| + | s.erase(p); | ||
| + | s.insert(make_pair(l-2,nl)); | ||
| + | Add(s.lower_bound(make_pair(l-2,nl))); | ||
| + | } | ||
| + | } | ||
| + | add(l-2); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | p=s.lower_bound(make_pair(x-1,-1)); | ||
| + | if(p==s.end()||(*p).first!=x-1) | ||
| + | { | ||
| + | s.insert(make_pair(l-1,x+1)); | ||
| + | Add(s.lower_bound(make_pair(l-1,x+1))); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | int nl=(*p).second; | ||
| + | Sub(p); | ||
| + | s.erase(p); | ||
| + | s.insert(make_pair(l-1,nl)); | ||
| + | Add(s.lower_bound(make_pair(l-1,nl))); | ||
| + | } | ||
| + | } | ||
| + | return; | ||
| + | } | ||
| + | if(((*p).second-x)&1) | ||
| + | { | ||
| + | int r=(*p).first,l=(*p).second; | ||
| + | Sub(p); | ||
| + | s.erase(p); | ||
| + | s.insert(make_pair(x-1,l)); | ||
| + | Add(s.lower_bound(make_pair(x-1,l))); | ||
| + | if(x+3<=r) | ||
| + | { | ||
| + | s.insert(make_pair(r,x+3)); | ||
| + | Add(s.lower_bound(make_pair(r,x+3))); | ||
| + | } | ||
| + | add(x-1); | ||
| + | return; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | int r=(*p).first,l=(*p).second; | ||
| + | Sub(p); | ||
| + | s.erase(p); | ||
| + | if(r>x) | ||
| + | { | ||
| + | s.insert(make_pair(r,x+2)); | ||
| + | Add(s.lower_bound(make_pair(r,x+2))); | ||
| + | } | ||
| + | if(l<x) | ||
| + | { | ||
| + | s.insert(make_pair(x-2,l)); | ||
| + | Add(s.lower_bound(make_pair(x-2,l))); | ||
| + | } | ||
| + | return; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int X[1000],Y[1000]; | ||
| + | |||
| + | void solve() | ||
| + | { | ||
| + | int a,b; | ||
| + | scanf("%d%d",&a,&b); | ||
| + | ++b; | ||
| + | int op=0,OP=0; | ||
| + | if(a<0) | ||
| + | { | ||
| + | OP=1; | ||
| + | a=-a; | ||
| + | } | ||
| + | int cnt=0,cnt2=0; | ||
| + | while(a) | ||
| + | { | ||
| + | int k=upper_bound(L+1,L+44,a)-L-1; | ||
| + | a-=L[k]; | ||
| + | op=OP; | ||
| + | if(op&1) | ||
| + | { | ||
| + | Y[cnt2++]=b+k; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | X[cnt++]=b+k; | ||
| + | } | ||
| + | if(b-k>=0) | ||
| + | { | ||
| + | op^=k&1; | ||
| + | if(op&1) | ||
| + | { | ||
| + | Y[cnt2++]=b-k; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | X[cnt++]=b-k; | ||
| + | } | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | op^=k&1; | ||
| + | if((b-k+1)&1) | ||
| + | { | ||
| + | op^=1; | ||
| + | } | ||
| + | if(op&1) | ||
| + | { | ||
| + | Y[cnt2++]=k-b; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | X[cnt++]=k-b; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | int i; | ||
| + | for(i=0;i<cnt;++i) | ||
| + | { | ||
| + | add(X[i]); | ||
| + | } | ||
| + | for(i=0;i<cnt2;++i) | ||
| + | { | ||
| + | del(Y[i]); | ||
| + | } | ||
| + | printf("%lld\n",ans); | ||
| + | } | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | L[0]=2; | ||
| + | L[1]=1; | ||
| + | int i; | ||
| + | for(i=2;i<44;++i) | ||
| + | { | ||
| + | L[i]=L[i-1]+L[i-2]; | ||
| + | } | ||
| + | int T; | ||
| + | scanf("%d",&T); | ||
| + | while(T--) | ||
| + | { | ||
| + | ans=0; | ||
| + | s.clear(); | ||
| + | int n; | ||
| + | scanf("%d",&n); | ||
| + | while(n--) | ||
| + | { | ||
| + | solve(); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| </code> | </code> | ||
| 行 333: | 行 734: | ||
| =====I===== | =====I===== | ||
| - | <hidden> | + | 题目、解答与代码见[[Stirling数]]。 |
| - | <code C> | + | |
| - | + | ||
| - | </code> | + | |
| - | </hidden> | + | |
| =====K===== | =====K===== | ||
2020-2021/teams/namespace/牛客多校第六场.1596015140.txt.gz · 最后更改: 2020/07/29 17:32 由 great_designer
