A.B-Suffix Array(待补)

题意：

将字符串 $s$ 的每个后缀化成 $B$ 数组，然后对 $B$ 数组进行字典序排序,求排序顺序

题解：

后缀数组还不会，学了来补，可以参考这两篇戳我~，戳我~

F.Infinite String Comparision

题意：

给定两个序列 $a$ 和 $b$ ，将两者延伸至无限长，询问两者的大小关系

题解：

第一想法是找两者长度的 $lca$ ，发现好像会爆内存。再想想可知只需要延伸至 $2*max(length(a),length(b))$ 比较即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    string a, b;
    while (cin >> a >> b)
    {
        int la = a.length(), lb = b.length();
        ll lc = 2 * max(la, lb);
        string na = "", nb = "";
        while (na.length() < lc)
            na += a;
        while (nb.length() < lc)
            nb += b;
        na = na.substr(0, lc);
        nb = nb.substr(0, lc);
        if (na < nb)
            cout << "<\n";
        else if (na == nb)
            cout << "=\n";
        else
            cout << ">\n";
    }
    return 0;
}

M.Minimum-cost Flow

题意：

给定一个 $n$ 个点和 $m$ 条边的网络，每条边有个费用 $c_i$ 。现在给出 $q$ 个询问，每个询问给出 $u_i$ 和 $v_i$ 两个整数，表示每条边的容量为 $\frac{u_{i}}{v_{i}}$ ，要求从源点到汇点需要有 $1$ 单元的流量，询问最小的费用是多少，结果表示为分数形式

题解：

很明显的最小费用流，如果知道 $cost(c,1)=cost(c*\frac{1}{c},\frac{1}{c})*c=cost(1,\frac{1}{c})*c$ 就好做了，其中 $cost(c,f)$ 表示在容量为 $c$ 中流量为 $f$ 所需的费用。那么原本建图时需要设置容量为 $\frac{u_{i}}{v_{i}}$ ,现在只需设置为 $1$ ，最终所需流量也不为 $1$ ，而是 $\frac{v_{i}}{u_{i}}$ ，当然最终答案还要再乘上 $\frac{u_{i}}{v_{i}}$ ,建完图剩下就是跑一遍最小费用流即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 55, M = 105, INF = 0x3f3f3f3f;
struct edge
{
    int y, nxt, c, w;
} e[M * 2];
int d[N], head[N], pre[N], infc[N], cross[N], s[N];
int tot, n, m, tp;
bool inq[N];
void init()
{
    tot = tp = 0;
    memset(head, -1, sizeof(head));
}

void add(int x, int y, int c, int w)
{
    e[tot] = edge{y, head[x], c, w};
    head[x] = tot++;
    e[tot] = edge{x, head[y], 0, -w};
    head[y] = tot++;
}

bool spfa()
{
    memset(d, INF, sizeof(d));
    memset(inq, 0, sizeof(inq));
    queue<int> q;
    d[1] = 0;
    infc[1] = INF;
    q.push(1);
    while (q.size())
    {
        int x = q.front();
        q.pop();
        inq[x] = 0;
        for (int i = head[x]; ~i; i = e[i].nxt)
        {
            int y = e[i].y;
            if (e[i].c && d[y] > d[x] + e[i].w)
            {
                d[y] = d[x] + e[i].w;
                infc[y] = min(infc[x], e[i].c);
                pre[y] = i;
                if (!inq[y])
                    q.push(y), inq[y] = 1;
            }
        }
    }
    return d[n] != INF;
}
void ek()
{
    int x = n;
    while (x != 1)
    {
        int i = pre[x];
        e[i].c -= infc[n];
        e[i ^ 1].c += infc[n];
        x = e[i ^ 1].y;
    }
    cross[++tp] = d[n];
    s[tp] = s[tp - 1] + d[n];
}

int main()
{
    while (scanf("%d%d", &n, &m) != EOF)
    {
        init();
        for (int i = 1; i <= m; ++i)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, 1, w);
        }
        while (spfa())
            ek();
        int q;
        scanf("%d", &q);
        while (q--)
        {
            ll u, v;
            scanf("%lld%lld", &u, &v);
            ll a = 0, b = v;
            if (tp * u < v)
                puts("NaN");
            else
            {
                a += s[v / u] * u;
                if (v % u != 0)
                    a += (v % u) * cross[v / u + 1];
                printf("%lld/%lld\n", a / __gcd(a, b), b / __gcd(a, b));
            }
        }
    }
    return 0;
}

I.1 or 2

题意：

给定一个 $n$ 个点和 $m$ 条边的图，对于每个节点给出一个 $d_i,b_I \in [1,2]$ ，表示与该结点相连的边数为多少，要求从 $m$ 条边中选取一些使得满足条件，判断是否存在满足条件的方案

题解：

