Ulog

我真的能吃这口饭吗...

发表于

图灵完备思路整理

一、基础逻辑运算

非门

或门

或非门

高电平

三路与门

三路或门

异或门

同或门

二、算术运算

半加器

全加器

三、处理器架构

四、编程

五、处理器架构2

六、函数

七、汇编挑战

未分类

一位取反器

一位开关

一位解码器

三位解码器

优雅存储

信号记数

元件工坊

八位全加器

八位或

八位非

加倍

奇变偶不变

奇数个信号

存储一字节

小盒子

延迟线

总线

成对的麻烦

指令解码器

数据选择器

条件判断

相反数

第二刻


算数引擎

计数器

逻辑引擎

发表于 更新于

前缀和

1.前缀和理解与实现

为什么要用前缀和？
前缀和顾名思义就是前几个数的和，arg[n]即为前n个数的和。这样当我们需要区间(l,r)的和时只需要求prefix[r]-prefix[l-1].
若我们选择遍历大小为n的数组，询问次数为q次。则时间复杂度为O(qn)。
而使用前缀和我们只需要花O(n)遍历数组，再花O(1)求得所需。

前缀和的实现
1.手写
开新的数组

1
2
3
4
5
6
7
vector<int>prefix(n);
for(int i=0;i<n;i++){
    //非起始位置
    if(i)prefix[i]=prefix[i-1]+arg[i];
    //起始位置
    prefix[i]=+arg[i];
}

原数组不用了

1
2
for(int i=0;i<n;i++)
    if(i)arg[i]+=arg[i-1];

2.库函数

1
2
//numeric库
partial_sum(arr.begin(),arr.end(),prefix.begin());

需要注意的点
需要注意下标为0时的数组越界
解决方法：
1.0特判

1
2
3
4
auto sumOf=[&](int l,int r){
    if(l==0)return prefix[r];
    return prefix[r]-prefix[l-1];
}

2.从1开始

1
2
//numeric库
partial_sum(arr.begin(),arr.end(),prefix.begin()+1);

2.前缀和变种

1.前缀积

同理，但是造成了容易溢出的问题。
mul(l,r)=prefix[r]/prefix[l-1]
我们通常会取模，但是这样mul就并不是简单的除法运算，需要用乘法逆元。如费马小定理等。

2.前缀异或和

xor(l,r)=prefix[r]^prefix[l-1]
前缀异或和有一个有趣的性质：有两个前缀相同，则区间的异或和为0。
实现

1
2
3
partial_sum(arr.begin(),arr.end(),xorsum.begin(),[](int prev,int cur){
    return prev^cur;
});

3.二维前缀和

左上角到某地方的前缀和，依据容斥原理
sum(x1,y1,x2,y2)=p[x2][y2]-p[x1][y2]-p[x2][y1]=p[x1][y1]

4.普遍前缀和

我们可以将前缀推广到任意运算，如max,min……但由于没有逆运算，不能求解区间问题。但面对多次查询还是适用的。

2.后缀和

用于求解终点与当前位置的信息。
实现

1
2
3
4
5
6
7
8
9
10
11
    for(int i=n-1;i>=0;i--){
        if(arr[i]){
            if(i!=n-1)suffix[i]=suffix[i+1];
            suffix[i]+=arr[i];
        }
    }
//库函数
    partial_sum(arr.rbegin(),arr.rend(),suffix.rbegin(),[](int prev,int cur){
        if(cur)return prev+cur;
        return cur;
    });

发表于 更新于

Maven

1.安装与IDEA使用

不赘述

2.依赖管理

1.简介

Maven使用pom.xml文件来定义项目依赖。
依赖的坐标

  • GroupId：组织或项目的唯一标识符，通常用反向域名命名
  • ArtifactId：项目或依赖名称。同组中有唯一性。
  • Version：版本号
  • Packaging：打包类型
1
2
3
4
5
6
//一个依赖示例
<dependency>
  <groupId>org.springframework.boot</groupId>
  <artifactId>spring-boot-starter-web</artifactId>
  <version>2.5.4</version>
</dependency>

依赖管理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//properties设置版本号
//dependencyManagement管理依赖
  <properties>
     <spring-version>6.0.6</spring-version>  
    </properties>
  <dependencyManagement>
        <dependencies>
            <dependency>
                <groupId>org.springframework</groupId>
                <artifactId>spring-context</artifactId>
                <version>${spring-version}</version>
            </dependency>
        </dependencies>
     </dependencyManagement>

依赖冲突:项目A依赖库B，B依赖C版本，A依赖C另一版本。Maven采取最近路径优先策略，选择离项目最近的一项，若距离相同则根据POM文件声明顺序。

3.构建管理

生命周期

  • validate：验证项目是否正确和所有必要信息是否可用。
  • compile：编译项目的源代码。
  • test：使用适当的单元测试框架（如 JUnit）测试编译好的代码。
  • package：将编译后的代码打包成可分发的格式（如 JAR、WAR）。
  • verify：运行任何集成测试来验证软件包的有效性。
  • install：将软件包安装到本地 Maven 仓库，以供本地项目使用。
  • deploy：将最终的构建结果复制到远程仓库，以供其他开发人员和项目共享。

4.Maven继承

子项目继承父项目的配置。通过继承机制，子项目可以复用父项目定义的依赖、插件、属性等配置，减少重复配置，提高项目的可维护性。

1
<parent></parent>

5.Maven聚合

聚合是指在一个父项目中管理多个子项目，使得构建和管理多个模块变得更加方便。在聚合项目的根目录中运行 Maven 命令，可以同时构建和管理所有子项目。
聚合项目（Aggregator Project）本身通常不包含代码，仅用于组织和管理子项目
聚合项目的 POM 文件通过 <modules> 元素定义了包含的子项目。通过聚合，可以一次性构建和管理所有子项目。简化了构建和发布过程。

1
2
3
<modules>
  <module></module>
</modules>

6.常用链接

依赖信息查询

0%