<?xml version="1.0" encoding="utf-8" ?><rss version="2.0"><channel><title><![CDATA[UIU114的博客]]></title><description><![CDATA[]]></description><link>https://blog.csdn.net/UIU114</link><language>zh-cn</language><generator>https://blog.csdn.net/</generator><copyright><![CDATA[Copyright &copy; UIU114]]></copyright><item><title><![CDATA[P1710 地铁涨价]]></title><link>https://blog.csdn.net/UIU114/article/details/170458427</link><guid>https://blog.csdn.net/UIU114/article/details/170458427</guid><author>UIU114</author><pubDate>Wed, 11 Nov 2026 08:00:00 +0800</pubDate><description><![CDATA[本题核心在于将“票价等于最短路径长度”的满意度条件转化为“存在仅由未涨价边构成的最短路径”。通过反向处理（从全涨价状态逐步恢复边权），利用BFS增量维护可用边下的最短边数 $ f[v] $，当 $ f[v] = d[v] $ 时点 $ v $ 满意。由于反向操作使距离单调不增，可局部松弛更新，避免重复跑最短路。关键优化：仅从恢复边两端触发松弛，且 $ happy $ 为累计量，每个点仅一次“达标”机会。时间复杂度 $ O(N + M + Q) $，高效解决原问题。]]></description><category></category></item><item><title><![CDATA[P1706 全排列问题]]></title><link>https://blog.csdn.net/UIU114/article/details/170367021</link><guid>https://blog.csdn.net/UIU114/article/details/170367021</guid><author>UIU114</author><pubDate>Tue, 10 Nov 2026 08:00:00 +0800</pubDate><description><![CDATA[本文详解洛谷P1706全排列问题的两种解法：一是使用next_permutation函数，需配合do-while循环确保首尾排列正确输出；二是通过DFS回溯，逐位枚举并用vis数组标记已选数字，天然保证字典序。两种方法时间复杂度均为O(n!×n)，代码简洁高效，重点强调了循环结构与状态恢复的细节。]]></description><category></category></item><item><title><![CDATA[P1677 [USACO18FEB] Hoofball B]]></title><link>https://blog.csdn.net/UIU114/article/details/170292129</link><guid>https://blog.csdn.net/UIU114/article/details/170292129</guid><author>UIU114</author><pubDate>Mon, 09 Nov 2026 08:00:00 +0800</pubDate><description><![CDATA[题目P1677通过构建每头牛指向最近邻居的函数图（出度为1），利用三色标记法识别环结构。答案由两部分构成：入度为0的牛需单独给球（起点），以及仅由环组成的连通块需额外一个球覆盖。通过遍历每个点并用状态0/1/2区分未访问、当前路径、已结束路径，正确判断环的存在性，避免误判。时间复杂度O(n²)，适用于n≤100。]]></description><category></category></item><item><title><![CDATA[P11246 [GESP202409 六级] 小杨和整数拆分]]></title><link>https://blog.csdn.net/UIU114/article/details/170248167</link><guid>https://blog.csdn.net/UIU114/article/details/170248167</guid><author>UIU114</author><pubDate>Sun, 08 Nov 2026 08:00:00 +0800</pubDate><description><![CDATA[本题为整数拆分问题，要求将正整数 $ n $ 拆分为最少个完全平方数之和。可用 BFS 或动态规划求解：BFS 从 $ n $ 出发，每次减去一个完全平方数，首次到达 0 的步数即为答案；DP 则定义 $ dp[j] $ 为凑出 $ j $ 的最少平方数个数，状态转移为 $ dp[j] = \min(dp[j - k^2] + 1) $，按完全背包方式枚举。两者时间复杂度均为 $ O(n\sqrt{n}) $，适用于 $ n \leq 10^5 $。]]></description><category></category></item><item><title><![CDATA[P11962 [GESP202503 六级] 树上漫步]]></title><link>https://blog.csdn.net/UIU114/article/details/170191900</link><guid>https://blog.csdn.net/UIU114/article/details/170191900</guid><author>UIU114</author><pubDate>Sat, 07 Nov 2026 08:00:00 +0800</pubDate><description><![CDATA[题目P11962[GESP202503六级]树上漫步的核心在于：在树上从起点s出发，走偶数步能到达的点，等价于与s同色的点。利用树的二分染色性质，任意两点间路径长度的奇偶性唯一，且走法步数奇偶性不变。因此，从s出发能停在t当且仅当dist(s,t)为偶数，即s与t同色。通过BFS对树进行二分染色，统计每种颜色的点数，即可快速回答每个点的答案。时间复杂度O(n)，适用于大规模数据。]]></description><category></category></item><item><title><![CDATA[CF 2232C1 Seating Arrangement (Easy Version)]]></title><link>https://blog.csdn.net/UIU114/article/details/170149182</link><guid>https://blog.csdn.net/UIU114/article/details/170149182</guid><author>UIU114</author><pubDate>Fri, 06 Nov 2026 16:00:00 +0800</pubDate><description><![CDATA[本题通过动态规划解决座位安排问题，核心思想是将状态压缩为“已开桌数o”，dp[o]表示开o张桌时最多可坐人数。关键在于：忽略具体人员与顺序，仅关注空位数量；贪心不可行，因开桌影响后续可用空位。状态转移分三种情况：跳过、开新桌（需未达上限）、加入（需有空位）。代码实现中使用nd数组避免覆盖，最后取dp数组最大值作为答案。复杂度O(n·min(x,n))，适用于n总和≤3000的规模。]]></description><category></category></item><item><title><![CDATA[P7012 [CERC2013] Draughts]]></title><link>https://blog.csdn.net/UIU114/article/details/170131290</link><guid>https://blog.csdn.net/UIU114/article/details/170131290</guid><author>UIU114</author><pubDate>Fri, 06 Nov 2026 08:00:00 +0800</pubDate><description><![CDATA[本题需对每个白子进行DFS搜索，枚举所有吃子顺序以求最大吃子数。因吃子会改变棋盘状态（中间黑子消失、起点空出、落点变白），后续可走路径依赖已吃棋子，故不能用BFS（无法保证状态唯一）。关键细节：1）必须遍历所有白子起点；2）直接读棋盘判断空/黑/白，避免冗余状态数组；3）一次吃子改三格，回溯时三处恢复，顺序对称，缺一不可；4）恢复时应还原原值，而非假设值。代码中三个典型错误：恢复错位、漏恢复、误判可吃对象，均源于状态管理混乱。最终通过清晰的状态维护与对称操作，正确求解最长吃子链。]]></description><category></category></item><item><title><![CDATA[B4292 [蓝桥杯青少年组省赛 2022] 路线]]></title><link>https://blog.csdn.net/UIU114/article/details/170048824</link><guid>https://blog.csdn.net/UIU114/article/details/170048824</guid><author>UIU114</author><pubDate>Thu, 05 Nov 2026 16:00:00 +0800</pubDate><description><![CDATA[【代码】B4292 [蓝桥杯青少年组省赛 2022] 路线。]]></description><category></category></item><item><title><![CDATA[B3862 图的遍历（简单版）]]></title><link>https://blog.csdn.net/UIU114/article/details/170047914</link><guid>https://blog.csdn.net/UIU114/article/details/170047914</guid><author>UIU114</author><pubDate>Thu, 05 Nov 2026 08:00:00 +0800</pubDate><description><![CDATA[本文对比了图的遍历问题的两种解法：普通BFS（枚举每个点进行BFS，复杂度O(N(N+M))）与反图BFS（从大到小处理节点，利用反图BFS一次性确定每个点能到达的最大编号，复杂度O(N+M)）。后者通过逆向建图和贪心赋值，确保每个点仅被访问一次，显著优化效率。核心思想是：若某点v未被赋值，则其答案为自身（因无法到达更大的已处理点），并通过反图传播至所有可到达v的点，最终得到最优解。]]></description><category></category></item><item><title><![CDATA[P1700 [USACO19OPEN] Milk Factory B]]></title><link>https://blog.csdn.net/UIU114/article/details/169946600</link><guid>https://blog.csdn.net/UIU114/article/details/169946600</guid><author>UIU114</author><pubDate>Wed, 04 Nov 2026 08:00:00 +0800</pubDate><description><![CDATA[本题关键在于：N个点、N-1条边且连通的图必为树，无环。定向无法形成有向环，故答案点出度必为0（汇点）。只需在反图中对每个汇点进行BFS，判断是否能到达所有点。若某汇点可达全部节点，则为唯一解；否则无解。代码通过反图转换“入可达”为“出可达”，仅需一次遍历即可判定，时间复杂度优化至O(N)。]]></description><category></category></item><item><title><![CDATA[P17294 [ICPC 2026 Xi‘an I] North and South]]></title><link>https://blog.csdn.net/UIU114/article/details/169952103</link><guid>https://blog.csdn.net/UIU114/article/details/169952103</guid><author>UIU114</author><pubDate>Wed, 04 Nov 2026 06:00:00 +0800</pubDate><description><![CDATA[本题核心思路是将“使数组元素相等”转化为“使前缀和偏差为零”。设目标值 $ v = \text{sum}/n $，若不可整除则无解。令 $ c[i] = a[i] - v $，问题变为通过偶数长度区间交替加减操作使 $ c $ 全为 0。引入前缀和 $ P[k] = \sum_{i=1}^k c[i] $，关键引理表明：每次操作仅对同奇偶下标的 $ P $ 增加 1。因此，$ P[k] $ 只能增加，若初始 $ P[k] &gt; 0 $ 则无解；且 $ P[n] $ 恒为 0，无需考虑。将需求 $ t[k]]></description><category></category></item><item><title><![CDATA[CF1847C Vampiric Powers, anyone?]]></title><link>https://blog.csdn.net/UIU114/article/details/169849302</link><guid>https://blog.csdn.net/UIU114/article/details/169849302</guid><author>UIU114</author><pubDate>Tue, 03 Nov 2026 08:00:00 +0800</pubDate><description><![CDATA[本题核心思路是将“任意子段异或”转化为“两个前缀异或的异或”。定义前缀异或 $ P[0]=0, P[k]=a_1\oplus\cdots\oplus a_k $，则区间 $[i,m]$ 的异或为 $ P[m] \oplus P[i-1] $。操作中每步追加值为 $ q \oplus c $（$ c $ 为当前末尾前缀），新末尾前缀变为 $ q $，即状态仅在集合 $ V = {P[0],\dots,P[n]} $ 内转移。最终所有可达值均为 $ V $ 中两数异或，答案即为 $ \max{p \oplus ]]></description><category></category></item><item><title><![CDATA[P1460 [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins]]></title><link>https://blog.csdn.net/UIU114/article/details/169744846</link><guid>https://blog.csdn.net/UIU114/article/details/169744846</guid><author>UIU114</author><pubDate>Mon, 02 Nov 2026 08:00:00 +0800</pubDate><description><![CDATA[本文详解洛谷P1460《健康的荷斯坦奶牛》三种解法：位掩码枚举、DFS回溯与迭代加深。位掩码通过二进制状态表示饲料选择，枚举所有组合（最多32768种），逐项验证维生素需求；DFS采用递归回溯，按编号顺序搜索，剪枝优化避免无效分支；迭代加深则从1种开始逐层试探，首次成功即为最优解，保证字典序最小。三者均高效处理G≤15的约束，核心思想为状态压缩与剪枝优化。]]></description><category></category></item><item><title><![CDATA[P1481 魔族密码]]></title><link>https://blog.csdn.net/UIU114/article/details/169653473</link><guid>https://blog.csdn.net/UIU114/article/details/169653473</guid><author>UIU114</author><pubDate>Sun, 01 Nov 2026 08:00:00 +0800</pubDate><description><![CDATA[本题为洛谷P1481“魔族密码”，是一道典型的动态规划题。核心思想是：按字典序排序后，对每个单词判断其是否能接在前面单词之后（即长度更长且为前缀）。利用compare(0, len, str)函数判断前缀关系，状态dp[i]表示以第i个单词结尾的最长词链长度，转移方程为dp[i] = max(dp[i], dp[j] + 1)。最终输出最大值。时间复杂度O(n²)，需注意排序与前缀判断。]]></description><category></category></item><item><title><![CDATA[CF2112C Coloring Game]]></title><link>https://blog.csdn.net/UIU114/article/details/169563119</link><guid>https://blog.csdn.net/UIU114/article/details/169563119</guid><author>UIU114</author><pubDate>Sat, 31 Oct 2026 08:00:00 +0800</pubDate><description><![CDATA[该题核心是统计满足条件的三元组数量：三个数之和大于数组最大值，且前两数之和大于第三数。优化思路为固定最大数 $a_k$，转化为在前 $k$ 个元素中统计两数之和大于 $\max(a_k, mx - a_k)$ 的配对数。利用双指针技巧，数组有序时可线性处理每组 $k$，时间复杂度从 $O(n^3)$ 降至 $O(n^2)$，避免超时。]]></description><category></category></item><item><title><![CDATA[P16237 [蓝桥杯 2026 省 B] 应急布线]]></title><link>https://blog.csdn.net/UIU114/article/details/169465240</link><guid>https://blog.csdn.net/UIU114/article/details/169465240</guid><author>UIU114</author><pubDate>Fri, 30 Oct 2026 08:00:00 +0800</pubDate><description><![CDATA[本题通过并查集求解连通块数量，目标为用最少跳线使所有计算机连通。设连通块数为 $ C $，则最少需 $ C-1 $ 条跳线。第二问将 $ 2(C-1) $ 个线头均摊至 $ N $ 台机器上，最小化单机最大负载，答案为 $ \lceil \frac{2(C-1)}{N} \rceil $，可通过构造证明可达。代码实现简洁高效。]]></description><category></category></item><item><title><![CDATA[P1233 [ICPC 2001 Taejon R] 木棍加工]]></title><link>https://blog.csdn.net/UIU114/article/details/169366162</link><guid>https://blog.csdn.net/UIU114/article/details/169366162</guid><author>UIU114</author><pubDate>Thu, 29 Oct 2026 08:00:00 +0800</pubDate><description><![CDATA[本题通过将木棍按长度降序排序，转化为求宽度序列的最少不上升子序列划分。利用动态规划求最长上升子序列长度 $ L $，并按 $ dp[i] $ 值分堆，证明同一堆内元素不增，且堆数恰为 $ L $。因此答案即为最长严格上升子序列的长度。]]></description><category></category></item><item><title><![CDATA[P1308 [NOIP 2011 普及组] 统计单词数]]></title><link>https://blog.csdn.net/UIU114/article/details/168656444</link><guid>https://blog.csdn.net/UIU114/article/details/168656444</guid><author>UIU114</author><pubDate>Wed, 28 Oct 2026 08:00:00 +0800</pubDate><description><![CDATA[题目要求统计字符串s1在s2中出现的次数及首次出现位置。由于输入含空格，需用getline读取。注意cin与getline混用时需用cin.ignore()清除换行符残留。将两字符串转为小写后，遍历s2按空格分割单词，匹配s1并记录次数与首位置。若未找到，输出-1；否则输出次数和起始位置。]]></description><category></category></item><item><title><![CDATA[P1271 【深基9.例1】选举学生会]]></title><link>https://blog.csdn.net/UIU114/article/details/168977901</link><guid>https://blog.csdn.net/UIU114/article/details/168977901</guid><author>UIU114</author><pubDate>Tue, 27 Oct 2026 08:00:00 +0800</pubDate><description><![CDATA[本题考察数据规模对算法选择的影响。虽可排序（O(m log m)）通过，但最优解为计数排序（桶思想），时间复杂度O(m + n)，仅需约2×10⁶次操作，效率提升显著。利用数组下标统计频次，避免排序开销，体现“根据数据量选算法”的核心思想。]]></description><category></category></item><item><title><![CDATA[CF2241D An Alternative Way]]></title><link>https://blog.csdn.net/UIU114/article/details/168772999</link><guid>https://blog.csdn.net/UIU114/article/details/168772999</guid><author>UIU114</author><pubDate>Mon, 26 Oct 2026 08:00:00 +0800</pubDate><description><![CDATA[该题核心思想是将数组差值 $ c = b - a $ 的前缀和 $ d $ 作为关键变量。操作 $[l, r]$ 相当于在 $ c $ 上对位置 $ l $ 加 1、$ r+1 $ 减 1（边界处理），其效果等价于使前缀和 $ d_l $ 增加 1，$ d_{r+1} $ 减少 1。由于每次操作只会让某些前缀和增加或不变，不会使其减小，因此若存在 $ d_k &lt; 0 $，则无解。反之，只要所有 $ d_k \geq 0 $，即可通过独立操作 $[k, k+1]$（或 $[n,n]$）来逐个“拧高”前缀]]></description><category></category></item></channel></rss>