赛时想了一种最大流的方案，但是给我hack掉了，赛后发现好多人都是这么过的，拉了个板子试试好像确实能过，造了组数据就给hack了。好像用带花树算法可以搞出来，下次研究下，先放个学习链接。戳我~
这题好像还是HDU3551的原题可以去参考一下这题的题解,是这题的加强版戳我~
一般图匹配题单

附上能hack掉最大流的样例

带花树

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5, M = 2e4 + 5, inf = 0x3f3f3f3f, mod = 1e9 + 7;
int d1[N], d2[N], n, m;
struct Blossom_Tree{
    vector<int>e[N];
    queue<int>q;
    int mh[N],pre[N],s[N],id[N],vis[N],n,num;
    void init(int nn){    //初始化 
        n=nn,num=0;
        for(int i=1;i<=n;i++) e[i].clear(),mh[i]=pre[i]=vis[i]=s[i]=id[i]=0;
    }
    void add(int u,int v){
        e[u].push_back(v),e[v].push_back(u);
    }
    int find(int x){ return s[x]==x?x:s[x]=find(s[x]);}
    int LCA(int x,int y){    //求LCA. 
    for(++num;;swap(x,y))
        if(x){
        if(id[x=find(x)]==num) return x;//在同一个奇环肯定能找到被编号的结点. 
        id[x]=num,x=pre[mh[x]];    //沿增广路径的非匹配边向上走直到找到祖先. 
    }
    }
    void blossom(int x,int y,int rt){    //缩点(开花)  O(n)
        while(find(x)!=rt){
            pre[x]=y,y=mh[x];
            if(vis[y]==2) vis[y]=1,q.push(y);//如果奇环上有2型结点 就变为1型结点加入队列. 
            if(find(x)==x) s[x]=rt;//只对根处理. 
            if(find(y)==y) s[y]=rt;
            x=pre[y];
        }
    }
    bool aug(int st){    //求增广路径.O(n) 
    for(int i=1;i<=n;i++) vis[i]=pre[i]=0,s[i]=i; 
    while(!q.empty()) q.pop();
    q.push(st),vis[st]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(auto v:e[u]){
            if(find(u)==find(v)||vis[v]==2) continue;//如果是已经缩点了或者是偶环直接继续，没有影响. 
            if(!vis[v]){    //如果没有被染色 
                vis[v]=2,pre[v]=u;
                if(!mh[v]){    //如果未被匹配，就进行匹配 
                    for(int x=v,last;x;x=last)    //增广路取反 
                        last=mh[pre[x]],mh[x]=pre[x],mh[pre[x]]=x;
                    return 1;
                }
                vis[mh[v]]=1,q.push(mh[v]); //否则将v的匹配结点染色，加入队列. 
            }
            else{
             int rt=LCA(u,v);    //找到LCA ,然后进行缩点. 
             blossom(u,v,rt),blossom(v,u,rt);
            }
        }
    }
    return 0;
    }
    int cal(){
        int ans=0;
        for(int i=1;i<=n;i++) if(!mh[i]&&aug(i)) ans++;    //最大匹配. 
        return ans;
    }
}DHS;
int main()
{
    while (scanf("%d%d", &n, &m)!=EOF)
    {
        int tot = 0;
        for (int i = 1, x; i <= n; i++)
        {
            scanf("%d", &x);
            if (x == 1)
                d1[i] = ++tot, d2[i] = d1[i];
            else
                d1[i] = ++tot, d2[i] = ++tot;
        }
        DHS.init(2 * m + tot);
        n = 2 * m + tot;
        for (int i = 1, u, v; i <= m; i++)
        {
            scanf("%d%d", &u, &v);
            int e1 = ++tot, e2 = ++tot;
            DHS.add(e1, e2);
            DHS.add(e1, d1[u]);
            DHS.add(e1, d2[u]);
            DHS.add(e2, d1[v]);
            DHS.add(e2, d2[v]);
        }
        puts(DHS.cal() * 2 == tot ? "Yes" : "No");
    }
    return 0;
}

附上错的最大流代码

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

typedef long long LL;
const int INF=0x3f3f3f3f;
const int MAXN = 2010,MAXM = 1200010;


