2026牛客暑期多校训练营1部分题解, 补题

• 链接: 点这里
• 通过: A, E, F, C, J
• 补题目: G

过题部分

F: Permutation Generation

• tag: 打表, 数学
• 赛时打表发现整体平移排列即可, 证明如下:
  

#include <bits/stdc++.h> using namespace std; mt19937 rnd(time(NULL)); // #pragma GCC optimize(3) // #pragma GCC optimize("inline") // #pragma GCC optimize("Ofast") // 快速读入整数模板 template <typename T> inline void Read(T&x) { char cu=getchar(); x=0; bool fla=0; // 负数标志 while(!isdigit(cu)) { if(cu=='-')fla=1; cu=getchar(); } while(isdigit(cu))x=x*10+cu-'0',cu=getchar(); if(fla)x=-x; } #define int long long const int inf = LLONG_MAX; #define pii pair<int, int> #define LL long long #define endl '\n' #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define rep(n) for(int i = 0; i < n; i++) const int mod = 1e9+7; void solve(){ int n, k, x; cin >> n >> k >> x; vector<int> arr(n + 1); int pos = -1; for(int i= 1; i <= n; i++) { cin >> arr[i]; if (arr[i] == x) pos = i; } vector<int> brr; for (int i = pos; i <= n; i++) { brr.push_back(arr[i]); } for (int i = 1; i < pos; i++) { brr.push_back(arr[i]); } // for (int i = 0; i < n; i++) { // cout << brr[i] << " "; // } // cout << endl; k = n - k; for (int i = k; i < n; i++) { cout << brr[i] << " "; } for (int i = 0; i < k; i++) { cout << brr[i] << " "; } cout << endl; } signed main(){ ios::sync_with_stdio(0),cin.tie(0), cout.tie(0); int T= 1; // cin >> T; while(T--){ solve(); } return 0; }

C:

• tag: 带权并查集
• 还是比较容易看出来是并查集的. 重要条件: 题目给出后加入的体积不小于之前的. 所以对于op1: 连通块的鱼都可以吃掉, 就是并查集的大小. 对于op2: 我们将并查集后插入的点总是作为根, 维护其余点吃掉根需要的最小额外代价.(根有最大的体积)

#include <bits/stdc++.h> using namespace std; mt19937 rnd(time(NULL)); // #pragma GCC optimize(3) // #pragma GCC optimize("inline") // #pragma GCC optimize("Ofast") // 快速读入整数模板 template <typename T> inline void Read(T&x) { char cu=getchar(); x=0; bool fla=0; // 负数标志 while(!isdigit(cu)) { if(cu=='-')fla=1; cu=getchar(); } while(isdigit(cu))x=x*10+cu-'0',cu=getchar(); if(fla)x=-x; } #define int long long const int inf = LLONG_MAX; #define pii pair<int, int> #define LL long long #define endl '\n' #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define rep(n) for(int i = 0; i < n; i++) const int mod = 1e9+7; int n, m, q; int ans; int tot; const int N = 5e5+19; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; map<pii, int> mp; struct union_find_set{ int fa[N]; int sz[N]; int sz_row[N]; int dis[N]; union_find_set() { for (int i = 0; i < N; i++) fa[i] = i; } int find(int x) { if (fa[x] == x) return x; int f = fa[x]; fa[x] = find(fa[x]); dis[x] = max(dis[x], dis[f]); return fa[x]; } void unionset(int x, int y) { int px = find(x); int py = find(y); if (px == py) return; fa[py] = px; sz[px] += sz[py]; dis[py] = max((int)0, -sz[py] + sz_row[px] + 1); } void merge(int x, int y, int v) { int id = mp[{x, y}]; sz_row[id] = v; sz[id] = 1; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (mp.count({nx, ny})) { int nid = mp[{nx, ny}]; unionset(id, nid); } } } int query1(int x, int y) { int id = mp[{x, y}]; find(id); return sz[id] - 1; } int query2(int x, int y) { int id = mp[{x, y}]; int f = find(id); return max(0LL, dis[id] - sz_row[id]); } }ufs; void op1(int x, int y, int v) { mp[{x, y}] = ++tot; ufs.merge(x, y, v); ans = ufs.query1(x, y); cout << ans << endl; } void op2(int x, int y) { ans = ufs.query2(x, y); cout << ans << endl; } void solve(){ cin >> n >> m >> q; for (int i = 1; i <= q; i++) { int op; cin >> op; int x, y, v; cin >> x >> y; x ^= ans; y ^= ans; if (op == 1) { cin >> v; op1(x, y, v); }else{ op2(x, y); } } } signed main(){ ios::sync_with_stdio(0),cin.tie(0), cout.tie(0); int T= 1; // cin >> T; while(T--){ solve(); } return 0; }

