Sprooc

纸牌均分 有 N 个人排成一排，它们的手中分别有 C[1] ~ C[N] 张纸牌，在每一步操作中，可以让某个人把自己手中的一张纸牌交给他旁边的一个人，求至少需要多少步操作才能让每个人手中持有的纸牌数相等。 首先令 M 为这N 个人的纸牌总数，显然，问题有解，M 能被 N 整除。令avg = M / N，均分完成后每个人都有 avg 张纸牌。 首先考虑第一个人，他只能与第二个人交换纸牌。若C[1] > avg，第一个人需要给第二个人 C[1] - avg 张纸牌；若C[1] < avg，第一个人需要从第二个人手中拿 avg - C[1] 张纸牌。 类似地，考虑第 i 个人和第 i + 1 个人之间的交换。令 $ S[i]=\sum_{k=1}^{i}C[i]$，即数组C的前缀和。若 S[i] < i * avg，那么第 i 个人必须从第 i + 1 个人手中拿走 i * avg - S[i] 张纸牌（否则前 i 个人的纸牌总数不可能为 i * avg，也不可能没人都有 avg 张牌）。同样若S[i] > i * avg，第 i 个人给第 i + 1 个人S[i] ...

所谓“倍增”，就是成倍增长。在一些求解空间较大的问题中，如果使用通常的线性递推，需要线性的时间复杂度。而如果采用倍增的方式，通常能优化为对数时间复杂度。简单地解释倍增思想，就是每次都试图使结果范围扩大一定长度，如果扩大后仍满足要求，则扩大，并将下一次试图扩大的长度变为原来的两倍；若不满足，则将扩大长度减半，再次尝试，若仍不满足，则继续减半。最终，扩大长度减为0，就得到了所需的结果。下面是两个使用倍增算法的例子。 求小于T的最大数组前缀和 给定一个长度为N的数列 A，然后进行若干次询问，每次给定一个整数T,求大的 k，满足 $\sum_{i=1}^{N}{A[i]}\le T$。你的算法必须是在线的（必须即时回答每一个询问能等待收到所有询问后再统一处理），假设$0\le T\le\sum_{i=1}^{N}{A[i]}$。 最朴素的做法当然是从前往后累加数组，直到累加和大于T，时间复杂度是O(N)。 首先用O(N)的时间预处理，求出前缀和数组，再用二分查找确定小于等于T的上界。每次查找O(logN)。 如果每次查找的T都很小，使用二分查找可能还不如直接从头遍历数组，那么可以使用倍增算 ...

互联网计算-名词解释 英文简称 英文全称 中文 解释 ABR area border routers 区域边界路由器 在使用OSPF的网络中，拥有连接不同区域的接口的路由器，通常是Area 0 和其他区域。 Access links 接入链路 交换机上的链路，只属于一个VLAN ACK acknowledgement 确认字符 在有确认的传输中，接收方发送给发送方的一种控制字符，表示发来的数据与收到 ACL access control list 访问控制列表 路由器或交换机接口的指令列表，控制端口进出数据包。 ad-hoc Network 自组网络 属于一次对话的各帧 Administrative Distance 管理距离 ⼀个0-255的值，提供路由可靠性的⼀个可选参数 ADSL asymmetric digital subscriber line 非对称数字用户线 上行和下行宽带不对称，利用频分服用，用电话线提供宽带服务 AMI alternate mark inversion 双极性传号交替反转码 n零电平表示“0”，正负 ...

现在是2024年1月4日，期末周第三天的晚上，下午考完了第一门必修课毛概，后天将要考计网。目前的精神状态一言难尽。 下午考完毛概走出考场，考的题目基本都会做，心情本应该是不错的，但莫名有种怅然若失的感觉。我一时间竟然不知道接下来应该干什么。回到宿舍，随意刷了一个小时的B站，然后下楼吃饭，又在学校里漫无目的地逛了半个钟。又回到宿舍，听了一个小时的歌，然后为了打发时间刷了两道力扣。然而，干什么都提不起劲，陷入了一种百无聊赖的状态，只想早点上床睡觉。按理说吧，现在应该抓紧时间复习，但感觉意义不大，该复习的基本都复习好了，完全找不到前几天拼了老命地复习那种感觉。回想起来，去年期末周我也差不多是这种状态。或许是我想太多？可能只是把自己逼太紧了。想一想这一个学期，尤其是学期末，基本没有出过校门，一直憋在宿舍学习。可能确实是我给自己太大压力了，以后还是多点放松，这种精神状态属实很糟糕。 最近偶然染上了陶喆。最开始是因为他的抽象了解到的，但听了几首歌之后完全被他的才华所折服。听97年的《David Tao》，让我重新感受到当初第一次听《Jay》时所受到的震撼。看来我还是喜欢哪个年代的R&B ...

期末复习的一周，时间真的很紧，所以这周的周记也会写得比较仓促。。。这周把计组和计网复习了一遍，接下来就剩数据结构与算法了。 刚刚复习的时候看到一个不错的算法，简单记录一下 2010年全国考研统考题（13 分）设将 n(n>1) 个整数存放到一维数组 R 中，试设计一个在时间和空间两方面尽可能有效的算法，将 R 中保有的序列循环左移 P (0< P< n )个位置，即将 R 中的数据由（ X0 X1 ……Xn-1 ）变换为( Xp Xp+1 ……Xn-1 X0 X1…Xp-1)。 算法的思想是做两次翻转，先将（ X0 X1 ……Xp-1 ）翻转，把( Xp Xp+1 ……Xn-1)，最后把整个数组翻转。时间复杂度O(n)，无需额外空间。 Leetcode第 377 场周赛时隔两个星期终于有空打一次周赛了。还是ac三题，最后一题没时间做了，而且也不会。简单总结一下： 第一题送分题 第二题超时了3次才ac。关键是没想起学过的一个点：先建堆后排序要比动态建堆快。 第三题Floyd算法，秒了，一次错误提交是因为有重边。 第四题，跳了。 下一周是这个学期最后一周 ...

