主页

题意 给你一个N*M的地图(N,M<=20),地图上’#’表示障碍物，’B’表示炸弹，数字表示宝藏序号（宝藏+炸弹个数 <=8），每个宝藏有价值（-200<=v<=200），’S’表示出发点。每次移动可以从一个格子移动到相邻格子(上下左右)。寻找一条路径从’S’出发再回到’S’的封闭路径，移动步数记为K，这个路径所包围的宝藏价值总和记为V，则这条路径的价值为V-K。题目即是求可行的最大的路径价值，并且不能包围炸弹。 题解 可以将炸弹转化为v=-1600的宝藏，这样可确保选不到炸弹。 状压一下选的宝藏，之后便可以跑dp。 那么怎么确定选中了哪些宝藏呢？可以运用射线法（很好理解、但之前不知道0.0）。 射线法 可以从点向任意方向发出一条射线，判断与这个...

题意 给你一个长度为 $N$ 的打乱的排列 $P$，每个数字移动的代价为： $A_i$, 向任意位置移动 $B_i$, 移动到最左边 $C_i$, 移动到最右边 求恢复成升序需要付出的最小代价。 题解 每个数字，只可能付出 $0/A_i/B_i/C_i$ 的代价，因此最终的方案一定是分为了三段。第一段全付出了B的代价，第二段中有位置刚好的，或需要付出A来调整的，第三段全付出了C的代价。 所以我们可以令 $dp_i$ 表示第二段在 $i$ 前一位结束的最小代价，可以写出以下式子： \[dp_i = min(preB_{i-1}, min_{j=1}^{pos_i-1}(dp_j+preA_{i-1}-preA_{j}))\] 解读一下，就是我们可以选择全选...

最近在修改 Ubuntu 20.10 系统的时区时发生了一些问题。 由于一开始安装的是 Ubuntu Server 后面因需求有增加又安装了 ubuntu-desktop，所以本能地在 GUI 界面找到了时区设置。但修改时区后却无法生效。 之后尝试使用 timedatectl set-timezone "Asia/Shanghai" 以设置时区，但提示 Access Denied （已经使用sudo了），所以只好去google了一下，找到了这篇文章，终于解决了问题。 rm /etc/localtime && ln -s /usr/share/zoneinfo/PRC /etc/localtime 希望 ubuntu-desktop 及 datetimectl ...

背景 CWOI Blog 这个概念被提出后，我就想到了通过 Gitlab 来进行协作编辑（因为之前开MC服也是通过这个来收集建议的），后面发现真的是非常适合： 审核文章：Developer 只能推送到其他分支，Maintainer 以上级别可以合并PR，通过PR来完成文章审核。 Gitlab CI：直接编译静态博客 Gitlab Pages：直接用来托管静态博客 Review Apps：在PR界面就可以创建一个预览环境 群组功能：外部人员无法看到文档源码 Pages Access Control 配置 那么如何避免外部人员看到Pages上部署的博客呢？一开始根本没想到官方会提供这一功能，都打算反代的时候加个 Basic Auth，或者后面写一个 OAut...

题面 给定一个简单无向图，求至少要加多少条边才能使图中包含至少一个简单奇环，求加边的方案数。 $ n,m \leq 10^5 $ Translated by @高飞@Luogu 输入格式 第一行 $n,m$，表示点、边的个数。 接下来 $m$ 行，每行两个整数 $a,b$，表示 $a$ 与 $b$ 之间有一条无向边。 输出格式 一行两个整数，表示最少加边的个数、加边的方案数。 题解 首先分析样例。 Input #1 4 4 1 2 1 3 4 2 4 3 Output #1 1 2 分析 #1 只需要添加紫色边或蓝色边即可构成奇环。 Input #2 3 3 1 2 2 3 3 1 Output #2 0 1 分析 #2 已经...

题面 给定一张带正权的无向图和一个源点，求边权和最小的最短路径树。 $ n,m \leq 3 \times 10^5 $ 感谢 @高飞@Luogu 提供的翻译 题解 什么是最短路径树 （其实CF英文题面中有）: 考虑一个连通无向图 $G$，一个以顶点 $rt$ 为根节点的最短路径树 $T$ 是图 $G$ 满足下列条件的生成树——树 $T$ 中从根节点 $rt$ 到其它顶点 $u$ 的路径距离，在图 $G$ 中是从 $rt$ 到 $u$ 的最短路径距离。 所以，我们可以先求出这个原图中，从源点出发到所有点距离最短是多少，在求的过程中，便可以记录每个被扩展的点的父亲，以建出一个最短路径树。 联系最小生成树的思路，我们可以发现每次扩展点的时候，被扩展到的点的父边只要...

题面 现有一个 $n$ 个点 $m$ 条边的无向图，要求用 ${1,2,3}$ 对每个点染色，使得相邻的两个点的权值的绝对值之差刚好为 $1$。现在需要求出任意一个方案，使得一共染了 $n_1$ 个 $1$，$n_2$ 个 $2$，$n_3$ 个 $3$。保证 $n_1+n_2+n_3=n$。 无解输出 NO。 有解输出一行 YES，并在下一行输出一个字符串，第 $i$ 位表示点 $i$ 的颜色。 $1 \leq n \leq 5 \times 10^3$, $0 \leq m \leq 10^5$ 题解 首先，如果有奇环显然无解。 多手推几次可以发现，$1,3$ 可以互换位置，$2$ 必定间隔出现。 所以可以进行二分图染色。 每个联通块中，必定有黑色全为 $2$...

题面 给出一棵 $n$ 个点的无根树，请在这棵树上选三个互不相同的节点，使得这个三个节点两两之间距离相等，输出方案数即可。 输入格式 每个测试点包含多组测试数据。 对于每组数据，第一行一个整数 $n$，表示节点数。 接下来 $n-1$ 行每行两个整数 $x,y$，描述一条边。 输入以一行一个 $0$ 作为结束。 输出格式 对于每组数据，输出一个整数表示答案。 样例输入 7 1 2 5 7 2 5 2 3 5 6 4 5 7 1 2 2 3 1 4 4 5 1 6 6 7 0 样例输出 5 2 数据范围 Subtask1 20pts: $sum n \leq 500$ Subtask2 35pts: $sum n \leq 5000$ Subtask3...