拿衣服==naive
拿(na)衣(i)服(ve)
cards
题解
发现牌堆最多只有$sqrt{n}$种,即1,2,3,4,5,6,7,8,9,10,成等差数列$frac{n*(n+1)}{2}==m$所以可以用链表维护
考场没打,懒了,其实即使没有这个性质我也应该打上链表啊,是对暴力优化,一定能使你暴力分更高就对了
知道自己暴力跑的慢就一定要优化,没时间优化算法可以,懒得优化一定不行
sort
题解
用的是DeepinC的状态定义,再次先%%%为敬,定义比题解简单很多,转移起来也很好转移
看到期望一眼dp(废话)
$rk[x][y]$表示在原有位置为x,新相对位置为y的概率
注意这里算的是相对位置,这个相对位置只在数相同时计算
例如1,1,1,1,2,2,2,原有位置5,新相对位置可以为1,2,3,表示在所有相同的2中它相对位置为1/2/3
有了这个,答案就很好算了
假设我们rk已经全部计算完成,维护sum[x]表示<=x数有sum[x]个,原位置为u
位置u答案就是$sumlimits_{j}rk[u][j]*j+sum[x-1]$就是枚举相对位置每一种情况
$rk$单独转移不好转移
$f[x][y][0/1]$归并排序时考虑完左面$x$个右面$y$个,最后考虑的是左/右
这里有了第三维定义我们就可以得知最后一个数是谁
转移就是左右相等随机取一个,要考虑其中一个已经考虑完
$f$转移就不放了
$f->rk$的转移
$tmp[j1+j2]=f[j1][j2][0]*rk[x][j1]$
$rk[x][nrk]=tmp[nrk]$
$tmp[j1+j2]=f[j1][j2][1]*rk[x][j2]$
$rk[x][nrk]=tmp[nrk]$
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define inv 499122177 #define mod 998244353 #define A 547 ll f[A][A][2],rk[A][A],a[A],lcnt[A*10],rcnt[A*10],tmp[A*10]; vector <ll> lv[A*10],rv[A*10]; ll ans,n; //rk[i][j],原位置i,新相对位置为j //只对相同的计算相对位置 void merge_sort(ll l,ll r){ // printf("l=%lld r=%lld ",l,r); if(l==r) return ; ll mid=(l+r)>>1; merge_sort(l,mid);merge_sort(mid+1,r); for(ll i=l;i<=mid;i++) lv[a[i]].push_back(i),lcnt[a[i]]++; for(ll i=mid+1;i<=r;i++) rv[a[i]].push_back(i),rcnt[a[i]]++; for(ll i=1;i<=1000;i++){ if(lcnt[i]==0&&rcnt[i]==0) continue ; for(ll j=0;j<=lcnt[i];j++) for(ll k=0;k<=rcnt[i];k++) f[j][k][0]=f[j][k][1]=0; f[0][0][0]=1; for(ll j=0;j<=lcnt[i];j++) for(ll k=0;k<=rcnt[i];k++){ if(j!=lcnt[i]&&k!=rcnt[i]){ f[j+1][k][0]=(f[j+1][k][0]+(f[j][k][0]+f[j][k][1])*inv%mod)%mod; f[j][k+1][1]=(f[j][k+1][1]+(f[j][k][0]+f[j][k][1])*inv%mod)%mod; } else if(j!=lcnt[i]) f[j+1][k][0]=(f[j+1][k][0]+f[j][k][0]+f[j][k][1])%mod; else if(k!=rcnt[i]) f[j][k+1][1]=(f[j][k+1][1]+f[j][k][0]+f[j][k][1])%mod; // printf("i=%lld f[%lld][%lld]=%lld %lld ",i,j,k,f[j][k][0],f[j][k][1]); } for(ll j=0;j<lcnt[i];j++){ for(ll j1=1;j1<=lcnt[i];j1++){ for(ll j2=0;j2<=rcnt[i];j2++){ tmp[j1+j2]=(tmp[j1+j2]+rk[lv[i][j]][j1]*f[j1][j2][0]%mod)%mod; } } for(ll nowrk=1;nowrk<=lcnt[i]+rcnt[i];nowrk++){ rk[lv[i][j]][nowrk]=(tmp[nowrk])%mod,tmp[nowrk]=0; // printf("rk[%lld][%lld]=%lld ",lv[i][j],nowrk,rk[lv[i][j]][nowrk]); } } for(ll j=0;j<rcnt[i];j++){ for(ll j1=0;j1<=lcnt[i];j1++){ for(ll j2=1;j2<=rcnt[i];j2++){ tmp[j1+j2]=(tmp[j1+j2]+rk[rv[i][j]][j2]*f[j1][j2][1]%mod)%mod; } } for(ll nowrk=1;nowrk<=lcnt[i]+rcnt[i];nowrk++){ rk[rv[i][j]][nowrk]=(tmp[nowrk])%mod,tmp[nowrk]=0; // printf("rk[%lld][%lld]=%lld ",rv[i][j],nowrk,rk[rv[i][j]][nowrk]); } } lv[i].clear();rv[i].clear();lcnt[i]=rcnt[i]=0; } // printf("l=%lld r=%lld ",l,r); } int main(){ scanf("%lld",&n); for(ll i=1;i<=n;i++) scanf("%lld",&a[i]); for(ll i=1;i<=n;i++) rk[i][1]=1; merge_sort(1,n); for(ll i=1;i<=n;i++) lcnt[a[i]]++; for(ll i=1;i<=1000;i++) lcnt[i]+=lcnt[i-1]; for(ll i=1;i<=n;i++){ ll ans=0; for(ll j=1;j<=lcnt[a[i]]-lcnt[a[i]-1];j++){ // printf("rk[%lld][%lld]=%lld ",i,j,rk[i][j]); ans=(ans+rk[i][j]*j)%mod; } printf("%lld ",ans+lcnt[a[i]-1]); } }
naive
题解
$Or-And+Min-Max$
暴力的话就是$st$表处理$Or-And+Min-Max$然后?$O1$处理
这里更新答案思想很不错,因为它还要至少包含某一个位置,用线段树维护,现在有一个区间$l,r$是合法的可以直接给$l,r$区间赋$max$
$Or-And$变化量很少只有$log$个,$Min-Max$又是递减的,于是可以在每一个$Or-And$相同区间内进行二分,找到最长符合$>=k$区间
维护$Or-And$用链表,支持合并
代码大致是这样
for(ll i=1;i<=n;i++){ for(ll j=pre[i];j;j=pre[j]){ if(ask(3,nxt[j],i)-ask(4,nxt[j],i)==ask(3,j,i)-ask(4,j,i)) del(j); }
代码
#include<bits/stdc++.h> using namespace std; #define ll int #define A 1111111 ll st[5][25][A],nxt[A],pre[A],a[A]; ll t,n,k,nowans,tail; ll logg[A]; void precl(){ t=23; for(ll i=1;i<=n;i++){ st[1][0][i]=a[i]; st[2][0][i]=a[i]; st[3][0][i]=a[i]; st[4][0][i]=a[i]; } for(ll j=1;j<=t;j++) for(ll i=1;i+(1<<j)-1<=n;i++){ st[1][j][i]=max(st[1][j-1][i],st[1][j-1][i+(1<<(j-1))]); st[2][j][i]=min(st[2][j-1][i],st[2][j-1][i+(1<<(j-1))]); st[3][j][i]=st[3][j-1][i]|st[3][j-1][i+(1<<(j-1))]; st[4][j][i]=st[4][j-1][i]&st[4][j-1][i+(1<<(j-1))]; } } ll ask(ll opt,ll l,ll r){ ll g=logg[r-l+1]; if(opt==1) return max(st[opt][g][l],st[opt][g][r-((1<<g))+1]); if(opt==2) return min(st[opt][g][l],st[opt][g][r-((1<<g))+1]); if(opt==3) return st[opt][g][l]|st[opt][g][r-((1<<g))+1]; if(opt==4) return st[opt][g][l]&st[opt][g][r-((1<<g))+1]; } struct node{ ll l,r,val,f; }tr[A*4]; void built(ll x,ll l,ll r){ tr[x].l=l,tr[x].r=r; if(l==r){ tr[x].val=-1; return ; } ll mid=(l+r)>>1; built(x<<1,l,mid); built(x<<1|1,mid+1,r); } void down(ll x){ tr[x<<1].f=max(tr[x<<1].f,tr[x].f); tr[x<<1|1].f=max(tr[x<<1|1].f,tr[x].f); tr[x<<1].val=max(tr[x<<1].val,tr[x].f); tr[x<<1|1].val=max(tr[x<<1|1].val,tr[x].f); tr[x].f=0; } void seg_add(ll x,ll l,ll r,ll val){ // printf("l=%d r=%d ",l,r); if(tr[x].l>=l&&tr[x].r<=r){ tr[x].val=max(val,tr[x].val); tr[x].f=max(val,tr[x].f); return ; } if(tr[x].f) down(x); ll mid=(tr[x].l+tr[x].r)>>1; if(mid>=l) seg_add(x<<1,l,r,val); if(mid<r) seg_add(x<<1|1,l,r,val); } void ask_point(ll x,ll pla){ if(tr[x].l==tr[x].r){ nowans=tr[x].val; return ; } if(tr[x].f) down(x); ll mid=(tr[x].l+tr[x].r)>>1; if(mid>=pla) ask_point(x<<1,pla); else ask_point(x<<1|1,pla); } ll cal(ll l,ll r){ return -ask(1,l,r)+ask(2,l,r)+ask(3,l,r)-ask(4,l,r); } void del(ll x){ // printf("**** "); ll nx=nxt[x],pr=pre[x]; nxt[pr]=nx; pre[nx]=pr; } void dfs(ll x){ if(tr[x].l==tr[x].r){ printf("%d ",tr[x].val); return ; } if(tr[x].f) down(x); dfs(x<<1); dfs(x<<1|1); } int main(){ // freopen("naive105.in","r",stdin); // freopen("zj.in","w",stdout); scanf("%d%d",&n,&k); nxt[0]=1; logg[0]=-1; for(ll i=1;i<=n;++i)logg[i]=logg[i>>1]+1; for(ll i=1;i<=n;i++) scanf("%d",&a[i]),nxt[i]=i+1,pre[i]=i-1; built(1,1,n); precl(); for(ll i=1;i<=n;i++){ for(ll j=pre[i];j;j=pre[j]){ if(ask(3,nxt[j],i)-ask(4,nxt[j],i)==ask(3,j,i)-ask(4,j,i)) del(j); } for(ll j=nxt[0];j<=i;j=nxt[j]){ ll l=pre[j]+1,r=j,R=i,ans=R; while(l<=r){ ll mid=(l+r)>>1; if(cal(mid,R)>=k){ r=mid-1; ans=mid; } else l=mid+1; } if(cal(ans,R)>=k){ seg_add(1,ans,R,R-ans+1); break; } } } dfs(1); }