NOIP 模拟 $31\; \rm Game$
2021/8/7 6:35:51
本文主要是介绍NOIP 模拟 $31\; \rm Game$,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题解
很容易求出在没有字典序最大的限制条件下的最多胜利场数。
这样就可以对于每一位放最优的解,怎么做,二分答案。
分两种情况,一种是当前一位是输的,一种是赢的,复杂度 \(\mathcal O(\rm nlog^2n)\) 卡卡常即可。
Code
#include<bits/stdc++.h> #define ri register signed #define p(i) ++i namespace IO{ char buf[1<<21],*p1=buf,*p2=buf; #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++ struct nanfeng_stream{ template<typename T>inline nanfeng_stream &operator>>(T &x) { ri f=1;x=0;register char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=0;ch=gc();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=gc();} return x=f?x:-x,*this; } }cin; } using IO::cin; namespace nanfeng{ #define FI FILE *IN #define FO FILE *OUT template<typename T>inline T cmax(T x,T y) {return x>y?x:y;} template<typename T>inline T cmin(T x,T y) {return x>y?y:x;} static const int N=1e5+7; int an[N],bn[N],tmx[N],tx,n,mx; struct ZKW{ #define ls(x) (x<<1) #define rs(x) (x<<1|1) struct segmenttree{int s,a,b;}T[N<<3]; int bs; ZKW() {bs=1;} inline void up(int x) { int tmp=cmin(T[ls(x)].b,T[rs(x)].a); T[x].s=T[ls(x)].s+T[rs(x)].s+tmp; T[x].a=T[ls(x)].a+T[rs(x)].a-tmp; T[x].b=T[ls(x)].b+T[rs(x)].b-tmp; } inline void build() {for (;bs<=mx;bs<<=1);} inline void update(int p,int x,int t) { p+=bs; if (t) T[p].b+=x; else T[p].a+=x; for (p>>=1;p;p>>=1) up(p); } }T; inline int main() { //FI=freopen("nanfeng.in","r",stdin); //FO=freopen("nanfeng.out","w",stdout); cin >> n; for (ri i(1);i<=n;p(i)) cin >> bn[i],mx=cmax(mx,bn[i]); for (ri i(1);i<=n;p(i)) cin >> an[i],mx=cmax(mx,an[i]),p(tmx[an[i]]); tx=mx; T.build(); for (ri i(1);i<=n;p(i)) T.update(bn[i],1,1),T.update(an[i],1,0); int ans=T.T[1].s; for (ri i(1);i<=n;p(i)) { T.update(bn[i],-1,1); ri l=bn[i]+1,r,res(-1); while(!tmx[tx]) --tx; r=tx; while(l<=r) { int mid(l+r>>1); T.update(mid,-1,0); if (T.T[1].s==ans-1) l=mid+1,res=mid; else r=mid-1; T.update(mid,1,0); } if (res!=-1) --ans,--tmx[res],printf("%d ",res),T.update(res,-1,0); else { l=1,r=bn[i],res; while(l<=r) { int mid(l+r>>1); T.update(mid,-1,0); if (T.T[1].s==ans) l=mid+1,res=mid; else r=mid-1; T.update(mid,1,0); } T.update(res,-1,0); printf("%d ",res); --tmx[res]; } } puts(""); return 0; } } int main() {return nanfeng::main();}
这篇关于NOIP 模拟 $31\; \rm Game$的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)