第17讲-输入输出 外围设备 输入输出操作通过连接到输入输出模块的各种外部设备完成，这些外部设备提供了在外部环境和计算机系统之间的数据交换，通常被称为外围设备（peripheral device），简称为外设（peripheral） 类型 人可读设备：适用于与计算机用户通信 显示器，打印机 机器可读设备：适用于与设备通信 磁盘，磁带 通信设备：适用于与远程设备通信 不能把外设直接连接到系统总线上 外设种类繁多，操作方法多种多样 外设的数据传送速度一般比存储器或处理器的慢得多 某些外设的数据传送速度比存储器或处理器要快 外设使用的数据格式和字长度通常与处理器不同 I/O模块 通过系统总线或中央交换器和存储器连接；通过专用数据线与一个或多个外设连接。I/O模块是计算机内部系统和外设之间的桥梁 外围设备的接口 输入输出模块的接口以控制、状态和数据信号的形式出现 与设备相关的控制逻辑控制外设的操作，以响应来自输入输出模块的命令 缓冲器用于缓存输入输出模块和外设之间传送的数据 缓冲器的大小一般为8 位或16 位 I/O模块的功能 处理器通信 命令译 ...

第16讲-控制器 处理器的结构 寄存器 寄存器分类 用户可见寄存器（user visible register） 允许编程人员通过机器语言或汇编语言访问，通过优化寄存器的使用而减少对主存的访问 控制和状态寄存器（control and status register） 由控制器来控制CPU 的操作，并由拥有特权的操作系统程序来控制程序的执行 大多数控制和状态寄存器在大多数机器上是用户不可见的 某些在控制或操作系统模式下执行的机器指令是用户可见的（如程序计数器，在x86上是用户可见的） 两者的区分并不严格 用户可见寄存器 通用寄存器（general purpose register，简称GPR） 可被程序员指派各种用途 数据寄存器（data register） 仅可用于保持数据而不能用于操作数地址的计算 地址寄存器（address register） 可以是自身有某些通用性，或是专用于某种具体的寻址方式 例如：段指针、变址寄存器、栈指针 条件码寄存器（condition codes register）/ 标志（flag）寄存器 CPU硬件设置这些条件 ...

第15讲-指令周期和指令流水线 指令周期 指令周期：处理单个指令的过程（时间） 取指周期：从内存中提取一条指令 执行周期：执行所提取的指令 只有当机器关闭、发生某种不可恢复的错误或遇到停止计算机的程序指令时，程序执行才会停止 间址周期 指令的执行可能涉及一个或多个存储器中的操作数，它们每个都要求一次存储器访问 使用间接寻址，还需要额外的存储器访问 间址周期：把间接地址的读取看成是一个额外的指令子周期 取操作数发生了2次 CPU的任务 取指令：CPU 必须从存储器（寄存器、cache 、主存）读取指令 解释指令：必须对指令进行译码，以确定所要求的动作 取数据：指令的执行可能要求从存储器或输入/输出（I/O）模块中读取数据 处理数据：指令的执行可能要求对数据完成某些算术或逻辑运算 写数据：执行的结果可能要求写数据到存储器或I/O 模块 CPU需求：寄存器 CPU需要在指令周期中临时保存指令和数据 CPU需要记录当前所执行指令的位置，以便知道从何处得到下一条指令 CPU需要一些小容量的内部存储器 假定CPU 有： 1个存储地址寄存器（MAR） 1个存储 ...

期末周临近，最近也开始复习了。而且越复习越发现不懂的东西还有很多。。。所以期末考试之前算法的学习应该会暂时放一放啦。但是每天刷三道题还要继续保持。 本来想着为了计组机考，这周复习一下Java的，结果发现用Java刷力扣还是有点难受，主要是自己不熟悉库。以后再花点时间深入学习一下Java吧。虽然没有复习Java，但应付计组机考还是挺轻松的。 CSP的成绩出来了。作为第一次考的成绩，虽然没到预期，也算还行吧。 这周没什么好记录的了，下周也要努力复习啦！

第14讲-指令系统 指令 指令的要素 操作码：指定将要完成的操作 源操作数引用：操作会涉及一个或多个源操作数，这是操作所需的输入 结果操作数引用：操作可能会产生一个结果 下一指令引用：告诉处理器这条指令执行完成后到哪儿去取下一条指令 指令表示 在计算机内部，指令由一个位串来表示 指令格式：对应于指令的各要素，这个位串划分成几个字段 大多数指令集使用不止一种指令格式 机器指令符号表示法： 操作码被缩写成助记符来表示 MUL：乘，DIVDIV：除，LOAD：由存储器装入，STOR：保存到存储器 操作数也可以用符号表示 用寄存器编号或内存地址替换操作数 指令格式 定长操作码：𝒏位操作码字段的指令系统最大能够表示𝟐 𝒏 条指令 可变长操作码 扩展操作码：不同地址数的指令具有不同长度的操作码 15条三地址指令操作码：0 0 0 0 ~ 1 1 1 015条二地址指令操作码：1 1 1 1 0 0 0 0 ~ 1 1 1 1 1 1 1 015条一地址指令操作码：1 1 1 1 1 1 1 1 0 0 0 0 ~ 1 1 1 1 1 1 1 1 1 1 1 ...