一上午又跟划水一样。一个暴力两个空题。
部分分又少又难写，真心难受的一场考试。
空题倒不是不会，但是分别只会$15,10$分的档。于是博了博信仰尝试冲正解。
然而当然什么都没有冲出来。
也一直在弄$T1$想尝试$n^2$过五万或十万那样，然而依旧没卡过去。
然后就惨成这样了。。。。。。
也是状态不太好。冲$T3$其实差不多应该能想到，还是把太多时间放到$T1,2$上了。
改题比较顺利。也许吧。今天可能是最后一次能学$OI$到这个时候了/
T1：摧毁图状数
大意：树，每次操作可以将一个点及其$1,2,...,k-1$辈祖先都点亮，对于所有$1 le k le n$求最少操作多少次能点亮整棵树。
贪心的点叶子一定是对的。设叶子有$L$个。那么答案的上界是$O(L+frac{n}{k})$
我们对于每个节点求出$a[i]$表示这个节点到子树里最近的叶子的距离。然后丢进$vector$里。
可以发现除了叶节点，$a[i]=k$的点一定是最先被操作的。然后拿个优先队列依次操作，每次操作前判定这个点是否已经被点亮。
所以弄一个$dfs$序+线段树。维护每个节点的子树内，被操作过的点的最小深度，与$dep[p]+k$比较一下即可。
预处理叶子个数后。入队点个数是调和级数。所以总复杂度是$O(nlog^2n)$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define S 100005 4 vector<int>s[S],v[S]; priority_queue<pair<int,int> >q; 5 int n,dep[S],ans[S],L,mnd[S],f[19][S],dfn[S],tim,t[S<<2],dfr[S],Q[S],T; 6 void pre(int p,int fa){ 7 dep[p]=dep[fa]+1; f[0][p]=fa; mnd[p]=n+1; dfn[p]=++tim; 8 for(int i=1;i<19;++i)f[i][p]=f[i-1][f[i-1][p]]; 9 for(int i=0,y;y=i<s[p].size()?s[p][i]:0;++i)if(y!=fa) 10 pre(y,p),mnd[p]=min(mnd[p],mnd[y]); 11 dfr[p]=tim; 12 if(mnd[p]==n+1)mnd[p]=dep[p],L++;v[mnd[p]-dep[p]].push_back(p); 13 } 14 int Fa(int p,int k){for(int i=18;~i;--i)if(k&1<<i)p=f[i][p];return p;} 15 #define lc p<<1 16 #define rc lc|1 17 #define md (L+R>>1) 18 void mdf(int x,int w,int p=1,int L=1,int R=n){ 19 if(L==R)return t[p]=w,void(); 20 if(x<=md)mdf(x,w,lc,L,md);else mdf(x,w,rc,md+1,R); 21 t[p]=min(t[lc],t[rc]); 22 } 23 int ask(int l,int r,int p=1,int L=1,int R=n){ 24 if(l<=L&&R<=r)return t[p]; 25 return min(l<=md?ask(l,r,lc,L,md):n+n,r>md?ask(l,r,rc,md+1,R):n+n); 26 } 27 int main(){//freopen("tree2.in","r",stdin); 28 cin>>n; memset(t,0x3f,sizeof t); 29 for(int i=1,a,b;i<n;++i)scanf("%d%d",&a,&b),s[a].push_back(b),s[b].push_back(a); 30 pre(1,0); 31 for(int i=0;i<v[0].size();++i)mdf(dfn[v[0][i]],dep[v[0][i]]); 32 for(int k=1;k<=n;++k){ 33 for(int i=0;i<v[k].size();++i)q.push(make_pair(dep[v[k][i]],v[k][i])); 34 while(!q.empty()){ 35 int p=q.top().second,x;q.pop(); 36 if(ask(dfn[p],dfr[p])<dep[p]+k)continue; 37 mdf(dfn[p],dep[p]); Q[++T]=dfn[p]; ans[k]++; 38 if(x=Fa(p,k))q.push(make_pair(dep[x],x)); 39 }while(T)mdf(Q[T],n+n),T--; 40 }int q,x;cin>>q;while(q--)scanf("%d",&x),printf("%d ",ans[min(n,x)]+L); 41 }
T2：排列统计
大意：一个长为$n$的排列，随机进行$k$次两元素交换，求最后的序列中$cnt$的期望。
$cnt$定义为：从前往后扫，如果当前值是前缀最大值，$cnt++$。$n le 100,k le 80$
枚举$x,y$表示最终序列中位置$x$上是数字$y$。
设$dp[i][j][0/1/2/3/4]$表示交换了$i$次后$[1,x-1]$中有$j$个大于$y$的数。
$0/2$表示$a[x]>y$。$1/3$表示$a[x]<y$。$4$表示$a[x]=y$
设$a[p]=y$。$0/1$表示$p>x$。$2/3$表示$p<x$。显然$4$表示$p=x$
然后就可以转移了，一共有$39$种转移。时间复杂度$O(39kn^3)$。常数很小。
然而最大的测试点依旧跑了$3.4s$。最开始时限开$2s$有点过了。$8s$是不是有点多了。。？
常数不重要，这题写出来已经不容易了。。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mod 1000000007 4 int qp(int b,int t,int a=1){for(;t;t>>=1,b=1ll*b*b%mod)if(t&1)a=1ll*a*b%mod;return a;} 5 int p[111],a[111],dp[2][111][5],ans,k,nw,nx=1,I,s,n; 6 void go(int t,int j,int r){if(I+j>=0)dp[nx][I+j][t]=(dp[nx][I+j][t]+1ll*r*dp[nw][I][s])%mod;} 7 int main(){ 8 cin>>n>>k; for(int i=1;i<=n;++i)scanf("%d",&a[i]),p[a[i]]=i; 9 for(int x=1;x<=n;++x)for(int y=x;y<=n;++y){ 10 int c=0,R=min(x-1,n-y),r=1+(x-1)*(x-1)+(n-x)*(n-x);memset(dp,0,sizeof dp); 11 for(int i=1;i<x;++i)c+=a[i]>y; 12 dp[nw][c][(a[x]==y)<<2|(p[y]>x)<<1|a[x]>y]=1; 13 for(int _=1;_<=k;++_,nw^=1,nx^=1)for(I=0;I<=R;++I){ 14 #define IF if(dp[nw][I][s]) 15 #define ls (LS-(s<2)) 16 #define rb (RB-(s&1)) 17 #define rs (n-x-rb-(s&2?1:0)) 18 int lb=I,LS=x-lb-1,RB=n-y-lb; 19 s=4;IF go(0,0,ls*2),go(1,-1,lb*2),go(2,0,rs*2),go(3,0,rb*2); 20 for(s=0;s<4;++s)IF go(4,s==1,2); 21 for(s=0;s<4;s+=2)IF go(s,0,2*(ls+rs)),go(s^1,0,2*rb),go(s^1,-1,2*lb); 22 for(s=1;s<4;s+=2)IF go(s,0,2*(lb+rb)),go(s^1,0,2*rs),go(s^1, 1,2*ls); 23 for(s=0;s<2; ++s)IF go(s^2, 1,rb*2),go(s^2,0,rs*2); 24 for(s=2;s<4; ++s)IF go(s^2,-1,lb*2),go(s^2,0,ls*2); 25 for(s=0;s<5; ++s)IF go(s,0,ls*rs*2+lb*rb*2+r),go(s,1,ls*rb*2),go(s,-1,lb*rs*2),dp[nw][I][s]=0; 26 }ans=(ans+dp[nw][0][4])%mod; 27 }cout<<1ll*ans*qp(qp(n*n,k),mod-2)%mod<<endl; 28 }
T3：归并排序
大意：长度为$2$的整次幂的排列。执行正常的归并排序，然而在递归到长度为$2$的区间时会随机返回两种情况之一。
支持操作：询问$x$最后出现在位置$y$的概率，以及支持交换原始序列中两个数的位置。$nle 2^{16},qle 10^5$
不难发现，如果递归边界的两个数是$x,y(x<y)$
那么排对了就相当于是$x,y$。排错了相当于是$y,y+0.5$
所以每个数对应着两个可能的值，概率都是$frac{1}{2}$且互相独立。分开考虑贡献，期望有多少数比询问的数小，概率是多少。
把每个数对应的两个数视为一个区间，询问的数视为两个点：
要么整个区间都比点小，排名直接$+2$，要么大，排名不变，要么可大可小，直接组合数计算。
树状数组维护左右端点的值，每次就相当于是求前后缀和了。时间复杂度$qlogn$
被玄学了。同一份代码交两次结果不一样。迷茫。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define S 1<<18 4 #define mod 1000000007 5 int L[S],R[S],a[S],n,iv,fac[S],finv[S],q,y; 6 void add(int*t,int p,int v){for(;p<=n*2+2;p+=p&-p)t[p]+=v;} 7 int ask(int*t,int p,int a=0){for(;p;p^=p&-p)a+=t[p];return a;} 8 int qp(int b,int t,int a=1){for(;t;t>>=1,b=1ll*b*b%mod)if(t&1)a=1ll*a*b%mod;return a;} 9 int C(int b,int t){return t<0||b<t?0:1ll*fac[b]*finv[t]%mod*finv[b-t]%mod;} 10 void ctb(int x,int v=1){ 11 int y=a[x],z=a[x^1]; if(y>z)swap(y,z); 12 add(R,z*2,v);add(R,z*2+1,v); 13 add(L,n*2+2-y*2,v);add(L,2*n+2-z*2,v); 14 } 15 int cal(int x){ 16 int l=ask(R,x-1),r=ask(L,2*n+3-x); 17 return 1ll*C(n-l-r,y-l)*qp(2,l)%mod*qp(2,r)%mod; 18 } 19 int main(){//freopen("10.in","r",stdin);freopen("0.out","w",stdout); 20 cin>>n; iv=qp(qp(2,n+1),mod-2); 21 for(int i=0;i<n;++i)scanf("%d",&a[i]); 22 for(int i=0;i<n;i+=2)ctb(i); 23 for(int i=fac[0]=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod; 24 finv[n]=qp(fac[n],mod-2); 25 for(int i=n-1;~i;--i)finv[i]=finv[i+1]*(i+1ll)%mod; 26 scanf("%d",&q); 27 for(int o,x;q--;){ 28 scanf("%d%d%d",&o,&x,&y);x--;y--; 29 if(n==1&&o==2)puts(y?"0":"1"); 30 else if(o==1)ctb(x,-1),ctb(y,-1),swap(a[x],a[y]),ctb(x),ctb(y); 31 else if(a[x]>a[x^1])printf("%lld ",2ll*cal(a[x]*2)*iv%mod); 32 else printf("%lld ",1ll*iv*(cal(a[x]*2)+cal(a[x^1]*2+1))%mod); 33 } 34 }