immix's blog

导言 命令行是一种强大、快捷的工具。有时候可以比 GUI 操作更加便捷。其另一大优点是可以极其容易的通过 ssh 控制其他机器。 初识命令行 在 Windows 下，常见 shell 有命令提示符(cmd)，PowerShell 两种。我们主要阐述 cmd。在 linux 平台上你还会见到 bash。bash 和 cmd 的命令是有一部分重合的。 打开 cmd 的一种方式是按 Windows 键，然后搜索 cmd；另一种方式是 Win+R，再输入 cmd 运行。 打开 cmd 后，你会见到这样的界面（因为我安装了 Windows Terminal，与你的电脑外观略有不同，但是内容是一样的）。 在提示符（>）后输入命令，然后按回车就可以看到命令的结果。你学过了 ping 和 ipconfig 命令，但让我们从头开始，学习最基本，使用频率最高的命令。 基本命令 基本命令只有两个（好耶），一个切换目录，一个查看当前目录内容。 cd cd = Chang Directory = 改变目录 用来改变当前的工作目录。在 cmd 中，使用 Tab 可以补全路径。使用 ↑ 键可以找到历史命令 ...

突发奇想，研究一下 ACG 歌词的用词特点。 获取歌词 找到了一个共有 4572 首歌（2023-5-10）的歌单，https://music.163.com/#/playlist?id=66652611 ，尝试获取其中所有歌的歌曲 id。 首先尝试查找有没有合适的 API，失败，尝试从歌单页面入手。 可以看到，网易云网页查看别人创建的歌单只可以看到前 20 首歌曲。但是如果我们将歌单复制到自己的自建歌单，则可以显示 1000 首。理论上可以创建 5 个歌单，然后进行获取。 分析网页结构，可以发现每个歌曲都是一个 a 标签，里面的 href 就是我们要的内容。 尝试在控制台编写一个 JS 来获取所有个歌曲 id。 1document.querySelectorAll("div.f-cb span.txt > a") 尝试使用这个选择器，发现能够成功获取所有 a 标签，接下来就是获取所有 a 标签的 href 属性。 12let result = ""document.querySelectorAll("div.f-cb spa ...

引入 洛谷P6175 无向图的最小环问题 给定一张带权无向图，求图中至少包含 333 个点的环，环上节点不重复，并且环上所有边权值和最小。 解法 我们考虑对 Floyd 算法进行修改，找出最小环。 设最小环由节点 V1−V2−⋯−VnV_1 - V_2 - \dots - V_nV1​−V2​−⋯−Vn​ 组成。 其中编号最大的节点为 VmV_mVm​ 与其相连的节点为 VpV_pVp​，VqV_qVq​。 则最小环可以表示为 Vp−{Vp,Vq之间不包含Vm的最短路}−Vq−VmV_p - \{V_p,V_q\text{之间不包含}V_m\text{的最短路}\} - V_q - V_mVp​−{Vp​,Vq​之间不包含Vm​的最短路}−Vq​−Vm​。 如下图： 这是可以证明的： 假设不是最短路：则最短路权值一定更小； 假设包含了 VmV_mVm​：则出现了重复的节点。 在 Floyd 算法中，我们知道，枚举中转点到 k 时，此时数组内下标小于 k 的值保存的是 1~(k-1) 内部之间的最短路。 因此在 Floyd 算法中枚举 i，j 的循环前面再添加一个循环即可。G[i] ...

前言 什么是类？ 类（Class）：可以片面的理解为一类相似事物的抽象。 以圆为例，圆具有半径这样一个相似的属性，并且都可以执行面积、周长等运算。 为什么用类？ 为了是代码更加抽象，封装。事实上，我们以前写的每个 python 代码里都创建了各种各样的类。 一些例子比如 DataFrame 类。 你可能会用 read_csv 创建一个 DataFrame 类，可能也会用下标运算符，来获取它的某一列，也可能会用它的 drop_duplicates 方法。事实上，你并不关心 DataFrame 是怎么把数据排在一起的，你也不关心为什么 drop_duplicates 就能把所有重复的去除，但是，通过这一个抽象的类，你可以方便的调用它的功能。 DataFrame类，将整个表的数据，仅仅用一个变量，就全部包含起来，就像是封装在了一个小小的纸板箱中📦。 需要注意的是，pandas 库并不是魔法，而是正常的 python 语法。一切 pandas 库的功能都是我们也可以实现出一模一样的。 比如说，为什么 df[(df['a']>5) & (df['b']<8)] 中用的是 & ...

POWER 多瑞卡得到了一份有趣而高薪的工作。每天早晨他必须关掉他所在村庄的街灯。所有的街灯都被设置在一条直路的同一侧。 多瑞卡每晚到早晨5点钟都在晚会上，然后他开始关灯。开始时，他站在某一盏路灯的旁边。 每盏灯都有一个给定功率的电灯泡，因为多端卡有着自觉的节能意识，他希望在耗能总数最少的情况下将所有的灯关掉。 多端卡因为太累了，所以只能以 1m/s的速度行走。关灯不需要花费额外的时间，因为当他通过时就能将灯关掉。 编写程序，计算在给定路灯设置，灯泡功率以及多端卡的起始位置的情况下关掉所有的灯需耗费的最小能量。 输入 输入文件的第一行包含一个整数 NNN，2≤N≤10002≤N≤10002≤N≤1000，表示该村庄路灯的数量。 第二行包含一个整数 VVV，1≤V≤N1≤V≤N1≤V≤N，表示多瑞卡开始关灯的路灯号码。 接下来的 NNN 行中，每行包含两个用空格隔开的整数 DDD和 WWW，用来描述每盏灯的参数，其中 0≤D≤10000≤D≤10000≤D≤1000，0≤W≤10000≤W≤10000≤W≤1000。DDD 表示该路灯与村庄开始处的距离(用米为单位来表示)，WWW 表示灯 ...

