Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial CPU内存 CPU-L1cache-L2cache-memery-disk 逻辑地址空间 抽象、隔离、保护、共享、虚拟化(临时放入disk) 内存管理 程序重定向，分段，分页，虚拟内存，按需分叶虚拟内存 地址空间和地址生成 C程序用变量表示地址，汇编还是用符号，机器码就开始使用逻辑地址了，CPU的MMU中有一段区域来映射逻辑地址到物理地址 约束程序的内存 程序只可以访问他自己的内存，当他访问其他地方的时候，操作系统应该使用安全检测 内存碎片 外部碎片，是分配单元之间的内存碎片 内部碎片，已经分配给了应用程序，但是应用程序没法使用它 连续内存分配 程序启动的时候要分配，运行的时候要分配 第一匹配分配算法 一个一个找，第一个碰到的合法的就分出去， 需要按地址排序，分配的时候需要寻找合适的分区，还有看自由分区能否与相邻空闲分区合并 简单，容易产生更大的空闲块，容易产生外碎片 最优分配算法 找差值 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 操作系统的启动 DISK中放操作系统，BIOS是基本的IO系统，检测外设，Bootloader能够加载OS，BIOS从CS段寄存器;IP指令寄存器开始执行，然后BIOS会POST(加电自检)，然后BIOS找到bootloader加载Bootloader，并传递控制权,然后Bootloader找到OS，读到内存吧控制权交给OS 操作系统的中断、系统调用、异常 系统调用是应用程序主动想操作系统发出服务请求， 异常是来源于不良的应用程序的非法指令 中断是来自不同硬件设备到额计时器和网络的中断 我们不能让应用程序直接访问外设，这不安全，另外OS可以提供更好的借口，通用可移植 中断处理 保存现场、查表、中断处理、清楚中断标志、恢复现场 异常处理 保存现场、查表、异常处理(杀死程序或者重新执行异常指令)、恢复现场 系统调用 printf(..); 会触发系统调用write(); 程序主要是用高层次 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 操作系统是什么 是一个控制软件，能管理应用程序，为应用程序提供服务，杀死应用程序，能够分配资源，能够管理外部设备，承上启下，硬件之上，应用程序之下， Kernel CPU调度,物理内存管理，虚拟内存管理，文件系统管理，中断处理和设备驱动 Kernel特征 并发，共享(1在一个时间点，只有一个程序能够访问2同时访问)，虚拟（利用多到程序设计技术，让每个用户都觉得有一个计算机为他服务），异步(程序走走停停，而不是一直走) 操作系统实例 Unix,Linux,Windows等

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 笛卡尔树 这个笛卡尔树没写出来，气死了 他是二叉树，他是堆，二叉树中序遍历的结果就是数组a 笛卡尔树的构造 先看一个简单的笛卡尔树 我们使用增量构建笛卡尔树来完成，就和增量构建后缀自动机一样容易。我们来对x分类讨论如果x比5小怎么样，如下如果x在5和7之间如果x在7和9之间如果x比9大呢 我们不难发现，每当增加一个新的值的时候，笛卡尔树变化的一定只有从根一直向右走的路径，我们可以想出一个很简单的方法，每次新增加值a[i+1]的时候，让他不断和右链比较，找到lower_bound的地方，然后插入到那去就可以了。 进一步发现，上诉代码需要维护指向父亲的指针，我们考虑到用一个栈来维护右链，栈低为根，栈顶为叶子，在弹栈的时候维护右儿子指针，在压栈的时候维护左儿子指针即可。代码如下 1234567891011121314int n;int a[N]; // a[1], a[2], a[3], a[4 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 阿里笔试 感觉很难受，笛卡尔树没写出来，气死了，我咋这么菜 第一题 有n个羊圈，第i个羊圈初始有a[i]个羊，每天早上每个羊圈会增加k的羊，每天晚上主人会选出羊圈中羊最多的那个，卖掉一半，变为$\lfloor \frac{a[i]}{2}\rfloor$个羊，问m天后剩下多少只羊。 n,k,m,a[i]<1e5 每天增加本质是区间加法，寻找羊最多的是区间最值查询，减半是单点修改，第一想到线段树，但是这么敲也太莽撞了，然后发现区间修改为全区间修改，考虑到可以懒惰化，即增加一个值add用来表示全区间增大的情况。区间加法的时候让add+=k即可，查询的时候是最值查询，修改的时候注意$\lfloor \frac{a[i]+add}{2}-add\rfloor$,这样用一个多重集合维护即可 第二题 给一个长度为n的数组，任意选择一个子串，问最大值的期望, n<1e6 笛 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 创建工作空间 我们先创建一个工作空间myGit，在其中创建一个项目project，植入两个文件a.txt和b.txt，并分别写入”a”和”b” 123456cd ~ mkdir -p myGit/projectcd myGit/projecttouch a.txt b.txtecho "a" >> a.txtecho "b" >> b.txt 初始化git 紧接着我们用git初始化这个项目 1git init 我们看到了输出,他的意思是我们创建了一个空的git仓库 1Initialized empty Git repository in /Users/s/myGit/project/.git/ 他的意思是说我们的git没有追踪任何一个文件，我们可以通过下面对指令来查看git的状态 1git status 紧接着 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 题目描述小敏和小燕是一对好朋友。他们正在玩一种神奇的游戏，叫 Minecraft。他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。他们想，在仅这一个操作下，最漂亮的工艺品能多漂亮。两个工艺品美观的比较方法是，从头开始比较，如果第i 个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第i+1 个方块。如果全都一样，那么这两个工艺品就一样漂亮。 输入格式第一行一个整数 n，代表方块的数目。第二行 n 个整数，每个整数按从左到右的顺序输出方块瑕疵度的值。 输出格式一行n 个整数，代表最美观工艺品从左到右瑕疵度的值。 输入样例121010 9 8 7 6 5 4 3 2 1 输出样例11 10 9 8 7 6 5 4 3 2 数据范围n<3e5 做法1 维护两个指针i,j让其表示两个子串， ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 前言 从大一上接触C++,到大一下接触ACM,到现在大三下,我自以为对C++有了很深的理解，其实不然，我不清楚的地方还特别多，准备趁此空闲时间重学C++。 const 与指针 这是这篇博文的重点，常常我们会碰到多种声明 1234const char* const a = new char[10];const char* a = new char[10];char* const a = new char[10];char* a = new char[10]; 他们有什么共性与不同呢?下面的程序演示了区别，注释的地方是非法操作会报错。 12345678910111213141516171819202122232425#include <iostream>using namespace std;int main() { const char* const a = ne ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 为什么我们需要设计模式 有一类问题会在软件设计中反复出现，我们能够提出一种抽象的方法来解决这类问题，这就是设计模式。 设计模式的七大原则 单一职责原则 接口隔离原则 依赖反转原则 里氏替换原则 开闭原则 迪米特法则 合成复用原则 23种设计模式5个创建型 单例模式 工厂模式 抽象工厂模式 原型模式 建造者模式 7个结构性 适配器模式 桥接模式 装饰者模式 组合模式 外观模式 享元模型 代理模式 11个行为型 模版方法模式 命令模式 访问者模式 迭代器模式 观察者模式 中介者模式 备忘录模式 解释器模式 状态模式 策略模式 责任链模式 单一职责原则 一个类只管一个职责。 例子1如果我们创建了交通工具类，他掌管着很多工具，汽车、飞机、轮船，显然我们不适合让一个类来管理这么多种交通工具，这样导致职责太多，也不适合分别为这三种交通工具建立3个类，这样导致修改过多，正确的做法是创建三个函数， ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial Spring 模块 Spring有六大模块，测试、容器、面向切面编程、instrumentation、数据访问与集成、Web与远程调用。 测试: Test 容器: Beans,Core,Context,Expression,ContextSupport 面向切面编程: AOP,Aspects instrumentation: instrument,instrumentTomcat 数据访问与集成: JDBC,Transaction,ORM,OXM,Messaging,JMS Web与远程调用: Web,WebServlet,WebPortlet,WebSocket 但是Spring远不止这些 Spring配置 Spring有三种配置方式，第一是通过XML配置，第二是通过JAVA配置，第三是隐式的bean返现机制和自动装配。建议优先使用三，而后是二，最后是一 自动化装配bean 有两种方法 ...