Posts

P1127 Word Chain 我理解的题目意思 找到所有单词的一种字典序最小的排列，使每个单词恰好使用一次，并且相邻两个单词满足前一个单词的尾字符等于后一个单词的首字符。 输入n个单词，相同的单词若出现了 k 次就需要输出 k 次。 $$1≤n≤1000$$解题思路 这个问题可以转化为有向多重图中的欧拉路径问题。 构造有向多重图 G=(V,E)，具体定义如下： 顶点集合 V：每个出现在任意单词首字符或尾字符中的字母对应一个顶点。 边集合 E：每个给定单词 S_i 对应一条有向边，其起点为单词的首字符，终点为单词的尾字符。即使两个单词的首尾字符相同，也将它们视为不同的边。 目标：找到所有单词的一种排列，使每个单词恰好使用一次，并且相邻两个单词满足前一个单词的尾字符等于后一个单词的首字符。 合法的单词排列与图中的欧拉路径一一对应。如果路径的起点与终点相同，则称其为欧拉回路。 进一步定义顶点的度数差： $\Delta(v)=out\_deg(v)-in\_deg(v)$ 欧拉路径存在的基本条件是： 所有与边关联的顶点必须属于同一个弱连通分量。 以下两种度数情况至少满足一种： 所有顶点的入度与出度相等； 恰好有一个顶点的度数差为 1，恰好有一个顶点的度数差为 -1，其余顶点的度数差均为 0。 在此基础上，可以得到以下定理。 定理一: 路径的起点选择 定理陈述： 如果一个有向多重图存在一条起点和终点不同的欧拉路径，那么起点必定是唯一一个满足下式的顶点 s： $out\_deg(s)-in\_deg(s)=1$ 证明： 设存在一条欧拉路径 P，其起点为 s，终点为 t，且 $s\ne t$。 由于欧拉路径需要经过图中的每一条边且每条边恰好一次，因此，对于任意既不是起点也不是终点的中间顶点 v，每次进入该顶点后都必须离开该顶点。于是，该顶点的入度与出度相等： $out\_deg(v)=in\_deg(v)$ 对于起点 s，路径从该顶点出发，但最终不会返回该顶点。因此，路径经过起点时，使用的出边比入边多一条，即： $out\_deg(s)=in\_deg(s)+1$ 从而得到： $\Delta(s)=1$ 同理，对于终点 t，路径最终进入该顶点并结束，因此使用的入边比出边多一条，即： $in\_deg(t)=out\_deg(t)+1$ 从而得到： $\Delta(t)=-1$ 综上，欧拉路径的起点是唯一一个满足 $\Delta(v)=1$ 的顶点，终点是唯一一个满足 $\Delta(v)=-1$ 的顶点，其余顶点的度数差均为 0。 因此，如果图中存在满足 $\Delta(v)=1$ 的顶点，那么在欧拉路径存在的前提下，该顶点必定是路径的起点，且起点唯一。 定理二：无解的度数条件 定理陈述： 如果一个有向多重图存在欧拉路径，则至多有一个顶点满足 $\Delta(v)=1$，至多有一个顶点满足 $\Delta(v)=-1$。 此外，如果存在一个满足 $\Delta(v)=1$ 的顶点，那么必须恰好存在一个满足 $\Delta(v)=-1$ 的顶点。 因此，如果有两个或更多顶点的度数差为 1，或者其他顶点的度数配置不满足上述条件，则不存在合法的单词排列。 ...

P1126 [CERC1996] 机器人搬重物 我理解的题目意思 一个 N×M 的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，机器人必须在最短的时间内从起点到终点。机器人接受的指令有： 向前移动 1 步（Creep）； 向前移动 2 步（Walk）； 向前移动 3 步（Run）； 向左转（Left）； 向右转（Right）。 每个指令所需要的时间为 1 秒。要求机器人完成任务所需的最少时间，若不能完成则输出-1。 $$1≤N,M≤50$$解题思路 输入 第一行为两个正整数 N,M，下面 N 行是储藏室的构造，0 表示无障碍，1 表示有障碍，数字之间用一个空格隔开。接着一行有 4 个整数和 1 个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东 E，南 S，西 W，北 N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。 处理输入：输入可以视为为网格的右下角坐标是否障碍，搜索需要网格点的网络是否障碍，这需要一个转换。因为一个障碍产生4个障碍网格点，机器人无法到边界，故扩充网格 N×M 到网格点网络 N+1×M+1，障碍的左上、上、左的点均为障碍点（包括自己）。 每次的操作 主体使用BFS进行搜索，考虑每次移动方向的变换：可以分为2部分先后考虑即换向、前进。 换向 在结构体中设置t记录当前方向，有4个方向可以选择： fx[5] = {0, -1, 1, 0, 0} fy[5] = {0, 0, 0, -1, 1} 方向按NSWE的顺序对应上下左右和1234，按只有顺时针旋转来考虑： ft[5] = {0, 1, 4, 2, 3} 实际上有逆时针旋转，故改变4个方向需要时间： abc[5] = {0, 1, 2, 1, 0} ...

