牛客训练赛1补题记录

牛客给的题解真的敷衍

J: Easy Integration 分部积分

题意：对于$1\le n \le 10^6$，求$\int_{0}^{1}(x-x^2)^n \mathrm{d}x$

2种方法：

1. 分部积分法

   $$\begin{aligned} \int_{0}^{1}(x-x^2)^n \mathrm{d}x &= \int_{0}^{1}x^n(1-x)^n \mathrm{d}x\\ &=\frac{1}{n+1} \int_{0}^{1}(1-x)^n \mathrm{d}x^{n+1} \quad \text{分部积分}\\ &=\frac{1}{n+1}[0+n\int_{0}^{1}x^{n+1}(1-x)^{n-1}] \mathrm{d}x \quad \text{继续分部积分}\\ &=\frac{n(n-1)}{(n+1)(n+2)} \int_{0}^{1} x^{n+2}(1-x)^{n-2} \mathrm{d}x\\ &=\text{多次分部积分} \cdots \\ &=\frac{n!}{(n+1)(n+2)\cdots(n+n)}\int_{0}^{1}x^{2n}(1-x)^0 \mathrm{d}x\\ &=\frac{(n!)^2}{(2n+1)!} \end{aligned}$$

2. 公式

   贝塔函数（第一类欧拉积分）:

   $$B(x,y)=\int_{0}^{1} t^{x-1}(1-t)^{y-1}\mathrm{d}t$$

   当x,y是正整数的时候，我们可以从伽马函数定义得到如下式子：

   $$B(x,y)=\frac{(x-1)!(y-1)!}{(x+y-1)!}$$

AC代码

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define redirect_input freopen("./input.txt", "r", stdin);
#define redirect_output freopen("./output.txt", "w", stdout);
#define debug(s, r) std::cerr << #s << ": " << (s) << (r == 0 ? ' ' : '\n')
#define pii pair<int, int>
#define sqr(x) ((x) * (x))
using namespace std;

const int maxn = 1e6 + 1000;
const ll mod = 998244353;

ll qpow(ll base, ll t){
    ll res = 1;
    while(t){
        if(t & 1) res = base * res % mod;
        base = base * base % mod;
        t >>= 1;
    }
    return res;
}

ll factor[maxn * 2], inv_fac[maxn * 2];

void init(){
    factor[1] = 1;
    for(int i=2; i < maxn * 2; i++){
        factor[i] = factor[i-1] * i % mod;
    }
    inv_fac[maxn * 2 - 1] = qpow(factor[maxn * 2 - 1], mod - 2);
    for(int i = maxn * 2 - 2; i > 1; i--){
        inv_fac[i] = inv_fac[i+1] * (i + 1) % mod;
    }
}

void solve() {
    init();
    ll n;
    while(cin >> n){
        cout << (sqr(factor[n]) % mod * inv_fac[n * 2 + 1]) % mod << '\n'; 
    }
}

signed main() {
    Android;
    solve();
}

H: Minimum-cost Flow 最小费用流 思维

题意：

给定一个$n$个点$m$条边的图，第$i$条边的费用为$c_i$。$q$次询问每次给出$u$和$v$，代表每条边的容量都为$u/v$，求流量为$1$时的最小费用。

做法：

由于询问次数过多，不可能每个询问都跑一遍最小费用流。

设$c(x, y)$代表网络中每条边的容量都为$x$，总流量为$y$时的最小费用，可以得到以下式子。

$$c(\frac{u}{v}, 1)=c(u,v)\times \frac{1}{v}=c(1, \frac{v}{u})\times \frac{u}{v}$$

---

考虑只跑一次最小费用流，得到c(1, \text{max_flow})，在跑最小费用流的过程中，我们把每次增广的费用记录下来（AC代码中的map<ll,ll> extension）。

在查询时，分情况讨论

• 如果\text{max_flow}<\frac{v}{u}，无解。
• 否则，按费用从小到大遍历增广路。设该增广路的容量为$cap$，费用为$c$，剩余未跑的流量为$\frac{r}{u}$（初始时$r=v$）：
  • 若$cap<\frac{r}{u}$，则该增广路被完全占用，则总费用$cost$增加$\frac{u}{v}\times cap\times c$，同时$r'=r-cap\times u$，继续遍历
  • 否则，该增广路并未完全占用，费用$cost$增加$\frac{u}{v}\times\frac{r}{u}\times c=\frac{rc}{v}$，同时$r'=0$，退出遍历

可见在这个过程中，分母永远是$v$，因此运算过程中可以忽略。

最后对分子分母化简即可。

AC代码:

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define redirect_input freopen("./input.txt", "r", stdin);
#define redirect_output freopen("./output.txt", "w", stdout);
#define debug(s, r) std::cerr << #s << ": " << (s) << (r == 0 ? ' ' : '\n')
#define pii pair<int, int>
#define sqr(x) ((x) * (x))
using namespace std;

struct Dinic{
    const static ll inf = 0x7f7f7f7f7f7f7f7f;
    const static int mx_edge = 150, mx_node = 70;
    int head[mx_node], edge_cnt, n;
    int cur[mx_node], que[mx_node], q_head, q_tail;
    bool in_queue[mx_node], vis[mx_node], extend_success;
    ll dist[mx_node], mx_flow;

    map<ll, ll> extension; 

    struct E{
        int v, nxt;
        ll cap, cost;
    } edge[2 * mx_edge];

    void init(int nx){
        n = nx, edge_cnt = 0;
        for(int i=0; i<=n; i++) head[i] = -1;
        extension.clear();
    }