胖男孩 麦克正如我们所知的已快乐地结婚，在上个月他胖了70磅。因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。 每晚麦克都详细地描述那一天他所吃的所有东西，但有时当他只想按一次某键时往往会按了不止一次，并且他的胖手指还会碰到他不想要按的键，麦克也知道自己的手指有问题，因此他在打字的时候很小心，以确保每打一个想要的字符时误打的字符不超过3个，误打的字符可能在正确字符之前也可能在其之后。 当斯拉夫克多次收到读不懂的电子邮件后，他总是要求麦克将电子邮件发3遍，使他容易读懂一点。 编写程序，帮助斯拉夫克根据他所收到的三封电子邮件求出麦克可能写出的最长的信。 输入 输入文件包含了三行文本。每一行文本包括麦克信件的一种版本。其中所有的字符都由英文字母表中的小写字母组成并且不超过100个。 输出 输出文件中第一行即唯一的一行数据应该包含斯拉夫克根据所收到的电子邮件推测出的最长信件。你可以相信问题一定有解，但解不一定是唯一的。 输入样例 cecqbhvaiaedpibaluk cabegviapcihlaaugck adceevfdadaepcialaukd 输出样例 ...

顺序对齐 考虑两个字符串右对齐的最佳解法。例如，有一个右对齐方案中字符串是 AADDEFGGHC 和 ADCDEGH。 AAD_DEFGGHC ADCDE__GH_ 每一个数值匹配的位置值 2 分，一段连续的空格值 -1 分。所以总分是匹配点的 2 倍减去连续空格的段数，在上述给定的例子中，6 个位置(A, D, D, E, G, H)匹配，三段空格，所以得分 2×6+(-1)×3=9 ，注意，我们并不处罚左边的不匹配位置。若匹配的位置是两个不同的字符，则既不得分也不失分。 请你写个程序找出最佳右对齐方案。 输入 输入文件包含两行，每行一个字符串，最长50个字符。字符全部是大字字母。 输出 一行，为最佳对齐的得分。 样例 输入样例 AADDEFGGHC ADCDEGH 输出样例 9 解法 然后从左边开始区间 DP，设 fi,jf_{i,j}fi,j​ 为第一个字符串左边 iii 位，第二个字符串左边 jjj 位的最大值。可以写出方程： fi,j=max⁡{fi−1,j−1+2(s1[i]=s2[j])fi−1,j−1(s1[i]≠s2[j])fk,j−1(1≤k< ...

任务 下载 任务具体内容.pdf (271kB) 分析 异常 为了让服务端可以正常的接收任何奇怪的请求并不会直接崩溃，我们来介绍 python 中的异常体系。 什么是异常 在 python 无法正常处理程序时就会发生一个异常。如果没有捕获处理它，程序会终止执行。 异常处理 在 python 中，异常处理由 try / except 语句组成。 最简单的一个示例如下： 123456try: print(1/0)except: print("program failed!")else: print("program success! :)") 在 try 语句后缩进，在这部分执行自己的代码。如果出错了，会执行 except 语句的部分，否则会执行 else 的部分。 在 except 语句后可以接一个异常名，这样只会捕获特定异常。常见的异常名字如下表。 异常名称 描述 Exception 所有异常都是 Exception，即 except Exception: 可以捕获所有异常。 ZeroDivision ...

洛谷P8867 [NOIP2022] 建造军营 之前 NOIP 的时候还没学 Tarjan 算法，无奈爆零，现在学完了，终于花一个下午自己做出来了。 前置知识： 双连通分量 树形 DP 题目做法 首先，会想到边双连通分量缩点，因为在非桥边上无论保护还是不保护都是一样的。 在缩点之后，一定会形成一棵树（因为存在环就还存在边双连通分量）。在树上考虑进行树形 DP 进行计数。 我们定义 fu,0\large{f_{u,0}}fu,0​ 为 uuu 所在的边双连通分量没有建造军营的方案数。fu,1\large{f_{u,1}}fu,1​ 为 uuu 所在的边双连通分量建造了军营的方案数。并且若 uuu 建造了军营，uuu 到根节点的边必须全部保护（这么设计是为了方便转移状态，但是统计答案时就不是 froot,1\large{f_{\text{root},1}}froot,1​ 了）。 定义如下变量： edgeuedge_uedgeu​：uuu 所在连通分量的边数； vertexuvertex_uvertexu​：uuu 所在连通分量的点数； sizusiz_usizu​：uuu 的儿 ...

套接字 介绍 套接字（socket）在网络编程中是最低级的，使用套接字可以获得最大的自由度。在实际进行网络编程时，比如进行爬虫，我们会使用 requests 库，来更快的进行 HTTP 请求（体现封装的概念）。 什么是套接字？ 要理解套接字是什么，我们先看它的英文单词释义。 套接字可以看成是两个网络应用程序进行通信时，各自通信连接中的端点。socket 取插座义，把服务器和客户端看作是插头和插座，是接入点和被接入点的关系。因此，socket 可以用来进行收发消息。 使用 我们先来认识 python 中套接字的支持。python 中，套接字由内置库 socket 提供。 建立套接字 使用 socket.socket(socket_family,socket_type) 函数建立套接字。 socket.socket 函数接收两个参数，分别为协议簇和套接字类型。 在本次（以及将来很久），你都只需要掌握一种套接字。其协议簇为 socket.AF_INET，指代 IPv4 协议，套接字类型为 socket.SOCK_STREAM，即基于 TCP 协议建立套接字。 以下是建立一个套接字的示例代 ...