namespace maxflow {
    typedef int type;
    const type INF=0x3f3f3f3f;
    struct node {
        int to; type cap; int next;
        node(int t=0,type c=0,int n=0):to(t),cap(c),next(n) {};
    } edge[MAXM];
    int head[MAXN],tot;
    void addedge(int from,int to,type cap,type rcap=0) {
        edge[tot]=node(to,cap,head[from]); head[from]=tot++;
        edge[tot]=node(from,rcap,head[to]); head[to]=tot++;
    }
    int dep[MAXN],cur[MAXN];//当前弧优化
    bool bfs(int s,int t,int n) {
        static int Q[MAXN],ST,ED;
        memset(dep+1,0,n*sizeof(int));
        ST=0; ED=-1;
        Q[++ED]=s; dep[s]=1;
        while (ST<=ED) {
            int u=Q[ST++];
            for (int i=head[u]; i!=-1; i=edge[i].next) {
                int v=edge[i].to;
                if (!dep[v]&&edge[i].cap) {
                    Q[++ED]=v; dep[v]=dep[u]+1;
                }
            }
        } return (dep[t]!=0);
    }
    type dfs(int x,const int &t,type flow=INF) {
        if (x==t||flow==0) return flow;
        type ret=0;
        for (int i=cur[x]; i!=-1; i=edge[i].next) {
            if (dep[x]+1==dep[edge[i].to]&&edge[i].cap){
                type f=dfs(edge[i].to,t,min(flow,edge[i].cap));
                edge[i].cap-=f; edge[i^1].cap+=f;
                ret+=f; flow-=f; cur[x]=i;
                if (flow==0) break;
            }
        } if (!ret) dep[x]=0;
        return ret;
    }
    type maxflow(int s,int t,int n) {//Dinic
        type ret=0;
        while (bfs(s,t,n)) {
            type f;
            memcpy(cur+1,head+1,n*sizeof(int));
            while ((f=dfs(s,t))>0) ret+=f;
        } return ret;
    }
    void init(int n) {
        memset(head+1,0xff,n*sizeof(int)); tot=0;
    }
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int s = 2*n+1,t = s+1;
        int sum = 0;
        maxflow::init(t);
        for(int i=1,d;i<=n;i++)
        {
            scanf("%d",&d);
            su***xflow::addedge(s,i,d);
            maxflow::addedge(i+n,t,d);
        }
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            maxflow::addedge(u,v+n,1);
            maxflow::addedge(v,u+n,1);
        }
        if(sum==maxflow::maxflow(s,t,t))
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

J.Easy Integration

题意：

求 $(\int_{0}^{1}(x-x^{2})^{n}dx) \% 998244353$

题解：

首先引入两个函数:

$\begin{cases} 贝塔函数： B(P,Q)=\int_{0}^{1}{x^{P-1}(1-x)^{Q-1}dx}\\ 伽马函数： \Gamma{(x)}=\int_{0}^{+\infty}{t^{x-1}e^{-t}dt}(x>0) \end{cases}$
可以发现所求即为 $B(n+1,n+1)$ ，因此根据 $B(P,Q)=\frac{\Gamma{(P)}\Gamma{(Q)}}{\Gamma{(P+Q)}}=\frac{(P-1)!+(Q-1)!}{(P+Q-1)!}$ 。
可得最终答案为 $B(n+1,n+1)=\frac{{n!}^{2}}{(2n+1)!}$
证明：
首先给出贝塔函数的一个递推公式： $B(P,Q)=\frac{Q-1}{P+Q-1}B(P,Q-1)$
因此 $B(P,Q)=\frac{Q-1}{P+Q-1}B(P,Q-1)=\frac{Q-1}{P+Q-1}*\frac{Q-2}{P+Q-2} \dots \frac{1}{P+1}B(P,1)$
又因为 $B(P,1)=\int_{0}^{1}{x^{P-1}dx}=\frac{1}{P}$
再给出伽马函数的递推公式； $\Gamma{(n)}=(n-1)!\Gamma{(1)}=(n-1)!$
所以可得 $B(P,Q)=\frac{Q-1}{P+Q-1}*\frac{Q-2}{P+Q-2} \dots \frac{1}{P+1}*\frac{1}{P}=\frac{Q-1}{P+Q-1}*\frac{Q-2}{P+Q-2} \dots \frac{1}{P+1}*\frac{1}{P}*\frac{(P-1)!}{(P-1)!}=\frac{(Q-1)!(P-1)!}{(P+Q-1)!}=\frac{\Gamma{(P)}\Gamma{(Q)}}{\Gamma{(P+Q)}}$ 得证。

这题好像还可以用oeis查到，学到了，oeis

贝塔函数
 伽马函数
 Wallis' integrals

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int maxn = 2e6 + 10;
typedef long long ll;
ll frac[maxn];
long long ksm(long long x, long long y)
{
    long long ans = 1;
    while (y)
    {
        if (y & 1)
            ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
int main()
{
    frac[0] = frac[1] = 1;
    for (int i = 2; i <= 2e6 + 5; i++)
    {
        frac[i] = frac[i - 1] * i % mod;
    }
    int n;
    while (cin >> n)
    {
        ll p = frac[n] * frac[n] % mod;
        ll q = frac[2 * n + 1];
        ll ans = p * ksm(q, mod - 2) % mod;
        cout << ans << "\n";
    }
    return 0;
}

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

A.B-Suffix Array(待补)

题意：

题解：

F.Infinite String Comparision

题意：

题解：

M.Minimum-cost Flow

题意：

题解：

I.1 or 2

题意：

题解：

J.Easy Integration

题意：

题解：

官方题解