HDU 3565 Bi-Peak Number:数位 DP 状态机求最大数位和
题目大意 峰值数:数位先增后减(位数≥3,首位非零)。Bi-Peak:两个峰值数拼接。求区间 [A,B] 内 Bi-Peak 数的最大数位和。 数位 DP 状
CodeVS 2926 黑白瓷砖:Polya 计数定理应用
题目大意 正三角形区域由小三角形组成,第 n 层有 n(n+1)/2 个小三角形。每个小三角形黑/白染色。两种染色若可通过旋转/翻转重合视为相同。求本质不同染色
POJ 2312 Battle City:优先队列 BFS 最短转弯/射击路径
题目大意 M×N 网格(≤300×300),坦克从 Y 出发到达 T。地形:空地 E、河流 R、钢墙 S、砖墙 B。动作:移动到相邻空地(1 回合),或向四方向
HDU 1159 最大公共子序列 (LCS):经典 DP 详解
题目大意 给定两字符串,求最长公共子序列(LCS)长度。多测试用例,至 EOF。 DP 状态与转移 dp[i][j]:s1[0..i-1] 与 s2[0..j
UVA 10755:三維最大子陣列和——降維與掃描線
UVA 10755 三維最大子陣列和 詳解 題目:給定 A×B×C 的長方體,每個單元格有權值(可正可負)。求一個子長方體,使其權值和最大。A,B,C ≤ 20
LeetCode Add Binary:字符串二进制加法模拟
题目大意 给定两个二进制字符串,返回它们的和(二进制字符串)。 模拟竖式加法 对齐长度:短串前补 0 从右向左逐位相加,维护进位 carry 当前位 = (
HDOJ 2952 Counting Sheep:网格连通分量计数 DFS
题目大意 H×W 网格(≤100×100),# 表示羊,. 表示草。上下左右相邻的羊属于同一群。求羊群数量。 DFS/BFS 标记连通分量 #include
HDU 5170/5171:大数比较取对数 / 斐波那契矩阵加速贪心
HDU 5170:大整数幂比较 比较 a^b 与 c^d 大小。直接算溢出,取对数:b·log10(a) vs d·log10(c)。注意精度,设阈值 1e-9
POJ 3630 Phone List:Trie 树判断前缀冲突
题目大意 给定 n 个电话号码字符串,判断是否存在某号码是另一号码的前缀。存在输出 NO,否则 YES。 Trie 树插入检测 插入每个字符串 插入过程中两
HDU 1561 城堡攻略:树形背包 DP 选 M 个节点最大权值
题目大意 N 座城堡(N≤200)形成树结构(每城堡有一前置城堡,0 表示根)。每城堡有宝物价值。必须攻克恰好 M 个城堡(M≤N),且攻克某城堡需先攻克其父城
LeetCode BST 迭代器:中序遍历迭代器设计 O(h) 空间
题目要求 实现二叉搜索树迭代器,支持 next() 返回下一个最小值,hasNext() 判断是否有下一个。要求均摊 O(1) 时间,O(h) 空间(h 为树高
BZOJ 3503 和谐矩阵:异或高斯消元求任意非零解
题目大意 m×n 矩阵,每个格子填 0/1。要求每个格子与其上下左右四邻域的 1 的个数为偶数(含自身)。输出任意非全零解。 建模:GF(2) 线性方程组
Rockethon 2015 C: Second Price Auction 期望 DP
题目大意 n 人竞拍,第 i 人出价均匀分布于 [l_i, r_i]。一价拍卖:最高价者得标,支付第二高价(允许并列第一)。求支付金额的期望。 解法思路:按第
HDU 3586 战场通信阻断:树形 DP + 二分答案
题目大意 树上 n 个节点(n≤1000),1 为根(总指挥),叶子为前线士兵。需切断若干边使所有叶子到根的路径不通。切断边权 ≤ x(设备上限),总权和 ≤
POJ 2185 Milking Grid:二维 KMP + Next 数组求最小周期子矩阵
题目大意 给定 R×C 字符矩阵(R≤10000, C≤75),求最小面积子矩阵,使其平铺可覆盖原矩阵(子矩阵尺寸不必整除原尺寸)。 核心洞察:行/列独立周期
POJ 2112 Optimal Milking:Floyd + 最大流 + 二分答案
题目大意 K 台挤奶机(K≤30),C 头奶牛(C≤200),每机每天最多挤 M 头(M≤15)。奶牛与机器间有多条路径。安排每头奶牛到一台机器,使所有奶牛路径
LeetCode 搜索插入位置:二分查找边界处理
题目大意 给定升序无重复数组 nums 和目标值 target,返回目标索引(若存在)或应插入位置(保持有序)。 二分查找模板 public class Se
UVA 1626 / ZOJ 1463 括号序列:区间 DP 构造最短合法超序列
题目大意 给定由 ()[] 组成的字符串(长 ≤ 100),求最短的合法括号序列,使其包含原串为子序列。合法定义:空串、括号包裹合法串、合法串拼接。 区间 D