闫学灿算法提高课
快读
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class 快读 {
static PrintWriter out=new PrintWriter(System.out);
static FastReader in=new FastReader();
public static void main(String[] args) throws IOException {
}
static boolean isPrime(long N) {
if (N <= 1) {
return false;
}
if (N <= 3) {
return true;
}
if (N % 2 == 0 || N % 3 == 0) {
return false;
}
for (int i = 5; i * i <= N; i = i + 6) {
if (N % i == 0 || N % (i + 2) == 0) {
return false;
}
}
return true;
}
}
class FastReader{
StringTokenizer st;
BufferedReader br;
public FastReader(){
br=new BufferedReader(new InputStreamReader(System.in));
}
String next(){
while (st==null||!st.hasMoreElements()){
try {
st=new StringTokenizer(br.readLine());
}catch (IOException e){
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
|
基础算法
位运算
64位整数除法
首先让我们来看下快速幂的模板
1
2
3
4
5
6
7
8
9
| static int qmi(int a,int k,int p){
int res=1;
while(k!=0){
if((k&1)==1) res=res*a%p;
a=a*a%p;
k>>=1;
}
return res;
}
|
快速幂，便是用乘法的形式得到乘方，我们可以发现：ab∗ac=a(b+c)，那么我们就可以把k转化成二进制的形式反复平方，这样就可以在logk的复杂度内得到ak次方，我们以求a13来举例 13的二进制是1101
| res |
a |
k |
循环结束 |
| a1 |
a2 |
110 |
第一轮 |
| a1 |
a4 |
11 |
第二轮 |
| a5 |
a8 |
1 |
第三轮 |
| a13 |
a16 |
0 |
第四轮 |
快速幂是用乘法实现乘方，龟速乘是用加法实现乘法，时间复杂度由o(1)变成o(logn)，龟速乘的时候可以一般可以不用担心溢出
把b拆成2进制的形式去乘a，然后最后加一起就是a*b%p;我们可以发现 a*b+a*c=a*(b+c) 那么我们把b划分成二进制的形式，依次与每项二进制相乘那么也能得出结果
1
2
3
4
5
6
7
8
9
| static long ksc(long a,long b,long p){
long res=0;
while (b!=0){
if((b&1)==1) res=(res+a)%p;
a=(a*2)%p;
b>>=1;
}
return res;
}
|
这次以a*13举例
| res |
a |
b |
循环结束 |
| a |
a*2 |
110 |
第一轮 |
| a |
a*4 |
11 |
第二轮 |
| 5a |
a*8 |
1 |
第三轮 |
| 13a |
a*16 |
0 |
第四轮 |
递归与递推
最常见递推的一种形式便是斐波拉契数列f(n)=f(n-1)+f(n-2)
递推就是存在某种关系的一个推理
费解的开关
性质:每个灯只会按一次，按得顺序没有影响，每个灯的状态，只会取决于上下左右的四个灯被按了多少次
因此，可以从上往下递推，推导每个开关是否应该被按
| 0 |
0 |
1 |
1 |
1 |
| 0 |
1 |
0 |
1 |
1 |
| 1 |
0 |
0 |
0 |
1 |
| 1 |
1 |
0 |
1 |
0 |
| 1 |
1 |
1 |
0 |
0 |
| 1 |
0 |
1 |
1 |
1 |
| 1 |
0 |
0 |
1 |
1 |
| 0 |
0 |
0 |
0 |
1 |
| 1 |
1 |
0 |
1 |
0 |
| 1 |
1 |
1 |
0 |
0 |
| 1 |
1 |
1 |
1 |
1 |
| 0 |
1 |
1 |
1 |
1 |
| 0 |
1 |
0 |
0 |
1 |
| 1 |
1 |
0 |
1 |
0 |
| 1 |
1 |
1 |
0 |
0 |
我们的思路是从上往下，依次锁死每一行的开关
首先，锁住第一行的开关，那么要使得第一行全部为1，只能第二行的开关去操作,当我们按下第二行第一个开关时，将会改变上下左右
接下来，我们按下第二行第二个开关，那么第一行便完成了，我们锁死第二行，对第三行操作，然后直到操作到最后一行，前四行都完成了，只要再检查最后一行是否全部完成就可以了
那么第一行的操作方式，我们可以进行枚举，那么一共是五个数，复杂度便是25
每个开关会影响五个灯，我们需要递推25个开关，一共500组数据，所以时间复杂度便是32*25*5*500=2e6
因为我们之前的思路都是锁死第一行的，那我们第一行的按法不能是固定的，我们可以预先枚举第一行的按法，也就是32种按法，得到第一行的结果，然后把第一行锁死。
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
| import java.util.Scanner;
public class 费解的开关 {
static int N=5;
static int dx[]={-1, 0, 1, 0, 0}, dy[] = {0, 1, 0, -1, 0};
static char g[][]=new char[N][N];
static char bg[][]=new char[N][N];
static void turn(int x,int y){
for(int i=0;i<5;i++){
int a=x+dx[i],b=y+dy[i];
if(a<0||a>=5||b<0||b>=5) continue;
g[a][b]^=1;
}
}
static void copyBToA(char a[][],char b[][]){
for(int i=0;i<a.length;i++){
System.arraycopy(b[i],0,a[i],0,a[i].length);
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T=in.nextInt();
while(T-->0){
for(int i=0;i<5;i++){
g[i]=in.next().toCharArray();
}
int res=10;
copyBToA(bg,g);
for(int i=0;i<32;i++){
int cnt=0;
for(int j=0;j<5;j++){
if((i>>j&1)==1){
turn(0,j);
cnt++;
}
}
for(int j=0;j<4;j++){
for(int k=0;k<5;k++){
if(g[j][k]=='0'){
turn(j+1,k);
cnt++;
}
}
}
boolean success=true;
for(int j=0;j<5;j++){
if(g[4][j]!='1'){
success=false;
break;
}
}
if(success){
res=Math.min(cnt,res);
}
copyBToA(g,bg);
}
if(res>6) res=-1;
System.out.println(res);
}
}
}
|
百度查了一下说System.copyof方法是最快的，这里使用该方法，拷二维数组的时候不能直接拷贝，直接拷贝复制的还是引用，其实是把b[i]复制给了a[i]，那么并没有拷贝元素，所以要写一个for循环转化一下，同时System.copy方法是目标数组在后面，也就是把第一个数组的值复制到第二个数组
约数之和
数论做法
分治本身就是递归，比如快排与归并排序，把一个问题分解成多个相同的子问题
解决此题首先要用到约数之和公式，每个正整数都可以表示成若干个质因子的乘积的形式
唯一分解定理的公式便是：
约数个数的公式便是：
约数之和的公式便是：
如果用循环求约数之和，复杂度会非常的高，我们求出该质因数的个数时,a是质因数,b是个数，假设数为8, 约数为1,2,4,8模拟一下
| t |
res |
b |
n轮结束 |
| 1+2 |
1 |
2 |
1 |
| (1+2)*2+1 |
1 |
1 |
2 |
| (1+2+4)*2+1 |
15 |
0 |
3 |
1
2
3
4
5
| long t=1,a=key,b=value;
while(b-->0){
t=(t*a+1)%mod;
}
res=res*t%mod;
|
| 数 |
唯一分解 |
约数个数 |
约数之和 |
实际约数 |
| 12 |
22∗3 |
(1+2)*(1+1)=6 |
(1+2+22)(1+3)=28 |
1,2,3,4,6,12 |
| 36 |
22∗32 |
(1+2)*(1+2)=9 |
(1+2+22)∗(1+3+33)=91 |
1,2,3,4,6,9,12,18,36 |
| 45 |
32∗5 |
(1+2)*(1+1)=6 |
(1+3+33)(1+5)=78 |
1,3,5,9,15,45 |
一个数A的质因子会很少，5e7大概也就30个,但这30个还需要*B,所以30*5e7大约是1.5e9
一个个算过去肯定是会超时的 所以我们就需要快速计算(1+p1+p2+⋅⋅⋅pk)
由第1张图的推导可知 约数之和公式为1+p1+p12+p1k=(p1(k+1)−1)/(p−1)
上面可以用快速幂来求 a(k+1)，因为取模运算中，除法会丢精度，所以可以乘a-1%p的逆元 ，逆元证明在第二张图
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
| import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class 约数之和 {
static final int mod=9901;
static int A,B;
static Map<Integer,Integer> primes=new HashMap<>();
static void putMap(int n){
if(!primes.containsKey(n)){
primes.put(n,1);
}else{
primes.put(n,primes.get(n)+1);
}
}
static void divide(int n){
for(int i=2;i<=n/i;i++){
while(n%i==0){
putMap(i);
n/=i;
}
}
if(n>1) putMap(n);
}
static long qmi(int a,int b){
long res=1;
while(b!=0){
if((b&1)==1) res=res*a%mod;
a= (int) ((long)a*a%mod);
b>>=1;
}
return res;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
A=in.nextInt();
B=in.nextInt();
divide(A);
long res=1;
for(int key:primes.keySet()){
int p=key,v=primes.get(key)*B;
if((p-1)%mod==0){
res= res*(v+1)%mod;
}else{
res=res*(qmi(p,v+1)-1)%mod*qmi(p-1,mod-2)%mod;
}
}
if(A==0) res=0;
System.out.println((res%mod+mod)%mod);
}
|
数论写法攻坚了一小时，踩了很多坑，
第一个是在分解质因数的时候，while循环里面应该是让key为i 而不是key 为n，结束后应该检测n是否>1而不是n>0，
第二个坑就是爆int中间结果，用long转化还是不太好用，不如直接全部用long，
第三个坑就是结果有负数，测试案例刚好是取模的数，所以最后要(res%mod+mod)%mod
分治法
但是如果不从数论角度，从算法角度上观察1+p1+p12+p1k(k代表质因数个数) 项数是k+1 令k+1=x
令p10+p1+p12+....p1k=sum(0,k) 如果进行递归的方式求解
- 如果x是偶数 我们可以进行一个划分，把[0,x/2-1]划分成一部分，[x/2,k]也是一部分
第一半是sum(0,x/2−1)=p10+p1+p12+...+p1(x/2−1)
第二半是sum(x/2,k)=p1(x/2)+p1(x/2+1)+....+p1k
我们可以发现$ p1^{(x/2)} * (p1^0+p1+p1^2+…+p1^{(x/2-1)}) $
=>p1(x/2)∗sum(0,x/2−1)==sum(x/2,k) 也就是第二部分的第一个数*第一部分就是第二部分所有
所以 sum(0,k)=(1+p1^(x/2)^) * sum(0,x/2-1)==1 * sum(0,x/2-1)+sum(x/2,x-1)
| k=3 |
x=4 |
x/2-1=1 |
0~1 |
2~3 |
| k=7 |
x=8 |
x/2-1=3 |
0~3 |
4~7 |
这是k为3和7的模拟
2.如果x是奇数 那k为偶数 那把sum(p,k)分成如下形式 变成p0+p∗x为偶数形式了
那么sum(p,k)=p0+p1+...+pk=>p0+p∗(p0+p1+...+p(k−1))=1+p∗(sum(p,k−1))
所以这题两个做法，第一个做法是用数论的方式快速求出每一段（pk+1/p−1modp），第二个是用分治的方式求出每一段
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
|
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class 约数之和分治法 {
static Map<Integer,Integer> primes=new HashMap<>();
static final int mod=9901;
static int A,B;
static void putMap(int n){
if(!primes.containsKey(n)){
primes.put(n,1);
}else{
primes.put(n,primes.get(n)+1);
}
}
static void divide(int n){
for(int i=2;i<=n/i;i++){
while(n%i==0){
putMap(i);
n/=i;
}
}
if(n>1) putMap(n);
}
static long qmi(int a,int b){
long res=1;
while (b!=0){
if((b&1)==1)res=res*a%mod;
a= (int) ((long)a*a%mod);
b>>=1;
}
return res;
}
static long sum(int p,int x){
if(x==1) return 1;
if(x%2==0){
return (qmi(p,x/2)+1)*sum(p,x/2)%mod;
}
return (qmi(p,x-1)+sum(p,x-1))%mod;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
A=in.nextInt();
B=in.nextInt();
divide(A);
long res=1;
for(int p:primes.keySet()){
int x=primes.get(p)*B+1;
res=res*sum(p,x)%mod;
}
if(A==0) res=0;
System.out.println((res%mod+mod)%mod);
}
}
|
分形之城
找规律的过程
初步一眼从图像观看，每一部分都是由上一级的旋转构成
除第一级以外，每一级分成四部分 左上角是上一级顺时针旋转90° ；右上角是上一级本身；右下角还是上一级本身；左下角是上一级逆时针旋转90°
从大小上来看，右上角和右下角是由上一级平移过来；左上角是关于 反对角线 对称；左下角是关于 主对角线 轴对称
做法是给定一个等级，求两个点的直线距离 ，通过数据可知 一共是431个点 会爆int 所以要用long
现在的问题是给定等级与编号，如何去求2个点的坐标
最初
左上角
左下角
通过看图可以发现，左上角是最小值，左下角是最大值
所以对于一个等级N，我们要求一个编号A 首先，我们要看A落到哪一个部分
对于一个N级，边长是2N次方 每一部分的边长是2(N−1)次方 那每一部分的个数就是2N次方
如果我们要看 a是哪个部分，就用a去整除一下每一部分的点的个数 也就是2N次方 得到的答案就是属于的部分
| 等级 N |
边长 2N |
总个数 4N |
部分边长 2(N−1) |
部分个数 2(2∗N−2) |
| 2 |
4 |
16 |
2 |
4 |
| 3 |
8 |
64 |
4 |
16 |
| 4 |
16 |
216 |
8 |
64 |
0在左上角；1在右上角；2在右下角；3在左下角
就可以变成子问题 get(N-1,A%block)
block求法便是4N/4 总个数是4N
对于每次递归，我们需要判断这个点在哪个位置，判断方式便是a/block，那在该位置的编号就是a%block 如果求到最后，得到了坐标，那就需要不断回溯平移 还有矩阵旋转
如果block 在这次的右上角，那么就要y+2(n−1)
如果block在右下角 y+2(n−1) x+2(n−1)
上面都是通过平移得到的，但左上角和左下角是旋转得到的
左上角其实是关于 x=y轴对称，那么只要把x,y颠倒就好了
左下角是关于y=-x+2^(N-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
|
import java.util.Scanner;
public class 分形之城 {
static class Pair{
long first;
long second;
public Pair(long first, long second) {
this.first = first;
this.second = second;
}
}
static Pair calc(long N,long m){
if(N==0) return new Pair(0,0);
long len=(long)1<<(N-1),block=(long)1<<(2*N-2);
Pair pos=calc(N-1,m%block);
long z=m/block;
long x=pos.first,y=pos.second;
if(z==0){
return new Pair(y,x);
}
if(z==1){
return new Pair(x,y+len);
}
if(z==2){
return new Pair(x+len,y+len);
}
return new Pair(len-1-y+len,len-1-x);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T=in.nextInt();
while(T-->0){
long N=in.nextLong();
long a=in.nextLong();
long b=in.nextLong();
Pair x=calc(N,a-1);
Pair y=calc(N,b-1);
long dx=x.first-y.first;
long dy=x.second-y.second;
double ans=Math.sqrt((double)(dx*dx+dy*dy))*10;
System.out.printf("%.0f\n",ans);
}
}
}
|
这道题首先踩得坑就是1<<31的时候要把1转成long,不然会溢出
然后对于本次递归，由父问题到子问题是确定自己是当前部分的第多少个，然后基于第一级开始计算。由子问题到父问题是回溯的过程，在回溯的过程中，把父问题的相对坐标给返回，所以子问题求的就是当前父问题的相对坐标，这个相对指的是对当前部分的相对
今天复习的时候发现这道题还是比较难，想了一会依旧没有完全想透，代码的递归是每次我降一个等级，偏居一隅，算出我在我这块位置的编号，这一步是在pos=calc(N-1,m%block)得到的。然后判断我是上一个等级的第几个分区； return的值是返回我在当前等级的编号是多少，
前缀和与差分
激光炸弹
首先读题，本题的题意是求矩阵内最大的R x R的和，可以使用二维前缀和o(1) 求出R x R，然后最大的复杂度是n * n 也就是5000 * 5000
因为前缀和数组的下标要从1开始，但数据范围是0开始，所以我们把每个坐标x+1,y+1
首先要注意 R * R个位置的正方形代表的正方形大小是(R−1)2
所以我们要求3 * 3位置的和，其实是求(0,0)~(2,2)的前缀和;又因下标全部+1 其实求得前缀和是 (1,1)~(3,3)
二维前缀和的构造 a[i,j]表示的是[i,j] 其本身及左上角所有数的和
用容斥原理便是a[3,3]-a[3,0]-a[0,3]+a[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
|
import java.io.*;
public class 激光炸弹 {
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in),65535));
static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
static int nextInt() throws IOException{
in.nextToken();
return (int)in.nval;
}
static int N,R;
static int M= (int) (5e3+10);
static int a[][]=new int[M][M];
public static void main(String[] args) throws IOException {
N=nextInt();
R=nextInt();
R=Math.min(5002,R);
int nx=R,my=R;
while(N-->0){
int x=nextInt();
int y=nextInt();
int w=nextInt();
x++;
y++;
nx=Math.max(nx,x);
my=Math.max(my,y);
a[x][y]+=w;
}
for(int i=1;i<=nx;i++){
for(int j=1;j<=my;j++){
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];
}
}
long res=0;
for(int i=R;i<=nx;i++){
for(int j=R;j<=my;j++){
res=Math.max(res,a[i][j]+a[i-R][j-R]-a[i-R][j]-a[i][j-R]);
}
}
out.println(res);
out.flush();
out.close();
}
}
|
其实30000多个输入，快读可用可不用；正常情况下求前缀和是给你两个点 x1,y1 x2,y2 让你求该范围内的前缀和 ；该题变成给你边长；x2,y2 求前缀和 减去边长得到是 x1-1,y1-1
同时这题有道陷阱，x y的范围其实很小，但给出的r是有1e9，所以把r>5001变成5001即可,做这题的时候觉得数据有错误，于是补了一个工单
因为一共有50012个点 可以把5001开大,但不能把5001开小,开大了多求的部分也都是0，不影响结果
增减序列
可以把1 1 2 2=>1 1 1 1 也可以 2 2 2 2，所以操作次数是一次，操作结果二种，选择一个区间[l,r]统一加一个数可以使用差分
差分数组是前缀和的逆运算，对差分数组求前缀和得到的就是原数组
差分s[i]=a[i]-a[i-1] 所以我如果希望数组的值都一样，那么其差分数组除了第一项以外，那其他项应该均为0
-
第一问变成至少操作多少次使得s[2]~s[n]均为0
-
第二问变成在最少操作次数前提下s[1]有多少种选择
首先对差分数组的操作，如果我们要使得[l,r]区间的数增加1 那么就变成s[l]+=1,s[r+1]-=1;l~r 的范围为 1~n 那么差分的范围就是1~n+1 但我们对差分计算前缀和的时候，并不需要计算到n+1 只需要计算到n就可以了。
首先是我们对差分数组的操作是四种 s[1]~b[n+1]；
这里的l和r是指对原数组的区间操作，转化成差分数组就变成l和r+1 以下四种操作是对于原数组而言
-
2<=l<=r<=n-1 该操作是相当于改变l和r之间的数 b[l]+=1 b[r+1]-=1|| b[l]-=1 b[r+1]+=1
-
l=1,r<=n-1 该操作是改变前r个数 b[1]+=1 b[r+1]-=1 || b[1]-=1 b[r+1]+=1
-
2<=l , r=n 该操作是改变l后的数 b[l]+=1 b[n+1]-=1 || b[l]-=1 b[n+1]+=1
-
l=1 r=n 该操作是相当于让整个区间全部+1 or -1 这个操作无意义
那么横看1 ，2 ，3
第一个操作同时操作了差分数组2个数，第二个操作操作了差分数组的1个数，第三个操作也是操作了差分数组的1个数
我们的操作是这样的，第一个操作可以将任意一个正负对同时加减，第二个操作可以将b[1]和b[r+1]改变，第三个操作可以将b[l]和b[n+1]改变
所以我们最少需要操作多少次就是差分数组从2~n正数和与负数和的绝对值的最大值
而在最少操作次数的前提下，有多少种方案，那么只有可供2与3操作的次数，比如整数是7 负数是 -5 那么操作1操作五次后,还剩下整数2，就只有2 方案 和 3 方案了。
我们可以发现，要不然是b[1]+=1,b[r]-=1<>b[1]-=1,b[r]+=1 或者是 b[r]-=1,b[n+1]+=1<>b[r]+=1,b[n+1]-=1; 就没有操作方式了，那么我们的任务便是将剩下的值变成0，可操作b[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
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
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class 增减序列 {
static class FastReader{
StringTokenizer st;
BufferedReader br;
public FastReader(){
br=new BufferedReader(new InputStreamReader(System.in));
}
String next(){
while (st==null||!st.hasMoreElements()){
try {
st=new StringTokenizer(br.readLine());
}catch (IOException e){
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
static PrintWriter out = new PrintWriter(System.out);
static FastReader in = new FastReader();
static int n;
static int N= (int) (1e5+10);
static int a[]=new int[N];
static int b[]=new int[N];
static void solve(){
n=in.nextInt();
for(int i=1;i<=n;i++){
a[i]=in.nextInt();
b[i]=a[i]-a[i-1];
}
long z=0,f=0;
for(int i=2;i<=n;i++){
if(b[i]>=0) z+=b[i];
else f+=b[i];
}
long tmpMax=Math.max(z,-f);
long tmpMin=Math.min(z,-f);
out.println(tmpMax);
out.println(tmpMax-tmpMin+1);
}
public static void main(String[] args) {
solve();
out.flush();
}
}
|
二分
最佳牛围栏
类似于这种询问最大最小平均值的，一般是用二分，具有二段性，便可以二分
判断，是否存在一个方案，使得方案的平均值>=avg avg是二分的枚举值
如果我们让每个数减去枚举的avg，那么就变成是否存在某段的和，大于等于0
那就说明原来的数的均值大于等于avg
题目变成是否存在长度>=F的一段和>=0
那么我们判断数组是否存在某一段的和大于等于0，那么便是和最大子序列和问题，首先我们可以用前缀和来实现o（1）求和，假设有前缀和数组a;最大部分的和是i~j 那么便为a[j]-a[i-1] 那么我们只需要使得a[i] 最小 ，a[j]最大即可
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
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class 最佳牛围栏 {
static class FastReader{
StringTokenizer st;
BufferedReader br;
public FastReader(){
br=new BufferedReader(new InputStreamReader(System.in));
}
String next(){
while (st==null||!st.hasMoreElements()){
try {
st=new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt(){
return Integer.parseInt(next());
}
long nextLong(){
return Long.parseLong(next());
}
double nextDouble(){
return Double.parseDouble(next());
}
}
static FastReader in=new FastReader();
static PrintWriter out=new PrintWriter(System.out);
static int N,F;
static void solve(){
N=in.nextInt();
F=in.nextInt();
double max=0;
for(int i=1;i<=N;i++) {
a[i]=in.nextDouble();
max=max>a[i]?max:a[i];
}
double l=0,r=max;
while (r-l>eps){
double mid=(l+r)/2;
if(check(mid)){
l=mid;
}else{
r=mid;
}
}
out.println((int)(r*1000));
}
static boolean check(double avg){
for(int i=1;i<=N;i++){
b[i]=b[i-1]+a[i]-avg;
}
double sum=0;
for(int i=0,j=F;j<=N;i++,j++){
sum=Math.min(b[i],sum);
if(b[j]-sum>=0) return true;
}
return false;
}
static double eps=1e-5;
static int max= (int) (1e5+10);
static double a[]=new double[max];
static double b[]=new double[max];
public static void main(String[] args) {
solve();
out.flush();
}
}
|
代码其实还是较为简单的，做的时候一开始是跟着yls思路走的，后来想，能否构造前缀和数组的时候不减去平均值，但是比较难做，因为所有的数都是正数，那么最大子段和就会一直上升，所以还是枚举均值比较好 二分的重点在于寻找二段性
二分是非常难的一个算法，要多加练习
特殊排序*
这道题使用的是LeetCode 核心代码模式的例题
反对称性是指a<b可以推出b>a 传递性是a>b b>c 可以推出 a>c
算了、暂时还是看不懂这道题、改日再看
排序
七夕祭
题意大体是说，给你一些坐标，这些坐标有一个喜欢标记，每次可以把该标记和相邻的上下左右的位置交换，最后使得每一行的标记一样多，每一列的标记一样多，如果不能满足，则输出impossible，如果都能满足则输出both和步骤数，满足其一输出row或col
这里对应的答案是row 1 只需把2,1 或者2,2向上或者向下移动就好
因为我们这里有四个糖果，列是除不尽的，所以列不可能行号是除的尽的，我们考虑行号
我们通过上面的条件，可以判定行和列是否能满足；
第二个条件便是，我们横向移动一个点，只会改变对应的列的位置点的数量，而不会改变对应行上的数量
那么换句话说我们使得列数量改变时，并不会影响行的数量，我们使得行数量改变时，不会影响列的数量
所以两个部分操作是独立的，我们可以先操作行的部分，再操作列的部分
所以该问题便是环形均分纸牌问题
便是变成了给定一个环序列，每个值存放的是每一行的摊点数量，每次只能操作该位置的数与相邻位置的数，且只能+1 或 -1
那么答案便是|x1|+|x2|+…+|x6|的最小值，我们每个点的数量应该是一样的
a=a1-x2+x1
a=a2-x3+x2…
a=an-x(n+1)+xn=>a=a6-x1+x6
把n个式子全部加起来，最后只剩下n * a = a1+a2…+an
公式推导 线性代数里的知识 把x1当成因变量，那么放到线段上看问题转化成x到6个点的和的最近距离，那么x便是所有点的均值
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
|
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static Scanner in = new Scanner(System.in);
static int N=100005;
static int row[]=new int[N],col[]=new int[N];
static int s[]=new int[N],c[]=new int[N];
static long work(int n,int a[]){
for(int i=1;i<=n;i++){
s[i]=s[i-1]+a[i];
}
if(s[n]%n!=0) return -1;
int avg=s[n]/n;
c[1]=0;
for(int i=2;i<=n;i++) c[i]=s[i-1]-avg*(i-1);
Arrays.sort(c,1,n+1);
long res=0;
for(int i=1;i<=n;i++) res=res+Math.abs(c[i] - c[(n +1)/2]);
return res;
}
static void solve(){
int n,m,t;
n=in.nextInt();
m=in.nextInt();
t=in.nextInt();
while (t-->0){
int x=in.nextInt();
int y=in.nextInt();
row[x]++;
col[y]++;
}
long r=work(n,row);
long c=work(m,col);
if(r!=-1&&c!=-1) {
System.out.println("both "+(r+c));
return;
}
if(r!=-1){
System.out.println("row "+r);
return;
}
if(c!=-1){
System.out.println("column "+c);
return;
}
System.out.println("impossible");
}
public static void main(String[] args) {
solve();
}
}
|
一道推公式的环形均摊纸牌问题 ，自己的数学底子还是有待提高，线代和高数很多知识自己还不了解
动态中位数
首先，我们只需要知道中间的数就好了，比他小的数我们无需排序，比他大的数我们也无需排序
可以使用两个堆，对顶堆，上面一个小根堆，下面一个大根堆
大根堆：降序排序的优先队列
小根堆：升序排序的优先队列
我们用小根堆去存大于中位数的数，大根堆去存小于中位数的数
当序列数为偶数的时候，确保两个堆中间的东西一样多，当序列为奇数的时候，确保下面的大根堆的个数比小根堆多一个，这样大根堆顶就是中位数
下面的大根堆里的最大元素，至少要比上面小根堆里的元素要小，且下面大根堆的元素数量，最多比小根堆的元素多一个
1.大根堆的所有元素都要比小根堆小=>大根堆堆顶比小根堆堆顶小
2.大根堆的元素数量最多要比小根堆多1，最少要和小根堆相等
在多1的情况下，便是奇数次，那么大根堆顶便是答案
1.首先对于输入的数，我们判定其是否比大根堆的堆顶大，如果大则插入小根堆中，否则则插入大根堆中
2.插入后，如果大根堆的元素数量比小根堆少，那么就把小根堆的堆顶加到大根堆
3.插入后，若大根堆的元素数量比小根堆多了两个，那么便把大根堆的堆顶加到小根堆
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static Queue<Integer> smallRootHeap=new PriorityQueue<>();
static Queue<Integer> bigRootHeap=new PriorityQueue<>((x,y)->{return y-x;});
static void solve(){
int No=in.nextInt();
int m=in.nextInt();
int cnt=0;
out.println(No+" "+(m+1)/2);
for(int i=1;i<=m;++i){
int x=in.nextInt();
if(bigRootHeap.isEmpty()||bigRootHeap.peek()>=x){
bigRootHeap.offer(x);
}else{
smallRootHeap.offer(x);
}
if (bigRootHeap.size()<smallRootHeap.size()){
bigRootHeap.offer(smallRootHeap.poll());
}
if (bigRootHeap.size()-smallRootHeap.size()>=2){
smallRootHeap.offer(bigRootHeap.poll());
}
if(cnt==10){out.println();cnt=0;}
if((i&1)==1) {
out.print(bigRootHeap.peek()+" ");cnt++;
}
}
out.println();
smallRootHeap.clear();
bigRootHeap.clear();
}
public static void main(String[] args) {
int p=in.nextInt();
while (p-->0)
solve();
out.flush();
}
static PrintWriter out=new PrintWriter(System.out);
static FastReader in = new FastReader();
static class FastReader{
StringTokenizer st;
BufferedReader br;
FastReader(){
br=new BufferedReader(new InputStreamReader(System.in));
}
String next(){
while (st==null||!st.hasMoreElements()){
try {
st=new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt(){
return Integer.parseInt(next());
}
}
}
|
对顶堆是一个神奇的算法，第一次学，希望能记住该思想
该思想便是不断的维护中位数，确保大根堆所有的数都比小根堆小，且数量最多多一个，最少相等，那么大根堆的堆顶在奇数情况下，便是中位数，同时代码的实现也是一个点，我们始终将其当成一个维护好的对顶堆去操作，因为我们的插入方式一定可以满足第一种，小根堆的所有数大于大根堆里的所有数，那么只需我们完成第二种：大根堆的数-小根堆的数>=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
|
import java.util.Scanner;
public class Main {
static int temp[]=new int[(int) (5e5+5)];
static long merge_sort(int q[],int l,int r){
if(l>=r) return 0;
int mid=l+r>>1;
long res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r){
if(q[i]<=q[j]){
temp[k++]=q[i++];
}else{
temp[k++]=q[j++];
res=res+mid-i+1;
}
}
while (i<=mid) temp[k++]=q[i++];
while (j<=r) temp[k++]=q[j++];
for(i=l,j=0;i<=r;i++,j++)q[i]=temp[j];
return res;
}
static void solve(){
int a[]=new int[op];
for(int i=0;i<op;i++) a[i]=in.nextInt();
System.out.println(merge_sort(a,0,op-1));
}
static int op;
static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
while ((op=in.nextInt())!=0){
solve();
}
}
}
|
在冒泡排序中，每做一次交换，那么就说明这两个数构成了一个逆序对，那么在将他们交换的同时，并不影响他们和别的数形成的逆序对
换个方式去想，一个数组如果没有逆序对就是升序
感觉是逆序对用的归并排序，并不能证明是相邻两个数的交换；但冒泡排序的交换是相邻的数，然后每次交换的时候应该就是这两个数构成的逆序对
RMQ
天才的记忆
快速查询区间最值问题，1e4组查询，2e5个数，那么时间复杂度应是nlogn以内
RMQ被又称作st表，本质上动态规划
预处理f(i,j):从i开始长度为2j，最大值是多少
f(i,j)=max{f(i,j-1),f(i+2j−1,j-1)};
对于每一个l~r区间的查询，首先该区间的长度为len=r-l+1 那么首先找到<=len 的 2 的 最 大 次 幂k
那么2 * 2k严格大于 len，那么便可以分成两段来求最大值
第一段为f(l,k) ，第二段就要变成以r为终点，长度为2k的区间 那么该区间便是f(r-2k+1,k) ,这两段的并集是完全包括l~r区间的 ，便是第二段的起点，要小于等于第一段的终点+1
f(l,k) 这个区间查的是**[l ~ l+2k-1]**区间的值 f(r-2k+1 , k)是 **[r-2k+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
| import java.util.Scanner;
public class 天才的记忆 {
static int N= (int) (2e5+10),M=18;
static int w[]=new int[N];
static int f[][]=new int[N][M];
static int n,m;
static void init(){
for(int j=0;j<M;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
if(j==0) f[i][j]=w[i];
else f[i][j]= Math.max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
}
}
static int query(int l,int r){
int len=r-l+1;
int k = (int)(Math.log(len) / Math.log(2));
return Math.max(f[l][k],f[r-(1<<k)+1][k]);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n=in.nextInt();
for(int i=1;i<=n;i++) w[i]=in.nextInt();
init();
m=in.nextInt();
while (m-->0){
int l=in.nextInt(),r=in.nextInt();
System.out.println(query(l,r));
}
}
}
|
核心便是跳表的知识，还有有待加强的数学
动态规划
数字三角形模型
摘花生
首先题目的意思便是从左往右，从上往下的方式读入数据，hello Kitty从左上角走到右下角所经过的最大价值，那么很明显这是一个数字三角形模型，每一点的状态可以从该点的上面或者左边转移而来，存放的是走到第i行第j列的位置的最大值，
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
|
import java.util.Scanner;
public class 摘花生 {
static Scanner in = new Scanner(System.in);
static void solve(){
int r=in.nextInt(),c=in.nextInt();
int a[][]=new int[105][105];
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
a[i][j]=in.nextInt();
}
}
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
a[i][j]=Math.max(a[i-1][j],a[i][j-1])+a[i][j];
}
}
System.out.println(a[r][c]);
}
public static void main(String[] args) {
int t=in.nextInt();
while (t-->0) solve();
}
}
|
最低通行费用
1.首先这题是询问数字三角形的最小值
2.该题虽说可以上下左右四个方向走，但只能走2n-1步，代表只能向下走或向右走
3.该题说不能走出网格外，代表在计算第一行和第一列的最小状态时候，要特判一下，只能从上方来或者只能从左边来
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
|
import java.util.Scanner;
public class Main {
static Scanner in = new Scanner(System.in);
static int w[][]=new int[105][105];
static void solve(){
int n=in.nextInt();
for(int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
w[i][j]=in.nextInt();
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==1){
w[i][j]+=w[i][j-1];
}else if(j==1){
w[i][j]+=w[i-1][j];
}else{
w[i][j]=Math.min(w[i][j-1],w[i-1][j])+w[i][j];
}
}
}
System.out.println(w[n][n]);
}
public static void main(String[] args) {
solve();
}
}
|
方格取数
该题是走同时走两次数字三角形，在这之前走一次数字三角形的思路便是f[i,j]为从(1,1)走到(i,j)的最大的路径和
在该题便是同时走两次数字三角形 ，状态为f[i1,j1,i2,j2] 代表从(1,1),(1,1)走到(i1,j1),(i2,j2)的最大路径和
曼哈顿距离定义为 两点间东西距离+南北距离
欧氏距离定义为 两点间的直线距离
1.我们可以发现，若同时走的话，两条路径的曼哈顿距离始终一样，便是i1+j1== i2+j2 ，那么我们的状态便可以改成f[k,i1,i2] 通过枚举曼哈顿距离来计算 j1与j2 k == i1+j1 == i2+j2
2.当曼哈顿距离一样的时候，那么仅有i1==i2，两点才重合，当两点重合时，该距离只能走一点
那么状态可以划分成四种
1.第1条路径从上方到达了最后一个点，第2条路径从上方到达了最后一个点f(i1-1,j1,i2-1,j2)=>f(k-1,i1-1,i2-1)
2.第1条路径从上方到达了最后一个点，第2条路径从左方到达了最后一个点f(i1-1,j1,i2,j2-1)=>f(k-1,i1-1,i2)
3.第1条路径从左方到达了最后一个点，第2条路径从上方到达了最后一个点f(i1,j1-1,i2-1,j2)=>f(k-1,i1,i2-1)
4.第1条路径从左方到达了最后一个点，第2条路径从左方到达了最后一个点f(i1,j1-1,i2,j2-1)=>f(k-1,i1,i2)
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
|
import java.util.Scanner;
public class Main {
static Scanner in = new Scanner(System.in);
static int N=15;
static int w[][]=new int[N][N];
static int f[][][]=new int[N*2][N][N];
static void solve(){
for(int k=2;k<=n*2;k++){
for(int i1=1;i1<=n;i1++){
int j1=k-i1;
if(j1<1||j1>n) continue;
for(int i2=1;i2<=n;i2++){
int j2=k-i2;
if(j2<1||j2>n) continue;
int x=f[k-1][i1-1][i2-1];
x=Math.max(f[k-1][i1-1][i2],x);
x=Math.max(f[k-1][i1][i2-1],x);
x=Math.max(f[k-1][i1][i2],x);
f[k][i1][i2]=x+w[i1][j1];
if(i1==i2) continue;
f[k][i1][i2]+=w[i2][j2];
}
}
}
System.out.println(f[n+n][n][n]);
}
static int n;
public static void main(String[] args) {
n=in.nextInt();
int r,c,s;
do{
r=in.nextInt();c=in.nextInt();s=in.nextInt();
w[r][c]+=s;
}while (r!=0);
solve();
}
}
|
第一次写这种三维dp的题目，感觉状态的表示与状态的转换要想好，此时对于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
37
38
39
40
41
42
43
44
45
|
import java.util.Scanner;
public class Main{
static int N=55;
static int w[][]=new int[N][N];
static int f[][][]=new int[N<<1][N][N];
static int n,m;
static void solve(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
w[i][j]=in.nextInt();
}
}
for(int k=2;k<=n+m;k++){
for(int i1=1;i1<=n;i1++){
int j1=k-i1;
if(j1>m||j1<1) continue;
for(int i2=1;i2<=n;i2++){
int j2=k-i2;
if(j2>m||j2<1) continue;
int x=f[k-1][i1][i2];
x=Math.max(x,f[k-1][i1-1][i2]);
x=Math.max(x,f[k-1][i1][i2-1]);
x=Math.max(x,f[k-1][i1-1][i2-1]);
f[k][i1][i2]=x+w[i1][j1];
if(i1==i2) continue;
f[k][i1][i2]+=w[i2][j2];
}
}
}
System.out.println(f[n+m][n][n]);
}
static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
n=in.nextInt();
m=in.nextInt();
solve();
}
}
|
那么首先要注意的是我们i1，i2是行号，那么枚举范围便是<=行号，状态是 f [ k] [i1] [i2] 因为i1+j1==i2+j2 == k
压缩了空间,k便是曼哈顿长度
最长上升子序列模型 LIS
最长上升子序列问题
状态表示：f[i]:表示为以a[i]结尾的最长上升子序列的个数
状态转移：所有**在a[i]前面的数且小于a[i]**构成的最长上升子序列f[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
|
import java.util.Scanner;
public class Main{
static int n;
static int a[]=new int[1005];
static int f[]=new int[1005];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n=in.nextInt();
int res=0;
for(int i=1;i<=n;i++) a[i]=in.nextInt();
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<i;j++){
if(a[i]>a[j]) f[i]= Math.max(f[i],f[j]+1);
}
}
for(int i=1;i<=n;i++) res= Math.max(res,f[i]);
System.out.println(res);
}
}
|
怪盗基德的滑翔翼
首先看这题，题意便是求最长下降子序列，那么状态f[i]便是以 a[i]结尾最长的下降子序列的个数
状态转移便是 在a[i]前面所有比a[i]大的数的最长的下降子序列的最大值+1
但是这道题还有一点便是，基德可以在任意一个楼的位置起跳，那么该题还需要同时统计最长上升子序列的数量，这样才能求出基德最多跳多少次，
因为LDS从左边往右，跳的时候覆盖了所有点往右跳的情况
LIS便是相当于从右往左跳，覆盖了所有点往左跳的情况
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
|
import java.util.Scanner;
public class Main {
static Scanner in = new Scanner(System.in);
static int k,n;
static void solve(){
n=in.nextInt();
int a[]=new int[105];
int f[][]=new int[105][2];
for(int i=1;i<=n;i++) a[i]=in.nextInt();
for(int i=1;i<=n;i++){
f[i][0]=1;
f[i][1]=1;
for(int j=1;j<i;j++) {
if(a[j]>a[i])
f[i][0]=Math.max(f[i][0],f[j][0]+1);
if(a[i]>a[j]) f[i][1]=Math.max(f[i][1],f[j][1]+1);
}
}
int res=-0x3f3f3f3f;
for(int i=1;i<=n;i++) res=Math.max(res,Math.max(f[i][0],f[i][1]));
System.out.println(res);
}
public static void main(String[] args) {
k=in.nextInt();
while (k-->0) solve();
}
}
|
登山
看登山这道题，从第一个景点开始到最后一个景点，且下山后便不能再次上山，那么该问题便是最大的以i为终点的最长上升子序列，和以i为起点，n为终点的最长下降子序列问题，那么以i为起点的最长下降子序列问题可以变成以n为起点，i为终点的最长上升子序列问题，
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
|
import java.util.Scanner;
public class 登山 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a[]=new int[1005];
int f[][]=new int[1005][2];
int n=in.nextInt();
for(int i=1;i<=n;i++){
a[i]=in.nextInt();
}
for(int i=1;i<=n;i++){
f[i][0]=1;
for(int j=1;j<i;j++){
if(a[i]>a[j]){
f[i][0]=Math.max(f[i][0],f[j][0]+1);
}
}
}
for(int i=n;i>=1;i--){
f[i][1]=1;
for(int j=n;j>i;j--){
if(a[i]>a[j]){
f[i][1]=Math.max(f[i][1],f[j][1]+1);
}
}
}
int res=0;
for(int i=1;i<=n;i++){
res=Math.max(res,f[i][0]+f[i][1]-1);
}
System.out.println(res);
}
}
|
合唱队形
这道题和上面一题很像，题目意思便是，使得选择的同学最多，便是出列的同学最少，那么需要构成最大的以i为终点的lis和以n为起点的 lis
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
|
import java.util.Scanner;
public class 合唱队形 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a[]=new int[1005];
int f[][]=new int[1005][2];
int n=in.nextInt();
for(int i=1;i<=n;i++){
a[i]=in.nextInt();
}
for(int i=1;i<=n;i++){
f[i][0]=1;
for(int j=1;j<i;j++){
if(a[i]>a[j]){
f[i][0]=Math.max(f[i][0],f[j][0]+1);
}
if(a[i]<a[j]){
f[i][1]=Math.max(f[i][1],f[j][1]+1);
}
}
}
for(int i=n;i>=1;i--){
f[i][1]=1;
for(int j=n;j>i;j--){
if(a[i]>a[j]){
f[i][1]=Math.max(f[i][1],f[j][1]+1);
}
}
}
int res=0;
for(int i=1;i<=n;i++){
res=Math.max(res,f[i][0]+f[i][1]-1);
}
System.out.println(n-res);
}
}
|
友好城市
这道题也是比较简单的一题，通过对案例的画图可以发现，如果对南岸城市排序好，那么对于其对应的北方城市，就构成了一个最长上升子序列的问题，当两组友好城市，一方南岸坐标和北岸坐标均大于时另一方，两城市的桥梁才不会相交，那么在一岸坐标确定的情况下，那么另一岸便是最长上升子序列问题，
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
|
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static class Pair
{
int x,y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
static Pair[] pairs=new Pair[5010];
static int f[]=new int[5010];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n=in.nextInt();
for(int i=1;i<=n;i++){
int x=in.nextInt();
int y=in.nextInt();
pairs[i]=new Pair(x,y);
}
Arrays.sort(pairs,1,n+1,(x,y)->{return x.x-y.x;});
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<i;j++){
if(pairs[i].y>pairs[j].y){
f[i]=Math.max(f[i],f[j]+1);
}
}
}
int res=0;
for(int i=1;i<=n;i++){
res=Math.max(f[i],res);
}
System.out.println(res);
}
}
|
最大上升子序列的和
那么在之前，我们f[i]表示的是以a[i]结尾的最长上升子序列的数量 状态转移是找出a[i]左边比a[i]小的最大的数量，
这题f[i]表示为以a[i]结尾的最长上升子序列的值 状态转移是找出a[i]左边比a[i]小的最大的值，
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
|
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n=in.nextInt();
int a[]=new int[1005];
int f[]=new int[1005];
for(int i=1;i<=n;i++){
a[i]=in.nextInt();
}
for(int i=1;i<=n;i++){
f[i]=a[i];
for(int j=1;j<i;j++){
if(a[j]<a[i]){
f[i]=Math.max(f[i],f[j]+a[i]);
}
}
}
int res=0;
for(int i=1;i<=n;i++){
res=Math.max(res,f[i]);
}
System.out.println(res);
}
}
|
拦截导弹
那么该题有两问，第一问便是最长不上升序列的长度，第二问便是划分最少的不上升子序列的个数
dilworth定理
1.划分最少的不上升子序列个数 == 最长上升子序列长度
2.划分最少的不下降子序列个数 == 最长下降子序列长度
3.划分最少的下降子序列长度 == 最长不下降子序列长度
4.划分最少的上升子序列长度 == 最长不上升子序列长度
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int lds[]=new int[1005];
int lis[]=new int[1005];
int a[]=new int[1005];
String line=new BufferedReader(new InputStreamReader(System.in)).readLine();
String values[]=line.split(" ");
for(int i=1;i<=values.length;i++) a[i]=Integer.parseInt(values[i-1]);
for(int i=1;i<=values.length;i++){
lds[i]=1;
lis[i]=1;
for(int j=1;j<i;j++){
if(a[i]<=a[j]){
lds[i]=Math.max(lds[i],lds[j]+1);
}
if(a[i]>a[j]){
lis[i]=Math.max(lis[i],lis[j]+1);
}
}
}
int res1=0,res2=0;
for(int i=1;i<=values.length;i++){
res1=Math.max(res1,lds[i]);
res2=Math.max(res2,lis[i]);
}
System.out.println(res1);
System.out.println(res2);
}
}
|
很有用的定理，要记下来，同时注意bufferedReader读数据的时候注意下标
导弹防御系统*
最长公共子序列
首先本题的状态划分为f[i,j] 表示为由长度 1~i 的a串和1~j的b串构成的最长公共子序列的长度 ，那么状态转移方程的推导就直接看最后一步 f [i] [j]
首先f[i] [j] 可以由 f[i-1] [j] 和 f[i] [j-1] 推导得来 ，当从这两个状态转移而来的时候便相当于分别把a串最后一个字符加入和b串最后一个字符加入，那么我们只需要考虑加入的情况即可
如果ab串最后1个字符相同，那么答案肯定就是f[i-1] [j-1] +1,
如果ab串最后1个字符不同，在b串已经全部填完的情况下，我们把a串最后一个字符加入，可能会对lcs的结果产生影响，因为 last_a和last_b不同，那我们就看f[i-1] [j] 的数量
同时，在a串已经全部填完的情况下 ，把b串最后一个字符插入，也可能会对lcs的结果产生影响，因为两个串最后1个字符不同，我们就看b的全部和a-1的情况就好了，这个情况就是b加入影响的结果
然后取这两个结果的最大值
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
|
import java.util.Scanner;
public class 最长公共子序列 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int lena=in.nextInt();
int lenb=in.nextInt();
int f[][]=new int[1005][1005];
char a[]=new char[1004];
char b[]=new char[1005];
String sa=in.next();
String sb=in.next();
for(int i=0;i<sa.length();i++){
a[i+1]=sa.charAt(i);
}
for(int i=0;i<sb.length();i++){
b[i+1]=sb.charAt(i);
}
for(int i=1;i<=lena;i++){
for(int j=1;j<=lenb;j++){
if(a[i]==b[j]){
f[i][j]=f[i-1][j-1]+1;
}else{
f[i][j]=Math.max(f[i-1][j],f[i][j-1]);
}
}
}
System.out.println(f[lena][lenb]);
}
}
|
状态转移方程还是要看最后一步怎么来的
最长公共上升子序列*
背包模型
01背包问题
01背包问题是所有背包问题的基础，对于每个物品他有选和不选两种方式，那么如果暴力去搜，复杂度便是2n
那么这里采用动态规划的方式：状态f[i,j]代表前i个物品，体积为j的最大价值
状态转移便是：对于每个物品v[i]，遍历所有的体积，在这个区间（m~v[i]）内的体积都可以拥有这个物品（加上该物品才等于j），不在这个区间的便是大小不允许选该物品，如果不选该物品，那么状态便是f[i-1] [j]。
换句话而言：当选择这个物品的时候，那么剩余背包的体积便是j-v[i]
此时这些体积是没有确定是否选择该物品的，如果选择该物品，便是j-v[i]的价值，加上v[i]的价值大于现在的价值，状态便是由f[i-1] [j-v[i]] 转移而来
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
| import java.util.Scanner;
public class Main{
static Scanner in = new Scanner(System.in);
static int n;
static int m;
static int v[]=new int[1005];
static int w[]=new int[1005];
static int f[][]=new int[1005][1005];
public static void main(String[] args) {
n=in.nextInt();
m=in.nextInt();
for(int i=1;i<=n;i++){
v[i]=in.nextInt();
w[i]=in.nextInt();
}
for(int i=1;i<=n;i++){
for(int j=m;j>=1;j--){
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]=Math.max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
System.out.println(f[n][m]);
}
}
|
那么我们可以发现，更新的时候只用到了两层，分别是f[i]和f[i-1]这一层，那我们便可以压缩空间成一维，这样我们原地更新的时候，在自己的基础上更新就相当于在f[i-1]层更新，然后把结果保存到了f[i]层，就像滚动数组，没更新的地方就相当于原本就是f[i-1] [j]的值
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
|
import java.util.Scanner;
public class 背包问题_01 {
static Scanner in = new Scanner(System.in);
static int n;
static int m;
static int v[]=new int[1005];
static int w[]=new int[1005];
static int f[]=new int[1005];
public static void main(String[] args) {
n=in.nextInt();
m=in.nextInt();
for(int i=1;i<=n;i++){
v[i]=in.nextInt();
w[i]=in.nextInt();
}
for(int i=1;i<=n;i++){
for(int j=m;j-v[i]>=0;j--){
f[j]=Math.max(f[j],f[j-v[i]]+w[i]);
}
}
System.out.println(f[m]);
}
}
|
二维01背包是无需考虑顺序逆序的，只需要特判选择该物品剩余背包的体积是否合法(＞0)，因为每一次都是从上一个状态转移而来
而一维背包是从逆序更新而来，如果顺序的话，转移的时候不一定是从f[i-1]时刻转移而来的，有可能会从f[i]状态转移而来，也就是选择了v[i]的情况
完全背包问题
完全背包和01背包很像，01背包是一维逆序遍历区间，对于每个结果的更新不会影响到后面，而且完全背包是一维二维都要正序遍历区间，对每个结果的更新会影响后面
这是因为要保证第i次循环中的状态f[i] [v]是由状态f[i-1] [v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1] [v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i] [v-c[i]]，所以就可以并且必须采用v= 0…V的顺序循环。这就是这个简单的程序为何成立的道理。
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
|
import java.util.Scanner;
public class Main {
static Scanner in = new Scanner(System.in);
static int n;
static int m;
static int v[] = new int[1005];
static int w[] = new int[1005];
static int f[] = new int[1005];
public static void main(String[] args) {
n = in.nextInt();
m = in.nextInt();
for (int i = 1; i <= n; i++) {
v[i] = in.nextInt();
w[i] = in.nextInt();
}
for (int i = 1; i <= n; i++) {
for (int j = v[i];j<=m; j++) {
f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
}
}
System.out.println(f[m]);
}
}
|
采药
那么这道题便是裸的01背包问题，时间便是背包容量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t=in.nextInt();
int m=in.nextInt();
int f[]=new int[1005];
for(int i=1;i<=m;i++){
int v=in.nextInt();
int w=in.nextInt();
for(int j=t;j-v>=0;j--){
f[j]=Math.max(f[j],f[j-v]+w);
}
}
System.out.println(f[t]);
}
}
|
装箱问题
那么该题也是裸的01背包问题，体积同时也是价值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
import java.util.Scanner;
public class 装箱问题 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int v=in.nextInt();
int n=in.nextInt();
int f[]=new int[20005];
for(int i=1;i<=n;i++){
int c=in.nextInt();
for(int j=v;j>=c;j--){
f[j]=Math.max(f[j],f[j-c]+c);
}
}
System.out.println(v-f[v]);
}
}
|
宠物小精灵之收服
高级数据结构
树状数组
图论
搜索
数学
