一道ICPC武汉邀请赛简单的博弈题
算法足迹
- [ICPC 2026 Wuhan I] Prime Game 博弈
- Codeforces Round 1122 D-Falling Concrete
Codeforces Round 1122 D-Falling Concrete题解
- 费用流&左偏树可并堆
进阶算法笔记:讲解最小费用最大流的 SSP 思想与 EK、Dinic 两种实现,并介绍左偏树这一合并高效的可并堆数据结构。
- 2026牛客暑期多校3-F Not Aqre 2(状压DP,矩阵加速)
牛客暑期多校 F 题『Not Aqre 2』题解:网格相邻不同色的计数,用状态压缩把列状态降到 128 种,再以矩阵快速幂加速沿列的递推。
- [USACO19FEB] Dishwashing G(贪心,二分)
USACO19FEB『Dishwashing G』题解:用多个栈模拟盘堆并保持堆底递增,二分定位目标堆再弹出插入,求能整理有序的最大前缀长度。
- 2025CCFCAT省赛-D.简单树上问题(位运算,树)
CCFCAT 省赛 D 题题解:对子树整体异或、代价为子树大小×x,用两次 DFS 自上而下贪心,求把所有节点权值清零的最小总代价。
- [蓝桥杯 2026 省 B] 理想温度 题解
蓝桥杯 2026 省 B『理想温度』题解:只关心 A、B 差值,用前缀和统计 0 的个数、哈希表维护同一差值区间,求一次区间补偿后处于理想温度的最大数量。
- [USACO21FEB] Just Green Enough S(单调栈)
USACO『Just Green Enough』题解:把『最小值恰为 100 的子矩阵』拆成 ≥100 与 >100 两个 01 矩阵相减,再用单调栈统计全 1 子矩阵。
- 2026杭电春季赛热身赛-1007最大三段和(kadane算法)
杭电春季赛热身 1007 题解:在『第二段长度为 1』的约束下,用 Kadane 算法预处理左右最大子段,枚举中点求最大三段和。
- [NOIP 2018 提高组] 货币系统(数学,dp)
NOIP2018 提高组『货币系统』题解:把冗余面额视为可被线性表示的向量,答案即向量组的秩,用排序 + 完全背包式 DP 求不能被表示的个数。
- 洛谷 P1714 切蛋糕[单调队列,前缀和]
洛谷 P1714『切蛋糕』题解:在长度不超过 m 的约束下求最大子段和,用单调队列维护窗口内最小前缀和,并详解 0 先入队等更新时机细节。
- [2025 杭电春季赛 1]船长(模拟,数论)
杭电春季赛『船长』题解:模拟淘汰赛求染染避开威胁水手的概率,结合乘法逆元与『编号减一 + 异或求对手』的技巧,只对有威胁的水手模拟以避免超时。
- 通信线路([USACO08JAN] Telephone Lines S)(二分,01最短路)
USACO『Telephone Lines』题解:二分升级花费阈值,把『超过阈值的边数』转化为 01 最短路用 Dijkstra 检验,求可免费 K 条边下的最小花费。
- [蓝桥杯 2013 国 A] 约数倍数选卡片(数论,dfs,图)
蓝桥杯『约数倍数选卡片』题解:把约数倍数关系建图,用 dfs 递归判定各起点的必胜/必输,求先手最小的必胜起点。
- 最短路算法:Dijkstra&Bellman-Ford&SPFA
图论最短路入门笔记:结合例题讲解 Dijkstra(优先队列优化)、Bellman-Ford(可处理负权)与 SPFA,对比三者的思路与适用场景。