腌萝卜干

未归档

题解(4)

/ 注册

全部文章 / 未归档（共199篇）

NOIP2018提高组.货币系统

题目 532. 货币系统思路关键找到性质, 在最优解˙中每一个 b i ∈ { a 1 , a 2 , . . . , a n } b_i \in \left \{ a_1, a_2, ..., a_n \right \} bi∈{ a1,a2,...,an}每一个...

2026-03-29

0 0

ABC399.D题解

题目 D - Switch Seats 算法标签: 模拟, 哈希思路对于序列中两个相同数字不能在同一个位置, 并且可以通过交换使得四个数字两两在相同位置代码 #include <iostream> #include <algorithm> #include...

2026-03-29

0 0

ABC399.E题解

题目 E - Replace 算法标签: 动态规划, 组合数学, 图论思路首先考虑是否有解, 然后再考虑最小操作步数, 观察什么情况下无解, 如果对于 i , j i, j i,j有 S i = S j S_i = S_j Si=Sj, 并且 T i ≠ T j T_i \ne T...

2026-03-29

0 0

NOIP2016提高组.换教室

题目 233. 换教室算法标签: 期望 d p dp dp, F l o y d Floyd Floyd求最短路思路因为只能在最开始的时候决定每节课的教室是否更换, 因此每个教室之间的概率是独立的, 也就是说总的期望的最小值可以分步计算, 设计状态 f [ i ] [ j ] [ ...

2026-03-29

0 0

NOIP2017提高组.宝藏

题目 529. 宝藏算法标签: 状态压缩 d p dp dp, 位运算, 贪心思路代价等于长度 × 当前点的深度长度 \times 当前点的深度长度×当前点的深度, 求代价的最小值, 直接想法是 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][...

2026-03-29

0 0

NOIP2016提高组.愤怒的小鸟

题目 524. 愤怒的小鸟算法标签: 状态压缩 d p dp dp, D a n c i n g − L i n k s Dancing-Links Dancing−Links 思路预处理所有经过两个点的抛物线, 问题就变成重复覆盖问题, 因为列数比较小, 因此可以使用状态压缩计算,...

2026-03-29

0 0

LIS离散化 + 树状数组

严格上升子序列正序 #include <iostream> #include <algorithm> #include <cstring> #include <vector> using namespace std; const int N = ...

2026-03-29

0 0

2019 CCF CSP-S2.括号树

题目 1153. 括号树算法标签: 树形 d p dp dp, 栈思路首先将问题简化, 将问题转化为序列, 我们发现每一个右括号匹配的做括号是唯一确定的, 那么就有状态表示 f [ i ] f[i] f[i]表示在前 i i i个集合当中的合法括号序列的集合, 属性就是方案数, 将集...

2026-03-29

0 0

NOIP2018提高组.保卫国王

题目 536. 保卫王国算法标签: 树形 d p dp dp, 树上倍增, L C A LCA LCA 思路在原问题基础上还有每个点的限制, 要求某些点必须选择, 某些节点不能选择将问题简化, 如果是一维问题, 可以前后缀分解来做将问题回到树形问题, 首先考虑只有一个点...

2026-03-29

0 0

NOIP2010提高组.引水入城

*前置题目 901. 滑雪 #include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 310, INF = 0x3f3f3f...

2026-03-29

0 0