Crack jar

jar包是啥

jar(java archieve file),java归档文件

与zip比较

其内容和zip文件非常相似,甚至可以直接使用360压缩这种软件解压

唯一的区别就是,jar中有一个META-INF目录,这里面有一个MANIFEST.MF文件,该文件可能长这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Manifest-Version: 1.0
Implementation-Title: challenge
Implementation-Version: 0.0.1-SNAPSHOT
Built-By: shiyu
Implementation-Vendor-Id: io.tricking
Spring-Boot-Version: 2.1.0.RELEASE
Main-Class: org.springframework.boot.loader.JarLauncher
Start-Class: io.tricking.challenge.ChallengeApplication
Spring-Boot-Classes: BOOT-INF/classes/
Spring-Boot-Lib: BOOT-INF/lib/
Created-By: Apache Maven 3.5.3
Build-Jdk: 1.8.0_102
Implementation-URL: https://projects.spring.io/spring-boot/#/spring-bo
 ot-starter-parent/challenge

其中最关键的是Main-Class信息,即jar包的入口点

有些jar包可以通过java -jar a.jar这种命令被执行,此时Main-Class就指定从哪个类的Main函数开始执行

可以理解为,这个META-INF/MANIFEST.MF就是一个清单,表明该jar包的概要信息.

jar包其他文件主就是class字节码文件等

打包目的

打jar包的目的,实际上和c/c++中制作.lib静态库或者.dll动态库一样,就一个文件,方便别人拷贝使用

模块化,标准化

只要写好文档,告诉别人如何调用jar包中的类和函数即可

maven管理的第三方库,都是使用jar包的形式提供的

jar vs war

war包是Sun公司提出的web应用程序格式

两者相同点,都是一个压缩包

不同点,目录结构有区别

凡是能打war包的东西,必然能够打jar包

如何打包

源代码

源代码结构

1
2
3
4
5
6
7
8
9
10

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# tree src -f
src
└── src/top
    └── src/top/dustball
        ├── src/top/dustball/Dao
        │   └── src/top/dustball/Dao/User.java
        └── src/top/dustball/Main.java

3 directories, 2 files

其中User.java是一个pojo

1
2
3
4
5
6
7
8
9
10
11
12
13

package top.dustball.Dao;
public class User {
    String username;
    String password;

    public User(String username,String password){
        this.username=username;
        this.password=password;
    }    
    public String toString(){
        return "["+username+","+password+"]";
    }
}

Main.java是程序入口,依赖User类

1
2
3
4
5
6
7
8

package top.dustball;
import top.dustball.Dao.User;
public class Main {
    public static void main(String[] args) {
        User user = new User("vader", "sjh");
        System.out.println(user);
    }
}

javac编译

打入jar包的都是class字节码文件,没有java源文件,因此首先需要javac编译

可以使用javac <sourcefile> -d out将所有字节码文件打包到out目录下

这里sourcefile没有找到一个一劳永逸的方法

每个javac命令最多只能编译一个目录下的所有java文件

1
2
3
4

top.dustball/
	Dao/
		User.java
	Main.java

这里Dao/User.java和Main.java在不同的目录下,并且Main.java中依赖User.java,因此需要写一个很长的编译命令

1
2

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# javac src/top/dustball/Dao/*.java src/top/dustball/*.java -d out

更好的方法是将所有需要编译的源代码文件写到一份清单中,然后让javac根据清单工作,比如在根目录下写一个JavaList.txt

1
2

src/top/dustball/Dao/User.java
src/top/dustball/Main.java

此时在此处执行javac,就是javac的当前工作目录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# javac @JavaList.txt -d out

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# ls
bin  JavaList.txt  lib  out  README.md  src

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# tree -f out
out
└── out/top
    └── out/top/dustball
        ├── out/top/dustball/Dao
        │   └── out/top/dustball/Dao/User.class
        └── out/top/dustball/Main.class

3 directories, 2 files

此时在根目录下已经生成了out目录,保留了包结构和所有class文件,下一步就是打jar包了

jar打包

1
2
3
4
5
6
7
8
9

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# jar -cvf Main.jar out/top/dustball/Main.class out/top/dustball/Dao/User.class
added manifest
adding: out/top/dustball/Main.class(in = 523) (out= 341)(deflated 34%)
adding: out/top/dustball/Dao/User.class(in = 897) (out= 485)(deflated 45%)

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# ls *.jar
Main.jar

此时在jar工作目录,也就是跟目录下,生成了Main.jar其中都有啥呢?

1
2
3
4
5
6

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# jar -tf Main.jar
META-INF/
META-INF/MANIFEST.MF
out/top/dustball/Main.class
out/top/dustball/Dao/User.class

两个class都已经打包进入了Main.jar

关键在这个META-INF/MANIFEST.MF

提取Main.jar之后,该文件长这样

1
2

Manifest-Version: 1.0
Created-By: 11.0.17 (Debian)

唯一的有效信息是jdk版本11.0.17,Debian操作系统

没有Main-Class入口点信息,显然直接java -jar是不可以执行的

1
2
3

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# java -jar Main.jar
no main manifest attribute, in Main.jar

没有主属性清单

怎么改呢?

写到这里发现一个重大错误,包名不统一了

啥意思呢?

之前javac,jar的工作目录都是根目录,而包在src路径之下,是根目录的子目录

1
2
3
4
5
6

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# jar -tf Main.jar
META-INF/
META-INF/MANIFEST.MF
out/top/dustball/Main.class
out/top/dustball/Dao/User.class

此处out路径被当作了包的最外层,

可能是jar打包认为out也是包路径,但是class自己认为out不是包路径,此后就出错了

而实际上应该让包从top开始,如下:

1
2
3
4
5
6

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# jar -tf Main.jar
META-INF/
META-INF/MANIFEST.MF
top/dustball/Main.class
top/dustball/Dao/User.class

按照这样修改之后,在META-INF/MANIFEST.MF中这样写:

1
2
3
4

Manifest-Version: 1.0
Created-By: 11.0.17 (Debian)
Main-Class: top.dustball.Main

这就指定好了入口类

然后重新打包,这一次需要-m指定META-INF/MANIFEST.MF文件,作为jar包清单

1
2
3
4
5
6

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire]
└─# jar -cvfm Main.jar META-INF/MANIFEST.MF top/dustball/Main.class top/dustball/Dao
added manifest
adding: top/dustball/Main.class(in = 523) (out= 341)(deflated 34%)
adding: top/dustball/Dao/(in = 0) (out= 0)(stored 0%)
adding: top/dustball/Dao/User.class(in = 897) (out= 485)(deflated 45%)

执行

1
2
3

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire]
└─# java -jar Main.jar
[vader,sjh]

更灵活的打包方式

javac编译时,使用清单列出需要编译的源文件是一个好办法

jar打包时有没有更方便的方法呢?

刚才我们有两个打jar包的方式,其一是直接指定所有class文件

1

jar -cvf Main.jar out/top/dustball/Main.class out/top/dustball/Dao/User.class

此时Manifest文件是自动生成的,不包含入口点等信息

需要编写Manifest文件之后重新打包

1

jar -cvfm Main.jar META-INF/MANIFEST.MF top/dustball/Main.class top/dustball/Dao

奇怪的是,当时Dao/User.class没有敲上,敲到Dao就停了,也成功打包了

现在把修改后的META-INF/MANIFEST.MF整体拷贝到out目录下,现在的out目录:

1
2
3
4
5
6
7
8
9
10
11
12

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree/out]
└─# tree -f
.
├── ./META-INF
│   └── ./META-INF/MANIFEST.MF
└── ./top
    └── ./top/dustball
        ├── ./top/dustball/Dao
        │   └── ./top/dustball/Dao/User.class
        └── ./top/dustball/Main.class

4 directories, 3 files

在此处指定META-INF/MANIFEST.MF并打包

1
2
3
4
5
6
7
8
9
10
11
12
13
14

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree/out]
└─# jar -cvfm Main.jar META-INF/MANIFEST.MF *
added manifest
ignoring entry META-INF/
ignoring entry META-INF/MANIFEST.MF
adding: top/(in = 0) (out= 0)(stored 0%)
adding: top/dustball/(in = 0) (out= 0)(stored 0%)
adding: top/dustball/Dao/(in = 0) (out= 0)(stored 0%)
adding: top/dustball/Dao/User.class(in = 897) (out= 485)(deflated 45%)
adding: top/dustball/Main.class(in = 523) (out= 341)(deflated 34%)

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree/out]
└─# ls
Main.jar  META-INF  top

执行jar包

1
2
3

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree/out]
└─# java -jar Main.jar
[vader,sjh]

更更灵活的打包方式

在打包的时候不指定入口点而在执行的时候指定入口点

out目录状态:

1
2
3
4
5
6
7
8
9
10

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree/out]
└─# tree -f
.
└── ./top
    └── ./top/dustball
        ├── ./top/dustball/Dao
        │   └── ./top/dustball/Dao/User.class
        └── ./top/dustball/Main.class

3 directories, 2 files

直接再次处打jar包

1
2
3
4
5
6
7
8
9

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree/out]
└─# jar -cvf Main.jar *
added manifest
adding: top/(in = 0) (out= 0)(stored 0%)
adding: top/dustball/(in = 0) (out= 0)(stored 0%)
adding: top/dustball/Dao/(in = 0) (out= 0)(stored 0%)
adding: top/dustball/Dao/User.class(in = 897) (out= 485)(deflated 45%)
adding: top/dustball/Main.class(in = 523) (out= 341)(deflated 34%)

运行时指定入口点

1
2
3

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree/out]
└─# java -cp Main.jar top.dustball.Main
[vader,sjh]

依赖jar包

现在jar包中有一个top.dustball.User类,在Test类中调用之