J: Show Hand

• tag: 极小化极大（Minimax）博弈算法, 暴力
• 赌神选一个牌, 自己选一个牌, 暴力计算(<50*50)
• 关键优化: 预处理每个人拿到某张底牌后，最终五张牌的牌型权值.赛时没有这个优化, t了, 让gpt写了一个.

#include <bits/stdc++.h> using namespace std; using ull = unsigned long long; int myCards[5]; int enemyCards[5]; bool used[52]; const char* answer[] = { "WoYaoYanPai", "PaiMeiYouWenTi", "GeiWoCaPiXie" }; // 花色编号不影响大小，只用于判断同花 int getSuit(char c) { if (c == 'C') return 0; if (c == 'D') return 1; if (c == 'H') return 2; return 3; // S } int getRank(char c) { if (c >= '2' && c <= '9') return c - '0'; if (c == 'T') return 10; if (c == 'J') return 11; if (c == 'Q') return 12; if (c == 'K') return 13; return 14; // A } // 将一张牌映射到 [0, 51] int getCardId(const string& s) { int rank = getRank(s[0]); int suit = getSuit(s[1]); return suit * 13 + rank - 2; } int cardRank(int id) { return id % 13 + 2; } int cardSuit(int id) { return id / 13; } /* 牌型编码。 按照以下顺序比较： 第一个数：牌型 后续数字：同牌型下的比较关键字 使用十五进制编码后，可以直接比较 ull 大小。 */ ull encode(initializer_list<int> values) { ull result = 0; int count = 0; for (int x : values) { result = result * 15 + x; ++count; } // 补齐到固定长度6，保证编码具有一致的字典序 while (count < 6) { result *= 15; ++count; } return result; } // 计算五张牌的牌型权值 ull evaluate(const int cards[5]) { int ranks[5]; int suits[5]; int cnt[15] = {}; for (int i = 0; i < 5; ++i) { ranks[i] = cardRank(cards[i]); suits[i] = cardSuit(cards[i]); ++cnt[ranks[i]]; } sort(ranks, ranks + 5, greater<int>()); bool flush = true; for (int i = 1; i < 5; ++i) { if (suits[i] != suits[0]) { flush = false; break; } } bool straight = false; int straightHigh = 0; // A2345，A在顺子中视为1 if (ranks[0] == 14 && ranks[1] == 5 && ranks[2] == 4 && ranks[3] == 3 && ranks[4] == 2) { straight = true; straightHigh = 5; } else { bool ok = true; for (int i = 1; i < 5; ++i) { if (ranks[i - 1] != ranks[i] + 1) { ok = false; break; } } if (ok) { straight = true; straightHigh = ranks[0]; } } int four = 0; int three = 0; int pairs[2] = {}; int pairCount = 0; int singles[5] = {}; int singleCount = 0; // 从大到小收集牌组，方便直接比较 for (int rank = 14; rank >= 2; --rank) { if (cnt[rank] == 4) { four = rank; } else if (cnt[rank] == 3) { three = rank; } else if (cnt[rank] == 2) { pairs[pairCount++] = rank; } else if (cnt[rank] == 1) { singles[singleCount++] = rank; } } // Royal Flush if (flush && straight && straightHigh == 14) { return encode({9, 14}); } // Straight Flush if (flush && straight) { return encode({8, straightHigh}); } // Four of a Kind if (four != 0) { return encode({ 7, four, singles[0] }); } // Full House if (three != 0 && pairCount == 1) { return encode({ 6, three, pairs[0] }); } // Flush if (flush) { return encode({ 5, ranks[0], ranks[1], ranks[2], ranks[3], ranks[4] }); } // Straight if (straight) { return encode({ 4, straightHigh }); } // Three of a Kind if (three != 0) { return encode({ 3, three, singles[0], singles[1] }); } // Two Pairs if (pairCount == 2) { return encode({ 2, pairs[0], // 较大的对子 pairs[1], // 较小的对子 singles[0] }); } // One Pair if (pairCount == 1) { return encode({ 1, pairs[0], singles[0], singles[1], singles[2] }); } // High Card return encode({ 0, ranks[0], ranks[1], ranks[2], ranks[3], ranks[4] }); } /* 返回值： 0：我赢 1：平局 2：赌神赢 */ int compareGame(ull myValue, ull enemyValue) { if (myValue > enemyValue) return 0; if (myValue == enemyValue) return 1; return 2; } void solve() { memset(used, false, sizeof(used)); string s; for (int i = 0; i < 4; ++i) { cin >> s; myCards[i] = getCardId(s); used[myCards[i]] = true; } for (int i = 0; i < 4; ++i) { cin >> s; enemyCards[i] = getCardId(s); used[enemyCards[i]] = true; } /* 对每一张可能作为底牌的牌，预处理对应牌型。 初始桌面有8张牌，因此剩余44张牌可供赌神先选。 赌神选完后，我再从剩下43张中选择。 */ ull myValue[52] = {}; ull enemyValue[52] = {}; for (int card = 0; card < 52; ++card) { if (used[card]) continue; myCards[4] = card; enemyCards[4] = card; myValue[card] = evaluate(myCards); enemyValue[card] = evaluate(enemyCards); } /* 博弈顺序： 赌神先选择 enemyCard； 我知道他的选择后，再选择 myCard。 对固定的 enemyCard： 我会选择结果最小的回应； 0最优，1其次，2最差。 赌神会选择让最终结果最大的 enemyCard。 */ int finalResult = 0; for (int enemyCard = 0; enemyCard < 52; ++enemyCard) { if (used[enemyCard]) continue; int myBestResult = 2; for (int myCard = 0; myCard < 52; ++myCard) { if (used[myCard] || myCard == enemyCard) continue; int result = compareGame( myValue[myCard], enemyValue[enemyCard] ); myBestResult = min(myBestResult, result); // 已经找到获胜回应，不需要继续枚举 if (myBestResult == 0) break; } // 赌神从他的所有选择中，选择对他最有利的结果 finalResult = max(finalResult, myBestResult); // 赌神已经找到必胜选择，可以直接结束 if (finalResult == 2) break; } cout << answer[finalResult] << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { solve(); } return 0; }

