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

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

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

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

随机推荐

  • 正是河豚欲上时的欲是什么意思

    “欲”意思为:将要,正要,想要。“正是河豚欲上时”意思为:而河豚此时正要逆流而上。出自于文学家苏轼的《惠崇春江晚景二首》。《惠崇春江晚景二首》是北宋文学家苏轼题惠崇的《春江晚景》所创作的组诗。原文内容

  • 饮用水的标准

    国家饮用水标准,是TDS值标准≤1000mgL,TDS值一般低于1000mgL就代表水质可以,但是TDS值越低,并不代表水质越好,还要进一步评定。2007年7月1日,由国家标准委和卫生部联合发布的

    2022-12-06
    000
  • 唐三彩是哪三彩

    唐三彩并非专指三种色彩,“三彩”是多彩的意思,出土的唐三彩主要是以黄、绿、白为主。唐朝工匠用各种矿物烧制出黄、绿、白、褐、蓝、黑等色彩的低温釉陶器,其中以黄、绿、白三色为主,所以人们习惯称之为“唐三彩

    2022-12-06
    000
  • 让我来朵蜜你吧什么意思

    让‌‌‌‌‌‌‌‌‌‌我来朵蜜你吧,是出自于《舞法天女》电视剧里的一句台词,“让我来朵蜜你吧”。意思就是我来辣吓你的狗眼,尴尬死你吧。 朵蜜是“do mi”,法苏是“fa so”,拉提是“la si”

    2022-12-06
    000
  • 明明那么普通却那么自信是什么意思

    明明那么普通却那么自信,这‌‌‌‌‌‌句话用来讽刺有些人自己很普通却觉得自己非常与众不同,并认为别人都是想占自己便宜。 本是他看起来那么普通,却那么自信,出‌‌‌‌‌‌‌自杨笠在《脱口秀大会》上说的一

    2022-12-06
    000
  • 沉迷学习无法自拔、沉迷学习日渐消瘦是什么意思

    沉迷学习,即“沉迷学习无法自拔”,用来形容不喜欢学习还要被迫装作非常积极、勤奋的样子的状态。因为没有学生敢在老师、家长面前大胆直言不喜欢学习。‌‌‌‌‌‌‌‌‌‌‌据说源自一网友发的一张照片:电脑上所

    2022-12-06
    000
  • 背书

    为某人背书,简单来说,就是做担保、做保证的意思。‌‌‌‌‌‌‌‌ 背书,本意是指背诵念过的书:上小学的时候每天早晨要~,背不出书要挨罚。 背书本来在商业行为中,是指有一种支票转让的时候,转让人要在支票

    2022-12-06
    000
  • 弘昼是咋死的

    历史上弘昼属于自然疾病死亡,他去世的时候不到三十岁。虽然也有说法认为弘昼是被乾隆帝给赐死的,但是从《清史稿》的记载中发现,弘昼生病的时候乾隆还专门去看望过他,弘昼死后也没有被剥夺爵位,由此可见弘昼是自

    2022-12-06
    000
  • 一盏茶是多久

    一盏茶的时间是十五分钟,也有些人认为是十分钟。因为茶凉的速度跟季节相关,如果天热的话一盏热茶需要十五分钟才能凉透,如果天不热的话一般需要十分钟就凉透了,所以用这种方法计时并不是很准确。其实古代计时的方

    2022-12-06
    000

发表评论

登录后才能评论

评论列表(0条)

    保存