在Test路径下有一个Main.jar这个包,还有测试类Test

1
2
3

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/Test]
└─# ls
Main.jar  Test.java

其中Test.java试图调用User类

1
2
3
4
5
6
7
8
9
10
11
12

package Test;

import top.dustball.Dao.User;

public class Test {
    public static void main(String[] args) {
        User user = new User("vader", "sjh");
        
        System.out.println(user);
    }
}

编译链接要加上-cp选项,指定依赖项

1 2	--class-path <path>, -classpath <path>, -cp <path> Specify where to find user class files and annotation processors

1

PS C:\Users\86135\Desktop\empire\Test> javac Test.java -cp Main.jar

由于Test.java有一个包Test,因此需要退到上级目录执行

1
2
3

PS C:\Users\86135\Desktop\empire\Test> cd ..
PS C:\Users\86135\Desktop\empire> java Test/Test
[vader,sjh]

命令

jar命令

jar命令是jdk的工具,该exe文件在jdk/bin目录下,需要将该bin目录添加到系统环境变量path,也就是配置jdk环境变量

jar -tf

列表列出jar包结构

1

jar -tf a.jar

1
2
3
4
5
6

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# jar -tf Main.jar
META-INF/
META-INF/MANIFEST.MF
out/top/dustball/Main.class
out/top/dustball/Dao/User.class

jar -xf

提取jar包文件,效果等同于解压

1
2
3
4
5
6
7
8
9
10
11

PS C:\Users\86135\Desktop\javacon> jar -xf challange.jar
PS C:\Users\86135\Desktop\javacon> ls

    Directory: C:\Users\86135\Desktop\javacon

Mode                 LastWriteTime         Length Name
----                 -------------         ------ ----
d----           2018/11/6    13:34                BOOT-INF
d----           2018/11/6    13:34                META-INF
d----           2018/11/6    13:34                org
-a---           2023/1/26    15:21       18134425 challange.jar

javac命令

javac java编译器,用于将源代码java文件编译为class字节码文件

javac可以类比为gcc或者g++

javac -d

指定class文件输出位置,保留包结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# tree src -f
src
└── src/top
    └── src/top/dustball
        ├── src/top/dustball/Dao
        │   └── src/top/dustball/Dao/User.java
        └── src/top/dustball/Main.java

3 directories, 2 files

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# javac src/top/dustball/Dao/*.java src/top/dustball/*.java -d out

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# ls
bin  lib  out  README.md  src

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree]
└─# tree out -f
out
└── out/top
    └── out/top/dustball
        ├── out/top/dustball/Dao
        │   └── out/top/dustball/Dao/User.class
        └── out/top/dustball/Main.class

3 directories, 2 files

javac -cp

链接外部依赖

1

PS C:\Users\86135\Desktop\empire\Test> javac Test.java -cp Main.jar

java命令

java -jar

执行自带入口点的jar包

java -cp

运行时指定jar包入口点

1
2
3

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/empire/empiree/out]
└─# java -cp Main.jar top.dustball.Main
[vader,sjh]

Class字节码文件

javac编译.java源文件之后生成的 class字节码文件

class文件其中都包含了什么?

java是如何编译链接的?

jar包和class的关系?

class文件能否理解为c语言编译生成的可重定位目标模块.o?

每个interface,每个类,都会编译生成一个class文件.即使两个类写到同一个java文件里了,编译后也会生成两个class文件

Point.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

package com.dustball;

import java.lang.Math;

interface Measurable {
  public double getDistance(Point p);
}

public class Point implements Measurable {

  protected double __x;
  protected double __y;

  public Point(double _x, double _y) {
    __x = _x;
    __y = _y;
  }

  public String toString() {
    return "(" + Double.toString(__x) + "," + Double.toString(__y) + ")";
  }

  public double getDistance(Point p) {
    double dist = 0;
    dist = (__x - p.__x) * (__x - p.__x) + (__y - p.__y) * (__y - p.__y);
    return Math.sqrt(dist);
  }
  public static void main(String[] args) {
    Point A=new Point(2,5);
    System.out.println(A.toString());
  }
}

class TaggedPoint extends Point {

  String __t;

  TaggedPoint(String _t, double _x, double _y) {
    super(_x, _y);
    __t = _t;
  }
}

final class Line {

  public Point __A;
  public Point __B;

  Line(Point _A, Point _B) {
    __A = _A;
    __B = _B;
  }
}

这里面有一个接口Measurable,一个Point类及其子类TaggedPoint,一个final类Line

编译后生成了四个文件

1
2
3
4
5
6
7
8
9
10
11
12

PS C:\Users\86135\Desktop\java\cmd\target\classes\com\dustball> ls

    Directory: C:\Users\86135\Desktop\java\cmd\target\classes\com\dustball

Mode                 LastWriteTime         Length Name
----                 -------------         ------ ----
-a---          2022/12/30    20:02            467 Line.class
-a---          2022/12/30    20:02            191 Measurable.class
-a---          2022/12/30    20:02           1004 Point.class
-a---          2022/12/30    20:02            456 TaggedPoint.class

PS C:\Users\86135\Desktop\java\cmd\target\classes\com\dustball> 010editor *.class

直接010editor *.class全部打开观察

class文件结构

整个class文件大体上线性地排列者以下几部分

magic

文件魔术0xCAFEBABE

minor_version/major_version

副/主 版本号

描述本class文件可以被java几执行

但是这个52是怎么来的?主版本号何曾到过52?

这是因为java的最初版本号是45,不是从0开始的

52是jdk1.8?然而我也不知道怎么换算的,可以从010editor模板代码中看出这一点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

string ClassFileOnComment(ClassFile &obj)
{
  switch(obj.major_version)
  {
    case 45:
      return "JDK 1.0 or JDK 1.1"; 
      break;
    case 46:
     return "JDK 1.2"; 
     break;
    case 47:
     return "JDK 1.3"; 
     break;
    case 48:
     return "JDK 1.4";
     break;
    case 49:
     return "JDK 1.5";
     break;
    case 50:
     return "JDK 1.6";
     break;
    case 51:
     return "JDK 1.7";
     break;
    case 52:
     return "JDK 1.8";
     break;
    case 53:
     return "JDK 1.9";
     break;
    default:
     return "JDK ?.?";
     break;
  }
}

constant_pool_count

常量池容量计数值,该值决定了紧接着的constant_pool[]数组的元素个数

constant_pool[]常量池

可以理解为可重定位目标模块中的符号表.symtab

这个数组的0下标位置是空出来不使用的,从1下标开始使用

0下标可以作为"空引用",也就是说其他元素引用0号元素意味着引用个寂寞

奇怪的是,这个数组的每个元素可以不一样大

正常c语言的结构体数组,每个元素都是相同大小的结构体,即使有些域用不到也得空着占位

而对于constant_pool:

每个元素最开始必然有一个tag成员,表明该元素是何种类型,也就确定了其占地大小,

常量池中主要存放两大类常量:字面量Literal和符号引用Symbolic References

access_flags

访问标志

两个字节表示的访问标志,用于描述本类的信息,多个属性按位或

索引集合

紧跟在访问标志之后,是

本类索引,

父类索引,

接口索引集合

只有接口是一个集合,是因为java中只允许单继承,父类只能有一个,但是接口可以实现多个

索引值是一个下标,比如this_class=1,意思是去常量池中找1号常量

tag=1表示utf8_info,即一个字符串

正好就是本类类名

又如super_class=3,意思是去常量池找3号常量

也是一个tag=1,utf8字符串,正好是Object类名

this_class和super_class之后是interfaces_count,一个整数表示本类实现了几个接口,有一个算一个都要列在后面的interfaces索引数组中

Point类只实现了一个Measurable接口他的索引号是5

字段表集合

用于描述接口或者类中声明的变量

首先是一个整数fields_count描述类有几个字段

紧跟着就是对每个字段的描述

这些描述包括:

access_flags,访问标志,包括static,public,final,volatile等等

name_index,符号名自己在常量池中的下标,也就是__x的下标

descriptor_index,类型名在常量池中的下标,也就是double的下标

attributes_count

access_flags

每一种属性占用一位,该位为0表示没有这种属性,为1表示有

共有16位,只用到9位

对于double __x;,其属性是0x0004(protected)

name_index

字段的简单名称

"简单名称"意思是没有加上类名前缀,

__x的完整名称应该是com/dustball/Point.__x

但是当前文件就是在描述Point类,显然没有必要再给其成员存放完整名称了

descriptor_index

描述符在符号表中的下标

描述符就是double,int等等的类型

只需要一个字符D就可以表明double类型

额外属性

额外属性可能有多个,因此首先一个attributes_count整数,表明有多少个额外属性

有多少个就在后面列明多少个

这里__x没有额外属性

方法表集合

方法表和字段表的结构比较相似

首先还是访问修饰

然后是简单名称引用和描述符引用

这两个合起来就正这样

<init>(DD)V这里<init>是构造函数名,(DD)表明两个double类型的参数,V表明无返回值