VS Code C++ 调试报错：preLaunchTask exit code -1 的排查与解决 今天在 VS Code 里写洛谷 P1126《机器人搬重物》，代码写完之后准备按 F5 调试，结果还没开始调试，VS Code 先给我弹了一个错误： 1 The preLaunchTask 'C/C++: g++.exe build active file' terminated with exit code -1. 一开始我第一反应就是： 是不是代码又写崩了？ 毕竟 P1126 本身就是 BFS，边界、数组、方向这些地方稍微写错一点，就很容易出问题。 但不对啊，我数据还没输呢，用hello world试了一下报同样的错。 整个过程比较曲折，中间还碰到了 chcp、tasks.json、launch.json、g++、gdb、VS Code 扩展等一堆东西。这里把整个过程记录下来，之后如果再碰到类似问题，也可以直接回来查。 一、刚开始的报错 按下 F5 后，VS Code 弹出： 1 The preLaunchTask 'C/C++: g++.exe build active file' terminated with exit code -1. 然后终端里面还有： 1 2 3 4 5 cmd /c chcp 65001>nul && D:\mingw64\bin\g++.exe -fdiagnostics-color=always -g D:\code_world\code_cpp\hello.cpp -o D:\code_world\code_cpp\hello.exe 'chcp' 不是内部或外部命令，也不是可运行的程序 Build finished with error(s). The terminal process failed to launch (exit code: -1). 最引人注意的就是： ...

Windows 11 磁盘清理实战：从 105 GB 到 117 GB 记录一次实际的 C 盘清理过程：先盘点空间，再按白名单保留开发环境和个人数据，最后处理可以安全删除的缓存。文中也记录了几个真正踩过的坑，以及后来整理出来的 PowerShell 脚本。 一、先把需求说清楚 这次清理最开始只有一个需求，内容很简单： 清理磁盘空间；VSCode 周边的 Git、Python、Go、JDK 等开发工具也算保留范围，Office、Zotero、Anki 等个人数据相关软件也不动。 环境基线 项目 初始状态 机器 笔记本（16 寸） 系统 Windows 11 家庭中文版 C 盘 148 GB 已用 / 104.94 GB 可用 D 盘 23.4 GB 已用 / 197.4 GB 可用 物理内存 15.7 GB，仅剩 3.9 GB 空闲 权限 非管理员（IsAdmin: False） 二、先侦察：到底是谁占了空间？ 清理磁盘最怕的不是删得慢，而是删错。尤其是 Windows，很多目录名字看起来很像缓存，实际上可能放着配置、项目或者个人数据。 所以这次没有上来就删，而是先把 C 盘一层层测一遍，看看空间到底花在哪里。 2.1 逐层下钻测量 这里主要用 Get-ChildItem -Recurse -File 配合 Measure-Object Length -Sum 统计目录实际大小。-Force 也不能省，否则隐藏文件和系统文件容易被漏掉。 ...

P1125 [NOIP 2008 提高组] 笨小猴 我理解的题目意思 一个字符串中出现次数最多的字母的出现次数是 maxn ，minn 是出现次数最少的字母的出现次数，如果 maxn−minn 是一个质数,那么输出 Lucky Word，再换行输出 maxn−minn 的值；否则输出 No Answer,，换行输出 0。 $$字符串长度小于 100$$解题思路 依题意模拟即可，用数组b记录字母出现次数，遍历出maxn、minn，再判断maxn−minn是否为质数。 代码： #include <iostream> #include <algorithm> using namespace std; char a[105]; int main() { cin >> a; int b[26] = {0}; for (int i = 0; a[i] != '\0'; i++) { b[a[i] - 'a']++; } int maxn = -1, minn = 105; for (int i = 0; i < 26; i++) { if (b[i] > 0) { maxn = max(maxn, b[i]); minn = min(minn, b[i]); } } int ans = maxn - minn; for (int i = 2; i <= ans / 2; i++) { if (ans % i == 0 && ans != 2) { cout << "No Answer" << endl << 0; return 0; } } if (ans < 2) cout << "No Answer" << endl << 0; else cout << "Lucky Word" << endl << ans; return 0; }

