2020牛客暑期多校训练营（第一场）题解

首先由于作者水平有限，可能只有部分的题解，且有些做法不一定标准，但是均可过题，大家见谅...

A: B-Suffix Array
这是一道结论题：首先题目是要求求一个B数组，但是这个B数组的求***有一定的问题，也就是整个字符串的B数组的一个后缀，但是它不一定满足是这个后缀的B数组，感觉可能有点绕...
然后B数组是求的和这个数最接近的pre，那么我们可以同理搞一个C数组，然后求一个与这个数最接近的suf，然后根据这个C数组做一下后缀排序，然后逆序的就是这个ans数组！
上面没有证明，这个证明可以感性理解下，感觉有一篇博客写的比较好，大概是你考虑比较Cx比Cy大，和Cx比Cy小的2种情况，然后分别发现与之对应的Bx和By的情况恰好相反，可以多举几个例子就可以发现。
同理这样的思路类似的字符串题也可以转化一下！
然后就是如果没有suf的情况，我们就设它为n，然后最后要在末尾加一个很大的数，这样保证答案的正确性...（这是一个易错点）
（另：这种做法叉姐说当且仅当字符集是2才满足条件，大家谨慎使用）
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=100005;
int n,buc[N],c[N],sa[N],rnk[N],fir[N],sec[N];char str[N];
void print(){
    for(int i=1;i<=n;i++)printf("%d%c",sa[i]," \n"[i==n]);
    for(int i=1;i<=n;i++)printf("%d%c",rnk[i]," \n"[i==n]);
}
void suffixsort(){
    for(int i=1;i<=n;i++)buc[i]=0;
    for(int i=1;i<=n;i++)buc[c[i]]++;
    for(int i=1;i<=n;i++)buc[i]+=buc[i-1];
    for(int i=n;i>=1;i--)sa[buc[c[i]]--]=i;
    rnk[sa[1]]=1;for(int i=2;i<=n;i++)rnk[sa[i]]=rnk[sa[i-1]]+(c[sa[i]]!=c[sa[i-1]]);
    //print();
    for(int k=1;k<=n;k<<=1){
        for(int i=1;i<=n;i++)fir[i]=rnk[i],sec[i]=(i+k<=n?rnk[i+k]:0);
        for(int i=1;i<=n;i++)buc[i]=0;
        for(int i=1;i<=n;i++)buc[sec[i]]++;
        for(int i=1;i<=n;i++)buc[i]+=buc[i-1];
        for(int i=n;i;i--)rnk[buc[sec[i]]--]=i;
        for(int i=1;i<=n;i++)buc[i]=0;
        for(int i=1;i<=n;i++)buc[fir[i]]++;
        for(int i=1;i<=n;i++)buc[i]+=buc[i-1];
        for(int i=n;i>=1;i--)sa[buc[fir[rnk[i]]]--]=rnk[i];
        rnk[sa[1]]=1;for(int i=2;i<=n;i++)rnk[sa[i]]=rnk[sa[i-1]]+(fir[sa[i]]!=fir[sa[i-1]]||sec[sa[i]]!=sec[sa[i-1]]);
        //printf("k:%d\n",k);print();
    }
}
int main(){
    while(scanf("%d",&n)!=EOF){
        scanf("%s",str+1);
        for(int i=1;i<=n;i++){
            c[i]=0;
            for(int j=i+1;j<=n;j++)if(str[j]==str[i]){c[i]=j-i;break;}
            if(!c[i])c[i]=n;
        }
        n++;c[n]=n;suffixsort();
        for(int i=n-1;i>=1;i--)printf("%d%c",sa[i]," \n"[i==1]);
    }
    return 0;
}

