牛客练习赛101题解

A-千层蛋糕

显然第一个是最大值第二个是最小值然后剩下的都不用管了。
时间复杂度:

#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-荒神在此

考虑到 的选择可以改变序列的奇偶性,所以无论后面的如何选择都可以通过调整 来变成奇数。
所以答案就是
时间复杂度:

#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-推理小丑

考虑从高位往低位贪心,考虑第 位是否必须填 。我们先默认 位填 ,再从大到小枚举一个 ,此时因为我们如果第 位可以为 就必须填 ,这样一定是对的,因为每个能够填上去的 都可以去分割序列中的一些段(也就是固定一些位置的 )。
这样最后看是否能找到一个合法的解就可以确定第 位是否必须填 了。
时间复杂度:

#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-罪业之都

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

#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-水没都市

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

#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-霜雪千年

我们固定 号点为根,那么答案就是有多少个点满足它没有被冰冻并且它父节点被冰冻了(或者他是根节点)。
考虑怎么计算这样的点数,首先两个节点被冰冻的概率不是独立的,所以我们不能直接拿概率乘起来,但是我们可以统计出所有数对 表示父节点抗寒能力为 ,子节点抗寒能力为 时子节点产生贡献的概率。
处理出一个 ,然后考虑计算抗寒能力分别为 的节点同时被冰冻的期望天数,设 ,那么最近的 天都要求两个节点都被冰冻,然后再往前 天要求第一个节点被冻住。
再维护一个 ,那对于时间 ,节点 同时被冰冻的概率就是
我们可以枚举一个 ,然后维护每个位置的 ,然后对于每个 我们是要求乘上一个位置差固定为 的也就是 然后求和。
不难发现这个可以用卷积处理,使用 处理即可。
时间复杂度:

#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;
}

题目名字出自:歌曲

全部评论
c题数据太水了吧 5 1111 2222 3333 4444 55555 这个样例,有人答案是2312,有4385,还有6145的
3 回复
分享
发布于 2022-06-24 22:11
如果有人要hack C题标程的话可以私聊我,我目前还没有找到标程的错误。 标程我稍后会在题解处贴出。 十分感谢!
1 回复
分享
发布于 2022-06-25 07:38
快手
校招火热招聘中
官网直投
C题我做的思路应该就是这样的,高位到低位,判断每位是否可以为0,只能过91%。不知道哪里问题,理解上不理解题还是白做的
点赞 回复
分享
发布于 2022-06-25 00:36
请问一下,F题的f(i,j)是代表的什么意思啊?
点赞 回复
分享
发布于 2022-07-14 01:52
偷偷问一句奖品怎么发😕
点赞 回复
分享
发布于 2022-06-25 22:03

相关推荐

头像
昨天 09:09
Java
点赞 评论 收藏
转发
14 收藏 评论
分享
牛客网
牛客企业服务