2022牛客多校（十）

2022牛客多校（十） 一、比赛小结

比赛链接："蔚来杯"2022牛客暑期多校训练营10

二、题目分析及解法（基础题） F、Shannon Switching Game?

题目链接：F-Shannon Switching Game?

题意：

给定一个无向图，初始时有一个token在s点，两个玩家Join Player和Cut Player轮流行动，Cut Player先动。Cut Player每次可以移除一条和token所在位置相邻的边, Join Player每次可以将token沿着一条未删除边移动, 如果token在某刻被移动到t则Join Player获胜，否则Cut Player获胜，求双方最优策略下的胜者。

题解：

• 我们可以求出在双方最优策略下使得Join Player可以将token移动到t的所有token起点集合,把这个集合叫做good set

• 首先,t点一定是在good set中的，我们从t开始逐步构建good set。某个不在good set中的顶点v如果有至少两条边连向good set中的某个顶点，那么从该点出发的话，由于Cut Player在一次 *** 作中只能切断其中的一条边，那么Join Player一定可以在一次 *** 作后将token移动到good set中的某个顶点，因此此时v也在good set中。

• 如果在某一时刻，任何不在good set中的顶点都只有至多一条边连向good set中的某个顶点,那么从不在good set中的任一顶点出发，Cut Player只需要每次切断可能连向good set的边即可,那么此时不在goodset中的顶点一定都不能到达t点。

• 构建可以通过维护一个队列来实现，时间复杂度为O(n+m),其中n是顶点个数,m是边数 。

代码：

#include 
using namespace std;
int T, n, m, s, t;
const int maxn = 1e2 + 5;
int g[maxn][maxn], num[maxn];
bool vis[maxn];
bool bfs() {
  queue<int> q;
  q.push(t);
  vis[t] = 1;
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = 1; i <= n; i++) {
      if (vis[i]) continue;
      num[i] += g[u][i];
      if (num[i] > 1) {
        q.push(i);
        vis[i] = 1;
      }
    }
  }
  return num[s] > 1;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> T;
  while (T--) {
    memset(vis, 0, sizeof vis);
    memset(g, 0, sizeof g);
    memset(num, 0, sizeof num);
    cin >> n >> m >> s >> t;
    while (m--) {
      int u, v;
      cin >> u >> v;
      g[u][v]++;
      g[v][u]++;
    }
    cout << (bfs() ? "Join Player" : "Cut Player") << endl;
  }
  return 0;
}

H、Wheel of Fortune

题目链接：H-Wheel of Fortune

题意：

炉石传说，一方转动了尤格萨隆的命运之轮触发了炎爆选项，双方英雄的血量分别为 A A A 和 B B B ，双方场面的血量分别为 { a i ∣ 1 ≤ i ≤ 7 } \{a_i|1\leq i \leq 7\} {ai​∣1≤i≤7} 和 { b i ∣ 1 ≤ i ≤ 7 } \{b_i|1\leq i \leq 7\} {bi​∣1≤i≤7} ，问 A A A 获胜的概率，答案对 998244353 998244353 998244353 取模

题解：

答案其实和怪的血量是无关的，令 x = ⌈ A 10 ⌉ , y = ⌈ B 10 ⌉ x=\lceil \frac{A}{10} \rceil , y = \lceil \frac{B}{10} \rceil x=⌈10A​⌉,y=⌈10B​⌉ ，则答案为 ∑ i = 0 x − 1 ( i + y − 1 i ) ⋅ 2 − ( y + i ) \displaystyle \sum_{i=0}^{x-1} {i+y-1 \choose i} \cdot 2^{-(y+i)} i=0∑x−1​(ii+y−1​)⋅2−(y+i)

代码：

