2022牛客多校(十)

2022牛客多校(十),第1张

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∣1i7} { b i ∣ 1 ≤ i ≤ 7 } \{b_i|1\leq i \leq 7\} {bi∣1i7} ,问 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=0x1(ii+y1)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 1i=jn,1k=lm

  • ∣ a i − a j ∣ = ∣ b k − b l ∣ |a_i-a_j| = |b_k-b_l| aiaj=bkbl

题解:

不失一般性,我们假设序列 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 1i=jn,1k=lm

  • 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;
}
三、题目分析及解法(进阶题)

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/3002956.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-27
下一篇 2022-09-27

发表评论

登录后才能评论

评论列表(0条)

保存