2022牛客暑期多校训练营8（DF）

题集链接；

• D Poker Game: Decision
  *
  • 思路
  • 代码
• F Longest Common Subsequence
  *
  • 题意
  • 思路
  • 代码

D Poker Game: Decision

模拟

思路

由于牌堆总数仅为6，所有情况也只有 $6!=720$ 种，可以枚举所有情况来进行判断；

对于当前情况，代码中使用 mnn 来代表此时操作者所有操作中的最优情况（此判断中赢为1），对来自下一层的返回值进行取负处理；

代码

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

pair<int, int> Alice[5], Bob[5];
pair<int, int> dui[6];
int vis[6];

// {color , number}

#define color first
#define number second

map<char, int> cover_to = {
    {'A', 14}, {'K', 13}, {'Q', 12}, {'J', 11}, {'T', 10}, {'9', 9},
    {'8', 8},  {'7', 7},  {'6', 6},  {'5', 5},  {'4', 4},  {'3', 3},
    {'2', 2},  {'S', 1},  {'H', 2},  {'C', 3},  {'D', 4},
};

int judge(vector<pair<int, int>>& v) {
   sort(v.begin(), v.end(),
        [](auto a, auto b) { return a.number < b.number; });
   int smc = 1;
   for (int i = 1; i <= 4 && smc; i++) {
      if (v[i].first != v[i - 1].first) smc = 0;
   }
   if (smc && v[0].second == 10 && v[1].second == 11 &&
       v[2].second == 12 && v[3].second == 13 && v[4].second == 14) {
      return 10;
   }
   sort(v.begin(), v.end(), [](pair<int, int> a, pair<int, int> b) {
      return (a.second - 1) % 13 < (b.second - 1) % 13;
   });
   if (smc && (v[1].second - 1) % 13 == (v[0].second - 1) % 13 + 1 &&
       (v[2].second - 1) % 13 == (v[1].second - 1) % 13 + 1 &&
       (v[3].second - 1) % 13 == (v[2].second - 1) % 13 + 1 &&
       (v[4].second - 1) % 13 == (v[3].second - 1) % 13 + 1) {
      reverse(v.begin(), v.end());
      return 9;
   }
   sort(v.begin(), v.end(),
        [](auto a, auto b) { return a.number < b.number; });
   if ((v[1].second == v[2].second && v[2].second == v[3].second) &&
       (v[0].second == v[1].second || v[3].second == v[4].second)) {
      if (v[4].number == v[3].number) swap(v[0], v[4]);
      return 8;
   }

   // Full house
   if ((v[0].second == v[1].second && v[1].second == v[2].second &&
        v[3].second == v[4].second) ||
       (v[0].second == v[1].second && v[2].second == v[3].second &&
        v[3].second == v[4].second)) {
      if (v[2].number == v[4].number) reverse(v.begin(), v.end());
      return 7;
   }

   // Flush
   if (smc && v[0].second != v[1].second &&
       v[1].second != v[2].second && v[2].second != v[3].second &&
       v[3].second != v[4].second) {
      reverse(v.begin(), v.end());
      return 6;
   }

   // Straight
   sort(v.begin(), v.end(), [](pair<int, int> a, pair<int, int> b) {
      return (a.second - 1) % 13 < (b.second - 1) % 13;
   });
   if ((v[1].second - 1) % 13 == (v[0].second - 1) % 13 + 1 &&
       (v[2].second - 1) % 13 == (v[1].second - 1) % 13 + 1 &&
       (v[3].second - 1) % 13 == (v[2].second - 1) % 13 + 1 &&
       (v[4].second - 1) % 13 == (v[3].second - 1) % 13 + 1) {
      reverse(v.begin(), v.end());
      return 5;
   }
   sort(v.begin(), v.end(),
        [](auto a, auto b) { return a.number < b.number; });
   {
      bool f = true;
      for (int i = 1; i < 5; i++)
         if (v[i].number == v[i - 1].number + 1)
            continue;
         else
            f = false;
      if(f) {
         reverse(v.begin() , v.end());
         return 5;
      }
   }

   // Three of a kind
   if ((v[0].second == v[1].second && v[1].second == v[2].second)) {
      if (v[3].number < v[4].number) swap(v[3], v[4]);
      return 4;
   }
   if ((v[1].second == v[2].second && v[2].second == v[3].second)) {
      swap(v[0], v[3]);
      if (v[3].number < v[4].number) swap(v[3], v[4]);
      return 4;
   }
   if ((v[2].second == v[3].second && v[3].second == v[4].second)) {
      reverse(v.begin(), v.end());
      if (v[3].number < v[4].number) swap(v[3], v[4]);
      return 4;
   }

   // Two pairs
   reverse(v.begin(), v.end());
   if (v[0].number == v[1].number && v[2].number == v[3].number)
      return 3;
   if (v[0].number == v[1].number && v[3].number == v[4].number) {
      swap(v[2], v[4]);
      return 3;
   }
   if (v[1].number == v[2].number && v[3].number == v[4].number) {
      swap(v[0], v[2]);
      swap(v[2], v[4]);
      return 3;
   }

   // Pair

   for (int i = 1; i < 5; i++) {
      if (v[i].number == v[i - 1].number) {
         swap(v[0], v[i - 1]);
         swap(v[1], v[i]);
         if(v[2].number<v[3].number)swap(v[2],v[3]);
         if(v[3].number<v[4].number)swap(v[3],v[4]);
         return 2;
      }
   }

   return 1;
}

