Q779’s Blog

全源最短路 Johnson算法 本文写于较早时期，之前对Dijkstra的理解不是很透彻 已经修改了部分显然错误的内容，有空会再仔细检查的 模板题：P5905 【模板】Johnson 全源最短路 题意简述：给定一个包含 \(n\) 个结点和 \(m\) 条带权边的有向图，求全源最短路，可能有负权重的边、重边、自环，部分数据卡 SPFA 算法（还特地针对了SLF优化） 题意很明确，就是卡SPFA、Dijkstra、Floyd的 这题用SPFA可以被卡成\(O(n^2m)\)，Dijkstra不能处理负权重的边，Floyd\(O(n^3)\)肯定超时 说了这么多，就是为了引出我们要讲的 Johnson 算法 Johnson算法可以判断给定的图中有无负环，在无负环时能给出全源最短路时间复杂度 \(O(n^2\log m)\) （Dijkstra采用优先队列优化，详细的分析可以看这边link） Johnson算法的核心为重新赋予权值，使得边权变成非负的新边权，而在运行过程中以Bellman-Ford和Dijkstra（以下提到的Dijkstra都用优先队列优化）作为自己的子程序 一、算法...

无序数组交换任意两个元素 最少交换次数 题目： 属于是经典题了，做完可以去做一下 UOJ233 【IOI2015】Sorting （确信 给定长度为 \(n\) 的排列，将元素升序排序，每次可以交换任意两个元素，最少要交换几次？ 如果是交换相邻两个元素，那就是逆序对的个数，这个本文不会提及（因为已经说完了 例： input: 6 1 4 2 3 5 6 output: 2 swap 2 4 swap 4 3 题解： 对于每个元素，我们将该元素和它的正确位置建边 最后一定是 \(1\sim n\) 个环（自环也算） 对于有 \(k\) 个元素的环，最少交换次数为 \(k-1\) 假设共有 \(p\) 个环，对于第 \(i\) 个环，有 \(k_i\) 个元素，则它的最少交换次数为 \(k_i - 1\) 因此 \[ \mathtt{ans} = \sum\limits_{i=1}^{p}{(k_i-1)} = \sum\limits_{i=1}^{p}{k_i} - p \] 显然 \[ n = \sum\limits_{i=1}^{p}{k_i} \] 所以答案就是 \...