#include 
using namespace std;
typedef long long ll;
const int maxn = 2e7 + 5;
const int mod = 998244353;
ll A, B, a, b, x, res;
ll fact[maxn];
ll qpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n) {
    if (n & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    n >>= 1;
  }
  return res;
}
ll inv(ll a, ll p) { return qpow(a, p - 2, p); }
ll C(ll b, ll a) {
  return fact[a] * inv(fact[b], mod) % mod * inv(fact[a - b], mod) % mod;
}
void init() {
  fact[0] = 1;
  for (int i = 1; i < maxn; i++) {
    fact[i] = fact[i - 1] * i % mod;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  init();
  cin >> A;
  for (int i = 1; i <= 7; i++) cin >> x;
  cin >> B;
  for (int i = 1; i <= 7; i++) cin >> x;
  a = ceil(1.0 * A / 10), b = ceil(1.0 * B / 10);
  for (int i = b; i <= b + a - 1; i++)
    res = (res + C(b - 1, i - 1) * inv(qpow(2, i, mod), mod) % mod) % mod;
  cout << res << endl;
  return 0;
}

I、Yet Another FFT Problem?

题目链接：I-Yet Another FFT Problem?

题意：

给定两个序列 A = { a i } , B = { b i } A=\{a_i\}, B=\{b_i\} A={ai​},B={bi​} ，是否存在 i , j , k , l i, j, k, l i,j,k,l 使得

• 1 ≤ i ≠ j ≤ n , 1 ≤ k ≠ l ≤ m 1\leq i\not= j \leq n, 1\leq k\not= l \leq m 1≤i=j≤n,1≤k=l≤m

• ∣ a i − a j ∣ = ∣ b k − b l ∣ |a_i-a_j| = |b_k-b_l| ∣ai​−aj​∣=∣bk​−bl​∣

题解：

不失一般性，我们假设序列 A , B A,B A,B 中均无重复元素，题目等价叙述为找到一组 i , j , k , l i, j, k, l i,j,k,l 使得

• 1 ≤ i ≠ j ≤ n , 1 ≤ k ≠ l ≤ m 1\leq i\not= j \leq n, 1\leq k\not= l \leq m 1≤i=j≤n,1≤k=l≤m

• a i + b l = a j + b k a_i+b_l=a_j+b_k ai​+bl​=aj​+bk​

  那么我们只需遍历 { a i + b j } \{a_i+b_j\} {ai​+bj​} ，利用抽屉原理遍历一下即可找到答案

代码：

#include 
using namespace std;
const int MAXN = 1e7 + 7;
const int N = 1e6 + 7;
int n, m;
int a[N], b[N], apos[MAXN], bpos[MAXN];
bool t[MAXN << 1];
int ansa[MAXN << 1], ansb[MAXN << 1];
signed main() {
  scanf("%d%d", &n, &m);
  vector<int> ans;
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    a[i] = x;
    if (!apos[x]) {
      apos[x] = i;
    } else if (ans.size() == 0) {
      ans.push_back(apos[x]);
      ans.push_back(i);
    }
  }
  for (int i = 1; i <= m; i++) {
    int x;
    scanf("%d", &x);
    b[i] = x;
    if (!bpos[x]) {
      bpos[x] = i;
    } else if (ans.size() == 2) {
      ans.push_back(bpos[x]);
      ans.push_back(i);
    }
  }
  if (ans.size() == 4) {
    for (auto v : ans) cout << v << " ";
    return 0;
  } else {
    sort(a + 1, a + n + 1);
    n = unique(a + 1, a + n + 1) - a - 1;
    sort(b + 1, b + m + 1);
    m = unique(b + 1, b + m + 1) - b - 1;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        int x = a[i] + b[j];
        if (t[x]) {
          printf("%d %d %d %d", ansa[x], apos[a[i]], ansb[x], bpos[b[j]]);
          return 0;
        }
        ansa[x] = apos[a[i]];
        ansb[x] = bpos[b[j]];
        t[x] = 1;
      }
    }
    printf("-1\n");
  }
  return 0;
}

三、题目分析及解法（进阶题）