牛客练习赛114

https://ac.nowcoder.com/acm/contest/63804

E Kevin的抽奖黑幕

题意

有 $n$ 个人，共 $m$ 轮抽奖。每轮抽奖抽 $k$ 个人发奖品，若有人连续 $d$ 轮没有获得奖品，那么他也能获得一个奖品。求最后所有人获得奖品的总和的期望。结果对 $9982443553$ 取模。

数据范围：$1\leq n,m\leq 2000,1\leq k\leq n,1\leq d,\leq m$。

题解

重要的观察是：可以单独计算一个人的贡献，然后乘上 $n$ 就是答案了。考虑如何计算一个人的：设 $f_{i,j}$ 为当前是第 $i$ 轮，他连续 $j$ 轮未抽中，直到第 $m$ 轮的获得奖品数的期望，转移是容易的：

$$f_{i,j}= \begin{cases} (f_{i+1,0}+1)\times\frac{k}{n}+(f_{i+1,j+1}\times\frac{n-k}{n}) &,0\leq j<d\\ f_{i+1,0}+1 &,j=d-1 \end{cases}$$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2005;
const int p=998244353;
ll f[N][N];
ll fpow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n,m,k,d;cin>>n>>m>>k>>d;
        ll p1=k*fpow(n,p-2)%p,p2=(n-k)*fpow(n,p-2)%p;
        for(int i=0;i<=d-1;i++) f[m][i]=0;
        for(int i=m-1;i>=0;i--)
        {
            for(int j=0;j<d;j++)
                f[i][j]=((f[i+1][0]+1)*p1+f[i+1][j+1]*p2)%p;
            f[i][d-1]=(f[i+1][0]+1)%p;
        }
        cout<<n*f[0][0]%p<<'\n';
    }
    return 0;
}

F Kevin去砍树

题意

有 $n$ 棵树，每棵树高度 $h_i$，价值 $w_i$。可以从任意一棵树开始砍伐，此后每次砍伐的树木必须与上一棵被砍伐的树相邻，且高度严格小于它。当一棵树被砍伐后，其左右的树被视为相邻。求所有方案中砍伐树木价值之和的最大值。

数据范围：$1\leq n\leq 2\times 10^5$。

题解

一个合法的砍伐序列一定是这样的：区间 $[l,r]$，且 $h_l<h_{l+1}<\cdots,<h_k>h_{k+1}>\cdots>h_r$。且中间没有相同的数字。那么，我们对每个点计算以它为右端点时左端点最远可以是多少。这样来设计状态：$f_{i,0/1}$ 分别表示以 $i$ 结尾一直上升的最远左端点和以 $i$ 结尾允许下降的最远左端点。那么有转移：

//lst[h[i]]表示上一个h[i]的位置
if(h[i]==h[i-1]) f[i][0]=f[i][1]=i;
else if(h[i]>h[i-1])
{
    f[i][0]=max(f[i-1][0],lst[h[i]]+1);
    f[i][1]=max(f[i-1][0],lst[h[i]]+1);
}
else
{
    f[i][0]=i;
    f[i][1]=max(f[i-1][1],lst[h[i]]+1);
}

其中 $h_i>h_{i-1}$ 时，一个合法的段只能是连续上升的，不能由一个上升加下降转移来，因为这样就出现了两段上升。$h_i<h_{i-1}$ 时，$h_i$ 只能归入下降段当中。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int h[N],w[N],lst[N],f[N][2];
ll sum[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        for(int i=0;i<=n;i++) lst[i]=0;
        for(int i=1;i<=n;i++) cin>>h[i];
        for(int i=1;i<=n;i++) cin>>w[i];
        for(int i=1;i<=n;i++) sum[i]=sum[i-1]+w[i];
        for(int i=1;i<=n;i++)
        {
            if(h[i]==h[i-1]) f[i][0]=f[i][1]=i;
            else if(h[i]>h[i-1])
            {
                f[i][0]=max(f[i-1][0],lst[h[i]]+1);
                f[i][1]=max(f[i-1][0],lst[h[i]]+1);
            }
            else
            {
                f[i][0]=i;
                f[i][1]=max(f[i-1][1],lst[h[i]]+1);
            }
            lst[h[i]]=i;
        }
        ll ans=0;
        for(int i=1;i<=n;i++) ans=max(ans,sum[i]-sum[min(f[i][0],f[i][1])-1]);
        cout<<ans<<'\n';
    }
    return 0;
}

G 图上异或难题

题意

有一张 $n$ 个点 $m$ 条边的图。现在将每个点染成黑色或白色，求所有两端点染上不同颜色的边边权异或和最大值。

数据范围：$1\leq n\leq 2\times 10^5,1\leq m\leq\min(\dfrac{n(n-1)}{2},2\times 10^5)$。

题解

考虑这样的转化：令每个点的点权为其连的所有边的异或和。那么答案就是这些点的最大子集异或和。考虑一条边 $(u,v)$，若 $u$ 和 $v$ 都被选了，那么它的边权出现两次，恰好抵消，否则它的边权有贡献。这刚好符合题意。

而最大子集异或和可以直接用线性基解决。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int B=60;
int a[N];
ll base[65];
void insert(ll x)
{
    for(int i=B;i>=0;i--)
        if(x&(1ll<<i))
        {
            if(!base[i])
            {
                base[i]=x;
                break;
            }
            else x^=base[i];
        }
}
ll qmx()
{
    ll res=0;
    for(int i=B;i>=0;i--)
        if((res^base[i])>res) res^=base[i];
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n,m;cin>>n>>m;
        memset(base,0,sizeof(base));
        for(int i=1;i<=n;i++) a[i]=0;
        for(int i=1;i<=m;i++)
        {
            int u,v,w;cin>>u>>v>>w;
            a[u]^=w,a[v]^=w;
        }
        for(int i=1;i<=n;i++) insert(a[i]);
        cout<<qmx()<<'\n';
    }
    return 0;
}