    void add_edge(int u, int v, ll cap, ll cost){
        edge[edge_cnt] = {v, head[u], cap, cost};
        head[u] = edge_cnt++;
        edge[edge_cnt] = {u, head[v], 0, -cost};
        head[v] = edge_cnt++;
    }

    bool spfa(int s, int t){
        for(int i=0; i<=n; i++) dist[i] = inf;
        q_head = q_tail = 0; que[q_tail++] = s;
        in_queue[s] = 1, dist[s] = 0;

        while(q_tail ^ q_head){
            int now = que[q_head++];
            q_head %= mx_node;
            in_queue[now] = false;
            for(int i=head[now], v; ~i; i=edge[i].nxt){
                if(edge[i].cap <= 0) continue;
                
                v = edge[i].v;
                if(dist[v] > dist[now] + edge[i].cost){
                    dist[v] = dist[now] + edge[i].cost;
                    if(!in_queue[v]){
                        in_queue[v] = true;
                        que[q_tail++] = v;
                        q_tail %= mx_node;
                    }
                }
            }
        }
        return dist[t] != inf;
    }

    ll dfs(int u, int t, ll lim){
        vis[u] = true;
        if(u == t){
            extend_success = true;
            mx_flow += lim;
            extension[dist[u]] += lim;
            return lim;
        }

        ll ret = 0, tmp;
        for(int & i=cur[u], v; ~i; i=edge[i].nxt){
            v = edge[i].v;
            if(dist[u] + edge[i].cost == dist[v] &&
               edge[i].cap > 0 &&
               (!vis[v] || v == t)){
                   tmp = dfs(v, t, min(lim-ret, edge[i].cap));
                   if(tmp > 0){
                       ret += tmp;
                       edge[i].cap -= tmp;
                       edge[i ^ 1].cap += tmp;
                       if(ret >= lim) break;
                   }
               }
        }

        return ret;
    }

    ll dinic(int s, int t){
        for(int i=0; i<=n; i++) in_queue[i] = false;
        mx_flow = 0;
        while(spfa(s, t)){
            for(int i=0; i<=n; i++) vis[i] = false;
            for(int i=0; i<=n; i++) cur[i] = head[i];
            do{
                extend_success = false;
                dfs(s, t, inf);
            }while(extend_success);
        }
        return mx_flow;
    }
}dinic;

void solve(int n, int m) {
    dinic.init(n);
    for(int i=0, u, v, c; i<m; i++){
        cin >> u >> v >> c;
        dinic.add_edge(u, v, 1, c);
    }
    ll mx_flow = dinic.dinic(1, n);

    int q; cin >> q;

    while(q--){
        ll u, v, r, numer = 0; // numer: numerator
        cin >> u >> v;
        if(mx_flow * u < v){
            cout << "NaN\n";
            continue;
        }

        r = v; // r: remaining
        for(pair<ll, ll> ext:dinic.extension){
            ll cost = ext.first, cap = ext.second;
            if(cap * u <= r){
                numer += cap * cost * u;
                r -= u * cap;
            }else{
                numer += r * cost;
                r = 0;
            }
            if(r <= 0) break;
        }
        ll g = __gcd(numer, v);
        cout << (numer / g) << "/" << (v / g) << '\n';
    }

}

signed main() {
    Android;
    int n, m;
    while(cin >> n >> m) solve(n, m);
}

F: Infinite String Comparision

题意：给你两个串$a,b$，比较$S_a=a^{\infty}$与$S_b=b^{\infty}$的字典序大小。

思路很简单，但原理并不简单。

解法：比较$a+b$与$b+a$的字典序大小即可。

import sys
class IoTool:
    DEBUG = 0
    def _reader_dbg():
        with open('./input.txt', 'r') as f:
            lines = f.readlines()
        return iter(lines)
    reader = _reader_dbg() if DEBUG else iter(sys.stdin.read().split('\n'))

input = lambda :next(IoTool.reader)

info = list(IoTool.reader)
for i in range(len(info) // 2):
    a = info[i * 2].strip()
    b = info[i * 2 + 1].strip()
    apb = a + b
    bpa = b + a
    if apb < bpa:
        print('<')
    elif apb == bpa:
        print('=')
    else:
        print('>')

原理与证明：

这题的重点在于判断两串是否相等。

根据Weak Periodicity Lemma，可以知道如果两个串的生成串$S_a=S_b=S$，即$a,b$均为$s$的循环节，那么$gcd(\mid a\mid,\mid b\mid)$也是$S$的周期。

那么可以将串$a,b$分别划分为多个块，每个块的长度为$gcd(\mid a\mid,\mid b\mid)$。设串$a$被分为$x$个块，串$b$被分为$y$个块。显然，$gcd(x,y)=1$。

现在问题变为：最少比较多少次，才能保证这$x+y$个块之间两两相同呢？显然次数的下界为$x+y-1$。

也就是说，对于串$a,b$的生成串，我们最少只需要比较 $gcd(a,b) * (x+y-1)=\mid a\mid + \mid b\mid - gcd(a,b)$ 个字符即可确定两串的生成串是否相同。

设串$a$的生成串中，第$i$个块为$A_i$；$B_i$同理。我们顺序判断 $A_i=B_i\quad i\in\{1,2,3,\cdots,x+y-1\}$，当$A_i\ne B_i$时，判断对应块的字典序大小即可。由于$x,y$互质，该方法能够保证串$a,b$中的$x+y$个块两两相同（反证法可得）。

I: 1 or 2 一般图最大匹配(带花树)