2020-2021:teams:namespace:牛客多校第六场
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:牛客多校第六场 [2020/07/29 10:25] great_designer [C] |
2020-2021:teams:namespace:牛客多校第六场 [2020/08/01 10:22] (当前版本) great_designer [I] |
||
|---|---|---|---|
| 行 162: | 行 162: | ||
| </hidden> | </hidden> | ||
| + | =====F===== | ||
| + | 以下是补题。 | ||
| + | |||
| + | 本题用到了斐波那契数和卢卡斯数的结论。[[斐波那契和卢卡斯]] | ||
| + | |||
| + | <hidden> | ||
| + | <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> | ||
| + | </hidden> | ||
| + | |||
| + | =====G===== | ||
| + | |||
| + | 纯粹的构造题。隔壁的天才题解告诉我们，循环填入就完事了。啊，我为什么就没想到呢…… | ||
| + | |||
| + | <hidden> | ||
| + | <code C> | ||
| + | |||
| + | #include<stdio.h> | ||
| + | |||
| + | int r[205][205],c[205][205]; | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | int t; | ||
| + | scanf("%d",&t); | ||
| + | while(t--) | ||
| + | { | ||
| + | int n,k; | ||
| + | scanf("%d%d",&n,&k); | ||
| + | if(k==1||n==1||2*(n+1)*n%k) | ||
| + | { | ||
| + | printf("-1\n"); | ||
| + | continue; | ||
| + | } | ||
| + | int res=0; | ||
| + | int i; | ||
| + | for(i=1;i<=n;i++) | ||
| + | { | ||
| + | int j; | ||
| + | for(j=1;j<=n;j++) | ||
| + | { | ||
| + | r[i][j]=res; | ||
| + | res=(res+1)%k; | ||
| + | } | ||
| + | for(j=1;j<=n+1;j++) | ||
| + | { | ||
| + | c[j][i]=res; | ||
| + | res=(res+1)%k; | ||
| + | } | ||
| + | } | ||
| + | for(i=1;i<=n;i++) | ||
| + | { | ||
| + | r[n+1][i]=res; | ||
| + | res=(res+1)%k; | ||
| + | } | ||
| + | for(i=1;i<=n+1;i++) | ||
| + | { | ||
| + | int j; | ||
| + | for(j=1;j<=n;j++) | ||
| + | { | ||
| + | printf("%d ",c[i][j]+1); | ||
| + | } | ||
| + | puts(""); | ||
| + | } | ||
| + | for(i=1;i<=n+1;i++) | ||
| + | { | ||
| + | int j; | ||
| + | for(j=1;j<=n;j++) | ||
| + | { | ||
| + | printf("%d ",r[i][j]+1); | ||
| + | } | ||
| + | puts(""); | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | =====H===== | ||
| + | |||
| + | 传说中的数位DP——标程如下。 | ||
| + | |||
| + | <hidden> | ||
| + | <code C> | ||
| + | |||
| + | #include<stdio.h> | ||
| + | #include<string.h> | ||
| + | |||
| + | void Add(int *x,int y) | ||
| + | { | ||
| + | (*x)+=y; | ||
| + | if((*x)>=1000000007) | ||
| + | { | ||
| + | (*x)-=1000000007; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int dp[105][2005][2][2]; | ||
| + | char s[105]; | ||
| + | int n,v[105]; | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | scanf("%s",s+1); | ||
| + | n=strlen(s+1); | ||
| + | int i; | ||
| + | for(i=1;i<=n;i++) | ||
| + | { | ||
| + | v[i]=s[i]-'0'; | ||
| + | } | ||
| + | dp[0][1000][0][0]=1; | ||
| + | for(i=0;i<n;i++) | ||
| + | { | ||
| + | int d; | ||
| + | for(d=0;d<2005;d++) | ||
| + | { | ||
| + | int f0; | ||
| + | for(f0=0;f0<2;f0++) | ||
| + | { | ||
| + | int f1; | ||
| + | for(f1=0;f1<2;f1++) | ||
| + | { | ||
| + | if(!dp[i][d][f0][f1]) | ||
| + | { | ||
| + | continue; | ||
| + | } | ||
| + | int V=v[i+1]; | ||
| + | int A; | ||
| + | for(A=0;A<10;A++) | ||
| + | { | ||
| + | int B; | ||
| + | for(B=0;B<10;B++) | ||
| + | { | ||
| + | if(A>B&&!f0) | ||
| + | { | ||
| + | continue; | ||
| + | } | ||
| + | if(B>V&&!f1) | ||
| + | { | ||
| + | continue; | ||
| + | } | ||
| + | int nf0=f0|(A<B); | ||
| + | int nf1=f1|(B<V); | ||
| + | Add(&dp[i+1][d+A-B][nf0][nf1],dp[i][d][f0][f1]); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | int res=0; | ||
| + | int d; | ||
| + | for(d=1000+1;d<2005;d++) | ||
| + | { | ||
| + | int f1; | ||
| + | for(f1=0;f1<2;f1++) | ||
| + | { | ||
| + | Add(&res,dp[n][d][1][f1]); | ||
| + | } | ||
| + | } | ||
| + | printf("%d\n",res); | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | =====I===== | ||
| + | |||
| + | 题目、解答与代码见[[Stirling数]]。 | ||
| + | |||
| + | =====K===== | ||
| + | |||
| + | 最初我开了两个map，结果TLE。 | ||
| + | |||
| + | 这个版本的标程里用到了stable_sort（例如归并排序），亲测删掉stable_则通过率0%。因此需要保证排序时元素有序性。 | ||
| + | |||
| + | <hidden> | ||
| + | <code C++> | ||
| + | |||
| + | #include<stdio.h> | ||
| + | |||
| + | #include<algorithm> | ||
| + | #include<vector> | ||
| + | |||
| + | using namespace std; | ||
| + | |||
| + | int a[500111],ord[500111],n,k; | ||
| + | |||
| + | bool cmp(int x,int y) | ||
| + | { | ||
| + | return a[x]<a[y]; | ||
| + | } | ||
| + | |||
| + | bool check() | ||
| + | { | ||
| + | int i; | ||
| + | for(i=1;i<=n;i++) | ||
| + | { | ||
| + | ord[i]=i; | ||
| + | } | ||
| + | stable_sort(ord+1,ord+n+1,cmp); | ||
| + | vector<pair<int,int> > vs; | ||
| + | for(i=2;i<=n;i++) | ||
| + | { | ||
| + | if(a[ord[i]]==a[ord[i-1]]) | ||
| + | { | ||
| + | int p1=ord[i-1],p2=ord[i]; | ||
| + | if(p2-p1>=k) | ||
| + | { | ||
| + | continue; | ||
| + | } | ||
| + | int vl=p2%k,vr=(p1-1)%k; | ||
| + | if(vl<=vr) | ||
| + | { | ||
| + | vs.push_back(make_pair(vl,vr)); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | vs.push_back(make_pair(vl,k-1)); | ||
| + | vs.push_back(make_pair(0,vr)); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | sort(vs.begin(),vs.end()); | ||
| + | int MX=-1; | ||
| + | for(i=0;i<(int)vs.size();i++) | ||
| + | { | ||
| + | if(MX<vs[i].first-1) | ||
| + | { | ||
| + | return true; | ||
| + | } | ||
| + | MX=(MX>vs[i].second?MX:vs[i].second); | ||
| + | } | ||
| + | if(MX<k-1) | ||
| + | { | ||
| + | return true; | ||
| + | } | ||
| + | return false; | ||
| + | } | ||
| + | |||
| + | void solve() | ||
| + | { | ||
| + | scanf("%d%d",&n,&k); | ||
| + | int i; | ||
| + | for(i=1;i<=n;i++) | ||
| + | { | ||
| + | scanf("%d",&a[i]); | ||
| + | } | ||
| + | if(check()) | ||
| + | { | ||
| + | puts("YES"); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | puts("NO"); | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | int tc; | ||
| + | scanf("%d",&tc); | ||
| + | while(tc--) | ||
| + | { | ||
| + | solve(); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/namespace/牛客多校第六场.1595989528.txt.gz · 最后更改: 2020/07/29 10:25 由 great_designer
