腌萝卜干

分类

未归档(199) 题解(8)

/ 注册

全部文章（共282篇）

NOI2015提高组.子串

题目 520. 子串思路设计状态表示 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]表示 a a a的前 i i i个字符, b b b的前 j j j个字符, 并且已经分割了 k k k个子串的所有方案, 将状态划分为包含第 i i i个字符和不包...

2026-03-29

0 0

2019 CCF CSP-S2.Emiya 家今天的饭

题目 1155. Emiya 家今天的饭思路容斥原理, d p + d p dp + dp dp+dp, 不是 d p o f d p dp \,of \, dp dpofdp 核心方法总得方案数减去不合法的方案数, 首先考虑前两个约束, 状态表示 f [ i ] [ j ] ...

2026-03-29

0 0

NOIP2007提高组.矩阵取数游戏

题目 492. 矩阵取数游戏思路不难发现, 每一行之间是独立的, 因此可以求出每一行的最大值, 然后行与行之间最大值相加, 就是总的最大值对于行内来说, 每次可以选取左边或者右边, 可以使用区间 d p dp dp求解, 时间复杂度 O ( n 3 ) O(n ^ 3) O(n3), ...

2026-03-29

0 0

NOIP2014提高组.飞扬的小鸟

题目 512. 飞扬的小鸟思路不难发现状态可以表示为 f [ i ] [ j ] f[i][j] f[i][j]也就是到达 ( i , j ) (i, j) (i,j)位置的最小点击数, 当前状态可以由上一个位置的状态转移, f [ i − 1 ] [ j + y ] f[i - 1]...

2026-03-29

0 0

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