牛客练习赛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; }
题目名字出自:歌曲