P1124 [ZJOI2001] 文件压缩 我理解的题目意思 对一个长度为 n 的字符串 S，首先根据它构造 n 个字符串，其中第 i 个字符串由将 S 的前 i−1 个字符置于末尾得到。然后把这 n 个字符串按照首字符从小到大排序，如果两个字符串的首字符相等，则按照它们在 S 中的位置从小到大排序。排序后的字符串的尾字符可以组成一个新的字符串 S′ ，它的长度也是 n，并且包含了 S 中的每一个字符。最后输出 S′ 以及 S 的首字符在 S′ 中的位置 p。 读入 S′ 和 p，输出字符串 S. $$1≤n≤10000，S 仅含小写字母$$解题思路 输入输出样例 #1 输入 #1 7 xelpame 7 输出 #1 example 注意到，S' 只是把原字符串 S 中的所有字符重新排列了一下，所以 S' 和 S 包含的字符完全相同。 我们把 S' 从小到大排序，得到： F = sort(S') 现在观察排序后的每一行。 原来的第 j 个字符串是： S[j] S[j+1] ... S[n] S[1] ... S[j-1] 所以： ...

P1123 取数游戏 我理解的题目意思 一个 N×M 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻 8 个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。 $$1≤N,M≤6，1≤T≤20，ai,j​≤10^5$$解题思路 注意到数据量很小，可以dfs最大的数字和，维护一个chosen数组做一个待选择数字是否有相邻数字被选择的判断。 代码： #include <iostream> #include <algorithm> using namespace std; int t, n, m, ans; int a[10][10]; // 检查 (x,y) 是否与已选的格子相邻 bool ok(int x, int y, bool chosen[10][10]) { for (int dx = -1; dx <= 1; dx++) { for (int dy = -1; dy <= 1; dy++) { if (dx == 0 && dy == 0) continue; int nx = x + dx; int ny = y + dy; if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && chosen[nx][ny]) return false; } } return true; } void dfs(int x, int y, int sum, bool chosen[10][10]) { if (x > n) { ans = max(ans, sum); return; } int nx = (y == m) ? x + 1 : x; int ny = (y == m) ? 1 : y + 1; dfs(nx, ny, sum, chosen); if (ok(x, y, chosen)) { chosen[x][y] = true; dfs(nx, ny, sum + a[x][y], chosen); chosen[x][y] = false; } } int main() { cin >> t; while (t--) { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j]; ans = 0; bool chosen[10][10] = {}; dfs(1, 1, 0, chosen); cout << ans << endl; } return 0; }

P1122 最大子树和 我理解的题目意思 给出n个点，点具有点权a[i]，n-1条双向边将点连接为一个树，通过剪枝使得剩下的点权和最大，输出最大值。 $$1≤n≤16000，a_i范围在 [−10^9,10^9] 内$$解题思路 使用vector数组记录点的邻接点，使用f[i]记录保留a[i]的最大点权和。初始化f[i]为a[i],dfs点i的邻接点k的最大点权和，若f[k]>0，则f[i]=f[i]+f[k]，同时设置一个fa用于避免反向搜索到起点。 代码： #include <iostream> #include <vector> using namespace std; vector<int> ad[20000]; int n; int ans = 1 << 31; int a[20000]; int f[20000]; void dfs(int u, int fa) { f[u] = a[u]; for (int i = 0; i < ad[u].size(); i++) { int t = ad[u][i]; if (t != fa) { dfs(t, u); if (f[t] > 0) { f[u] += f[t]; } } } } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n - 1; i++) { int x, y; cin >> x >> y; ad[x].push_back(y); ad[y].push_back(x); } dfs(1, 0); for (int i = 1; i <= n; i++) ans = max(ans, f[i]); cout << ans; return 0; } 参考 Mutsumi_0114

