immix's blog

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 协议建立套接字。 以下是建立一个套接字的示例代 ...

在阅读本文前，请确认你掌握了割点和桥的求法，否则请先阅读 连通性问题（2）- 割点和桥。 概念 仿照强连通分量，我们来定义边双连通分量和点双连通分量。 边双连通分量：原图的一个极大边双连通子图。 点双连通分量：原图的一个极大点双连通子图。 边双连通分量 洛谷P8436 【模板】边双连通分量 边双连通分量求解十分简单。只需把原图中的所有桥删去，在新图上所求得的连通分量就是边双连通分量。 求边双连通分量可以使用并查集或 dfs 求连通分量。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091#include<bits/stdc++.h>using namespace std;const int N = 5e5+5;struct Edge{ int u,v; b ...

概念 割点、桥是在无向图中的概念。 割点：删除节点 uuu 后，原图变为不连通，则称 uuu 为割点。 桥（割边）：删除边 (u,v)(u,v)(u,v) 后，原图变为不连通，则称 (u,v)(u,v)(u,v) 为桥。 点双连通：不存在割点的无向图称为点双连通图。 边双连通：不存在桥的无向图称为边双连通图。 一张点双连通图不一定是边双连通图，割点之间的连边不一定是桥，桥的起点和终点也不一定是割点。 割点 我们来考虑如何修改 Tarjan 算法求割点。 如上图，对于节点 uuu 来说，若存在 uuu 的子节点 vvv，使得 lowv≥dfnu\text{low}_v\geq\text{dfn}_ulowv​≥dfnu​，则 uuu 为割点。（因为从节点 vvv，无法回到 uuu 的父节点，则删除 uuu 后，vvv 与图其余部分不连通） 但对于根节点来说，这个判断是错误的。考虑只有一个子树的根节点。此时删除根结点后，原图仍然连通（本质即上文中图其余部分不存在了）。因此，对于根节点，我们需要判断子树数量。若子树数量多于一个，则根节点为割点，反之则不是。 桥 首先，桥一定是树枝边 ...

概念 强连通：有向图 GGG 中，任意两个节点互相可达。 强连通分量 (Strongly Connect Componet,SCC)：原图的一个极大强连通子图。也就是说，一个强连通分量是 强连通的：强连通分量内任意两个节点互相可达 极大的：不存在节点 u′u'u′，使得强连通分量加入 u′u'u′ 后仍然是一个强连通子图。 缩点：如果我们把每个强连通分量中的所有点看成一个点，就构成了一个 SCC 图。这个图一定不会存在有向环，因此是一个 DAG。 如上图左，节点 1、4 单独构成一个 SCC，节点2、5，节点3、6，节点7、8、9、10、11、12 构成了三个 SCC。缩点后得到新图如上图右所示。可以观察到，确实是一个有向无环图。 Tarjan 算法 Tarjan 算法可以在 O(V+E)O(V+E)O(V+E) 的复杂度下，通过一次 DFS 找出一个图的所有强连通分量。另外，Tarjan 算法还可稍加修改，用于求解割点、桥、双连通分量问题。 在讨论 Tarjan 算法之前，我们先了解搜索树。在对有向图进行 DFS 时，会形成一颗搜索树。每次搜 ...

DAY-1 省选前基本没有复习，都在做其他事情。最后周五晚上开了虚拟机想写点板子，结果也没写动，就写了个 A+B。不过把 NOI Linux 2.0 好好试了试，最后在考试前十个小时发现还是 Code::Blocks 最好用（只有CB有补全）。 DAY1 提早了三刻钟到，站了半个小时，然后在要进考场的时候看到了xpt（）。进了考场，老师说 Linux 和 Windows 都可以随便选，四周环视了一圈，都是用 Windows 的，不过我还是用了 Linux。打开 Code::Blocks 的时候没找到哪里调编译选项，调了 5 分钟。 T1 一开始不会做，思考了 x=1x=1x=1 的部分分之后想出来了。期望得分：100分。 T2 图论题，不会做，只会枚举每条边是不是新增的然后判断。复杂度 O(n2m)O(n2^m)O(n2m)，期望得分：10分。 T3 背景是一棵树，打一个贪心和一个链的特例，期望得分：36分。 DAY2 T1 不会做，只打了第一个特例。期望得分：20分。 T2 感觉和CF某题很像，打了40分部分分。 T3 完全不会，只能输出1。期望得分：2分。 总期望得分 100+10 ...