牛客练习赛101题解

A-千层蛋糕

显然第一个是最大值第二个是最小值然后剩下的都不用管了。
时间复杂度： $O(n)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#define file(x) freopen("data"#x".in","r",stdin);freopen("data"#x".out","w",stdout);
#define ll long long
using namespace std;
const ll N=1e6+10;
ll n,a[N];
signed main()
{
//    file(10);
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    printf("%lld\n",(a[n]-a[1])*(n-1));
    return 0;
}

B-荒神在此

考虑到 $a_1$ 的选择可以改变序列的奇偶性，所以无论后面的如何选择都可以通过调整 $a_1$ 来变成奇数。
所以答案就是 $\frac{(n+1)!}{2}$ 。
时间复杂度： $O(n)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#define file(x) freopen("data"#x".in","r",stdin);freopen("data"#x".out","w",stdout);
#define ll long long
using namespace std;
const ll P=998244353;
ll n,ans;
signed main()
{
//    file(10);
    scanf("%lld",&n);ans=1;
    for(ll i=3;i<=n+1;i++)
        ans=ans*i%P;
    printf("%lld\n",ans);
    return 0;
}

题目名字出自：文豪野犬第三季

C-推理小丑

考虑从高位往低位贪心，考虑第 $i$ 位是否必须填 $1$ 。我们先默认 $i$ 位填 $0$ ，再从大到小枚举一个 $j<i$ ，此时因为我们如果第 $j$ 位可以为 $1$ 就必须填 $1$ ，这样一定是对的，因为每个能够填上去的 $j$ 都可以去分割序列中的一些段（也就是固定一些位置的 $a_x<a_{x+1}$ ）。
这样最后看是否能找到一个合法的解就可以确定第 $i$ 位是否必须填 $1$ 了。
时间复杂度： $O(n\log ^2 a)$

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,a[N];
int main()
{
    scanf("%d",&n);
    if(n<1||n>1e5)return -1;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<n;i++) 
        if(a[i]>=a[i+1])return -1;
    int ans=0;
    for(int j=30;j>=0;j--){
        int now=ans;
        for(int k=j-1;k>=0;k--){
            bool flag=0;now|=1<<k;
            for(int i=1;i<n;i++)
                if((a[i]&now)>(a[i+1]&now))
                {flag=1;break;}
            if(flag)now^=1<<k;
        }
        bool flag=0;
        for(int i=1;i<n;i++)
            if((a[i]&now)>=(a[i+1]&now))
            {flag=1;break;}
        if(flag)ans|=(1<<j);
    }
    for(int i=1;i<n;i++)
        if((a[i]&ans)>=(a[i+1]&ans))
            return -1;
    printf("%d\n",ans);
    return 0;
}

题目名字出自：长夜余火

D-罪业之都

如果有环，那么就直接找到一个环定向，然后其他的点都指向这个环就行了。
然后考虑是树的情况怎么做，我们随意找一个根开始出发，对于每个位置记录一个 $f_i$ 表示 $i$ 号点的子树最多能延伸一条向下长度为 $f_i$ 的路径，如果 $f_i$ 是负数则表示不能往下延伸，至少向上延伸一条长度为 $f_i$ 的要求路径。
这样我们去合并相邻子树时找到一个能往下的最深的，看下其他往上的能不能都塞到那条里去就行了。因为一个子树能向下证明它自身就能够合法，所以能向下就向下一定最优。
时间复杂度： $O(n+m)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#define file(x) freopen("shadow"#x".in","r",stdin);freopen("shadow"#x".out","w",stdout);
using namespace std;
const int N=1e5+10;
struct node{
    int to,next;
}a[N<<2];
int n,m,tot,ls[N],f[N],g[N];
bool v[N],r[N],ans[N<<2];
void addl(int x,int y){
    a[++tot].to=y;
    a[tot].next=ls[x];
    ls[x]=tot;return;
}
int dfs(int x,int fa){
    if(v[x])return x;v[x]=1;
    for(int i=ls[x];i;i=a[i].next){
        int y=a[i].to;
        if(y==fa)continue;
        int p=dfs(y,x);
        if(p){
            if(p!=-1)ans[i]=1,r[x]=1;
            if(p==x)return -1;
            return p;
        }
    }
    return 0;
}
void dfs2(int x,int fa){
    if(v[x])return;v[x]=1;
    for(int i=ls[x];i;i=a[i].next){
        int y=a[i].to;
        if(r[y]||y==fa)continue;
        ans[i^1]=1;dfs2(y,x);
    }
    return;
}
void calc(int x,int fa){
    g[x]=-f[x];
    for(int i=ls[x];i;i=a[i].next){
        int y=a[i].to;
        if(y==fa)continue;
        calc(y,x);
        if(g[y]>=0){
            ans[i]=1;
            if(g[y]>=-g[x]-1)g[x]=max(g[x],g[y]+1);
        }
        else if(g[y]<0){
            ans[i^1]=1;
            if(-g[y]-1>=g[x])g[x]=min(g[x],g[y]+1);
        }
    }
    return;
}
int main()
{
    scanf("%d%d",&n,&m);tot=1;
    for(int i=1;i<=n;i++)scanf("%d",&f[i]);
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        addl(x,y);addl(y,x);
    }
    if(m!=n-1){
        dfs(1,0);
        memset(v,0,sizeof(v));
        for(int i=1;i<=n;i++)
            if(r[i])dfs2(i,0);
    }
    else{
        calc(1,0);
        if(g[1]<0)return puts("-1")&0;
    }
    for(int i=3;i<=tot;i+=2)
        if(ans[i])putchar('1');
        else putchar('0');
    putchar('\n');
    return 0;
}
/*
5 4
0 2 0 1 3
4 2
5 4
5 1
3 4
*/

