计蒜课八月模拟赛题解

看见机房有大佬上周写了上面的普及信心赛于是我康了康 8月的提高组模拟赛 9月的还没开始qwq

真的有点难主要是我先打开了T2 我再次对自己的数学产生了怀疑我现在还是不会写T2

T1 又又又又都错题了下次重建图尽量写vector 都写邻接表变量差不多的容易搞混我这个同学变又写错了

T1 ：https://nanti.jisuanke.com/t/41086

题目大意就是一个有向图删一个点把与他直接和间接相连的点删掉然后求删掉所有点的最小最大代价；

为了避免这个环的情况我们显然是先 tarjan 求一下强连通分量然后考虑缩点显然是删掉这个强连通分量的任意一个点这个强连通分量都会被删掉

但是题目要求我们求出最大最小代价那我们在求tarjan的过程中维护每一个块的最大最小代价

那么对于最小代价显然是缩点之后入度为0的节点的代价的累和

对于最大代价我们反向建图从叶子结点往上便利然后每一个连通块的最大代价累和即可

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
template<typename T>inline void read(T &x) {
    x=0;T f=1,ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    if(ch=='-') f=-1, ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    x*=f;
}
const int N=250000;
int n,m,x,y,cnt=0,ans1,ans2,num,tot,tc,top;
int in1[N],in2[N],Stack[N],minn[N],cost[N],maxx[N],dfn[N],low[N],lin[N],linc[N],ins[N],belong[N];
struct gg {
    int y,next;
}a[N],e[N];
inline void add(int x,int y) {
    a[++tot].y=y;
    a[tot].next=lin[x];
    lin[x]=tot;
}
inline void add_c2(int x,int y) {
    e[++tc].y=y;
    e[tc].next=linc[x];
    linc[x]=tc;
}
inline void tarjan(int x) {
    dfn[x]=low[x]=++num;
    Stack[++top]=x; ins[x]=1;
    for(int i=lin[x];i;i=a[i].next) {
        int y=a[i].y;
        if(!dfn[y]) {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(ins[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]) {
        ++cnt;
        int k;
        do {
            k=Stack[top--];
            ins[k]=0;
            belong[k]=cnt;
            minn[cnt]=min(minn[cnt],cost[k]);
            maxx[cnt]=max(maxx[cnt],cost[k]);
        }while(x!=k);
    }
}
inline void topsort() {
    queue<int>q;
    for(int i=1;i<=cnt;i++) if(!in2[i]) q.push(i);
    while(q.size()) {
        int x=q.front();ans2+=maxx[x]; q.pop();
        for(int i=linc[x];i;i=e[i].next) {
            int y=e[i].y;
            in2[y]--;
            if(!in2[y]) q.push(y);
        }
    }
}
int main() {
    //freopen("1.in.cpp","r",stdin);
    read(n); read(m);
    for(int i=1;i<=n;i++) read(cost[i]),minn[i]=inf,maxx[i]=-inf;
    for(int i=1;i<=m;i++) {
        read(x); read(y);
        add(x,y);
    }
    for(int i=1;i<=n;i++) {
        if(!dfn[i]) tarjan(i);
    }
    for(int i=1;i<=n;i++) {
        //cout<<maxx[i]<<endl;
        for(int j=lin[i];j;j=a[j].next) {
            int y=a[j].y;
            if(belong[i]!=belong[y]) {
                //add_c(belong[i],belong[y]);没必要建图了; 
                add_c2(belong[y],belong[i]);
                in1[belong[y]]++;
                in2[belong[i]]++;
            }
        }
    }
    ans1=ans2=0;
    for(int i=1;i<=cnt;i++)
        if(!in1[i]) ans1+=minn[i];
    topsort();
    printf("%d %d\n",ans1,ans2);
    return 0;
}

T2 恶心数学题？？？原来只做过一个简化版的qwq 模拟赛当时考了然后暴毙了；

那个模拟赛我也没有写题解那我在这里总结一下好吧题目大意：

从（0,0）这个点不跨过 y=x 和 y=x-(n-m）到达（n,m）的方案数保证 n>=2m

显然需要用不考虑跨过任何一条直线的方案数-跨过某一条直线的方案数*2+跨过两条的方案数；

这种题目的一般思路显然是总的方案数 $\tbinom{n+m}{m}$

然后考虑跨过某一条直线的方案数 $\tbinom{n+m}{m-1}$

因为题目保证n>=2m 所以跨过第二条直线的时候就没有机会跨过第一个了qwq 所以一定是先跨过第一条线在跨过第二条线

用和卡特兰数类似的方法也能求出来方案数 $\tbinom{n+m}{m}$-$\tbinom{n+m}{m-1}$*2+$\tbinom{n+m}{m-2}$

这个T2 就比较恶心了目标就是求从 (0,0)走到 (n,m) 且不经过 y=x+a 和 y=x+b 这两条的方案数，模数为 998244353 。

考虑怎么做呢其实我的思路也是在不断订正的我第一遍看到不会写只会分类讨论但是刘神指导说应该是有通解的

那么我们不妨一点一点思考讨论一下这种组合数求解这种问题的方法

如果给定（n，m）和一个点 p（a，b）只能往右往上走求出不经过这个点p 到达终点的方案数；

那么我们也是用所有的方案数减去经过 p的方案数

总的方案数 $\tbinom{n+m}{m}$ 然后考虑一定经过p的方案数那么我们先从（0，0）走到（a，b）的方案数

的方

计蒜课 八月模拟赛题解

计蒜课八月模拟赛题解