浅谈补码的原理和正确性 前言 upd 2022.2.14 我就该早点看《计算机组成原理》，补码的定义就是 一个 \(n\) 位二进制数 \(N\) 的二进制补码定义为 \(2^n-N\) 不过本文还是严谨证明了它的正确性，以下为原文 补码是怎么来的？ 负数的补码为什么是按位取反（除了符号位）再加 \(1\) ? 补码的正确性能保证吗？ 补码背后的数学原理是什么？ 本文围绕原理和正确性介绍了补码 一、我们为什么用补码？ 我们以 \(8\) 位二进制数为例 \(8\) 位无符号数，可以表示 \(0\sim255\) 以内的数（即 \(00000000 \sim 11111111\) ），那么如果我们要表示负数呢？ 我们都知道正、负号能够表示正、负数，可是计算机“看不懂“，它只能识别 \(0,1\) 于是，就出现了原码 最高位表示数的正负，\(0\) 表示 正 ，\(1\) 表示负 \(8\) 位有符号数，以原码形式存储则可以表示 \(0 \sim 127\)（即 \(00000000 \sim 01111111\) ） 和 \(-127 \sim 0\) （即 \(111111...

ubuntu ibus输入法 突然无法输入 （延迟过高） 解决方法 前言 ibus拼音输入法最近不知道为何出现了一些异常问题（经常卡死） 被困扰了很久后，终于找到了解决办法 upd.20220423 在中文维基上查到了这样的资料 由于读取sqlite词库时有大量的IO操作，ibus-pinyin在系统高负载时输入时有卡住的现象。 upd.20220423 fcitx差点把你们可爱的q779给整没了，现在他继续用ibus了（重装了一遍） upd.20230608 有位热心网友提供了一些参考： 一、具体表现 写代码时，突然键盘像失灵了一样打不出字，过了好一会才慢慢显示出来 可以说延迟太高了 在此期间终端却可以打开，鼠标也可以正常移动 关闭窗口什么的都没问题，就是打不出字 二、解决方法 如果您的ubuntu中除了ibus拼音输入还有英文输入，那这个方法必定有效 首先切换到en，即英语输入(右上角wifi图标旁边) 然后ctrl+alt+t打开终端 输入 ibus restart 重启ibus拼音输入法 切换回ibus输入法，然后你原先输入的就出现了！ 而且可以正常使用了！ ...

ubuntu VMware报错could not open…解决方法 前言 本人在使用VMware时报了这个错 could not open /dev/vmmon:?????? 经过多方查阅资料，为大家提供一个有效的解决办法 一、具体表现 安装好VMware，虚拟机也创建完了 一运行结果就报错了 一开始以为权限问题，用root打开也一样(显然没用) 二、解决方法 需要关闭安全启动 (\(\mathrm{\color{black}{secure \ boot}}\)) 安全启动设计之初作用是防止恶意软件侵入 事实上它能够做到的仅仅是当电脑引导器被病毒修改之后，它会给出提醒并拒绝启动 因此基本上没什么用 什么？在哪里关闭？？ 当然是BIOS里 进入BIOS (开机后出现电脑品牌的图标时狂按F12) 下面看我拍的照片就懂了吧… 注:我的电脑是DELL的，其他品牌的我不知道 图片可能有点糊，还请谅解 改完记得保存哦！ 然后打开ubuntu，虚拟机就可以正常运行了 总结 本文介绍了因安全启动导致的报错的解决方法

ubuntu 追逐鼠标指针的小猫~Oneko 前言 最近发现了一个有趣的软件 Oneko 可以让一只小猫追着鼠标指针跑 是不是很有趣？ 一、下载Oneko 打开终端 sudo apt install oneko 安装即可 然后它就会在应用程序中了 二、使用Oneko 只要输入这个指令就行 oneko 然后就会有以下效果 Oneko 或者也可以添加到收藏夹后直接单击 不过关闭需要右键，选择Oneko STOP 三、自定义Oneko 官方给的参数如下 Usage: oneko [<options>] Options are: -display <display> : Neko appears on specified display. -fg <color> : Foreground color -bg <color> : Background color -speed <dots> -time <microseconds> -idle <dots> -name <name>...

ubuntu 显示键盘按键 前言 在看一些主播玩游戏时，他们屏幕上会有一个虚拟键盘，可以显示按键 当时觉得很神奇，就想着给ubuntu也弄一个 庆幸的是，ubuntu的确有这种软件 一、KeyMon简介 这个软件叫key-mon，全称Keyboard Status Monitor，即键盘状态监视器 注:截图时我按住了shfit键 不过相对于别的软件，这个就显得有些简单 但不可否认的确有效果 二、安装步骤 打开终端 sudo apt install key-mon 安装即可 适用于ubuntu18.04，目前ubuntu20.04也可以用 三、自定义设置 希望更好的体验？ 右键选择Settings...设置就可以了 总结 本文介绍了KeyMon的安装方法 显示键盘按键就这么简单

linux及windows对拍程序 C++ 前言 OI赛制的比赛中，选手不能看到自己的成绩，那么如何保证代码正确呢？ 1.水品高 秒切 2.暴力+对拍 尝试调正解 本文给出了linux和windows的对拍程序 一、什么是对拍？ 在比赛中，某道题已经写出了暴力解法（须保证正确），开始尝试写正解 我们就可以用到对拍程序，用于对比暴力解法和尝试解法的输出结果，以判断该解法的是否是正解 注:暴力解法通常跑不了很大的点，因此对拍时数据不强，即使正确也未必是正解 那么对拍程序怎么写呢？ 二、怎么写对拍程序？ 对拍程序的写法有很多种，但结构基本一致 while(1)//不一定要用死循环 { 生成随机数据 暴力解法跑一遍 尝试解法跑一遍 比对 } 接下来，我将以A+B Problem为例 首先，写暴力程序std.cpp #include<bits/stdc++.h> using namespace std; #define int long long #define R register #define FILE signed main() { ...

ubuntu 内存占用过高导致卡死 解决办法 一、具体表现 例如下图 在这里插入图片描述 注:图示版本为ubuntu18.04，现在我用的是ubuntu20.04 二、原因 查阅到了一些资料 在Linux中经常发现空闲内存很少，似乎所有的内存都被系统占用了，表面感觉是内存不够用了，其实不然。这是Linux内存管理的一个优秀特性，在这方 面，区别于 Windows的内存管理。主要特点是，无论物理内存有多大，Linux 都将其充份利用，将一些程序调用过的硬盘数据读入内存，利用内存读写的高速特性来提高Linux系统的数据访问性能。 Linux 的这一特性，主要是利用空闲的物理内存，划分出一部份空间，做为 cache 和 buffers ，以此提高数据访问性能。 Linux 优先使用物理内存，当物理内存还有空闲时，linux是不会施放内存的，即时占用内存的程序已经被关闭了（这部分内存就用来做缓存了）。也就是说，即使你有很多内存,用过一段时间后，也会被占满。这样做的好处是，启动那些刚开启过的程序、或是读取刚存取过得数据会比较快，对于服务器很有好处。 总结一下，我的这种情...

整数的划分 动态规划 题目描述 每个非负整数都可以被拆分，比如说 2 = 2 2 = 1+1 3 = 3 3 = 2+1 3 = 1+1+1 输入格式 一个非负整数\(n(0 \leq n \leq 100)\) 输出格式 输出可以被拆分的方案数 输入样例 4 输出样例 5 样例解释 4 = 4 4 = 3+1 4 = 2+2 4 = 2+1+1 4 = 1+1+1+1 共5种 本题是我在学 \(dp\) 时候做的一道题 看到题目首先来一发暴力搜索 40分解法 #include<bits/stdc++.h> using namespace std; #define int long long #define R register int n,ans; int vis[500005]; void dfs(R int x,R int y) { if(x<0)return;//拆过头了 if(!x)//没法拆了 { ...

ubuntu20.04 桌面图标显示异常及解决方法 前言 更新至ubuntu20.04后，出现了一些以前没有的问题 桌面上有些图标不显示 一、具体表现 例如有一次我在做备忘录时 我习惯地打开终端 cd 桌面 gedit 账号.txt 桌面效果 然后我写了一些东西，保存后，桌面变成了这样 (注:并非每次都会出现这种问题) 打开文件夹，显示我桌面上的文件都存在，但是桌面上不显示，双击文件原来的位置也没有用 二、原因 这种情况是\(\text{gnome\ shell}\)出现了异常 众所周知重启电脑能解决大部分问题，但是总不能动不动就重启吧？ 三、解决方法 按下alt+F2，会跳出一个窗口，然后输入一个r(重启gnome shell） 然后再看一眼桌面，就恢复了 总结 碰到gnome shell问题，重启它一般能解决

CF652B z-sort 题解 题目链接：CF652B z-sort 题意：一种叫Z排序的方法，奇数位递增，偶数位递减，给定数组请用此方法排序 题意要求奇数位递增，偶数位递减 那每次只要输出最小值和最大值就可以了 这里给出了优先队列的写法 #include<bits/stdc++.h> using namespace std; #define R register #define int long long priority_queue<int> q1;//大根堆 priority_queue< int,vector<int>,greater<int> > q2;//小根堆 int n; signed main() { scanf("%lld",&n); for(R int i=0,t; i<n; i++) { scanf("%lld",&t); q1.push(t); q2.push(t); } for(...