题目名字出自：黑暗之魂3

E-水没都市

因为我们只能抬高路径，所以最后淹没时间肯定不会变短，而因为最后一批都是合法的，所以我们显然也没有必要让最后淹没时间变长。
所以我们可以直接算一个最小生成树得到最后的淹没时间 $T$ ，那么然后就是要求 $1$ 号点到 $n$ 号点的所有路径上都至少经过一条高度为 $T$ 的边，而对于一条边 $h_i$ 高度抬到 $T$ 的话需要用 $T-h_i$ 次魔法。
不难联想到最小割，每条边的权值为 $T-h_i$ ，然后求 $1$ 到 $n$ 的最小割就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define file(x) freopen("data"#x".in","r",stdin);freopen("data"#x".out","w",stdout);
#define ll long long
const ll N=2e5+10;
using namespace std;
struct node{
    ll x,y,w;
}e[N];
struct edge{
    ll to,next,w;
}a[N<<1];
ll n,m,tot,Lim,ls[N],fa[N],dep[N],ans;
queue<int> q;
ll find(ll x)
{return (fa[x]==x)?(x):(fa[x]=find(fa[x]));}
bool cmp(node x,node y)
{return x.w<y.w;}
void addl(ll x,ll y,ll w){
    a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;
    a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=w;
    return;
}
bool bfs(){
    while(!q.empty())q.pop();q.push(1);
    memset(dep,0,sizeof(dep));dep[1]=1;
    while(!q.empty()){
        ll x=q.front();q.pop();
        for(ll i=ls[x];i;i=a[i].next){
            ll y=a[i].to;
            if(!a[i].w||dep[y])continue;
            dep[y]=dep[x]+1;
            if(y==n)return 1;
            q.push(y);
        }
    }
    return 0;
}
ll dinic(ll x,ll flow){
    if(x==n)return flow;
    ll rest=0,k;
    for(ll i=ls[x];i;i=a[i].next){
        ll y=a[i].to;
        if(dep[x]+1!=dep[y]||!a[i].w)continue;
        rest+=(k=dinic(y,min(flow-rest,a[i].w)));
        a[i].w-=k;a[i^1].w+=k;
        if(flow==rest)return flow;
    }
    if(!rest)dep[x]=0;
    return rest;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=m;i++)
        scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].w);
    sort(e+1,e+1+m,cmp);
    for(ll i=1;i<=n;i++)fa[i]=i;
    for(ll i=1;i<=m;i++){
        ll x=find(e[i].x),y=find(e[i].y);
        if(x==y)continue;
        Lim=e[i].w;fa[x]=y;
    }
    for(ll i=1;i<=m;i++)
        if(Lim>e[i].w)addl(e[i].x,e[i].y,Lim-e[i].w);
    while(bfs())ans+=dinic(1,1e18);
    printf("%lld\n",ans);
    return 0;
}
/*
3 2 5
2 1 3
1 4 4
4 5 1
3 4 2
3 5 1
*/

题目名字出自：歌曲

F-霜雪千年

