Posts

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

VSCode Remote-SSH 报错修复记录 现象 重装云服务器系统后，VSCode 远程连接失败，报错内容类似： @ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @ Host key for 124.222.53.248 has changed and you have requested strict checking. Host key verification failed. Offending ECDSA key in C:\Users\hp/.ssh/known_hosts:11 原因 重装服务器系统后，服务器的 SSH host key（主机密钥）发生了改变，但本地的 ~/.ssh/known_hosts 文件里仍保留着重装前旧系统的指纹记录。 SSH 出于防止中间人攻击的安全考虑（strict checking），当发现同一 IP 的主机指纹 与本地记录不一致时，会拒绝连接，而 VSCode 的 Remote-SSH 插件无法处理这种 交互式确认，因此直接失败。 解决步骤 1. 删除本地旧 host key 在本地电脑执行（Windows 下可用 Git Bash / PowerShell / CMD 均可）： 1 ssh-keygen -R 124.222.53.248 将 124.222.53.248 替换为你的服务器 IP。 ...

P1119 灾后重建 我理解的题目意思 给出N个点、M条双向边、点存在的最早时间ti。做Q次查询t时刻点x和y之间的最短距离，若此时无法连通，则输出-1。 $$t_0​≤t_1​≤⋯≤t_{N−1}​$$ $$查询的 t 是不下降的$$ $$1≤N≤200，0≤M≤N×(N−1)/2​，1≤Q≤50000,所有输入数据涉及整数均不超过 10^5$$解题思路 每次查询时遍历小于等于t的tk,使用floyd算法计算加入点k之和的最短路径长度数组，初始化最短路径长度数组为一个较大的数inf，若f[x][y]=inf则输出-1，否则输出f[x][y]。 代码： #include <iostream> #include <algorithm> #define len 205 using namespace std; int a[len]; int f[len][len]; int n, m; void update(int k) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (f[i][j] > f[i][k] + f[k][j]) f[i][j] = f[i][k] + f[k][j]; } } return; } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; f[i][i] = 0; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j) f[i][j] = 1e9; } } for (int s = 1; s <= m; s++) { int x, y, w; cin >> x >> y >> w; f[x][y] = f[y][x] = w; } int q; int k = 0; cin >> q; for (int s = 1; s <= q; s++) { int x, y, t; cin >> x >> y >> t; while (a[k] <= t && k < n) { update(k); k++; } if (t < a[x] || t < a[y]) cout << -1 << endl; else { if (f[x][y] == 1e9) cout << -1 << endl; else cout << f[x][y] << endl; } } return 0; } 参考 Time_Rune

P1118 [USACO06FEB] Backward Digit Sums G/S 我理解的题目意思 给两个正整数 n,sum 。将数字从 1 到 n 按某种顺序写下来，然后将相邻的数字相加，得到一个数字更少的新列表,重复这个过程，直到只剩下一个数字,若这个数字等于sum，则输出满足这个条件的字典序最小的序列1~n;否则不输出。 $$1≤N≤12，1≤sum≤12345$$解题思路 数组ai每次相邻相加的过程，最终结果的系数就是杨辉三角的对应行。所以先预处理出c记录杨辉三角系数，再进行深度优先搜索尝试所有顺序，设置一个pos，按字典序尝试数字填入a[pos]，结合剪枝优化时间，在字典序尝试之前先判断已经填入的 a[i]*c[i] 之和是否大于sum，大于则停止搜索。当pos等于n时，判断 a[i]*c[i] 之和是否等于sum。 代码： #include <iostream> #include <algorithm> using namespace std; int n, sum; int a[15],c[15]; bool vis[15]; void ini(){ for(int i=0;i<n;i++){ c[i]=1; for(int j=1;j<=i;j++){ c[i]=c[i]*(n-j)/j; } } } int calc(){ int res=0; for(int i=0;i<n;i++){ res+=a[i]*c[i]; } return res; } bool dfs(int pos){ if(pos==n)return calc()==sum; int csum=0; for(int i=0;i<pos;i++){ csum+=a[i]*c[i]; } if(csum>sum)return false; for(int i=1;i<=n;i++){ if(!vis[i]){ vis[i]=true; a[pos]=i; if(dfs(pos+1))return true; vis[i]=false; } } return false; } int main() { cin >> n >> sum; ini(); if(dfs(0)){ for(int i=0;i<n;i++){ cout<<a[i]<<" "; } } return 0; }