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没有学习过这个知识点, 也没有做过相关题目, 第一次见, 未来几天搞明白这个点.

相关新闻

LangChain 与 LangGraph 实战:构建可编排的大模型智能应用

LangChain 与 LangGraph 实战:构建可编排的大模型智能应用

一、为什么需要 LangChain 和 LangGraph 直接调用大模型 API 很容易,但当应用变得复杂时,开发者很快会遇到以下问题: Prompt 散落在各个业务函数中;多轮对话上下文难以管理;工具调用逻辑与模型调用逻辑混杂&#xff1b…

2026/11/16 15:22:24 阅读更多 →
0基础入门嵌入式记录:STM32按键中断控制LED项目总结

0基础入门嵌入式记录:STM32按键中断控制LED项目总结

本篇为个人零基础学习 STM32 点灯项目的复盘与记录,旨在梳理自己的理解与踩坑过程,并非专业的系统教学教程。本人也是初学阶段,文中若有表述不严谨或理解偏差的地方,欢迎各位前辈和读者批评指正,共同学习进步。对芯片引…

2026/11/18 0:26:02 阅读更多 →
Windows免安装版MySQL8详细安装配置教程(ZIP 压缩包版)

Windows免安装版MySQL8详细安装配置教程(ZIP 压缩包版)

1 前言很多小伙伴在安装MySQL时,习惯去找MSI安装包一路“下一步”,但这种方式会在系统里写入大量注册表信息,卸载不干净时还容易留下各种残留,导致重装失败。其实MySQL官方一直提供ZIP压缩包版(也叫noinstall ZIP Arch…

2026/11/3 7:21:55 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/19 21:38:27 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/19 21:38:49 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/19 21:39:09 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/19 21:36:50 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/19 21:37:45 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/19 21:36:20 阅读更多 →

日新闻

周新闻

月新闻