补提部分

G: Precision Error?!

• tag: 数学, 思维
• 重要条件: ϵ = 0.01, 是一个比较大的数?
• 构造两个平行的平面, 距离为1, 每个平面n个点, 平面内的点距离比ϵ大一点点, 两个平面之间的点距离不小于1, 可以证明不大于1 + ϵ.
• 赛时看到ϵ想当然认为是浮点误差, 没想到还可以这样.

#include <bits/stdc++.h> using namespace std; mt19937 rnd(time(NULL)); // #pragma GCC optimize(3) // #pragma GCC optimize("inline") // #pragma GCC optimize("Ofast") // 快速读入整数模板 template <typename T> inline void Read(T&x) { char cu=getchar(); x=0; bool fla=0; // 负数标志 while(!isdigit(cu)) { if(cu=='-')fla=1; cu=getchar(); } while(isdigit(cu))x=x*10+cu-'0',cu=getchar(); if(fla)x=-x; } #define ld long double #define int long long const int inf = LLONG_MAX; #define pii pair<int, int> #define LL long long #define endl '\n' #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define rep(n) for(int i = 0; i < n; i++) const int mod = 1e9+7; void solve(){ int n; cin >> n; ld step = 0.0101L; vector<pair<ld, ld>> points; for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { if (points.size() >= n) continue; points.push_back({i * step, j * step}); } } cout << n * 2 << endl; cout << fixed << setprecision(10); for(auto [a, b] : points) { cout << a << " " << b << " " << 0.0L << endl; } for(auto [a, b] : points) { cout << a << " " << b << " " << 1.0L << endl; } } signed main(){ ios::sync_with_stdio(0),cin.tie(0), cout.tie(0); int T= 1; // cin >> T; while(T--){ solve(); } return 0; }

H: Rock-Paper-Scissors Master

• tag: 马尔可夫决策过程（MDP）
• 没有学习过这个知识点, 也没有做过相关题目, 第一次见, 未来几天搞明白这个点.