int check(vector<pair<int, int>> as, vector<pair<int, int>> bs) {
   int a = judge(as), b = judge(bs);
   if (a > b)
      return 1;
   else if (a < b)
      return -1;
   else {
      if (a == 10) return 0;
      for (int i = 0; i < 5; i++) {
         if (as[i].number > bs[i].number)
            return 1;
         else if (as[i].number < bs[i].number)
            return -1;
      }
      return 0;
   }
}

int get(int last = 6) {
   if (last == 0) {
      int k = check(vector<pair<int, int>>(begin(Alice), end(Alice)),
                    vector<pair<int, int>>(begin(Bob), end(Bob)));
      return k;
   }

   int mnn = -1;

   for (int i = 0; i < 6; i++) {
      if (vis[i]) continue;
      vis[i] = 1;
      if (last % 2 == 0)
         Alice[5 - (last + 1) / 2] = dui[i];
      else
         Bob[5 - (last + 1) / 2] = dui[i];
      mnn = max(-get(last - 1), mnn);
      vis[i] = 0;
      if (mnn == 1) break;
   }

   return mnn;
}

void solve() {
   for (int i = 0; i < 2; i++) {
      string s;
      cin >> s;
      Alice[i] = {cover_to[s[1]], cover_to[s[0]]};
   }
   for (int i = 0; i < 2; i++) {
      string s;
      cin >> s;
      Bob[i] = {cover_to[s[1]], cover_to[s[0]]};
   }

   for (int i = 0; i < 6; i++) {
      string s;
      cin >> s;
      dui[i] = {cover_to[s[1]], cover_to[s[0]]};
   }

   auto ans = get();

   // cout << ans << '\n';

   if (ans == 1)
      cout << "Alice\n";
   else if (ans == 0)
      cout << "Draw\n";
   else
      cout << "Bob\n";
}

int main() {
   int t;
   cin >> t;

   while (t--) solve();

   return 0;
}

F Longest Common Subsequence

数学

题意

给出两个数列长度和随机数生成方式，求按要求生成两数列后，两数列的最长公共子序列；

思路

介于数列长度非常大（$1e6$）通常的DP方法复杂度不可接受；

我们考虑数列的生成方式：由于在生成过程中，一个数的取值只与上一个数有关，那么在这两个序列中，只要有一位相同，那么接下来的部分均相同；

我们只需要记录下每个数字在序列n中第一次出现的下标，如果在m中再次出现，我们便可以计算出以其起始的最长公共子序列长度，并更新答案；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    ll t, n, m, p, x, a, b, c;
    cin >> t;
    while (t--)
    {
        scanf("%lld%lld%lld%lld%lld%lld%lld", &n, &m, &p, &x, &a, &b, &c);
        unordered_map<ll, int> mp;
        for (int i = 1; i <= n; i++)
        {
            x = a * x % p * x % p + b * x % p + c;
            x %= p;
            if (!mp[x])
                mp[x] = i;
        }
        ll ans = 0;
        for (int i = 1; i <= m; i++)
        {
            x = a * x % p * x % p + b * x % p + c;
            x %= p;
            if (mp[x])
            {
                ans = max(ans, min(n - mp[x] + 1, m - i + 1));
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}