A

开个桶$a$,实时记录每一个数出现的次数

比如$a_i$就表示当前$i$这个数出现的次数。

然后$a_i$就会形成一个“塔“,$c_i$就表示塔高至少为$i$的塔有多少个。

前缀和$c_i$代表的意义就是在$1\sim i$的高度(次数限制)下,一共有多少个数。

这个有什么用呢?

当枚举$k$,假设现在答案为$x$,那么也就是说一个数至多出现了$x$次,

总的个数是$k*x$,前缀和数组$c_x$的意义恰好就是在$1\sim x$的次数限制下,一共有多少个数。这时候只需要判断$c_x\ge k*x$,就能判断有无解,因为$c_x\ge k*x$,总能存在一种方案,使得能构成$x$次操作(就想办法把$x$层的$k$个塔给填到限制高度,也就是填满,之后横着看)。

可以二分答案,亦可以线性求解。

B

很明显的期望$DP$式子

$\large f_{i,j}=\frac{i*f_{i-1,j}+j*f_{i,j-1}+max(i,j)}{i+j}$

$\large g_{i,j}=f_{i,j}-max(i,j)$

$i>j$时,有

$$g_{i,j}+i=\frac{i}{i+j}f_{i-1,j}+\frac{j}{i+j}f_{i,j-1}+\frac{i}{i+j}$$

$$g_{i,j}+i=\frac{i}{i+j}(g_{i-1,j}+i-1)+\frac{j}{i+j}(g_{i,j-1}+i)+\frac{i}{i+j}$$

$$g_{i,j}=\frac{i}{i+j}g_{i-1,j}+\frac{j}{i+j}g_{i,j-1}$$

$i<j$时,同理。

$i=j$时,$g_{i,j}=\frac{1}{2}g_{i-1,j}+\frac{1}{2}g_{i,j-1}+\frac{1}{2}$

综上,$g_{i,j}=\frac{i}{i+j}g_{i-1,j}+\frac{j}{i+j}g_{i,j-1}+\frac{1}{2}[i=j]$

这个形式是不是很像从$(n,m)$走到$(0,0)$啊?

答案就是$g_{n,m}+\max\{n,m\}$

如何统计$g_{n,m}$?根据上面的推论,只有对角线的点权为$\frac{1}{2}$,因此只有对角线的点权会对答案产生贡献。

因此,可以用组合数去算出经过对角线的至少一个点的路径数,再除以总路径数,就可以得出答案。

$max\{n,m\}+\large \sum\limits_{i=1}^{min(n,m)}\frac{C_{n+m-2*i}^{n-i}*C_{2*i}^i}{2*C_{n+m}^n}$

牢记$E(aX+bY)=a*E(X)+b*E(Y),E(X)=\sum p_i*x_i$啊!!!!

C

这道题比较难,相信你们都已经看到了许多博客,所以块长为$256$就不讲了。

设$f_{x,i}$表示将$x$当作块的底端,往上$255$个节点,与$x$构成一个块$pos_x$,下面还有$i$个块,第$i$个块的底端到$x$块的最大值,即$\max\limits_{\forall j\in pos_x}\{w_j~xor~(dep_x+i*256-dep_j)\}$。

因此只需要预处理出块中每一个点,到与其本身能达到最大值的块,也就是$w_i~xor~(dep_x-dep_i)$的前$8$位(总共就$16$位)与$255$的异或值。

之后由于已经最大化了贡献,可以考虑用背包去更新其他位置的块。

对于询问操作,就是将$y(p)$不断往上跳,并更新块数$sz$(从原$y$跳到当前节点$p$历经的块数),贡献即为$f_{p,sz}$,与当前答案进行比较。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
using namespace std;
const int N=5e4+10,T=256;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct edge{int y,next;}a[N<<1];int last[N],len;
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
int dep[N],fa[N];
void dfs(int x)
{
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y==fa[x])continue;
        fa[y]=x;dep[y]=dep[x]+1;dfs(y);
    }
}
inline void mmax(int &x,int y){x=(x>y?x:y);}
int f[N][T],jump[N],w[N];
int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    int n,m;qr(n),qr(m);
    for(int i=1;i<=n;i++)qr(w[i]);
    for(int i=1,x,y;i<n;i++)qr(x),qr(y),ins(x,y),ins(y,x);
    fa[1]=0;dep[1]=1;dfs(1);
    for(int i=1;i<=n;i++)
    {
        int x=i;
        for(int j=0;j<T&&x;++j,x=fa[x])
        {
            int t=(w[x]^j)>>8;//dep
            mmax(f[i][(T-1)^t],(w[x]^j)|((T-1)<<8));
        }
        jump[i]=x;
        for(int j=0;j<8;++j)for(int k=0;k<T;++k)
            if(f[i][k^(1<<j)])mmax(f[i][k],f[i][k^(1<<j)]^(1<<(j+8)));
    }
    while(m--)
    {
        int x,y,p;qr(x),qr(y);p=y;int ans=w[x]^(dep[y]-dep[x]);
        for(int i=0;dep[x]<=dep[jump[p]];++i,p=jump[p])ans=max(ans,f[p][i]);
        for(;dep[x]<=dep[p];p=fa[p])ans=max(ans,(dep[y]-dep[p])^w[p]);
        qw(ans);puts("");
    }
    return 0;
}