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

2026牛客暑期多校训练营1部分题解, 补题链接: 点这里通过: A, E, F, C, J补题目: G过题部分F: Permutation Generationtag: 打表, 数学赛时打表发现整体平移排列即可, 证明如下:#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(Tx) { char cugetchar(); x0; bool fla0; // 负数标志 while(!isdigit(cu)) { if(cu-)fla1; cugetchar(); } while(isdigit(cu))xx*10cu-0,cugetchar(); if(fla)x-x; } #define int long long const int inf LLONG_MAX; #define pii pairint, 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 1e97; void solve(){ int n, k, x; cin n k x; vectorint arr(n 1); int pos -1; for(int i 1; i n; i) { cin arr[i]; if (arr[i] x) pos i; } vectorint 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(Tx) { char cugetchar(); x0; bool fla0; // 负数标志 while(!isdigit(cu)) { if(cu-)fla1; cugetchar(); } while(isdigit(cu))xx*10cu-0,cugetchar(); if(fla)x-x; } #define int long long const int inf LLONG_MAX; #define pii pairint, 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 1e97; int n, m, q; int ans; int tot; const int N 5e519; int dx[] {0, 0, 1, -1}; int dy[] {1, -1, 0, 0}; mappii, 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 Handtag: 极小化极大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_listint 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, greaterint()); bool flush true; for (int i 1; i 5; i) { if (suits[i] ! suits[0]) { flush false; break; } } bool straight false; int straightHigh 0; // A2345A在顺子中视为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(Tx) { char cugetchar(); x0; bool fla0; // 负数标志 while(!isdigit(cu)) { if(cu-)fla1; cugetchar(); } while(isdigit(cu))xx*10cu-0,cugetchar(); if(fla)x-x; } #define ld long double #define int long long const int inf LLONG_MAX; #define pii pairint, 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 1e97; void solve(){ int n; cin n; ld step 0.0101L; vectorpairld, 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 Mastertag: 马尔可夫决策过程MDP没有学习过这个知识点, 也没有做过相关题目, 第一次见, 未来几天搞明白这个点.