【考试总结】2022-04-06
Fable
考虑冒泡排序的性质即如果某个数前面有元素大于之，那么一定在这轮这种元素数量恰好减少 \(1\)
那么可以计算出来经过 \(k\) 轮后的每个位置的数字前面有几个元素大于之，然后使用数据结构维护最小的前方没有元素大于之的数即可
这样子的数据结构需要支持区间减法，所以写了线段树
Code Display
const int N=200010;
int n,m,a[N],k,b[N];
struct Fenwick{
int c[N];
inline int query(int x){
int res=0;
for(;x<=m;x+=x&(-x)) res+=c[x];
return res;
}
inline void insert(int x,int v){
for(;x;x-=x&(-x)) c[x]++;
return ;
}
}T;
int lsh[N];
bool vis[N];
vector inv[N];
struct Seg{
int Mn[N<<2],tag[N<<2];
inline void push_tag(int p,int v){Mn[p]+=v; tag[p]+=v;}
inline void push_down(int p){
if(tag[p]){
push_tag(p<<1,tag[p]);
push_tag(p<<1|1,tag[p]);
tag[p]=0;
} return ;
}
inline void push_up(int p){
Mn[p]=min(Mn[p<<1],Mn[p<<1|1]);
return ;
}
inline void build(int p,int l,int r){
if(l==r){
Mn[p]=inv[l].back();
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid); build(p<<1|1,mid+1,r);
return push_up(p);
}
inline void upd(int p,int l,int r,int st,int ed){
if(st<=l&&r<=ed) return push_tag(p,-1);
int mid=(l+r)>>1; push_down(p);
upd(p<<1,l,mid,st,ed);
if(ed>mid) upd(p<<1|1,mid+1,r,st,ed);
return push_up(p);
}
inline int dfs(int p,int l,int r){
if(l==r){
inv[l].pop_back();
Mn[p]=inv[l].size()?inv[l].back()+tag[p]:n+1;
return l;
}
int mid=(l+r)>>1,res=0;
push_down(p);
if(Mn[p<<1]==0) res=dfs(p<<1,l,mid);
else res=dfs(p<<1|1,mid+1,r);
push_up(p);
return res;
}
}seg;
signed main(){
freopen("fable.in","r",stdin); freopen("fable.out","w",stdout);
n=read(); k=read();
rep(i,1,n) a[i]=read(),lsh[i]=a[i];
sort(lsh+1,lsh+n+1);
m=unique(lsh+1,lsh+n+1)-lsh-1;
rep(i,1,n){
a[i]=lower_bound(lsh+1,lsh+m+1,a[i])-lsh;
b[i]=T.query(a[i]+1);
T.insert(a[i],1);
}
rep(i,1,n){
b[i]=max(0ll,b[i]-k);
inv[a[i]].emplace_back(b[i]);
}
rep(i,1,m){
sort(inv[i].begin(),inv[i].end());
reverse(inv[i].begin(),inv[i].end());
}
seg.build(1,1,m);
rep(i,1,n){
int v=seg.dfs(1,1,m);
print(lsh[v]);
if(v>1) seg.upd(1,1,m,1,v-1);
}
return 0;
}
Fiend
逆序对奇数减，偶数加，符合行列式定义，平凡做法就是直接求行列式 \(A_{i,l_i\sim r_i}=1\) 的值
但是发现每行的 \(1\) 是连续的，可以对于每列找到所有这列有元的行中右端点最小的，并将其它的行 \(l_j\leftarrow r_i+1\)
如果需要交换行那么需要将行列式的值取反
那么使用左偏树维护所有的左端点，要支持的操作是取出堆顶，合并两个堆
同时在左偏树的每个节点维护点对应的行编号以及逆映射，交换两行时就能维护正确的行号了
Code Display
const int N=1e5+10;
int n,nds;
int rt[N],ls[N],rs[N],dep[N],mp[N],id[N],val[N];
inline int merge(int x,int y){
if(!x||!y) return x+y;
if(val[x]>val[y]) swap(x,y);
rs[x]=merge(rs[x],y);
if(dep[rs[x]]>dep[ls[x]]) swap(ls[x],rs[x]);
dep[x]=dep[rs[x]]+1;
return x;
}
inline void pop(int &x){x=merge(ls[x],rs[x]);}
inline int New(int v,int lin){
int p=++nds;
mp[lin]=p; id[p]=lin;
dep[p]=1;
val[p]=v;
return p;
}
signed main(){
freopen("fiend.in","r",stdin); freopen("fiend.out","w",stdout);
int T=read(); while(T--){
n=read();
for(int i=1;i<=n;++i){
int l=read(),r=read();
rt[l]=merge(rt[l],New(r,i));
}
int ans=1;
for(int i=1;i<=n;++i){
if(!rt[i]){ans=0; break;}
if(id[rt[i]]!=i){
id[mp[i]]=id[rt[i]];
mp[id[rt[i]]]=mp[i];
ans*=-1;
}
int v=val[rt[i]];
pop(rt[i]);
if(val[rt[i]]==v){ans=0; break;}
if(v0) puts("Y");
else if(ans==0) puts("D");
else puts("F");
for(int i=1;i<=n;++i){
dep[i]=ls[i]=rs[i]=val[i]=0;
id[i]=mp[i]=0;
rt[i]=0;
}
nds=0;
}
return 0;
}
Flair
使用互质数对 \((a,b)\) 不能表示出来的最大数是 \(ab-a-b\) 推导不互质的数对可以发现：在 \(x>10000\) 后，每个菜品数量所消耗的钱数是每 \(\rm GCD\{c\}\) 一循环的，同时在每个循环节中都是以 \(\rm GCD-1\to 0\) 方式递减
那么使用倍增 \(\rm MTT\) 配合 \(f_{i,j}=pf_{i-1,j-1}+(1-p)f_{i,j}\) 计算 \(G_r=\sum\limits_{i\equiv r\bmod\ {\rm{GCD}}} f_{n,i}\) 后可以得到选择菜品数较多时候的答案
对于选择菜品数对应的浪费的钱数未进入循环节的情况，可以另做一个背包来算浪费数，而对应的选菜概率的计算可以使用 组合数等于下降幂除阶乘 的方式来解决
Code Display
const int N=10010;
int n,m,p,c[N];
const double pi=acos(-1);
struct node{
long double x,y;
node(){}
node(long double xx,long double yy){x=xx; y=yy; return ;}
node operator +(const node &a)const{return node(x+a.x,y+a.y);}
node operator -(const node &a)const{return node(x-a.x,y-a.y);}
node operator *(const node &a)const{return node(x*a.x-y*a.y,x*a.y+y*a.x);}
inline node conj(){return node(x,-y);}
inline void clear(){x=y=0;}
}A0[N<<2],B0[N<<2],A1[N<<2],B1[N<<2],W[N<<2],F[N<<2],G[N<<2],H[N<<2];
int r[N<<2];
inline void FFT(node *f,int lim,int opt){
rep(i,0,lim-1){
if(i>1; node tt;
W[0]=node(1,0);
rep(i,1,len-1) W[i]=node(cos(pi/len*i),opt*sin(pi/len*i));
for(int k=0;k>1]>>1|((i&1)?(lim>>1):0);
}
for(int i=0;i>15,A0[i].y=a[i]&32767; FFT(A0,lim,1);
for(int i=0;i>15,B0[i].y=b[i]&32767; FFT(B0,lim,1);
for(int i=0;i dp(20010,1000100);
dp[0]=0;
int up=2e4;
for(int i=1;i<=m;++i){
for(int j=0;j+c[i]<=up;++j) if(dp[j]==0) dp[j+c[i]]=0;
}
for(int i=up-1;i>=0;--i) ckmin(dp[i],dp[i+1]+1);
rep(i,0,g-1) poly[i]=bas[i]=0;
poly[0]=1;
bas[1]=p; bas[0]=100-p;
int y=n,lenb=2,lenp=1;
while(y){
if(y&1){
MTT(poly,bas,poly,lenp,lenb);
lenp=min(g,lenp+lenb-1);
}
MTT(bas,bas,bas,lenb,lenb);
lenb=min(g,lenb*2-1);
y>>=1;
}
int ans=0;
int dfac=1,pwp=1,curpw=ksm(100-p,n),Inv=ksm(100-p,mod-2);
for(int i=0;i<=min(n,10000ll);++i){
int contr=mul(mul(pwp,curpw),mul(dfac,ifac[i]));
ckadd(ans,mul(dp[i],contr));
ckdel(poly[i%g],contr);
ckmul(dfac,n-i);
ckmul(pwp,p);
ckmul(curpw,Inv);
}
for(int i=1;i