ZR 集训 Day30 - 模拟赛

前言 今天是集训最后一天。。。 题目： 排列游戏 我们发现，想要字典序最小，肯定第一个填 1 是最优的，这样以来后面每个位置的奇偶性都确定了，我们直接按照从小到大放就行。 但是有一个特例，就是当 n \mod 4=3 的时候，第一个放 1 没有合法解，只能放 2。 代码： C++ #include using namespace std; int c,T,n; signed main(){ scanf("%d%d",&c,&T); while(T--){ scanf("%d",&n); if(n%4==3){ for(int i=1;i*4 `#include using namespace std; int c,T,n; signed main(){ scanf("%d%d",&c,&T); while(T--){ scanf("%d",&n); if(n%4==3){ for(int i=1;i*4n;i++) printf("%d %d %d %d ",4*i-2,4*i-3,4*i-1,4*i); printf("%d %d %d\n",n-(n%4)+2,n-(n%4)+1,n-(n%4)+3); } else{ for(int i=1;i*4n;i++) printf("%d %d %d %d ",4*i-3,4*i-2,4*i,4*i-1); if(n%4==1) printf("%d\n",n-(n%4)+1); else if(n%4==2) printf("%d %d\n",n-(n%4)+1,n-(n%4)+2); else printf("\n"); } } return 0; }` 时间线 当我们固定 r1 时，需要寻找一个 r2 使得： \min_{i=1}^{r1} a_i = \max_{i=r2+1}^n a_i - \text{mex}_{i=r1+1}^{r2} a_i 易证 \max_{i=r2+1}^n a_i - \text{mex}_{i=r1+1}^{r2} a_i 具有单调性，所以二分找到满足条件的 r2 的区间即可。 代码： C++ #include using namespace std; #define int long long const int N=1e6+5; int c,T,n; int a[N],cnt[N],pre[N],mex[N],lg[N],st[20][N]; int qmax(int l,int r){ int k=lg[r-l+1]; return max(st[k][l],st[k][r-(1>c>>T; while(T--){ cin>>n; for(int i=1;i>a[i]; pre[1]=a[1]; for(int i=2;i=1;i--){ if(a[i]=1) mex[i-1]=now; } for(int i=2;i>1]+1; for(int i=1;i>1; int F=qmax(i+1,mid)-mex[mid]; if(F>=L) fl=mid,r=mid-1; else l=mid+1; } if(fl==-1) continue; if(qmax(i+1,fl)-mex[fl]!=L) continue; l=i+1,r=n-1; while(l>1; int F=qmax(i+1,mid)-mex[mid]; if(F `#include using namespace std; #define int long long const int N=1e6+5; int c,T,n; int a[N],cnt[N],pre[N],mex[N],lg[N],st[20][N]; int qmax(int l,int r){ int k=lg[r-l+1]; return max(st[k][l],st[k][r-(1k)+1]); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>c>>T; while(T--){ cin>>n; for(int i=1;in;i++) cin>>a[i]; pre[1]=a[1]; for(int i=2;in;i++) pre[i]=min(pre[i-1],a[i]); for(int i=0;in+2;i++) cnt[i]=0; int now=0; for(int i=n;i>=1;i--){ if(a[i]n) cnt[a[i]]++; while(cnt[now]) now++; if(i-1>=1) mex[i-1]=now; } for(int i=2;in;i++) lg[i]=lg[i>>1]+1; for(int i=1;in;i++) st[0][i]=a[i]; for(int k=1;klg[n];k++) for(int i=1;i+(1k)-1n;i++) st[k][i]=max(st[k-1][i],st[k-1][i+(1(k-1))]); int ans=0; for(int i=1;in-2;i++){ int L=pre[i],l=i+1,r=n-1,fl=-1,fr=-1; while(lr){ int mid=(l+r)>>1; int F=qmax(i+1,mid)-mex[mid]; if(F>=L) fl=mid,r=mid-1; else l=mid+1; } if(fl==-1) continue; if(qmax(i+1,fl)-mex[fl]!=L) continue; l=i+1,r=n-1; while(lr){ int mid=(l+r)>>1; int F=qmax(i+1,mid)-mex[mid]; if(FL) fr=mid,l=mid+1; else r=mid-1; } if(fr==-1) continue; ans+=fr-fl+1; } coutans"\n"; } return 0; }` 暂存 对于一个二元组 (i,j) \ (j>i)，考虑计算如果想要 a_i 换到 a_j 后面又多少种可能性。 首先，对于 i=1，我们只需暂存 a_i，并保证 a_{i+1} 到 a_j 都不被暂存即可，可能性为 2^{n-1-(j-i)}。 对于 i>1，我们不仅需要满足以上条件，还要保证 a_{i-1} 不会被暂存，可能性就是 2^{n-2-(j-i)}。 所以对于 a_i,a_j，如果 a_ia_j，贡献就是总可能性减去交换的可能性。 对于 i=1 我们可以直接记录答案；对于 i>1，我们会发现，固定 j 时乘法分配律一下就变成单点修改区间查询问题了，用一个树状数组维护即可。 代码： C++ #include using namespace std; #define int long long const int N=2e5+5; const int mod=998244353; int c,T,n; int a[N],b[N],p2[N],inv[N]; inline int fpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y>>=1; } return res; } inline int qpow(int x,int y){ if(x==2){ if(y>=0) return p2[y]; return inv[-y]; } if(y>=0) return fpow(x,y); return fpow(fpow(x,-y),mod-2); } struct BIT{ int tr[N]; void add(int x,int k){ for(;x0;x-=x&-x) (res+=tr[x])%=mod; return res; } void clear(){ for(int i=1;i>c>>T; p2[0]=1,inv[0]=1; int inv2=fpow(2,mod-2); for(int i=1;i>n; num.clear(),bit.clear(); for(int i=1;i>a[i],b[i]=a[i]; sort(b+1,b+1+n); for(int i=1;ia[i]) ans=((ans+qpow(2,n-1)-swp)%mod+mod)%mod; } bit.add(a[2],qpow(2,2)); num.add(a[2],1); for(int i=3;i `#include using namespace std; #define int long long const int N=2e5+5; const int mod=998244353; int c,T,n; int a[N],b[N],p2[N],inv[N]; inline int fpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y>>=1; } return res; } inline int qpow(int x,int y){ if(x==2){ if(y>=0) return p2[y]; return inv[-y]; } if(y>=0) return fpow(x,y); return fpow(fpow(x,-y),mod-2); } struct BIT{ int tr[N]; void add(int x,int k){ for(;xn;x+=x&-x) (tr[x]+=k)%=mod; } int get(int x){ if(x0) return 0; int res=0; for(;x>0;x-=x&-x) (res+=tr[x])%=mod; return res; } void clear(){ for(int i=1;in;i++) tr[i]=0; } }bit,num; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>c>>T; p2[0]=1,inv[0]=1; int inv2=fpow(2,mod-2); for(int i=1;iN;i++){ p2[i]=(p2[i-1]*2)%mod; inv[i]=(inv[i-1]*inv2)%mod; } while(T--){ int ans=0; cin>>n; num.clear(),bit.clear(); for(int i=1;in;i++) cin>>a[i],b[i]=a[i]; sort(b+1,b+1+n); for(int i=1;in;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b; if(n==1){ cout"0\n"; continue; } for(int i=2;in;i++){ int swp=qpow(2,n-i); if(a[1]a[i]) (ans+=swp)%=mod; if(a[1]>a[i]) ans=((ans+qpow(2,n-1)-swp)%mod+mod)%mod; } bit.add(a[2],qpow(2,2)); num.add(a[2],1); for(int i=3;in;i++){ int sum=bit.get(n)-bit.get(a[i]),ni=num.get(n)-num.get(a[i]); ans=((ans-((qpow(2,n-2-i)*sum)%mod))%mod+mod)%mod; ans=(ans+((qpow(2,n-1)*ni)%mod))%mod; sum=bit.get(a[i]-1); ans=(ans+((qpow(2,n-2-i)*sum)%mod))%mod; bit.add(a[i],qpow(2,i)); num.add(a[i],1); } coutans"\n"; } return 0; }`