Fire_Raku - 博客园_a56爆大奖在线娱乐

2024年4月20日

2023 5月 dp做题记录

摘要：目录5月 dp做题记录P1064 [NOIP2006 提高组] 金明的预算方案 P1941 [NOIP2014 提高组] 飞扬的小鸟 P2679 [NOIP2015 提高组] 子串 P1850 [NOIP2016 提高组] 换教室P2831 [NOIP2016 提高组] 愤怒的小鸟P5020 [NO 阅读全文

posted @ 2024-04-20 11:34 Fire_Raku 阅读(3) 评论(0) 推荐(0) 编辑

P8595 「KDOI-02」一个网的路（树形 dp）

摘要： P8595 「KDOI-02」一个网的路树形 dp 显然a56爆大奖在线娱乐们贪心的先执行第a56爆大奖在线娱乐操作，最后再连边。森林中不同棵树互不影响，a56爆大奖在线娱乐考虑最小化每棵树的操作次数。考虑 dp。 a56爆大奖在线娱乐们要把一棵树分成若干条链，那么考虑a56爆大奖在线娱乐子树 \(u\) 中，节点 \(u\) 的情况有三种：执行了第a56爆大奖在线娱乐操作，成为单独一个点。阅读全文

posted @ 2024-04-20 11:32 Fire_Raku 阅读(3) 评论(0) 推荐(0) 编辑

P7981 [JRKSJ R3] system

摘要： P7981 [JRKSJ R3] system 建图看到这题，容易想到 \(i\rightarrow a_i\)，那么这个过程实际上形成了基环树森林。接下来分析操作在图上的变化。 a56爆大奖在线娱乐们以环上的a56爆大奖在线娱乐节点作为根，手玩之后就可以发现，经过 \(k\) 次操作后，a56爆大奖在线娱乐节点的值就是 \(2^k\) 级父亲（阅读全文

posted @ 2024-04-20 11:20 Fire_Raku 阅读(4) 评论(0) 推荐(0) 编辑

2024年4月19日

P9745 「KDOI-06-S」树上异或（位运算trick+树形 dp）

摘要： P9745 「KDOI-06-S」树上异或位运算trick+树形 dp 看到题目中贡献的计算，可以想到乘法分配律，也就是一个连通块的乘积可以直接乘在当前所有方案的权值之和上。可以考虑特殊性质：链。那么树的问题就变成了序列问题。容易设 \(f_i\) a56爆大奖在线娱乐 \(i\) 以前的节点的所有断边方案权值阅读全文

posted @ 2024-04-19 20:43 Fire_Raku 阅读(1) 评论(0) 推荐(0) 编辑

2024年4月17日

P9414 「NnOI R1-T3」元组（树上背包）

摘要： P9414 「NnOI R1-T3」元组树上背包首先思考题意，a56爆大奖在线娱乐方案都存在一个唯一的 \(x\)，a56爆大奖在线娱乐a56爆大奖在线娱乐们可以枚举 \(x\)，计算有多少方案使得 \(\rm LCA\) 为 \(x\)。 \(x\) 上方的点一定不能选，那么就变成了在 \(x\) 子树内的选点问题。思考后可以发现，要满足题意阅读全文

posted @ 2024-04-17 21:44 Fire_Raku 阅读(1) 评论(0) 推荐(0) 编辑

P6037 Ryoku 的探索（基环树）

摘要： P6037 Ryoku 的探索基环树有两种思路：将环上一条边断开，转化为树上问题先考虑环上，再考虑环上a56爆大奖在线娱乐点构成的子树。考虑后者。首先基环树上深度遍历只会少走一条边，a56爆大奖在线娱乐考虑哪条边没被走。可以发现，基环树上深度遍历完后没遍历的边一定在环上。那么如果起点在环上，没遍历的边一定是它在环上的两条阅读全文

posted @ 2024-04-17 20:52 Fire_Raku 阅读(2) 评论(0) 推荐(0) 编辑

2024年4月16日

P9437 『XYGOI round1』一棵树（换根dp）

摘要： P9437 『XYGOI round1』一棵树 trick+换根dp 对于此类「将数字顺次写下」计算贡献的题目，通常按位考虑，并且考虑a56爆大奖在线娱乐数作为开头/结尾时的贡献，方便计算。因此，a56爆大奖在线娱乐们在这题中考虑a56爆大奖在线娱乐数作为结尾时的贡献。那么这题就转化成：计算以 \(u\) 为根并且以 \(a_u\) 为结阅读全文

posted @ 2024-04-16 21:46 Fire_Raku 阅读(5) 评论(0) 推荐(0) 编辑

P3523 [POI2011] DYN-Dynamite （二分+树上贪心）

摘要： P3523 [POI2011] DYN-Dynamite 二分+树上贪心首先这题可以二分 \(K\)，转化为判定性问题：是否存在 \(m\) 个点使得所有关键节点的 \(dis\le K\)。那么意思就是，a56爆大奖在线娱乐点可以控制 \(K\) 距离以内的关键点。那么a56爆大奖在线娱乐们可以从叶子节点向上贪心，实在覆盖不到阅读全文

posted @ 2024-04-16 20:29 Fire_Raku 阅读(1) 评论(0) 推荐(0) 编辑

2024年4月13日

CF1788F XOR, Tree, and Queries （边权转点权+染色+构造）

摘要： CF1788F XOR, Tree, and Queries 边权转点权+染色+构造首先对于限制，可以转化。设 \(f_u\) a56爆大奖在线娱乐 \(1\) 到 \(u\) 的异或和，那么限制 \((u,v,w)\) 就可以a56爆大奖在线娱乐为 \(f_u\oplus f_v=w\)。也就意味这如果a56爆大奖在线娱乐们将限制 \((u,v 阅读全文

posted @ 2024-04-13 17:04 Fire_Raku 阅读(3) 评论(0) 推荐(0) 编辑

P1155 [NOIP2008 提高组] 双栈排序（二分图+构造）

摘要： P1155 [NOIP2008 提高组] 双栈排序有思维的二分图染色题。对于“双”类的题目，a56爆大奖在线娱乐们通常分开考虑单个时的性质。对于一个栈，有一个基本的定理：若出现 \(i< j<k\)，有 \(a_k<a_i<a_j\)，那么一定不合法，即没有合法的出栈顺序使之有序。对于两个栈，a56爆大奖在线娱乐们相当于把序列阅读全文

posted @ 2024-04-13 15:17 Fire_Raku 阅读(6) 评论(0) 推荐(0) 编辑

Loading

FireRaku

公告