P1121 环状最大两段子段和 我理解的题目意思 给出一段长度为 n 的环状序列 a，即认为 a1​ 和 an​ 是相邻的，选出其中连续不重叠且非空的两段使得这两段和最大。 $$2≤n≤2×10^5，−10^4≤a_i​≤10^4$$解题思路 从前到后计算出到a[i]之前的最大字段和af[i]，从后到前计算出到a[i+1]之前的最大字段和ab[i],遍历枚举出最大的af[i]+ab[i+1]作为初始的环状最大两段子段和ans。 再计算将max方法改为min，从前到后计算出到a[i]之前的最小字段和mf[i]，从后到前计算出到a[i+1]之前的最小字段和mb[i],遍历枚举出最小的af[i-1]+ab[i+1]作为最小两段子段和t，因为最大两段子段可以相邻。 比较ans和sum-t，ans=max(ans,sum-t). 代码： #include <iostream> #include <algorithm> #include <cstring> #define size 300000 using namespace std; int n; int a[size], af[size], ab[size], mf[size], mb[size]; int sum; int getmin(int *arr, int l) { mf[1] = a[1]; for (int i = 2; i <= l; i++) mf[i] = min(mf[i - 1], 0) + a[i]; for (int i = 2; i <= l; i++) mf[i] = min(mf[i - 1], mf[i]); int ans = 1ll << 31ll - 1ll; mb[l] = a[l]; for (int i = l - 1; i > 1; i--) mb[i] = min(mb[i + 1], 0) + a[i]; for (int i = l - 1; i > 1; i--) mb[i] = min(mb[i + 1], mb[i]); for (int i = 2; i <= l- 1; i++) ans = min(ans, mf[i - 1] + mb[i + 1]); return ans; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; } af[1] = a[1]; for (int i = 2; i <= n; i++) af[i] = max(af[i - 1], 0) + a[i]; for (int i = 2; i <= n; i++) af[i] = max(af[i - 1], af[i]); int ans = 1ll << 31ll; ab[n] = a[n]; for (int i = n - 1; i > 1; i--) ab[i] = max(ab[i + 1], 0) + a[i]; for (int i = n - 1; i > 1; i--) ab[i] = max(ab[i + 1], ab[i]); for (int i = 1; i <= n - 1; i++) ans = max(ans, af[i] + ab[i + 1]); // ans = max(ans, sum - getmin(a, n - 1)); ans = max(ans, sum - getmin(a + 1, n - 1)); cout << ans; return 0; } 参考 zhy137036

P1120 [CERC 1995] 小木棍 我理解的题目意思 有一些同样长的木棍，把这些木棍随意砍成几段，直到每段的长都不超过 50。给出n段小木棍的长度,找出原始木棍的最小可能长度。 $$1≤n≤65，1≤a_i​≤50$$解题思路 首先确定原始木棍的长度范围，也就是搜索范围： 原始木棍数量大于等于2，长度len上限是$\frac{1}{2} \sum_{i=1}^{n}a_i$，下限为$max(a_i)$。 原始木棍数量等于1,长度len$=\sum_{i=1}^{n}a_i$，直接输出就行。 对于原始木棍数量大于等于2的情况，使用dfs进行搜索，要进行几个剪枝，下面是构造过程： 先对a[i]进行从大到小排序，因为更小的小木棍可以更灵活地组成木棍，要后使用。 设置一个used数组记录哪些小木棍已使用。 使用参数last,rest,k分别表示上一个使用的小木棍、木棍剩余需要长度、填充的第几个木棍。 当rest=0时，判断凑成木棍个数是否满足，若不满足则从1到n进行dfs搜索未访问的小木棍； 当rest!=0时，从last到n进行进行dfs搜索未访问的小木棍，这里可以进行几个剪枝：a[i] > rest就跳过，搜索下一个；搜索完之后，如果a[i] = rest，直接返回false；跳过相同长度的木棍。 代码： #include <iostream> #include <algorithm> #include <cstring> using namespace std; int n; int a[70]; bool used[70]; int sum; int len; int m; bool cmp(int a, int b) { return a > b; } bool dfs(int last, int rest, int k) { if (rest == 0) { if (k == m) return true; int i = 1; while (i <= n && used[i]) i++; if (i > n) return false; used[i] = true; if (dfs(i, len - a[i], k + 1)) return true; used[i] = false; return false; } for (int i = last; i <= n; i++) { if (used[i] || a[i] > rest) continue; used[i] = true; if (dfs(i, rest - a[i], k)) return true; used[i] = false; if (a[i] == rest) return false; // 跳过相同长度的木棍 while (i + 1 <= n && a[i + 1] == a[i]) i++; } return false; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; } sort(a + 1, a + 1 + n, cmp); for (len = a[1]; len <= sum / 2; len++) { if (sum % len != 0) continue; fill(used, used + n + 1, false); m = sum / len; used[1] = true; if (dfs(1, len - a[1], 1)) { cout << len; return 0; } // used[1] = false; //搜索程序本身已经处于时间复杂度临界状态，而这条语句本身不改变搜索逻辑。虽然只是一次赋值，但整个程序可能运行了大量 DFS。 } cout << sum; return 0; } 参考 Kaori