main([Ljava/lang/String;)V,这里main是主函数名([Ljava/lang/String;)注意这里中括号没有对齐,只有左中括号表明参数是一个数组类型

然后是attributes_count属性个数和attributes属性表

字段,方法都可以有属性表

方法编译成的opcode就放在其属性表中

属性表

Code属性

attribute_name_index=Code

表明这是Code属性

attribute_length

本属性的长度

max_stack

操作数栈深度最大值

max_locals

局部变量最大存储空间(单位:槽)

32位及以下数据用一个槽

64位及以上用两个槽

槽可以复用,函数中用完死了的变量给后面的新局部变量腾空

max_stack和max_locals两者共同决定了函数栈帧的大小

code_length

指令长度

code

指令码,可以类比作x86机器码

只不过这个指令是给JVM看的,x86机器码是给x86机器看的

用javap 反编译也可以看到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public com.dustball.Point(double, double);
  descriptor: (DD)V
  flags: (0x0001) ACC_PUBLIC
  Code:
    stack=3, locals=5, args_size=3
       0: aload_0
       1: invokespecial #13                 // Method java/lang/Object."<init>":()V
       4: aload_0
       5: dload_1
       6: putfield      #16                 // Field __x:D
       9: aload_0
      10: dload_3
      11: putfield      #18                 // Field __y:D
      14: return
    LineNumberTable:
      line 14: 0
      line 15: 4
      line 16: 9
      line 17: 14
    LocalVariableTable:
      Start  Length  Slot  Name   Signature
          0      15     0  this   Lcom/dustball/Point;
          0      15     1    _x   D
          0      15     3    _y   D
  MethodParameters:
    Name                           Flags
    _x
    _y

至于java自己造的给虚拟机看的那些指令,现在不想研究

关于jvm多重要多重要,感觉都是大量java码农吹出来的.不如看先看明白CSAPP

java编译链接

同一包下有两个文件,存在依赖关系

App.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14

package top.dustball;
import top.dustball.Point;

public class App 
{

    public static void main( String[] args )
    {

        Point p=new Point(2,5);
        System.out.println(p.toString());
    }
}

Point.java

1
2
3
4
5
6
7
8
9
10
11
12

package top.dustball;
public class Point {
    double x;
    double y;
    public Point(double x,double y){
        this.x=x;
        this.y=y;
    } 
    public String toString(){
        return "("+x+","+y+")";
    }
}

其中App.java中,Main函数引用Point构造函数和toString函数

如果只编译App.java会报告找不到符号出错误

需要同时编译App.java和Point.java

1

javac App.java Point.java 

在同一目录下生成Point.class和App.class文件

如果要用java执行App.class文件,需要推到包路径下java top/dustball/App

1
2
3
4
5
6
7

PS C:\Users\86135\Desktop\vsJava\empire\src\main\java\top\dustball> javac App.java Point.java 
PS C:\Users\86135\Desktop\vsJava\empire\src\main\java\top\dustball> java App
错误: 找不到或无法加载主类 App
原因: java.lang.NoClassDefFoundError: top/dustball/App (wrong name: App)
PS C:\Users\86135\Desktop\vsJava\empire\src\main\java\top\dustball> cd ../../
PS C:\Users\86135\Desktop\vsJava\empire\src\main\java> java top/dustball/App
(2.0,5.0)

这两个class文件都有用,如果把Point.class搬走,只执行App.class会报告链接错误

1
2
3
4
5

PS C:\Users\86135\Desktop\vsJava\empire\src\main\java> java top/dustball/App
(2.0,5.0)
PS C:\Users\86135\Desktop\vsJava\empire\src\main\java> java top/dustball/App       
错误: 加载主类 top.dustball.App 时出现 LinkageError
        java.lang.ClassFormatError: Incompatible magic value 1347093252 in class file top/dustball/App

这个Point.class的位置在导入类的时候就决定了

1
2

package top.dustball;
import top.dustball.Point;

也就是说必须得和App同一路径下

jar包

java archieve

文件魔数是504B0304,和zip压缩包是相同的

解压缩或者jar -xf 命令均可以拆jar包

1
2
3
4
5
6
7
8
9
10
11
12

PS C:\Users\86135\Desktop\jar> jar -xf junit-4.13.2.jar
PS C:\Users\86135\Desktop\jar> ls

    Directory: C:\Users\86135\Desktop\jar

Mode                 LastWriteTime         Length Name
----                 -------------         ------ ----
d----           2021/2/13    17:31                junit
d----           2021/2/13    17:31                META-INF
d----           2021/2/13    17:31                org
-a---            2023/1/3    21:30         384581 junit-4.13.2.jar
-a---           2021/2/13    17:31          11376 LICENSE-junit.txt

解出来/org/junit和/junit两个目录下面都是class文件

因此实际上jar包可以理解为静态库,里面的class文件可以理解为可重定位目标模块

麻了麻了怎么用jar包,jar包如何自己运行,用到时候再看吧,全是答辩

数位DP

P2602 数字计数

给定正整数a,b,求\([a,b]\)所有的整数中,0到9每个数码各自总共出现多少次

由前缀和的思想,设\(sum[n]\)表示\([0,n]\)中0到9各个数码各自出现了多少次

那么\(sum[b]-sum[a-1]\)就是所求值

问题转化为如何求\(sum[n]\)即\([0,n]\)中0到9各个数码各自出现了多少次

设计状态\(dp[i]\)表示"当范围涵盖了完整的i位时,前i位中每个数字出现的次数."

啥意思呢?

比如对于\([1000,1999]\)显然能够找出i=1的完整区间,比如\([1000,1009]\)等等

显然也能够找出i=2的完整区间,比如\([1900,1999]\)等等

显然也能够找出i=3的完整区间,比如\([1000,1999]\),只有这一个

找不出i=4的完整区间了

如果对于[10,2000000],这就可以找到i=4的完整区间,也就是低四位能够遍历[0,9999]这个范围的区间,比如

\([10000,19999]\)

这样设计dp有一个隐患就是,忽略了前导0的区别.比如给定区间[0,999],显然最大可以找到i=3的区间[0,999]

但是正常情况下,0不能作为前导,也就是说不能有012或001或000或020这种数字,可以有210或100这种数字

最后再考虑去除前导零的情况,现在先不考虑

状态转移方程为: \[ dp[i]=10\times dp[i-1]+10^{i-1} \] 如何考虑这个方程呢?排列组合问题

第i位假设放了一个X(先不管到底放了啥),考虑他对低i-1位的影响,

X有0,1,2,...,9十种可能,于是之前计算得到的dp[i-1]就得乘以10,

也就是说,1在低i-1上出现过\(10\times dp[i-1]\)次

okk,现在看低i-1位给第i位造成的影响,第i位假如放一个1,低i-1位随便放有\(10^{i-1}\)种放法

因此1就在第i位上出现过\(10^{i-1}\)次

举个实际例子,以[0,999]为例,前导零的情况也计算在内

\(dp[1]=1\),边界条件,意思是区间为[0,9]的时候,一个数字显然只出现一次

\(dp[2]=10\times dp[1]+10^{1}=20\)

假设个位上放一个X,十位有十种可能,0X,1X,2X,3X,...,9X,也就是说,十位对个位计数的贡献就是\(10\times dp[1]\)

假设十位上放一个X,个位有十种可能,X0,X1,X2,X3,...,X9.也就是说,个位对十位计数的贡献就是\(10^{1}\)

笑死,只有两位,要不你影响我,要不我影响你,怎么贡献方式还不一样?

再多一位就可以体现了

\(dp[3]=10\times dp[2]+10^{2}=300\)

这时候发现貌似不容易计算百位对于前两位的贡献了,如何解释\(10\times dp[2]\)怎么来的呢?

可以这样想:

原来在计算\(dp[2]\)时,这样只有一个[0,99]区间,而考虑了百位之后,就有

\([0,99],[100,199],[200,299],...,[900,999]\)这10个区间了,每个区间内数字的出现个数都是\(dp[2]\)现在有十个相同区间,因此当有三位的时候,从前两位计算得到的数字出现个数就是\(10\times dp[2]\)

假设百位上放一个X,前两位稍微一动就是一个新数,X就得多记录一次

比如X23,X24,X25,这样百位上的X就记了3次.那么前两位一共有多少种可能的排列呢?\(10^2\)那么X在第三位上出现的次数就是\(10^2\)

然后考虑如何去除前导0

去除前导零,也就是给0的计数中去掉0出现在最高位的情况

去除前导0,只会对0的计数有影响,对其他数字没有影响,因为

012345去除前导0不是说把012345给去掉,而是保留12345,12345这五个数字各自统计一次,0此时不应计数

要去除i=6上的前导零计数,也就是去除

0XXXXX这种情况对0计数的贡献,显然有\(10^5\)种

去除i=5上的前导零计数,也就是去除

0XXXX这种情况对0计数的贡献,显然有\(10^4\)种

也就是去除第i位上的前导0影响,就是去除\(10^{i-1}\)次0的计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=15;
long long dp[maxn];
long long pow_10[maxn];

vector<long long> solve(long long n){
    long long temp=n;
    int length=0;
    int top[maxn];
    vector<long long> result(10);
    while(n){
        top[++length]=n%10;
        n/=10;
    }
    for(int i=length;i>=1;--i){
        for(int j=0;j<10;++j){
            result[j]+=dp[i-1]*top[i];
        }
        for(int j=0;j<top[i];++j){
            result[j]+=pow_10[i-1];
        }
        temp-=pow_10[i-1]*top[i];
        result[top[i]]+=temp+1;
        result[0]-=pow_10[i-1];
    }
    return result;
}
long long l,r;
int main(){
    cin>>l>>r;
    pow_10[0]=1;
    for(int i=1;i<maxn;++i){
        dp[i]=dp[i-1]*10+pow_10[i-1];
        pow_10[i]=10*pow_10[i-1];
    }
    vector<long long>left=solve(l-1);
    vector<long long>right=solve(r);
    for(int i=0;i<=9;++i){
        cout<<right[i]-left[i]<<" ";
    }
    return 0;
}

其中比较抽象的是后面这个循环,他里面都干了什么呢?

1

for(auto j=0;j<10;++j)result[j]+=dp[i-1]*top[i];

计算当前位i随便安排时,对前i位中,数位统计的贡献

使用\(top[i]\)因为第i位上只有\([0,top[i]-1]\)共\(top[i]\)种情况

为什么不是\([0,top[i]]\)共\(top[i]+1\)种情况?假如对于\([0,6524]\)

当前i=4,top[4]=6,可以找到区间[0,999],[1000,1999]

[2000,2999],[3000,3999],[4000,4999],[5000,5999]

共6个=top[4]

没有包括[6000,6999],因为最大到6524,即top[i]作为最高位时前i位找不出完整的区间来

1

for(auto j=0;j<top[i];++j)result[j]+=pow(10,i-1); 

计算前i位随便安排时,对第i位数位统计的贡献

由于最高位上只可能出现\([0,top[i]-1]\),再高top[i]没有完全区间,再高\(top[i]+1\)不可能出现,因此不能统计对\([top[i],9]\)这些数字的贡献

比如当n=6524

i=6,也就是说存在1XXX,2XXX,3XXX,4XXX,5XXX这些完整区间(XXX表示[0,999])

6XXX没有完全区间,只有[6000,6524]

更不存在7XXX了

1
2
3

       
temp-=pow(10,i-1)*top[i];//去掉最高位
result[top[i]]+=temp+1;//之前统计贡献时,i位的最高数字总是不满区间,现在单独处理

啥意思呢?还是n=6524举例子

temp=n=6524

然后temp=6524-6000=524

这524就是对top[4]=6统计次数的贡献,也就是6在i=4位上出现了524+1=525次

加一的原因是,524表示[0,524]共525种情况

1

result[0]-=pow(10,i-1);//去除前导零

前导零有多种情况,比如0524,0024,0004,0000

这里每次只会处理一种情况,i=4时只会消除0999,0998,...,0000这种前导0.

P8764 二进位问题

\([1,n]\)这些整数中,二进制表示有k个1的有多少个

如果问题变成:m个二进制位,其中有k个1的有多少个数

显然是\(C_m^k\)

假设n表示成二进制形式之后,最高位是\(bit[len]=1\),最低位是\(bit[1]\)

显然前\(len-1\)位所有状态都包含在内了,因此首先有\(C_{len-1}^k\),也就是最高位位0时,低\(len-1\)位任意安排

下面考虑最高位为1的情况,

从次高位\(bit[len-1]\)往低位bit[1]方向看

如果\(bit[i]\)为0则跳过,否则加上\(C_{i-1}^{k-t}\)

其中t表示\([i+1,len]\)这些位上的1个数

比如\(n=101000,len=6\)

为啥加上这个数呢?第4位上有一个1,这表明存在

\([100000b,100111b]\),低三位存在完整区间,从这个完整区间中统计有\(k-1\)个1的数,是因为之前已经有一个1了,需要在剩下的位中找出k-1个1即可

现在的主要问题是如何快速求解\(C_m^k\)

\(C_m^0=1\)

\(C_m^k=C_{m-1}^{k-1}+C_{m-1}^k\)

用\(c[m][k]\)数组预处理即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//c[m][k]
const int maxm=100;
const int maxk=100;
long long c[maxm][maxk];


void init(){
    // c[1][0]=c[1][1]=1;
    c[0][0]=1;
    for(int i=1;i<maxm;i++){
        c[i][0]=1;
        for(int j=1;j<i;++j){
            c[i][j]=c[i-1][j-1]+c[i-1][j];
        }
        c[i][i]=1;
    }
}
void print(){
    for(int i=1;i<20;i++){
        for(int j=0;j<=i;j++){
            cout<<c[i][j]<<" ";
        }
        cout<<endl;
    }
}

long long n;
int k;
long long bit[maxm];
long long len;

int main(){
    init();
    cin>>n>>k;
    long long temp=n;
    while(temp){
        bit[++len]=temp&1;
        temp>>=1;
    }
    long long result=0;
    result+=c[len-1][k];
    int t=1;
    for(int i=len-1;i>=1;--i){
        if(bit[i]==0){
            continue;
        }
        if(k-t<0)break;
        result+=c[i-1][k-t];
        ++t;

    }
    cout<<result<<endl;

    return 0;
}

P2657 windy数

定义windy数:相邻两个十进制位必须至少差2,比如135,2597等等

给定区间[l,r]求这之间的windy数有多少

问题转化为[1,n]中的windy数有多少

设计状态: \[ dp[i][j]表示i个10进制位,最高位第i位上是j的windy数的个数 \] 边界条件显然是只有一位的时候,\(dp[1][j]=1\)

转移方程: \[ dp[i][j]=\sum_{|k-j|\ge2}dp[i-1][k] \]

下面考虑[1,n]中有多少windy数

首先划分成十进位

dec[len],dec[len-1],...,dec[1],最高位是dec[len]

那么显然有低len-1位的完整区间,全算上

第len位上,从1到dec[len]-1这些dp[len][i]也是都有的

只剩下len位上放dec[len]的情况了,这是最贴近上边界的情况,如何考虑?

i从len-1往1遍历

对于当前位i,尝试放置\(0\le j<dec[i]\),因为第i位最高可以为dec[i],比他小的数都存在

然后判断j是否合法,依据就是j和dec[i+1]距离是否大于等于2,

如果是,则加上\(dp[i][j]\)

这样第i位就统计完毕,尝试往更低位统计,第i位最终放置的是dec[i]

如果dec[i+1]和dec[i]相差小于2,就不能继续往低位统计了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn=20;
long long dp[maxn][10];
void init(){
    for(int j=0;j<10;++j){
        dp[1][j]=1;
    }
    for(int i=2;i<maxn;i++){
        for(int j=0;j<10;++j){
            for(int k=0;k<10;k++){
                if(abs(j-k)>=2){
                    dp[i][j]+=dp[i-1][k];
                }
            }
        }
    }
}
long long solve(int n){
    if(n==0){
        return 0;
    }
    long long result=0;
    long long temp=n;
    long long dec[maxn];
    memset(dec,0,sizeof(dec));
    int len=0;
    while(temp){
        dec[++len]=temp%10;
        temp/=10;
    }
    // cout<<"actived"<<endl;
    for(int i=1;i<=len-1;++i){
        for(int j=1;j<=9;++j){
            result+=dp[i][j];
        }
    }
    for(int j=1;j<dec[len];++j){
        result+=dp[len][j];
    }
    for(int i=len-1;i>=1;--i){
        // cout<<"in loop"<<endl;
        for(int j=0;j<=dec[i]-1;++j){
            if(abs(j-dec[i+1])>=2){
                result+=dp[i][j];
            }
        }
        if(abs(dec[i]-dec[i+1])<2){
            break;
        }
    }



    return result;
}


int l,r;

int main(){
    cin>>l>>r;
    init();
    // cout<<solve(r+1)<<endl<<solve(l)<<endl;
    cout<<solve(r)-solve(l-1)<<endl;


    return 0;
}

P4999 烦人的数学作业

给定区间[l,r],求每个数各个十进制位的数字和

比如[123,125],就有1+2+3+1+2+4+1+2+5

首先问题转化为[1,n]区间上拆分数字和P1836 数页码

然后问题还可以转化为P2602求每个数字出现的次数

最终累计i×i的出现次数即可

后端MVC框架

参考SMBMS: 跟着狂神做超市订单管理系统 (gitee.com)

MVC框架的使用时机

当需求分析结束后,数据库也已经建立完毕了.建立了四张数据表

1
2
3
4
5
6
7
8
9
10
11
12

mysql> use smbms;
Database changed
mysql> show tables;
+-----------------+
| Tables_in_smbms |
+-----------------+
| smbms_bill      |
| smbms_provider  |
| smbms_role      |
| smbms_user      |
+-----------------+
4 rows in set (0.00 sec)

下面的任务就是写后端逻辑代码了,此时使用MVC框架建立项目

MVC框架是什么

整个后端在MVC框架中分了三层,DAO,Service,Controller

DAO层:data access object,数据访问层.每一个DAO类一定对应一个数据表,DAO类的函数,只做原子操作,CRUD

一个函数只实现一个功能,比如给定一个账单号,查库删除该账单

或者给定一个用户名和新密码,修改其密码.

可以理解为,DAO类的函数,一般只执行一条sql语句,一般只影响一行

Service层:服务层.对Dao层的包装,一个Service层函数可能调用一个或者多个Dao层函数.返回pojo对象.

比如service上一个login(userCode,userPassword),首先会用userCode去查smbms_user表,然后用获取到的表项实例化一个user pojo,然后user.getPassword和userPassword进行对比,相同则返回user对象,否则返回null指针

Controller层:控制层,由Servlet实现,直接接收来自前端的get或者post请求,提取参数,决定使用哪种服务

画个图表示一下

MVC框架如何作用

以登录逻辑为例,分析从前端请求到获得响应的整个过程

1.前端发起HTTP请求

请求服务端你的login.do资源,携带两个get参数

目标DNS:localhost,会被本地hosts文件映射到IP:127.0.0.1

目标端口:8080

2.该请求到达了服务端

经过TCP/IP协议栈,将HTTP报文交给位于应用层的web服务器(tomcat)

3.服务器首先查询web.xml

找到login.do这路径应该映射给控制层的LoginServlet

1
2
3
4
5
6
7
8

<servlet>
    <servlet-name>LoginServlet</servlet-name>
    <servlet-class>com.threepure.servlet.user.LoginServlet</servlet-class>
</servlet>
<servlet-mapping>
    <servlet-name>LoginServlet</servlet-name>
    <url-pattern>/login.do</url-pattern>
</servlet-mapping>

至于tomcat具体怎么将HTTP请求报文交给LoginServlet的,目前不清楚,留作后话

可能手写一个玩具tomcat服务器就知道了,但不是现在

于是将该get请求交给LoginServlet.doGet(req,resp)

4.调用控制层LoginServlet.doGet函数

首先提取参数

1
2

String userCode = req.getParameter("userCode");
String userPassword = req.getParameter("userPassword");

然后调用服务层,查询用户名密码是否正确

1
2

UserServiceImpl userService = new UserServiceImpl();
User user = userService.login(userCode, userPassword);

这里user是一个pojo类型,其属性和user数据表的属性一一对应,一个user对象对应一条user表的记录

然后根据user是否为空,决定是否登陆成功

1
2
3
4
5
6
7

if (user!=null){//user非空说明存在该用户且用户名密码正确
    req.getSession().setAttribute(Constants.USER_SESSION, user);//设置session
    resp.sendRedirect("jsp/frame.jsp");//跳转登录之后的界面
}else {//要么不存在用户名,要么密码错误,反正登不上
    req.setAttribute("error", "用户名或者密码错误");
    req.getRequestDispatcher("login.jsp").forward(req, resp);//重新登录
}

结果有两个,

一个是设置session,保存用户登录状态,也就是设置了访问权限,此后过滤器会根据是否有session决定能否访问网站资源

一个是返回resp,设置页面重定向.实际上是返回了重定向的HTTP respond报文

5.调用服务层userService.login(userCode, userPassword)函数

首先提升作用域,建立两个局部变量

1
2

Connection connection = null;
User user = null;

connection的建立和销毁都由本login函数决定,也就是资源的创建和销毁是Service服务层决定的

然后调用Dao层函数,根据userDao.getLoginUser(connection, userCode)查询是否存在用户

1
2
3
4
5
6
7
8

try {
    connection = DruidDao.getConnection();
    user = userDao.getLoginUser(connection, userCode);
} catch (SQLException throwables) {
    throwables.printStackTrace();
} finally {
    DruidDao.closeResource(null, null, connection);
}

查完了立刻在finally中释放资源

如果存在该用户,Dao层会返回一个user pojo,和数据库中该用户的记录对应.

然后要判断用户密码是否正确,如果正确返回该pojo,控制层会使用该pojo执行其他业务.

如果密码错误或者user不存在,均会返回null,控制层发现该返回值为null就知道了用户名密码错误

1
2
3
4
5
6

if (user != null) {
    if (!user.getUserPassword().equals(password)) {
        user = null;
    }
}
return user;

6.调用DAO层userDao.getLoginUser(connection, userCode)函数

首先提升作用域,创建局部变量

1
2
3

PreparedStatement pstm = null;
ResultSet rs = null;
User user = null;

然后调用DAO公共底层DruidDao.execute函数,查库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

       if (connection != null) {
           String sql = "select * from smbms_user where userCode=?";
           Object[] params = {userCode};
           try {
               rs = DruidDao.execute(connection, pstm, rs, sql, params);//rs可能有多条
               if (rs.next()) {//最终user是rs的最后一条记录
                   user = new User();
                   user.setId(rs.getInt("id"));//使用rs记录实例化一个pojo
                   user.setUserCode(rs.getString("userCode"));
                   user.setUserName(rs.getString("userName"));
                   user.setUserPassword(rs.getString("userPassword"));
                   user.setGender(rs.getInt("gender"));
                   user.setBirthday(rs.getDate("birthday"));
                   user.setPhone(rs.getString("phone"));
                   user.setAddress(rs.getString("address"));
                   user.setUserRole(rs.getInt("userRole"));
                   user.setCreatedBy(rs.getInt("createdBy"));
                   user.setCreationDate(rs.getTimestamp("creationDate"));
                   user.setModifyBy(rs.getInt("modifyBy"));
                   user.setModifyDate(rs.getTimestamp("modifyDate"));
               }
               DruidDao.closeResource(rs, pstm, connection);//释放资源
           } catch (SQLException throwables) {
               throwables.printStackTrace();
           }
       }
return user;

7.调用DAO层公共函数Druid.execute

CRUD根据读写性质分成两种,只读的查,和读写的增删改

并且只有查询要返回记录,其他的操作只需要返回几行受到影响即可

因此execute有两个重载,一个负责只读的查,一个负责读写的增删改

这里使用sql预编译,目的是提高速度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

/**
 * @description:编写查询公共方法
 */
public static ResultSet execute(Connection connection, PreparedStatement preparedStatement, ResultSet resultSet, String sql, Object[] params) throws SQLException {
    preparedStatement = connection.prepareStatement(sql);
    for (int i = 0; i < params.length; i++) {
        //setObject()占位符是从1开始，而数组是从0开始；
        preparedStatement.setObject(i + 1, params[i]);
    }
    System.out.println("DruidDao>>查>>SQL :" + preparedStatement.toString());
    resultSet = preparedStatement.executeQuery();
    return resultSet;
}

/**
 * @description:编写增删改公共方法
 */
public static int execute(Connection connection, PreparedStatement preparedStatement, String sql, Object[] params) throws SQLException {
    preparedStatement = connection.prepareStatement(sql);
    for (int i = 0; i < params.length; i++) {
        //setObject()占位符是从1开始，而数组是从0开始；
        preparedStatement.setObject(i + 1, params[i]);
    }
    System.out.println("DruidDao>>增删改>>SQL :" + preparedStatement.toString());
    return preparedStatement.executeUpdate();
}

MVC框架的建立过程

参考SMBMS: 跟着狂神做超市订单管理系统 (gitee.com)

准备工作

0.搭建服务器环境,使用tomcat服务器部署javaweb项目

1.建立pojo目录,在该目录下,给每个数据表建立一个一一对一个的pojo类

1
2
3
4
5

smbms/src/main/java/top/dustball/pojo/
	User.java
	Provider.java
	Bill.java
	Role.java

2.建立Dao层公共底层类,实现execute函数

1
2

smbms/src/main/java/top/dustball/dao/
	DaoBase.java

3.引入资源,包括前端的jsp页面,js,css文件.数据库连接设置

1
2

smbms/src/main/java/resources/
	db.properties

1
2
3
4
5
6
7
8
9
10
11
12

smbms/src/main/webapp/
	jsp/
		...
	js/
		...
	css/
		...
	images/
		...
	login.jsp
	error.jsp
	...

其中smbms/src/main/webapp/这下面的jsp,js,css,images等都是前端的工作.

前端和后端的接口是jsp和web.xml共同决定的,请求路径以及get或者post的参数名称

1
2

login.jsp
<form class="loginForm" action="${pageContext.request.contextPath }/login.do"  name="actionForm" id="actionForm"  method="post" >

1
2
3
4
5
6
7
8
9

web.xml
    <servlet>
        <servlet-name>LoginServlet</servlet-name>
        <servlet-class>com.threepure.servlet.user.LoginServlet</servlet-class>
    </servlet>
    <servlet-mapping>
        <servlet-name>LoginServlet</servlet-name>
        <url-pattern>/login.do</url-pattern>
    </servlet-mapping>

至于前端的页面长什么样,后端不用管,后端只关心控制层接收到的get参数叫什么,是叫"username",还是"UserName"还是"userCode".

前端需要知道一个get请求应该发往哪一个Servlet

只有这两个是前后端开发者需要协商的

4.建立字符过滤器,设置前后端都使用utf-8编码

自顶向下还是自底向上

目前感觉两种方法均可

两头都很具体,顶上是前端写好的请求,参数名都已知,交给哪一个Servlet也是确定的

底下有几个数据表,都长什么样也是确定的

中间的service层很多情况下只是对Dao层的一个薄封装,以service层的UserServiceImpl.login函数为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public User login(String userCode, String password) {
    Connection connection = null;
    User user = null;

    try {
        connection = DruidDao.getConnection();
        user = userDao.getLoginUser(connection, userCode);
    } catch (SQLException throwables) {
        throwables.printStackTrace();
    } finally {
        DruidDao.closeResource(null, null, connection);
    }
    //进行密码匹配
    if (user != null) {
        if (!user.getUserPassword().equals(password)) {
            user = null;
        }
    }
    return user;
}

实际上这么一长段的核心功能就是

接收一个userCode一个password,返回一个user pojo.就是多加了一个密码判断

UserServiceImpl.updataPwd更明显,直接调用了Dao层,除此之外啥也没干

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public boolean updatePwd(int id, String pwd) {
    Connection connection = null;
    boolean flag = false;

    try {
        connection = DruidDao.getConnection();
        if (userDao.updatePwd(connection, id, pwd) > 0) {
            flag = true;
        }
    } catch (SQLException throwables) {
        throwables.printStackTrace();
    } finally {
        DruidDao.closeResource(null, null, connection);
    }
    return flag;
}

还是采用自顶向下吧,根据前端存在的需求,决定后端写哪些服务

比如对于用户表,不存在修改用户名的需求,因为有新建用户就够了.

如果自底向上写的话,不知道需要对用户表的哪些字段进行什么操作.

如果自顶向下写的话,首先知道的就是需求,然后根据需求决定下层要提供什么服务,然后再实现该服务,不需要的服务不写

建立Controller层

前端和后端商量好的,前端可能会产生哪些请求,每个请求发给哪个servlet

再细分一下,感觉

1
2
3
4
5

这是前端写的
	<servlet-mapping>
        <servlet-name>LoginServlet</servlet-name>
        <url-pattern>/login.do</url-pattern>
    </servlet-mapping>

1
2
3
4
5
6

这是后端写的
	<servlet>
        <servlet-name>LoginServlet</servlet-name>
        <servlet-class>com.threepure.servlet.user.LoginServlet</servlet-class>
    </servlet>

现在就面临一个问题

用户的行为可能有很多,比如登录,注销,修改密码,订单管理,供应商管理等等

这么多行为,应该用几个servlet实现?

针对用户的行为,有三个Servlet,LoginServlet,LogoutServlet,UserServlet

为啥要这样划分?

首先考虑权限问题,前端是无法过滤请求的,权限控制只能是后端的权限过滤器来做

权限过滤器根据session是否设置决定能否请求资源,对任何/jsp/*的请求生效

用户的行为中,只有登录界面是在设置session前可以访问的,因此webapp下面的login.jsp不会被权限过滤,任何情况均可访问

因此登录行为自己建立一个LoginServlet

登录和注销,两个行为都会更改session状态,因此各自一个Servlet处理业务

其他的用户行为都需要登录权限,因此在jsp目录下,收到权限过滤器保护,这些行为都有session状态,都发往一个UserServlet

通过一个method参数,决定该UserServlet调用何种服务

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
    String method = req.getParameter("method");
    if ("savepwd".equals(method) && method != null) {
        this.updatePwd(req, resp);
    } else if ("pwdmodify".equals(method) && method != null) {
        this.pwdmodify(req, resp);
    } else if ("query".equals(method) && method != null) {
        this.userQuery(req, resp);
    } else if ("add".equals(method) && method != null) {
        this.add(req, resp);
    } else if ("getrolelist".equals(method) && method != null) {
        this.getRoleList(req, resp);
    } else if ("ucexist".equals(method) && method != null) {
        this.userCodeExist(req, resp);
    } else if ("view".equals(method) && method != null) {
        this.getUserById(req, resp, "userview.jsp");
    } else if ("modify".equals(method) && method != null) {
        this.getUserById(req, resp, "usermodify.jsp");
    } else if ("modifyexe".equals(method) && method != null) {
        this.userModify(req, resp);
    } else if ("deluser".equals(method) && method != null) {
        this.deleteUser(req, resp);
    }
}

实际上是控制耦合,这个method参数就是控制开关

Bill和Provider各自只有一个Servlet,也在doGet方法上采用控制耦合

总的来说,尽量少建立Servlet,可以使用控制耦合,大体上还是一个数据表对应一个Servlet,所有发生在该表上的行为,用一个Servlet处理,通过method参数的不同区分Service层的服务

建立Service层

Controller层建立完毕之后,Service实际上已经固定了

User.getUserById给定一个用户名,查库建立一个user pojo,从控制层到服务层到数据访问层逐层往下扔就是了

1
2
3
4
5
6
7
8
9
10
11
12

Controller层User.getUserById
	private void getUserById(HttpServletRequest req, HttpServletResponse resp, String url) throws ServletException, IOException {
        //获取传入的id
        String uid = req.getParameter("uid");
        if (!StringUtils.isNullOrEmpty(uid)) {
            UserServiceImpl userService = new UserServiceImpl();
            User userById = userService.getUserById(uid);//往下扔
            req.setAttribute("user", userById);
            req.getRequestDispatcher(url).forward(req, resp);
        }
    }

建立DAO层

每一个数据表都会对应一个pojo类,一个Dao层类

每一个数据表都会对应一个pojo类,一个Dao层类

每一个数据表都会对应一个pojo类,一个Dao层类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Dao/
	│  DaoBase.java
	│
	├─bill
	│      BillDao.java
	│      BillDaoImpl.java
	│
	├─provider
	│      ProviderDao.java
	│      ProviderDaoImpl.java
	│
	├─role
	│      RoleDao.java
	│      RoleDaoImpl.java
	│
	└─user
	        UserDao.java
	        UserDaoImpl.java

比如用户表user,对应一个pojo User,然后在Dao/user/下面有一个UserDao接口和一个UserDaoImpl实现

这个UserDao接口干了啥呢?

每一个函数,都对应于一种user表中的原子操作(一条sql语句)

每一个函数,都对应于一种user表中的原子操作(一条sql语句)

每一个函数,都对应于一种user表中的原子操作(一条sql语句)

"中途优化是万恶之源"

等整个网站正常运行起来之后,再考虑如何优化,到那时候再考虑使用什么Druid连接池

最初就用最普通的mysql就可以了

Service层:

动态规划-区间DP

模板题一般长这样:

给一个区间[1,n]

给定一种操作:合并子区间,两个相邻子区间[i,j],[j+1,k]合并,得到一定的收益或者付出一些代价.这个收益或者代价必然是和两个子区间相关的函数,比如sum[i,j]+sum[j+1,k]

求将整个区间合并为一个数,获得的最大收益或者付出的最小代价

P1880 合并环状石子

一圈石子有n组,其中第i组有a[i]个,合并两组石子的代价是两组石子个数和,求将所有石子合并成一组需要的最大代价和最小代价

本题需要先把环拆成线,其弱化版也就是无环版本P1775 石子合并（弱化版

首先需要把这个圈解开,比较好的方法是将[1,n]展开成线性,然后复制一遍接到后面,就是

设计状态

\[ max\_dp[i][j]=将[i,j]区间合并成一组的最大代价\\ min\_dp[i][j]=将[i,j]区间合并 成一组的最小代价 \]

显然边界条件是: \[ \forall _{1\le i\le 2n}max\_dp[i][i]=0\\ \forall _{1\le i\le 2n}min\_dp[i][i]=0\\ \] 意思是将一组石子和自己合并(合并个寂寞),其代价为0,因为不需要合并

\[ max\_dp[i][j]=\max_{i\leq k<j}(max\_dp[i][k]+max\_dp[k+1][j])+\sum_{i\leq l\leq j}a[l]\\ min\_dp[i][j]=\max_{i\leq k<j}(min\_dp[i][k]+min\_dp[k+1][j])+\sum_{i\leq l\leq j}a[l] \]

其中\(\sum_{i\leq l\leq j}a[l]\)也就是从i到j的石子总个数,可以维护前缀和降低复杂度 \[ \sum_{i\leq l\leq j}a[l]=prefix[j]-prefix[i-1] \]

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <iostream>
#include <algorithm>
using namespace std;
int n;
const int INF=1e9;
const int maxn=210;
int value[maxn];
int max_dp[maxn][maxn];//max_dp[i][j]为合并闭区间[i,j]所需要的最大代价
int min_dp[maxn][maxn];
int prefix[maxn];
int main(){
    cin>>n;
    
    int v;
    prefix[0]=0;
    for(int i=1;i<=n;i++){
        cin>>v;
        value[i]=value[i+n]=v;
        prefix[i]=prefix[i-1]+value[i];
        max_dp[i][i]=max_dp[i+n][i+n]=0;//初始化边界条件,只有一堆时不需要合并,因此无代价
        min_dp[i][i]=min_dp[i+n][i+n]=0;
    }
    for(int i=1+n;i<=n*2;i++){
        prefix[i]=prefix[i-1]+value[i];
    }

    for(auto delta=1;delta<n;delta++){//delta,步长,确定区间左端点i之后,右端点j=i+delta,显然delta初始值应该是1
        for(auto i=1;i+delta<=2*n;i++){
            auto j=i+delta;
            auto temp_max=0;
            auto temp_min=INF;//临时变量,用于计算最值
            for(auto k=i;k<j;++k){
                temp_max=max(temp_max,max_dp[i][k]+max_dp[k+1][j]+prefix[j]-prefix[i-1]);//状态转移
                temp_min=min(temp_min,min_dp[i][k]+min_dp[k+1][j]+prefix[j]-prefix[i-1]);
            }
            max_dp[i][j]=temp_max;
            min_dp[i][j]=temp_min;
        }
    }
    int max_value=0;
    int min_value=1e9;
    for(int i=1;i<=n;i++){
        max_value=max(max_value,max_dp[i][i+n-1]);
        min_value=min(min_value,min_dp[i][i+n-1]);
    }
    cout<<min_value<<endl<<max_value<<endl;


    return 0;
}

P1063 合并能量珠子

每个珠子有两头,记作(l,r),相邻两个珠子的相向两头数值相同,比如 \[ (a,b)(b,c)(c,d)(d,a) \] 合并两个相邻珠子\((a,b)(b,c)\)得到的能量是\(a\times b\times c\),合并之后形成新珠子\((a,c)\)

将整个项链合并,求得到的最大能量值

还是将整个环拆成[1,n]然后拷贝一份接到后面

\(dp[i][j]\)表示合并区间[i,j]能够得到的最大能量,其中i表示第i个珠子,j表示第j个珠子

边界条件仍然是\(dp[i][i]=0\),只有一个珠子不需要合并

状态转移: \[ dp[i][j]=\max_{i\le k< j}(dp[i][k]+dp[k+1][j]+node[k].l\times node[k].r\times node[k+1].r) \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int maxn=210;
int n;
struct Bead{
    int __energy;//合并成当前珠子时能够获得的最大能量
    int __l;//左标记
    int __r;//右标记
    Bead(int _l=0,int _r=0,int _e=0):__l(_l),__r(_r),__energy(_e){}
    int l()const{
        return __l;
    }
    int r()const{
        return __r;
    }
    void setL(int _l){
        __l=_l;
    }
    void setR(int _r){
        __r=_r;
    }  
    void setEnergy(int _e){
        __energy=_e;
    }
    int energy(){
        return __energy;
    }
    string toString()const{
        return "("+to_string(__l)+","+to_string(__r)+")";
    }
    friend ostream &operator<<(ostream &os,const Bead &bead){
        os<<bead.toString();
        return os;
    }
}bead[maxn][maxn];
int dp[maxn][maxn];


int main(){
    cin>>n;
    int l;
    int r;
    for(int i=1;i<=n;i++){
        cin>>l;
        bead[i][i].setL(l);
        bead[i+n][i+n].setL(l);
        bead[i+n-1][i+n-1].setR(l);
        bead[i-1][i-1].setR(l);
    }
    bead[2*n][2*n].setR(bead[0][0].r());
    for(auto delta=1;delta<n;++delta){
        for(auto i=1;i+delta<=2*n;++i){
            auto j=i+delta;
            int max_energy=0;
            int temp_energy=0;
            int max_k=0;
            for(auto k=i;k<j;++k){
                
                temp_energy=max(max_energy,bead[i][k].energy()+bead[k+1][j].energy()+bead[i][k].l() * bead[i][k].r() * bead[k+1][j].r());
                if(temp_energy>max_energy){
                    max_energy=temp_energy;
                    max_k=k;
                }
            }
            bead[i][j].setEnergy(max_energy);
            bead[i][j].setL(bead[i][max_k].l());
            bead[i][j].setR(bead[max_k+1][j].r());
        }
    }
    int result=0;

    for(int i=1;i<=n;i++){
        int j=i+n-1;
        result=max(result,bead[i][j].energy());
    }
    cout<<result<<endl;
    return 0;
}

P1005 矩阵取数

对于一个给定的 \(n \times m\) 的矩阵，矩阵中的每个元素 \(a_{i,j}\) 均为非负整数。游戏规则如下：

1. 每次取数时须从每行各取走一个元素，共 \(n\) 个。经过 \(m\) 次后取完矩阵内所有元素；
2. 每次取走的各个元素只能是该元素所在行的行首或行尾；
3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 \(\times 2^i\)，其中 \(i\) 表示第 \(i\) 次取数（从 \(1\) 开始编号）；
4. 游戏结束总得分为 \(m\) 次取数得分之和。

对于任意矩阵，可以求出取数后的最大得分。

由于第i次取数的权重为\(2^i\),显然应尽量保留大数放到最后取

并且取第一行和第二行的数没有影响

因此实际上可以先解决一行内的取数问题,问题转化为:

m个数,第i个数是a[i],每次取数只能从头或者尾取数,第j次取数x的得分是\(2^j\times x\),求m次取数最高得分

如果没有只能头尾取数的限制,显然直接m个数排序后按照从小到达的顺序取数,现在有一个只能从头或者尾取数的限制

暴力搜索的算法容易想到dfs(deque,level)表示当前双端队列deque,当前要取第level个数

但是m最大为80,这就意味着dfs的时间复杂度是\(O(2^{80})\)显然超时

显然要使用更吊的方法

设计状态: \[ dp[i][j]\leftarrow要在闭区间[i,j]中取数,全部取完后最终能够得到的最大值 \]

状态转移: \[ dp[i][j]=max(dp[i][j-1]+a[j][j]\times 2^k,dp[i+1][j]+a[i][i]\times 2^k) \] 其中k是第k次取数,k=n-i-j+2

dp[1][n]是第1次取数

屑题害得考尼玛的高精度,有个🔨意思啊,没活可以咬打火机

P4767 邮局

v个村庄,p个邮局

第i个村庄在a[i]位置

邮局都要建在村庄里,要求所有村庄到最近邮局的距离和最小

求这个最小距离和是多少

设计状态: \[ dp[i][j]表示前i个村庄放了j个邮局,最小距离和 \]

状态转移 \[ dp[i][j]=\min_{1\le k\le i}(dp[k][j-1]+w(k+1,i)) \] 其中\(w(l,r)\)表示,在第l个和第r个(包括两头)村庄之间放一个邮局时,这一段上的村庄的最短距离和

这个玩意儿怎么求呢?

设\([l,r]\)区间上的村庄坐标为\(x[l],x[l+1],x[l+2],...,x[r-1],x[r]\)

假设放这个邮局的坐标为\(x\),则问题相当于 \[ w(l,r)=min(|x-x[l]|+|x-x[l+1]|+|x-x[l+2]|+...+|x-x[r-1]|+|x-x[r]|) \] 令\(f(x)=|x-x[l]|+|x-x[l+1]|+|x-x[l+2]|+...+|x-x[r-1]|+|x-x[r]|\)

也就是求该函数在\([l,r]\)上的最小值点

怎么求呢?画图观察一下,

如果有奇数项,比如\(y=|x-x_1|+|x-x_2|+|x-x_3|\),这个函数必然有一个尖儿,也就是我们需要的最小值,并且这个极小值点等于 \(中位数(x_1,x_2,x_3)\)

如果有偶数项,比如\(y=|x-x_1|+|x-x_2|+|x-x_3|+|x-x_4|\),就没有这个尖儿,但是有一个水平的最低谷,这个最低谷介于两个中位数之间

这就有\(w(l,r)\)的求解方法了:

1
2
3
4
5
6
7

w(l,r):
	mid=向下取整((l+r)/2)
	dist_sum=0;
	for all k among [l,r]:
		dist_sum+=abs(x[k]-x[mid])
		
	return dist_sum;

每次调用\(w(l,r)\),时间复杂度都是\(T(r-l+1)=O(n)\)

可以预处理所有的\(w(l,r)\)

1
2
3
4
5

for(int l=1;l<=n;++l){
	for(int r=l;r<=n;++r){
		W[l][r]=w(l,r);
	}
}

外面又套了\(O(n^2)\)的循环

总复杂度是\(O(n^3)\),然而n最大是3000,显然\(O(n^3)\)会超时

如果能给他降为\(O(n^2)\)就可以了

这个\(w[l,r]\)的求法可以继续优化

假设已经知道了\(w[l,r-1]\),现在要求\(w[l,r]\) \[ w[l,r]=w[l,r-1]+x[r]-x[mid(l,r)]\\ mid(l,r)=\lfloor\frac{l+r}{2}\rfloor \] 这条结论看上去很诡异,太简洁了,并且好像中位数的变动只会影响到新加入的第r个村庄,前面的[l,r-1]村庄到邮局的最近距离和仍然是使用的原来的中位数,我自己推导的式子中是有中位数的变化的

如果\(r-l+1\)是一个奇数,那么最右边再加一个,下标中位数不变,相当于邮局位置不用改动,那么[l,r]所有的村庄到这个邮局的距离和不变,\(w[l,r+1]=w[l,r]+|x[r+1]-x[mid]|\)

如果\(r-l+1\)是一个偶数,那么最右边再加一个,下标中位数得往右移动一个,新mid=老mid+1,那么

\(w[l,r+1]=w[l,r]+|x[新mid]-x[老mid]|\times (l-r+1)+|x[r+1]-x[新mid]|\)

再考虑\(r-l+1\)是奇数的情况,如果保持下标中位数不变,实际上对于[l,r+1]时,这个中位数是左中位数

完全可以+1使用右中位数

因此两种情况统一了,即 \[ w[l,r+1]=w[l,r]+(x[mid+1]-x[mid])\times (r-l+1)+x[r+1]-x[mid+1] \]

然而仔细一想确实可以忽略中位数的变化.怎么想呢?

\[ \begin{aligned} w[l,r-1]&=\sum_{l\le k\le r-1}|x[k]-x[mid(l,r-1)]|\\ w[l,r]&=\sum_{l\le k\le r}|x[k]-x[mid(l,r)]|\\ \end{aligned} \] 如果[l,r-1]之间有偶数个村庄,那么选取邮局建立在左中位数村庄或者右中位数村庄,甚至两者直接的地方(虽然只允许建立在村庄里),[l,r-1]所有的村庄到这个邮局的距离和都是最短的,这在图上对应水平谷底那一段

不妨让邮局建立在右中位数村庄,也就是\(\lfloor\frac{l+r-1}{2}\rfloor+1\)

那么[l,r]有奇数个村庄,其中位数唯一,也就是\(\lfloor \frac{l+r}{2}\rfloor\)

由于[l,r-1]之间有偶数个村庄,因此可以设\(r-1-l+1=r-l=2k\)带入上两式 \[ \begin{aligned} \lfloor\frac{l+r-1}{2}\rfloor+1&=\lfloor k+l-\frac{1}{2}\rfloor+1=k+l-1+1=k+l\\ \lfloor \frac{l+r}{2}\rfloor&=\lfloor k+l\rfloor=k+l \end{aligned} \] 这就证明了[l,r]的中位数恰好是[l,r-1]的右中位数,因此两种情况可以选择同一个中位数,因此新加入r村庄的时候w[l,r]直接加上w[l,r-1],无需进行中位数的校正

如果[l,r-1]之间有奇数个村庄,那么只需要让[l,r]选取左中位数和[l,r-1]的中位数是一个点,同理可证

证毕

实际上证完了看这个结论很容易想,但是之前思维就太僵化了,以后记住这个结论吧

加上w计算的优化,加上四边形不懂事的优化

okk,现在dp的时间复杂度成功降到了\(O(n^2)\)

优化后的w,其计算的时间复杂度也是\(O(n^2)\)

总时间复杂度就是\(O(n^2)\)

应该可以通过了吧

不想写了,开摆,明天写了题解然后再看看四边形不懂事优化

阳了四天,摆了四天...

首先是不加四边形不等式优化的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include <iostream>
#include <algorithm>
using namespace std;
int v, p;
const int INF = 1e9;
const int maxv = 3010;
const int maxp = 310;
int x[maxv];
int w[maxv][maxv];
int dp[maxv][maxp];
// int s[maxv][maxp];
int s[maxv];
int main()
{
    // cin.tie(0);
    cin >> v >> p;
    for (int i = 1; i <= v; ++i)
    {
        cin >> x[i];
    }

    sort(x + 1, x + v + 1);//使村庄的坐标升序排列

    //初始化w数组
    for (int l = 1; l <= v; ++l)
    {
        w[l][l] = 0; // 从l号村庄上建立邮局,到该村庄的最短邮局距离就是0
        for (int r = l + 1; r <= v; ++r)
        {
            w[l][r] = w[l][r - 1] + x[r] - x[(l + r) >> 1];
        }
    }


    //初始化dp数组
    for (int i = 0; i <= v; i++)
    {
        s[i]=i;
        for (int j = 0; j <= p; ++j)
        {
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;

    
    for (auto j = 1; j <= p; ++j)
    {
        for (auto i = 1; i <= v; ++i)
        {
            int temp_min = INF;
            for (auto k = s[i-1]; k < i; ++k)
            {
                if(temp_min>dp[k][j - 1] + w[k + 1][i]){
                    temp_min=dp[k][j - 1] + w[k + 1][i];
                    s[i]=k;//四边形不等式优化
                }
                // temp_min = min(temp_min, dp[k][j - 1] + w[k + 1][i]);
            }
            dp[i][j] = temp_min;
        }
    }

    // i,j遍历顺序反了,导致计算dp[i][j]时,dp[k][j-1]可能还没有经过计算
    //  for(auto i=1;i<=v;++i){
    //      for(auto j=1;j<=p;++j){
    //          int temp_min=INF;
    //          for(auto k=1;k<i;++k){
    //              temp_min=min(temp_min,dp[k][j-1]+w[k+1][i]);
    //          }
    //          dp[i][j]=temp_min;
    //      }
    //  }
    cout << dp[v][p];

    return 0;
}

动态规划-四边形不等式优化

证明及其他详细资料见luoyongjun999/code: code (github.com)

区间dp的状态转移,一般长这样(以P1775石子合并为例):

1
2
3
4
5
6
7
8
9
10
11
12
13

for(int delta=1;delta<=n;++delta){
    for(auto i=1;i+delta<=n;++i){
        auto j=i+delta;
        int temp_min=INF;
        for(auto k=i;k<j;++k){
            if(dp[i][k]+dp[k+1][j]<temp_min){
                temp_min=dp[i][k]+dp[k+1][j];
                s[i][j]=k;
            }
        }
        dp[i][j]=temp_min+prefix[j]-prefix[i-1];
    }
}

三层循环,复杂度\(O(n^3)\)

使用四边形不等式优化(能够证明成立的前提下),可以将最里圈k的遍历范围从\([i,j)\),缩减到\([s[i][j-1],s[i+1][j]\),这个范围结合上i和j的范围能够证明,三层循环的时间复杂度实际上是\(O(n^2)\)

这里\(s[i][j]\)的实际意义是,当\(dp[i][j]=\min_{i\leq k<j}(dp[i][k]+dp[k+1][j])+\sum_{i\leq k\leq j}a[k]\)在k处取得最小值时,此时的k就作为\(s[i][j]\)

边界条件是\(s[i][i]=i\)

用法见P1775

P1775 石子合并（弱化版)

一排N堆石头第i堆石头有a[i]个,合并两堆石头的得分是两堆石头的数量和

求最后合并只剩一堆时取得的最小得分,其中\(N\le 300,a[i]\leq 1000\)

P1880那个题是环状的,这个是线性的

设计状态: \[ dp[i][j]表示合并[i,j]所有的石子,获得的最小得分 \] 边界条件: \[ dp[i][i]=0,即合并一堆时合并个寂寞 \] 状态转移: \[ dp[i][j]=\min_{i\leq k<j}(dp[i][k]+dp[k+1][j])+\sum_{i\leq k\leq j}a[k] \] 前缀和优化: \[ \sum_{i\leq k\leq j}a[k]=prefix[j]-prefix[i-1]\\ dp[i][j]=\min_{i\leq k<j}(dp[i][k]+dp[k+1][j])+prefix[j]-prefix[i-1] \] 四边形不等式优化:

实际上需要证明\(dp[i][j]\),但是可以证明只要是\(w[i][j]\)满足四边形不等式,\(dp[i][j]\)也自动满足四边形不等式,

因此首先证明\(w[i][j]=\sum_{i\leq k\leq j}a[k]=prefix[j]-prefix[i-1]\)满足应用四边形不等式的条件,即证:

1.定义:对于任意\(i<i+1\leq j<j+1\),都有 \[ w[i][j]+w[i+1][j+1]\leq w[i][j+1]+w[i+1][j] \] 2.单调性:对于任意\(i\le i'\le j\le j'\),都有 \[ w[i][j']\ge w[i'][j] \] 证明如下:

对于定义: \[ w[i][j]+w[i+1][j+1]=prefix[j]-prefix[i-1]+prefix[j+1]-prefix[i] \]

\[ w[i][j+1]+w[i+1][j]=prefix[j+1]-prefix[i-1]+prefix[j]-prefix[i] \]

左=右,定义成立

对于单调性: \[ w[i][j']-w[i'][j]=prefix[j']-prefix[i-1]-prefix[j]+prefix[i'-1]\\ =(prefix[j']-prefix[j])+(prefix[i'-1]-preifx[i-1]) \] 由于\(i\le i'\le j\le j'\),并且前缀函数\(prefix[i]\)单调不减,因此上式非负,即 \[ w[i][j']\ge w[i'][j] \] 证毕

下面就可以使用四边形不等式的性质定理优化了

\[ dp[i][j]=\min_{s[i-1][j]\leq k<s[i][j+1]}(dp[i][k]+dp[k+1][j])+prefix[j]-prefix[i-1] \] 这里\(s[i][j]\)的实际意义是,当\(dp[i][j]=\min_{i\leq k<j}(dp[i][k]+dp[k+1][j])+\sum_{i\leq k\leq j}a[k]\)在k处取得最小值时,此时的k就作为\(s[i][j]\)

边界条件是\(s[i][i]=i\)

\(s[i][j]\)的计算并不是头铁地从i到j遍历k先求\(s[i][j]\),而是跟随dp一起求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=310;
const int INF=1e9;
int n;
int a[maxn];
int dp[maxn][maxn];
int s[maxn][maxn];
int prefix[maxn];


int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        s[i][i]=i;
        dp[i][i]=0;
        prefix[i]=prefix[i-1]+a[i];
    }
    for(int delta=1;delta<=n;++delta){
        for(auto i=1;i+delta<=n;++i){
            auto j=i+delta;
            int temp_min=INF;
            for(auto k=i;k<j;++k){
                if(dp[i][k]+dp[k+1][j]<temp_min){
                    temp_min=dp[i][k]+dp[k+1][j];
                    s[i][j]=k;
                }
            }
            dp[i][j]=temp_min+prefix[j]-prefix[i-1];
        }
    }
    cout<<dp[1][n]<<endl;
    return 0;
}

至于四边形不等式的正确性,现在还没有完全转阴,啥时候脑子不浑了再看吧...

动态规划-状压DP

状态压缩DP,也就是把局面状态压缩到一个整数中,用整数的运算表示状态转移

模板题一般是,往棋盘上放同一种棋子,并且不能让他们掐架,问题有两种:

一共要放k个,求放法有几种?

最多放多少个?

g++ -std=c++11 -O2

P1896 八王八

一个\(N\times N\)的国象棋盘上放\(k\)个王八,要求这k个王八不能掐架.求有多少种放王八的方法

其中\(1\leq N\leq 9,0\leq k\leq N\times N\)

类似于八皇后问题,但是王八的攻击范围只有周围八格,更近

状态压缩

棋盘的每个格子,要么有王八,要么没王八,因此 可以用1表示有,0表示无的状态

那么整个棋盘可以看成有N行,每行有N个格子

比如一个\(4\times 4\),没有王的棋盘就可以是

1
2
3
4

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

可以将一行压缩为一个整数,最左侧是最低位比如

1 0 0 1 0 1 0 ->0101001b=41

如果想让一行中的王八不掐架,那么不能有任何两个1相邻.这一点怎么判断呢?

假设current_state=41表示当前行状态

那么(current_state&((current_state>>1)|current_state<<1))就可以判断有没有王八掐架

为啥呢?

比如状态41显然是合法的

如何让相邻两行的王八不掐架呢?

(current_state&((previous_state)|(previous_state<<1)|(previous_state>>1)))

道理类似于不让一行中的王八掐架,上一行的一个王八,那么本行中该王八的左下,正下,右下都不能有王八

状态转移

设计状态:

dp[currnet_row][cnt_king_used][current_state]表示:

已经安排了[1,current_row]的王八,

已经安排了cnt_king_used个王八,

当前行,也就是第current_row的状态是current_state

状态转移方程: \[ \begin{aligned} &dp[current\_row][cnt\_king\_used][current\_state]=\\ &\sum_{previous\_state}dp[previous\_row][cnt\_kings\_used-cnt\_kings\_of[current\_row]\ ][previous\_state] \end{aligned} \] 初始状态:

前0行(不存在这一行),放了0个王八,状态显然是0,此时的摆放方法dp[0][0][0]=0

完整程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long dp[10][100][2000];//dp[i][j][k]前i行中已经摆了j个王,其中第i行的状态是k.的数量
int n,k;

vector<int>legal_states;
int cnt_kings_in_state[2000];

bool isLegalState(const int &k){
    if((k&((k<<1)|(k>>1)))==0){
        return true;
    }
    return false;
}
bool isInvasion(const int &a,const int &b){
    return (a&((b<<1)|(b>>1)|b));
}

int main(){
    cin>>n>>k;
    int current_state;
    int cnt_state;
    for(int i=0;i<(1<<n);i++){
        current_state=i;
        cnt_state=0;
        while(current_state){
            cnt_state+=current_state&1;
            current_state>>=1;
        }
        cnt_kings_in_state[i]=cnt_state;
        if(isLegalState(i)){
            legal_states.push_back(i);
        }
    }
    dp[0][0][0]=1;
    for(int current_row=1;current_row<=n;current_row++){
        
        auto previous_row=current_row-1;

        for(auto current_state:legal_states){//当前行合法状态
            
            for(auto previous_state:legal_states){//上一行的合法状态

                if(isInvasion(current_state,previous_state)==false){

                    for(
                        int cnt_tot_kings=cnt_kings_in_state[current_state];
                        cnt_tot_kings<=k;
                        ++cnt_tot_kings
                    ){
                        
                        dp[current_row][cnt_tot_kings][current_state]+=
                            dp[previous_row][cnt_tot_kings-cnt_kings_in_state[current_state]][previous_state];

                    }
                }
            }
        }
    }
    long long result=0;
    for(auto current_state:legal_states){
        result+=dp[n][k][current_state];
    }
    cout<<result<<endl;

    return 0;
}