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

比赛地址：

https://ac.nowcoder.com/acm/contest/5666

补题开始了，一题题慢慢补吧，顺序由简到难，尽量将能补的题都补了，这篇长久更新。

F Infinite String Comparision

题目地址：

https://ac.nowcoder.com/acm/contest/5666/F

基本思路：

这题很明显不会比较很多次，所以我们我们可以猜一下结论，我们直接尝试将字符串循环比较 $sz(a) + sz(b)$ 次就行了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

string s1,s2;
int solve(){
  int k1 = s1.size(),k2 = s2.size();
  int p1 = 0,p2 = 0;
  for(int i = 0 ; i < k1 + k2 + 1; i++){
    if(s1[p1] > s2[p2]) return 1;
    else if(s1[p1] < s2[p2]) return -1;
    p1 = (p1 + 1) % k1,p2 = (p2 + 1) % k2;
  }
  return 0;
}
signed main() {
  IO;
  while (cin >> s1 >> s2){
    int tmp = solve();
    if(tmp == 1) cout << '>' << '\n';
    else if(tmp == -1) cout << '<' << '\n';
    else cout << '=' << '\n';
  }
  return 0;
}

J Easy Integration

题目地址：

https://ac.nowcoder.com/acm/contest/5666/J

基本思路：

这题正常做法应该是求个积分，但我数学不太好，不太愿算了，提供一下比赛时的非常规做法~~网络赛现状~~ 。
我们可以用一些计算软件或者高级计算器，算出前几项的结果，然后我们去 $oeis$ 就能找到公式 $ans = \frac{(n!)^{2}}{(2n + 1)!}$
预处理一下阶乘求个逆元就能计算答案了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int mod = 998244353;
int qpow(int a, int b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = 1ll * res * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return res;
}
const int maxn = 2000020;
int n,fac[maxn];
signed main() {
  IO;
  fac[1] = 1;
  for (int i = 2; i <= 2000010; i++) fac[i] = fac[i - 1] * i % mod;
  while (cin >> n) {
    int t1 = fac[2 * n + 1] % mod;
    int t2 = fac[n] % mod * fac[n] % mod;
    int p = t1 * qpow(t2,mod - 2) % mod;
    int ans = 1ll * qpow(p,mod - 2);
    cout << ans << '\n';
  }
  return 0;
}

I 1 or 2

题目地址：

https://ac.nowcoder.com/acm/contest/5666/I

基本思路：

比较容易看出应该是个网络流匹配，但是难点在于如何构图。
我们将每个点按度拆点，同时再将边拆成两个点，将边对应的点与这个点拆出的每个度点相连,具体构图参照如下：
例如样例的第三个输入 $n = 3$ 度分别为 $1,1,2$ 边为 $1-3,2-3$ ，那么构图如下:
图片说明
那么构图之后我们再求最大匹配(完美匹配一定是最大匹配)，如果最大匹配是完美匹配，就证明每条边的两头都匹配了一个点的一个度，并且没有未匹配到的度，那么就是符合要求的。
然后就是带花树求一般图的最大匹配的模板就是了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

struct edge {
    int u, v;
}e[2005];
int n,m;

/****************带花树求一般图最大匹配算法*****************/
int match[1005],newbase;
int inqueue[1005],inpath[1005],G[1005][1005],inblossom[1005],father[1005];
int du[1005],c[500005],base[1005],start,finish,head,tail;
int lca(int u,int v) {
  memset(inpath, 0, sizeof inpath);
  while (true) {
    u = base[u];
    inpath[u] = 1;
    if (!match[u]) break;
    u = father[match[u]];
  }
  while (true) {
    v = base[v];
    if (inpath[v]) break;
    v = father[match[v]];
  }
  return v;
}
void reset(int u) {
  while (u != newbase) {
    int v = match[u];
    inblossom[base[v]] = inblossom[base[u]] = 1;
    u = father[v];
    if (base[u] != newbase) father[u] = v;
  }
}
void blossomcontract(int u,int v) {
  newbase = lca(u, v);
  memset(inblossom, 0, sizeof inblossom);
  reset(u);
  reset(v);
  if (base[u] != newbase) father[u] = v;
  if (base[v] != newbase) father[v] = u;
  for (int i = 1; i <= n; i++)
    if (inblossom[base[i]]) {
      base[i] = newbase;
      if (!inqueue[i]) c[++tail] = i, inqueue[i] = 1;
    }
}
void findaugmentingpath() {
  memset(inqueue, 0, sizeof inqueue);
  memset(father, 0, sizeof father);
  for (int i = 1; i <= n; i++) base[i] = i;
  head = 1;
  tail = 1;
  c[1] = start;
  inqueue[start] = 1;
  finish = 0;
  while (head <= tail) {
    int u = c[head++];
    for (int v = 1; v <= n; v++)
      if (G[u][v] && base[u] != base[v] && match[v] != u) {
        if (v == start || (match[v] > 0) && (father[match[v]] > 0)) {
          blossomcontract(u, v);
        } else if (father[v] == 0) {
          father[v] = u;
          if (match[v]) {
            c[++tail] = match[v];
            inqueue[match[v]] = 1;
          } else {
            finish = v;
            return;
          }
        }
      }
  }
}
void augmentpath() {
  int u, v, w;
  u = finish;
  while (u > 0) {
    v = father[u];
    w = match[v];
    match[u] = v;
    match[v] = u;
    u = w;
  }
}
bool solve() {
  int res = 0;
  memset(match, 0, sizeof match);
  for (int i = 1; i <= n; i++)
    if (!match[i]) {
      start = i;
      findaugmentingpath();
      if (finish) augmentpath(), res++;
    }
  for (int i = 1; i <= n; i++)
    if (!match[i]) return false;
  return true;
}
/***********************************************************/

vector<int> memo[110];
void build() { // 建图;
  int cnt = 0;
  memset(G, 0, sizeof G);
  for(int i = 0 ; i <= n ; i++) memo[i].clear();
  rep(i, 1, n) {
    rep(j, 1, du[i]) memo[i].push_back(++cnt);
  }
  rep(i, 1, m) {
    int t1 = ++cnt;
    for (auto it : memo[e[i].u]) G[t1][it] = G[it][t1] = 1;
    int t2 = ++cnt;
    for (auto it : memo[e[i].v]) G[t2][it] = G[it][t2] = 1;
    G[t1][t2] = G[t2][t1] = 1;
  }
  n = cnt;
}
signed main() {
  while (cin >> n >> m) {
    for (int i = 1; i <= n; i++) du[i] = read();
    for (int i = 1; i <= m; i++) {
      e[i].u = read();
      e[i].v = read();
    }
    build();
    if (solve()) {
      puts("Yes");
    } else {
      puts("No");
    }
  }
  return 0;
}