F:Infinite String Comparision
这场的签到题，感觉没有什么好说的吧，就是大概我们长度为x和y，比较到x+y就可以了，其实是x+y-gcd(x,y)但是我也不是很会证明，考试的时候可以举一个100000和99999的极限例子就可以发现这个规律
作者在比赛的时候为了保险比到了3*max(x,y)，这也是一种不错的考场做法...
代码这里可以有很多写法，实现起来很简单，就不给了/xk
H：Minimum-cost Flow
这题考察了一些有关于网络流的流量一些变形和转化
首先是我们可以发现这里的流量和费油可以同时乘上一个常数c，然后最后计算的时候我们只需要把它再除回来就可以了！
然后我们可以搞一个1作为稳定的流量，针对不同的流量我们只需要除一个常数1/c即可！
注意，这个ans函数在坐标系里是凸函数，因此我们增广的时候用一个vector<int>span，记录一下增广的过程的费用，然后我们只需要在询问的时候遍历这个vector然后卡到最优即可，由于图的大小较小，所以这个vector的大小不会很大，我们就O(size)完成了一次查询！
注意一种NaN的情况，就是无论如何都增广不到指定ans的一种可能，要特判一下！
代码：</int>

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=105,M=205,Inf=2e9;
int n,m,q,fst[N],tote,s,t,dis[N],mn[N],pre[N],from[N];bool inq[N];LL flow,cost;
struct Edge{int to,f,w,nxt;}e[M];
vector<LL>span;
inline void adde(int u,int v,int f,int w){
    e[++tote]=(Edge){v,f,w,fst[u]};fst[u]=tote;
    e[++tote]=(Edge){u,0,-w,fst[v]};fst[v]=tote;
}
inline bool EK(){
    queue<int>que;while(!que.empty())que.pop();
    for(int i=1;i<=n;i++)dis[i]=Inf,inq[i]=false;
    que.push(s),inq[s]=true,dis[s]=0,mn[s]=Inf;
    while(!que.empty()){
        int u=que.front();que.pop();inq[u]=false;
        for(int i=fst[u];i!=-1;i=e[i].nxt){
            int v=e[i].to,f=e[i].f,w=e[i].w;
            if(f>0&&dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;mn[v]=min(mn[u],f);pre[v]=i;from[v]=u;
                if(!inq[v])inq[v]=true,que.push(v);
            }
        }
    }
    return dis[t]<Inf;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=1;i<=n;i++)fst[i]=-1;tote=1;
        s=1;t=n;flow=cost=0;span.clear();
        for(int i=1,u,v,w;i<=m;i++)scanf("%d%d%d",&u,&v,&w),adde(u,v,1,w);
        while(EK()){
            for(int i=t;i!=s;i=from[i])e[pre[i]].f-=mn[t],e[pre[i]^1].f+=mn[t];
            flow+=(LL)mn[t];cost+=(LL)dis[t]*mn[t];span.pb(dis[t]);
        }
        scanf("%d",&q);
        while(q--){
            LL u,v;scanf("%lld%lld",&u,&v);//u/v*v/u
            if(flow*u<v)puts("NaN");
            else{
                LL ff=v,cc=u,ans=0;
                for(auto x:span)if(ff>=u)ff-=u,ans+=u*x;else{ans+=ff*x;break;}
                LL g=__gcd(ans,v);printf("%lld/%lld\n",ans/g,v/g); 
            }
        }
    }
    return 0;
}

I：1 or 2
这题的正解好像是什么带花树，很神仙，作者不会
于是这里有两种优秀的做法，时间在目前配置的较水的数据比标算快
1 随机化，也就是叉姐说的概率算法，可以每次考虑还不满足条件的情况，然后用一个vector记录一个点的边的编号和另外一个点，然后我们把不满足条件的一一调整，这里可能是一种比较奇怪的随机化，类似于相对于一个模板我们不断类似于退火的思想慢慢靠近，然后最后判断是否满足条件，中间到底是先调整哪边我们要用随机的思想，这样可以较好的利用最优性的概率，然后达到算法的稳定性！
2 dfs爆搜，这个算法需要改变一下搜索的方式，然后我们加一些剪枝就可以通过，比较玄学！可以见代码：

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=105;
int n,m,d[N],id[N];bool usd[N];vector<pii>e[N];
bool dfs(int dep){
    if(dep>n)return true;
    int u=id[dep];
    if(!d[u])return dfs(dep+1);
    for(auto edg:e[u]){
        int v=edg.first,num=edg.second;
        if(!d[v]||usd[num])continue;
        d[u]--,d[v]--,usd[num]=true;
        if(dfs(dep))return true;
        d[u]++,d[v]++,usd[num]=false;
    }
    return false;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=1;i<=n;i++)scanf("%d",&d[i]),id[i]=i,e[i].clear();
        for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),e[u].pb(pii(v,i)),e[v].pb(pii(u,i)),usd[i]=false;
        sort(id+1,id+n+1,[&](int u,int v){return e[u].size()<e[v].size();});
        puts(dfs(1)?"Yes":"No");
    }
    return 0;
}

J：Easy Integration
积分题，作者不太会证明，考试的时候降智了，没写出来...
后来可以通过分子和分母找规律，可以得到结论：
(n!)^2/(2n+1)！
这里有一个好办法，就是通过模数和分数给出在模数下取模的形式，即ans，得到分子和分母（dreamoon神仙以前出的一道题）
给出这个找分子和分母的程序（网上的代码，不是作者写的，这里借鉴一下）
找分数的代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
void f(ll a, ll b, ll c, ll d, ll& x, ll& y){
    ll q = a / b + 1;
    if (q <= c / d){
        x = q;
        y = 1;
        return;
    }
    q--;
    a -= q * b; c -= q * d;
    f(d, c, b, a, y, x);
    x += q * y;
    return;
}
int main(){
    int t;
    scanf("%d", &t);
    while (t--){
        ll b, y, a, p, x;
        scanf("%lld%lld", &p, &x);
        f(p, x, p, x - 1, b, y);
        a = b * x - y * p;
        printf("%lld/%lld\n", a, b);
    }
    return 0;
}

作者本题的代码就不给了，很好实现一个快速幂和逆元就可以完事了...见谅