我们固定 $1$ 号点为根，那么答案就是有多少个点满足它没有被冰冻并且它父节点被冰冻了（或者他是根节点）。
考虑怎么计算这样的点数，首先两个节点被冰冻的概率不是独立的，所以我们不能直接拿概率乘起来，但是我们可以统计出所有数对 $(x,y)$ 表示父节点抗寒能力为 $x$ ，子节点抗寒能力为 $y$ 时子节点产生贡献的概率。
处理出一个 $s_r=\sum_{i=1}^r \frac{a_i}{n}$ ，然后考虑计算抗寒能力分别为 $x$ 和 $y$ 的节点同时被冰冻的期望天数，设 $x\geq y$ ，那么最近的 $y$ 天都要求两个节点都被冰冻，然后再往前 $x-y$ 天要求第一个节点被冻住。
再维护一个 $t_r=\sum_{i=1}^r \frac{a_i-1}{n-1}$ ，那对于时间 $r$ ，节点 $x$ 和 $y$ 同时被冰冻的概率就是 $\frac{s_{r}\times t_r}{s_{r-x}\times t_{r-y}}$ 。
我们可以枚举一个 $x$ ，然后维护每个位置的 $\frac{s_r\times t_r}{s_{r-x}}$ ，然后对于每个 $y$ 我们是要求乘上一个位置差固定为 $y$ 的也就是 $\frac{1}{t_{r-y}}$ 然后求和。
不难发现这个可以用卷积处理，使用 $NTT$ 处理即可。
时间复杂度： $O(m^2\log m+n)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cctype>
#define file(x) freopen("snow"#x".in","r",stdin);freopen("snow"#x".out","w",stdout);
#define ll long long
using namespace std;
const ll N=1e6+10,M=1100,P=998244353;
ll n,m,L,ans,p[N],q[N],w[N];
ll r[N],x[N],y[N],f[M][M];
vector<ll> G[N];
ll read(){
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
ll power(ll x,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*x%P;
        x=x*x%P;b>>=1;
    }
    return ans;
}
void NTT(ll *f,ll n,ll op){
    for(ll i=0;i<n;i++)
        if(i<r[i])swap(f[i],f[r[i]]);
    for(ll p=2;p<=n;p<<=1){
        ll len=p>>1,tmp=power(3,(P-1)/p);
        if(op==-1)tmp=power(tmp,P-2);
        for(ll k=0;k<n;k+=p){
            ll buf=1;
            for(ll i=k;i<k+len;i++){
                ll tt=f[i+len]*buf%P;
                f[i+len]=(f[i]-tt+P)%P;
                f[i]=(f[i]+tt)%P;
                buf=buf*tmp%P;
            }
        }
    }
    if(op==-1){
        ll invn=power(n,P-2);
        for(ll i=0;i<n;i++)
            f[i]=f[i]*invn%P;
    }
    return;
}
void solve(ll d,ll *f){
    for(ll i=0;i<L;i++)x[i]=y[i]=0;
    for(ll i=d;i<=m;i++)x[i]=p[i]*power(p[i-d],P-2)%P*power(q[i],P-2)%P;
    reverse(x,x+1+m);
    for(ll i=1;i<=m;i++)y[i]=q[i];
    NTT(x,L,1);NTT(y,L,1);
    for(ll i=0;i<L;i++)x[i]=x[i]*y[i]%P;
    NTT(x,L,-1);
    for(ll i=0;i<=m;i++)f[i]=x[m+i];
    return;
}
void dfs(int x,int fa){
    for(int i=0;i<G[x].size();i++){
        int y=G[x][i];
        if(y==fa)continue;
        int A=w[x],B=w[y];
        (ans+=(f[A][0]-f[abs(A-B)][min(A,B)]))%=P;
        dfs(y,x);
    }
    return;
}
signed main()
{
    n=read();m=read();p[0]=q[0]=1;
    ll invn=power(n,P-2),invp=power(n-1,P-2);
    for(ll i=1;i<=m;i++){
        ll x=read();
        p[i]=p[i-1]*x%P*invn%P;
        q[i]=q[i-1]*x%P*invn%P;
        q[i]=q[i]*(x-1)%P*invp%P;
    }
    for(ll i=1;i<=n;i++)w[i]=read();
    L=1;while(L<=m+m)L<<=1;
    for(ll i=0;i<L;i++)r[i]=(r[i>>1]>>1)|((i&1)?(L>>1):0);
    for(ll i=0;i<=m;i++)
        solve(i,f[i]);
    for(ll i=1;i<n;i++){
        ll x,y;scanf("%lld%lld",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x); 
    }
    ans=(m-f[w[1]][0]+P)%P;
    dfs(1,0);
    printf("%lld\n",(ans+P)%P);
    return 0;
}

题目名字出自：歌曲