LV5

1.熊怪吃核桃

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

森林里有一只熊怪，很爱吃核桃。不过它有个习惯，每次都把找到的核桃分成相等的两份，吃掉一份，留一份。如果不能等分，熊怪就会扔掉一个核桃再分。第二天再继续这个过程，直到最后剩一个核桃了，直接丢掉。

有一天，熊怪发现了 1543 个核桃，请问，它在吃这些核桃的过程中，一共要丢掉多少个核桃。

题解

枚举

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {

      int n=1543;
      int ans=0;
      while(n>0)
      {
        if(n%2!=0)
        {
          n--;
          ans++;
        }
        n=n/2;  
      }
      System.out.print(ans);

    }
}

2.平方序列

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小明想找到两个正整数 X 和 Y，满足

  1. 2019<X<Y;

  2. 20192,X2,Y2X^2,Y^2 组成等差数列。

请你求出在所有可能的解中，X+Y 的最小值是多少？

题解

外层循环控制小的数内层控制大的数，找到一个符合条件的就退出

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {

      for(long x=2020;x<10000;x++)
      {
        for(long y=x+1;y<10000;y++)
        {
          if((x*x)-(2019*2019)==(y*y)-(x*x))
          {
            System.out.print(x+y);
            return;
          }
        }
      }
    }
}

3.生成树

问题描述

下面是一个 8 个结点的无向图的邻接矩阵表示，其中第 i 行第 j 列表示结点 i 到结点 j 的边长度。当 长度为 0 时表示不存在边。

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

9 0 8 1 4 0 0 0

3 8 0 9 0 0 0 0

0 1 9 0 3 0 0 5

0 4 0 3 0 7 0 6

0 0 0 0 7 0 5 2

0 0 0 0 0 5 0 4

9 0 0 5 6 2 4 0

请问，这个图的最小生成树大小的多少?

题解

就是最小生成树问题，k和p算法都行，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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.util.*;

public class Main {

    static class Edge implements Comparable<Edge> {
        int u, v, w;
        Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
        public int compareTo(Edge o) {
            return this.w - o.w;
        }
    }

    static int[] parent;

    static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    static boolean union(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa == fb) return false;
        parent[fa] = fb;
        return true;
    }

    public static void main(String[] args) {

        int[][] g = {
            {0,9,3,0,0,0,0,9},
            {9,0,8,1,4,0,0,0},
            {3,8,0,9,0,0,0,0},
            {0,1,9,0,3,0,0,5},
            {0,4,0,3,0,7,0,6},
            {0,0,0,0,7,0,5,2},
            {0,0,0,0,0,5,0,4},
            {9,0,0,5,6,2,4,0}
        };

        int n = 8;

        List<Edge> edges = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (g[i][j] != 0) {
                    edges.add(new Edge(i, j, g[i][j]));
                }
            }
        }

        Collections.sort(edges);

        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        long ans = 0;
        int count = 0;

        for (Edge e : edges) {
            if (union(e.u, e.v)) {
                ans += e.w;
                count++;
                if (count == n - 1) break;
            }
        }

        System.out.println(ans);
    }
}

4.斐波那契数列最大公约数

题目描述

斐波那契数列满足 F1=F2=1，从 F3 开始有 Fn=Fn−1+Fn−2。

请你计算 GCD(F2020,F520)，其中 GCD(A,B) 表示 A 和 B 的最大公约数。

题解

大整数加上辗转相除法

代码

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.math.BigInteger;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
      BigInteger[] arr = new BigInteger[2021];
          arr[1] = new BigInteger("1");
          arr[2] = new BigInteger("1");
          for(int i = 3; i < 2021; i++){
              arr[i] = arr[i - 1].add(arr[i - 2]);
          }
      System.out.println(GCD(arr[2020], arr[520]));
    }
    public static BigInteger GCD(BigInteger a, BigInteger b){
      while(!b.equals(BigInteger.ZERO)){
        BigInteger temp = b;
        b = a.mod(b);
        a = temp;
      }
      return a;
    }
}

5.小平方

问题描述

小蓝发现, 对于一个正整数 n 和一个小于 n 的正整数 v, 将 v 平方后对 n 取余可能小于 n 的一半, 也可能大于等于 n 的一半。

请问, 在 1 到 n−1 中, 有多少个数平方后除以 n 的余数小于 n 的一半。

例如, 当 n=4 时, 1,2,3 的平方除以 4 的余数都小于 4 的一半。

又如, 当 n=5 时, 1,4 的平方除以 5 的余数都是 1, 小于 5 的一半。而 2,3 的平方除以 5 的余数都是 4 , 大于等于 5 的一半。

输入格式

输入一行包含一个整数 n 。

输出格式

输出一个整数, 表示满足条件的数的数量。

样例输入

1
5

样例输出

1
2

题解

遍历

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);    
        double n = scan.nextDouble();
        int count =0;
        for(int i=1;i<n;i++) {
            if(i*i%n<n/2) {
                count++;
            }
        }
        System.out.println(count);
        }
}

6.汉诺塔

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。

大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上(可以借助第三根柱子做缓冲)。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

据说完成大梵天的命令需要太多的移动次数，以至被认为完成之时就是世界末日！

你的任务是精确计算出到底需要移动多少次。

很明显，如果只有 2 个圆盘，需要移动 3 次。

圆盘数为 3，则需要移动 7 次。

那么 64 个呢？

题解

经典dp，dp[i]=2*dp[i-1]+1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.math.BigInteger;

public class Main {
  public static void main(String[] args) {

    BigInteger bit = new BigInteger("2");
    bit = bit.pow(64);
    bit = bit.subtract(new BigInteger("1"));
    System.out.println(bit);

  }

  public static int hann(int n) {
    if (n == 1) {
        return 1;
    }
    return hann(n-1) * 2 +1;
  }
}

7.求值

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

学习了约数后，小明对于约数很好奇，他发现，给定一个正整数 t，总是可以找到含有 t 个约数的整数。小明对于含有 t 个约数的最小数非常感兴趣，并把它定义为 St 。

例如 S1=1,S2=2,S3=4,S4=6S_1=1,S_2=2,S_3=4,S_4=6，⋅⋅⋅。

现在小明想知道，当 t=100 时，StS_t是多少？即 S100S_{100} 是多少？

题解

用约数个数公式：如果一个数能被分解成几个质因数相乘n=p1a1⋅p2a2⋅⋯⋅pkakn=p_1^{a1}⋅p_2^{a2}⋅⋯⋅p_k^{ak}，那么其约数的个数为(a1+1)(a2+1)⋯(ak+1)(a_1+1)(a_2+1)⋯(a_k+1)，可以先遍历每一个数字用试除法先求出质因数的指数，再算个数是否等于100。也可以反过想100可以有哪些数相乘得到，得到指数后相乘推出最小的数

代码

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

    public static void main(String[] args) {
        int s = 100;
        long i;
        for (i = 1; i <= Long.MAX_VALUE; i++) {
            long temp = i;
            int countFactor = 1;
            for (long j = 2; j <= temp / j; j++) {
                int count = 0;
                while (temp % j == 0) {
                    count++;
                    temp /= j;
                }
                if (count > 0) countFactor = countFactor * (count + 1);
            }
            if (temp > 1) countFactor = countFactor * 2;
            if (countFactor == s) break;
        }
        System.out.println(i);
    }

}

8.机房

问题描述

这天, 小明在机房学习。

他发现机房里一共有 n 台电脑, 编号为 1 到 n, 电脑和电脑之间有网线连接, 一共有 n−1 根网线将 n 台电脑连接起来使得任意两台电脑都直接或者间接地相连。

小明发现每台电脑转发、发送或者接受信息需要的时间取决于这台电脑和多少台电脑直接相连, 而信息在网线中的传播时间可以忽略。比如如果某台电脑 用网线直接连接了另外 d 台电脑, 那么任何经过这台电脑的信息都会延迟 d 单位时间 (发送方和接收方也会产生这样的延迟, 当然如果发送方和接收方都是同一台电脑就只会产生一次延迟)。

小明一共产生了 m 个疑问: 如果电脑 uiu_i 向电脑 viv_i 发送信息, 那么信息从 uiu_i 传到 viv_i 的最短时间是多少?

输入格式

输入共 n+m 行, 第一行为两个正整数 n,m 。

后面 n−1 行, 每行两个正整数 x,y 表示编号为 x 和 y 的两台电脑用网线 直接相连。

后面 m 行, 每行两个正整数 ui,viu_i,v_i 表示小明的第 i 个疑问。

输出格式

输出共 m 行, 第 i 行一个正整数表示小明第 i 个疑问的答案。

样例输入

1
2
3
4
5
6
7
4 3
1 2
1 3
2 4
2 3
3 4
3 3

样例输出

1
2
3
5
6
1

样例说明

这四台电脑各自的延迟分别为 2,2,1,1 。

对于第一个询问, 从 2 到 3 需要经过 2,1,3, 所以时间和为 2+2+1=5 。

对于第二个询问, 从 3 到 4 需要经过 3,1,2,4, 所以时间和为 1+2+2+1=6。

对于第三个询问, 从 3 到 3 只会产生一次延迟, 所以时间为 1 。

题解

n个点，n-1个边，所以是一棵树。首先用一个dfs记录好父节点，记录深度并且计算每个点从根节点开始的路径和。再构造一个倍增表，用于后面找公共祖先。进行LCA查询，先把两个点提到同一个高度，在这个高度下，进行倍增跳跃，向上找父节点是否相同，直到返回最近公共祖先。最后计算，结果为两个点的路径和减去两次从根节点到两个点的最近公共祖先的路径和，再加上一次公共祖先。

代码

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
import java.util.Scanner;
import java.util.ArrayList;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    static int n, m, LOG;
    static ArrayList<Integer>[] g;
    static long[] deg;      
    static int[] depth;
    static int[][] up;      
    static long[] pref;   

    static void dfs(int v, int fa) 
    {
      up[0][v] = fa;
      depth[v] = depth[fa] + 1;
      pref[v] = pref[fa] + deg[v];

      for (int to : g[v]) 
      {
          if (to == fa) continue;
          dfs(to, v);
      }
    }

    static void build() 
    {
      depth[0] = 0;
      pref[0] = 0;
      dfs(1, 0);

      for (int k = 1; k < LOG; k++) 
      {
          for (int v = 1; v <= n; v++) 
          {
              int mid = up[k - 1][v];
              up[k][v] = up[k - 1][mid];
          }
        }
    }

    static int lca(int a, int b) 
    {
        if (depth[a] < depth[b]) 
        {
          int t = a; a = b; b = t;
        }

        int diff = depth[a] - depth[b];
        for (int k = 0; k < LOG; k++) 
        {
          if (((diff >> k) & 1) == 1)
          {
            a = up[k][a];
          }           
        }

        if (a == b) return a;

        for (int k = LOG - 1; k >= 0; k--) 
        {
          if (up[k][a] != up[k][b]) 
          {
              a = up[k][a];
              b = up[k][b];
          }
        }
      return up[0][a];
    }

    static long query(int u, int v) 
    {
      int p = lca(u, v);
      return pref[u] + pref[v] - 2L * pref[p] + deg[p];
    }


    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        LOG = 1;
        while ((1 << LOG) <= n) LOG++;

        g = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();

        deg = new long[n + 1];
        depth = new int[n + 1];
        pref = new long[n + 1];
        up = new int[LOG][n + 1]; 

        for (int i = 0; i < n - 1; i++) 
        {
          int x = scan.nextInt();
          int y = scan.nextInt();
          g[x].add(y);
          g[y].add(x);
          deg[x]++; 
          deg[y]++;
        }
        build();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) 
        {
          int u = scan.nextInt();
          int v = scan.nextInt();
          sb.append(query(u, v)).append('\n');
        }

        System.out.print(sb.toString());    

        scan.close();
    }
}

9.连号区间数

题目描述

小明这些天一直在思考这样一个奇怪而有趣的问题：

在 1 ~ N 的某个全排列中有多少个连号区间呢？

这里所说的连号区间的定义是：

如果区间 [L,R] 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1 的"连续"数列，则称这个区间连号区间。

当 N 很小的时候，小明可以很快地算出答案，但是当 N 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入描述

第一行是一个正整数 N(1≤N≤50×104)N(1≤N≤50×10^4), 表示全排列的规模。

第二行是 N 个不同的数字 Pi(1≤Pi≤N)P_i (1≤P_i≤N)，表示这 N 个数字的某一全排列。

输出描述

输出一个整数，表示不同连号区间的数目。

输入输出样例

示例

输入

1
2
4
3 2 4 1

输出

1
7

题解

遍历每一个区间，如果这个区间的下标相减等于元素相减，那么说明是连续的

代码

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
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int max=0,min=0;
        int count=0;

        int N=scan.nextInt();
        int[] P=new int[N];
        for(int i=0;i<N;i++)
        {
          P[i]=scan.nextInt();
        }

        for(int i=0;i<N;i++)
        {
          max=min=P[i];
          for(int j=i;j<N;j++)
          {
            if(max<P[j])
            {
              max=P[j];
            }
            if(min>P[j])
            {
              min=P[j];
            }
            if(max-min==j-i)
            {
              count++;
            }
          }
        }
        System.out.print(count);


        scan.close();
    }
}

10.三羊献瑞

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

观察下面的加法算式：

1
2
3
4
      祥 瑞 生 辉
  +   三 羊 献 瑞
-------------------
   三 羊 生 瑞 气

其中，相同的汉字代表相同的数字，不同的汉字代表不同的数字。

请你输出“三羊献瑞”所代表的 4 位数字（答案唯一）。

题解

最开始的想法是遍历所有两个四位数相加的情况，找出符合的，注意要把部分数字相同的情况排除掉，能做出来但是超时。还有一种做法是每个数位遍历0-9，有八层循环，但是不会超时，而且还能剪枝剪掉很多层循环，最后只剩三四层。

代码

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
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改


public class Main {
    public static void main(String[] args) {
/*
        int[] a=new int[4];
        int[] b=new int[4];
        int[] c=new int[5];
        for(int i=1001;i<10000;i++)
        {
            int ta=0,tb=0,tc=0;
            for(int j=1001;j<10000;j++)
            {
                ta=i;
                tb=j;
                tc=i+j;
                if(tc<10000)
                {
                    continue;
                }
                for(int k=0;k<4;k++)
                {
                    a[k]=ta%10;ta=ta/10;
                    b[k]=tb%10;tb=tb/10;
                }
                for(int q=0;q<5;q++)
                {
                    c[q]=tc%10;tc=tc/10;
                }

                boolean[] used=new boolean[10];
                int[] x={a[3], a[2], a[1], a[0], b[3], b[2], b[1], c[0]};
                boolean o=true;
                for(int v:x)
                {
                    if(used[v])
                    {
                        o=false;
                        break;
                    }
                    else
                    {
                        used[v]=true;
                    }
                }
                if(!o)
                {
                    continue;
                }
                
                if(b[0]==a[2]&&c[1]==b[0]&&c[2]==a[1]&&c[3]==b[2]&&c[4]==b[3])
                {
                    System.out.println(b[3]*1000+b[2]*100+b[1]*10+b[0]);
                    return;
                }
            }
        }
*/

 //两个四位数相加最高值是19998，所以e（三）只能是1，a（祥）+e（三）+后面可能存在的进位，所以a（祥）只能是8或9，下面的f（羊）也同理，只有两种。
 //主要的只需要枚举b（瑞），g（献）和d（辉），通过其他几位再算出来c（生）即可

      System.out.print(1085);

    }
}

11. 平均

问题描述

有一个长度为 n 的数组（n 是 10 的倍数），每个数 aia_i 都是区间 [0,9] 中的整数。小明发现数组里每种数出现的次数不太平均，而更改第 i 个数的代价为 bib_i，他想更改若干个数的值使得这 10 种数出现的次数相等（都等于 n10\frac n{10}），请问代价和最少为多少。

输入格式

输入的第一行包含一个正整数 n。

接下来 n 行，第 i 行包含两个整数 ai,biai,bi ，用一个空格分隔。

输出格式

输出一行包含一个正整数表示答案。

样例输入

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

样例输出

1
27

样例说明

只更改第 1,2,4,5,7,8 个数，需要花费代价 1+2+4+5+7+8=27。

题解

只需要知道哪些数字要改，不用知道具体要改成什么。可以用优先队列来存储对应数字的代价，再去比较已经出现的数字中超过平均值的，就在其对应的优先队列中取出一个数字

代码

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
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        int c=n/10;
        long sum=0;
        PriorityQueue<Integer>[] pqs=new PriorityQueue[10];
        for (int i = 0; i < 10; i++) {
            pqs[i]=new PriorityQueue<Integer>(); 
        }
        for (int i = 0; i < n; i++) {
            int a=scanner.nextInt();
            int b=scanner.nextInt();
            pqs[a].add(b);
        }
        for (int i = 0; i < 10; i++) {
            while (pqs[i].size()>c) {
                sum+=pqs[i].poll();
            }
        }
        System.out.print(sum);
    }    
}

12.跳蚱蜢

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

有 9 只盘子，排成 1 个圆圈。 其中 8 只盘子内装着 8 只蚱蜢，有一个是空盘。 我们把这些蚱蜢顺时针编号为 1 ~ 8。

每只蚱蜢都可以跳到相邻的空盘中， 也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。

请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列， 并且保持空盘的位置不变（也就是 1−8 换位，2−7换位,…），至少要经过多少次跳跃？

题解

将其看作是一个线性数组，空盘看作0，即012345678，要换成087654321，每次移动0，可以与其前后各两个中的任意一个换位置，每次有四种选择，为了求最小的步数可以用bfs广搜。同时除了第一次外其他每次移动中的四种选择都有一种是当前状态的前一种状态，要剪枝，这样才能避免超时。

代码

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
import java.util.*;

public class Main {
    public static void main(String[] args) {
        String start = "012345678";  
        String target = "087654321"; 

        Queue<Pair<String, Integer>> queue = new LinkedList<>();
        
        Set<String> visited = new HashSet<>();

        queue.add(new Pair<>(start, 0));
        visited.add(start);

        while (!queue.isEmpty()) {
            Pair<String, Integer> current = queue.poll();
            String currentState = current.getKey();
            int currentStep = current.getValue();

            if (currentState.equals(target)) 
            {
                System.out.println(currentStep);
                return;
            }

            int zeroIndex = currentState.indexOf('0');
            int[] nextStates = getNextStates(zeroIndex);

            for (int next : nextStates) 
            {
                String nextState = swap(currentState, zeroIndex, next);
                if (!visited.contains(nextState)) 
                {
                    visited.add(nextState);
                    queue.add(new Pair<>(nextState, currentStep + 1));
                }
            }
        }
    }

    private static int[] getNextStates(int zeroIndex) {
        int[] nextStates = new int[4];
        nextStates[0] = (zeroIndex - 1 + 9) % 9; 
        nextStates[1] = (zeroIndex + 1) % 9;     
        nextStates[2] = (zeroIndex - 2 + 9) % 9; 
        nextStates[3] = (zeroIndex + 2) % 9;     
        return nextStates;
    }

    private static String swap(String state, int from, int to) {
        char[] chars = state.toCharArray();
        char temp = chars[from];
        chars[from] = chars[to];
        chars[to] = temp;
        return new String(chars);
    }

    static class Pair<K, V> {
        K key;
        V value;

        Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}

13.最优包含

题目描述

我们称一个字符串 S 包含字符串 T 是指 T 是 S 的一个子序列，即可以从字符串 S 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 T 完全一样。

给定两个字符串 S 和 T，请问最少修改 S 中的多少个字符，能使 S 包含 T ？

其中，1≤∣T∣≤∣S∣≤1000。

输入描述

输入两行，每行一个字符串。

第一行的字符串为 S，第二行的字符串为 T。

两个字符串均非空而且只包含大写英文字母。

输出描述

输出一个整数，表示答案。

输入输出样例

示例

输入

1
2
ABCDEABCD
XAABZ

输出

1
3

题解

这一题很像LCS最长公共子序列问题。

对于LCS问题， 设X=x1x2…xmX=x_1x_2…x_m和Y=y1y2…ynY=y_1y_2…y_n是两个序列，Z=z1z2…zkZ=z_1z_2…z_k是这两个序列的一个最长公共子序列。

会有三种可能

  • 如果xm=ynx_m=y_n，那么zk=xm=ynz_k=x_m=y_n，且Zk−1Z_{k-1}是Xm−1，Yn−1X_{m-1}，Y_{n-1}的一个最长公共子序列

    • 这种情况下只要把xm=ynx_m=y_n加入LCS末尾即可

  • 如果xm≠ynx_m≠y_n

  • 那么zk≠xmz_k≠x_m，意味着Z是Xm−1X_{m-1}，Y的一个最长公共子序列

  • 那么zk≠ynz_k≠y_n，意味着Z是X，Yn−1Y_{n-1}的一个最长公共子序列

    • 这两种情况下要取最大值

即

C[i][j]={0C[i−1][j−1]+1max(C[i][j−1],C[i−1][j])C[i][j]=\begin{cases}0\\ C[i-1][j-1]+1\\ max(C[i][j-1],C[i-1][j])\\ \end{cases} i=0或j=0i,j>0且xi=yji,j>0且xi≠yi\begin{matrix}i=0或j=0\\ i,j>0且x_i=y_j\\ i,j>0且x_i \neq y_i\\ \end{matrix}

下面这个函数就可以直接返回最长公共子序列的长度

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
public static int LCS(String X,String Y,int[][] B)
{
    int x_len=X.length();
    int y_len=Y.length();
    
    int[][] C=new int[x_len+1][y_len+1];
    
    for(int i=1;i<x_len+1;i++)
    {
        C[i][0]=0;
        B[i][0]=-2 //表示无方向
    }
    for(int j=1;j<y_len+1;j++)
    {
        C[0][j]=0;
        B[0][j]=-2;
    }
    
    for(int i=1;i<x_len+1;i++)
    {
        for(int j=1;j<y_len+1;j++)
        {
            if(X.charAt(i-1)==Y.charAt(j-1))
            {
                C[i][j]=C[i-1][j-1]+1;
                B[i][j]=0; //表示方向左上
            }
            else
            {
                if(C[i-1][j]>C[i][j-1])
                {
                    C[i][j]=C[i-1][j];
                    B[i][j]=-1; //表示方向向上
                }
                else
                {
                    C[i][j]=C[i][j-1];
                    B[i][j]=1; //表示方向向左
                }
            }
        }
    }
    return C[x_len][y_len];
    
}

上面的函数同时用B记录了如何回溯出这个最长公共子序列，所以可以在写一个函数用于回溯出这个字符串。在主函数中用StringBuilder创建一个变量，调用完函数后再返回toString

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void buildLCS(int[][] B,String X,int x_len,int y_len)
{
    if(x_len==0||y_len==0)
    {
        return;
    }
    if(B[x_len][y_len]==0)
    {
        outputLCS(B,X,x_len-1,y_len-1); //左上
        sb.append(X.charAt(x_len-1));
    }
    else if(B[x_len][y_len]==-1)
    {
        buildLCS(B,X,x_len-1,y_len); //向上
    }
    else
    {
        buildLCS(B,X,x_len,y_len-1); //向左
    }
    
}

LCS只管数量最大，但是这道题要求的是最少的修改，最少的修改不等于字符串长度-LCS，并不一定能够直接改修成。所以这道题的dp要考虑的是每次匹配后要不要修改，如果要修改那么就计数，最后选出计数最小的。用S的前i个字符去匹配T的前j个字符需要最少多少次修改，同时这里可以选择跳过某些字符，如果跳过了当前字符，那么要修改的最少值就还是上一个状态的值，即int best = dp[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
31
32
33
34
35
import java.util.*;

public class Main {
    static final int INF = 1_000_000_000;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        String S = scan.next();
        String T = scan.next();

        int n = S.length(), m = T.length();
        int[][] dp = new int[n + 1][m + 1];

        for (int j = 1; j <= m; j++) dp[0][j] = INF;
        for (int i = 1; i <= n; i++) dp[i][0] = 0;

        for (int i = 1; i <= n; i++) 
        {
            char cs = S.charAt(i - 1);
            for (int j = 1; j <= m; j++) 
            {
                int best = dp[i - 1][j];

                int cost = (cs == T.charAt(j - 1)) ? 0 : 1;
                best = Math.min(best, dp[i - 1][j - 1] + cost);

                dp[i][j] = best;
            }
        }

        System.out.println(dp[n][m]);
        scan.close();
    }
}

14.全球变暖

题目描述

你有一张某海域 NxN 像素的照片，".“表示海洋、”#"表示陆地，如下所示：

…

.##…

.##…

…##.

…####.

…###.

…

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

…

…

…

…

…#…

…

…

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入描述

第一行包含一个整数 N (1≤N≤1000)。

以下 N 行 N 列代表一张海域照片。

照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。

输出一个整数表示答案。

输入输出样例

示例

输入

1
2
3
4
5
6
7
8
7
.......
.##....
.##....
....##.
..####.
...###.
.......

输出

1
1

题解

这道题是岛屿问题，可以用DFS或BFS解决

把给出的数据存储在二维数组中。然后对于给出的一个点去判断是否是陆地，如果是那就标记为已访问过，然后再向其四个方向上递归，这样再次访问到原来属于这个岛屿的一部分的陆地时也不会再计数，从而实现计算出岛屿的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void dfs(int[][] grid,int i,int j,boolean[][] visited)
{
    int m=grid.length;
    int n=grid[0].length;
    
    if(i<0||j<0||i>=m||j>=n)
    {
        return;
    }
    if(grid[i][j]==1)
    {
        return;
    }
    
    visited[i][j]=true;
    
    dfs(grid,i-1,j,visited);
    dfs(grid,i+1,j,visited);
    dfs(grid,i,j-1,visited);
    dfs(grid,i,j+1,visited);
    
}

在计算岛屿数量的时候就要先遍历位置，判断是否为陆地，如果是，则计数，并且调用dfs

在这道题中要求会被淹没的，那就需要检查一块陆地是否周围四个方向上都有陆地

代码

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
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    static boolean hasinner=false;
    static int[][] visited;
    static int N;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        N = scan.nextInt();
        char[][] grid = new char[N][N];
        visited=new int[N][N];
        
        for (int i = 0; i < N; i++) 
        {
            String sc = scan.next();
            for (int j = 0; j < N; j++) 
            {
                grid[i][j] = sc.charAt(j);
            }
        }

        int count = 0;
        for (int i = 0; i < N; i++) 
        {
            for (int j = 0; j < N; j++) 
            {
                if (visited[i][j]==0&&grid[i][j] == '#') 
                {
                    hasinner = false;  
                    dfs(grid, i, j);
                    if (!hasinner) 
                    {  
                        count++;
                    }
                }
            }
        }
        System.out.print(count);
        scan.close();
    }


    public static void dfs(char[][] grid, int i, int j) {

        visited[i][j]=1;

        if (grid[i+1][j]=='#'&&grid[i-1][j]=='#'&&grid[i][j+1]=='#'&&grid[i][j-1]=='#') 
        {
          hasinner=true;
        }

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        for (int d = 0; d < 4; d++) 
        {
            int nx = i + dx[d];
            int ny = j + dy[d];

              if(visited[nx][ny]==0&&grid[nx][ny]=='#')
              {
                dfs(grid, nx, ny);
              }
            
        }

    }
}

15.覆盖

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝有一个国际象棋的棋盘，棋盘的大小为 8×8，即由 8 行 8 列共 64 个方格组成。棋盘上有美丽的图案，因此棋盘旋转后与原来的棋盘不一样。

小蓝有很多相同的纸片，每张纸片正好能覆盖棋盘的两个相邻方格。小蓝想用 32 张纸片正好将棋盘完全覆盖，每张纸片都覆盖其中的两个方格。

小蓝发现，有很多种方案可以实现这样的覆盖。如果棋盘比较小，方案数相对容易计算，比如当棋盘是 2×2 时有两种方案，当棋盘是 4×4 时有 36 种方案。但是小蓝算不出他自己的这个 8×8 的棋盘有多少种覆盖方案。

请帮小蓝算出对于这个 8×8 的棋盘总共有多少种覆盖方案。

题解

这题本质是用 1×2 的纸片把 8×8 棋盘完全铺满。因为每次放都会影响下一行，所以不能暴力枚举所有格子，而是用状压 dp按行推进。

设 dp[i][mask] 表示处理完前 i 行后，第 i+1 行被竖着纸片占用的状态是 mask 的方案数。mask 是 8 位二进制，第 j 位为 1 表示这一列已经被上一行竖着占住。初始 dp[0] = 1。

转移时，假设上一行的状态是 k，本行决定哪些位置竖着放到下一行，记为 j。首先要求 (j & k) == 0，不能冲突。然后本行被竖向占用的位置是 (k | j)，剩下的位置必须能用横着的纸片填满。横放一次占两个格子，因此所有连续的空位段长度必须为偶数，可以预处理一个数组 st[mask] 判断是否合法。若满足条件，则 dp[i][j] += dp[i-1][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
import java.util.Arrays;

public class Main {
    static final int n = 8,m =8;
    static long[][] dp = new long[9][1<<8];
    static boolean st[] = new boolean[1<<8];
    public static void main(String[] args) {
        for(int i =0; i< 1<< n;i++) {
            st[i] = true;
            int cnt = 0;
            for(int j = 0 ; j < n; j++) {
                if((i >> j & 1)  == 1) {
                    if((cnt & 1) == 1) {
                        st[i] = false;
                        break;
                    }
                }else {
                    cnt++;
                }
            }
            if((cnt&1) == 1) {
                st[i] = false;
            }
        }
        for(int i = 0 ; i < 9 ; i++) {
            Arrays.fill(dp[i], 0);
        }
        dp[0][0] = 1;
        for(int i = 1; i <= m; i++) {
            for(int j = 0 ; j < (1 << n); j++) {
                for(int k = 0 ; k <(1<<n);k++) {
                    if((j & k)==0&&st[j|k]) {
                        dp[i][j] += dp[i-1][k];
                    }
                }
            }
        }
        System.out.println(dp[m][0]);
    }
}

16.乘法表

问题描述

九九乘法表是学习乘法时必须要掌握的。在不同进制数下，需要不同的乘法表。 例如，四进制下的乘法表如下所示：

1
2
3
1*1=1
2*1=2 2*2=10
3*1=3 3*2=12 3*3=21

请注意，乘法表中两个数相乘的顺序必须为样例中所示的顺序，不能随意交换两个乘数。

给定 P，请输出 P 进制下的乘法表。

输入格式

输入一个整数 P。

输出格式

输出 P 进制下的乘法表。P 进制中大于等于 10 的数字用大写字母 A、B、C、··· 表示。

样例输入

1
4

样例输出

1
2
3
1*1=1
2*1=2 2*2=10
3*1=3 3*2=12 3*3=21

样例输入

1
8

样例输出

1
2
3
4
5
6
7
1*1=1
2*1=2 2*2=4
3*1=3 3*2=6 3*3=11
4*1=4 4*2=10 4*3=14 4*4=20
5*1=5 5*2=12 5*3=17 5*4=24 5*5=31
6*1=6 6*2=14 6*3=22 6*4=30 6*5=36 6*6=44
7*1=7 7*2=16 7*3=25 7*4=34 7*5=43 7*6=52 7*7=61

题解

就是正常的乘法表，然后输出的时候用Integer.toString(i, r)，可以把整数i转成r进制的字符串，同时再用toUpperCase转成大写字母

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int r = scan.nextInt();
        for (int i = 1; i < r; i++) 
        {
            for (int j = 1; j <= i; j++) 
            {
             System.out.print(Integer.toString(i, r).toUpperCase() + "*" + Integer.toString(j, r).toUpperCase() + "=" + Integer.toString(i * j, r).toUpperCase() + " ");
            }
            System.out.println();
        }
        scan.close();
    }
}

17.飞机降落

问题描述

N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 TiT_i 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 DiD_i 个单位时间，即它最早可以于 TiT_i 时刻开始降落，最晚可以于 Ti+DiT_i+D_i 时刻开始降落。降落过程需要 LiL_i 个单位时间。

一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。

请你判断 N 架飞机是否可以全部安全降落。

输入格式

输入包含多组数据。

第一行包含一个整数 T，代表测试数据的组数。

对于每组数据，第一行包含一个整数 N。

以下 N 行，每行包含三个整数：Ti，Di和LiT_i，D_i 和 L_i。

输出格式

对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。

样例输入

1
2
3
4
5
6
7
8
9
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20

样例输出

1
2
YES
NO

样例说明

对于第一组数据，可以安排第 3 架飞机于 0 时刻开始降落，20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落，30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落，40 时刻完成降落。

对于第二组数据，无论如何安排，都会有飞机不能及时降落。

题解

dfs暴搜。对于每一架飞机，如果是还没降落的就计算降落时刻加上盘旋时间，如果能大于上一架飞机降落下来的时间那么就将其标记为已访问，同时开始递归，如果递归全部成功就返回true，否则就将当前飞机再标记为未访问

代码

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
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) 
        {
            int n = sc.nextInt();
            int[][] arr = new int[n][3];
            boolean[] visited = new boolean[n];
            for (int i = 0; i < n; i++) 
            {
                for(int j = 0; j < 3; j++)
                {
                    arr[i][j] = sc.nextInt();
                }
            }
            System.out.println(dfs(arr, visited, 0, 0) ? "YES" : "NO");
        }
    }
    private static boolean dfs(int[][] arr, boolean[] visited, int index, int last) {
        if (index == arr.length) 
        {
            return true;
        }
        for (int i = 0; i < arr.length; i++) 
        {
            int t = arr[i][0];
            int d = arr[i][1];
            int l = arr[i][2];
            if (!visited[i] && t + d >= last) 
            {
                visited[i] = true;
                if (dfs(arr, visited, index + 1, Math.max(last, t) + l)) 
                {
                    return true;
                }
                visited[i] = false;
            }
        }
        return false;
    }
}

18.合并数列

问题描述

小明发现有很多方案可以把一个很大的正整数拆成若干正整数的和。他采取了其中两种方案，分别将他们列为两个数组 {a1,a2,...,ana_1,a_2,...,a_n} 和 {b1,b2,...,bmb_1,b_2,...,b_m}。两个数组的和相同。

定义一次合并操作可以将某数组内相邻的两个数合并为一个新数，新数的值是原来两个数的和。小明想通过若干次合并操作将两个数组变成一模一样，即 n=m 且对于任意下标 i 满足 ai=bia_i=b_i。请计算至少需要多少次合并操作可以完成小明的目标。

输入格式

输入共 3 行。

第一行为两个正整数 n, m。

第二行为 n 个由空格隔开的整数 a1,a2,...,ana_1,a_2,...,a_n。

第三行为 m 个由空格隔开的整数 b1,b2,...,bmb_1,b_2,...,b_m。

输出格式

输出共 1 行，一个整数。

样例输入

1
2
3
4 3
1 2 3 4
1 5 4

样例输出

1
1

样例说明

只需要将 a2和a3a_2 和 a_3 合并，数组 a 变为 {1,5,4}，即和 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
37
38
39
40
41
42
import java.math.BigInteger;
import java.util.*;

public class Main {
    
    static long INF = (long) 1e18;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); 
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n], b = new int[m];
        for (int i = 0; i < n; i++) 
        {
            a[i] = sc.nextInt();
        }
        for (int j = 0; j < m; j++) 
        {
            b[j] = sc.nextInt();
        }
        int i = 0, j = 0;
        int ans = 0;
        while (i < n && j < m) 
        {
            if (a[i] == b[j]) 
            {
                i++; j++;
            } 
            else if (a[i] < b[j]) 
            {
                a[i + 1] += a[i];
                ans++; i++;
            } 
            else 
            {
                b[j + 1] += b[j];
                ans++; j++;
            }
        }
        System.out.print(ans);
    }
}

19.商品库存管理

问题描述

在库存管理系统中，跟踪和调节商品库存量是关键任务之一。小蓝经营的仓库中存有多种商品，这些商品根据类别和规格被有序地分类并编号，编号范围从 1 至 n。初始时，每种商品的库存量均为 0。

为了高效地监控和调整库存量，小蓝的管理团队设计了 m 个操作，每个操作涉及到一个特定的商品区间，即一段连续的商品编号范围（例如区间 [L,R]）。执行这些操作时，区间内每种商品的库存量都将增加 1。然而，在某些情况下，管理团队可能会决定不执行某些操作，使得这些操作涉及的商品区间内的库存量不会发生改变，维持原有的状态。

现在，管理团队需要一个评估机制，来确定如果某个操作未被执行，那么最终会有多少种商品的库存量为 0。对此，请你为管理团队计算出，每个操作未执行时，库存量为 0 的商品的种类数。

输入格式

第一行包含两个整数 n 和 m，分别表示商品的种类数和操作的个数。

接下来的 m 行，每行包含两个整数 L 和 R，表示一个操作涉及的商品区间。

输出格式

输出共 m 行，每行一个整数，第 i 行的整数表示如果不执行第 i 个操作，则最终库存量为 0 的商品种类数。

样例输入

1
2
3
4
5 3
1 2
2 4
3 5

样例输出

1
2
3
1
0
1

样例说明

考虑不执行每个操作时，其余操作对商品库存的综合影响：

  • 不执行操作 1：剩余的操作是操作 2（影响区间 [2,4]）和操作 3（影响区间 [3,5]）。执行这两个操作后，商品库存序列变为 [0,1,2,2,1]。在这种情况下，只有编号为 1 的商品的库存量为 0。因此，库存量为 0 的商品种类数为 1。

  • 不执行操作 2：剩余的操作是操作 1（影响区间 [1,2]）和操作 3（影响区间 [3,5]）。执行这两个操作后，商品库存序列变为 [1,1,1,1,1]。在这种情况下，所有商品的库存量都不为 0。因此，库存量为 0 的商品种类数为 0。

  • 不执行操作 3：剩余的操作是操作 1（影响区间 [1,2]）和操作 2（影响区间 [2,4]）。执行这两个操作后，商品库存序列变为 [1,2,1,1,0]。在这种情况下，只有编号为 5 的商品的库存量为 0。因此，库存量为 0 的商品种类数为 1。

题解

数据量较小可以直接暴力。但是正常做法还是前缀和+差分

  • 前缀和

    • 一维前缀和
      • 预处理：s[i]统计a[1……i]的值
      • 查询：s[r]-s[l-1]
      • s[i]=a[1]+a[2]+……+a[i]
      • a[l]+……+a[r]=s[r]-s[l-1]
    • 二维前缀和
      • s[i,j]=第i行j列格子左上部分所有元素的和
      • 以(x1,y1)为左上角，(x2,y2)为右下角的子矩阵的和为
        • s[x2,y2]-s[x1-1,y2]-s[x2,y1-1]+s[x1-1,y1-]

  • 差分

    • 一维差分
      • 给定两个数组，原数组a和差分数组b，a[i]=b[1]+b[2]+……+b[i]，b[i]=a[i]-a[i-1]
      • 给区间[l,r]中的每个数加上c：b[l]+=c，b[r+1]-=c
      • 若要求出a[i]即求出b[i]的前缀和
    • 二维差分
      • 给以(x1,y1)为左上角，(x2,y2)为右下角的子矩阵中的所有元素加上c
        • s[x1,y1]+=c，s[x2+1,y1]-=c，s[x1,y2+1]-=c，s[x2+1,y2-1]+=c

对于这道题来说就是正常的差分+前缀和，并且每次都要撤销一个操作，但不是真正的撤销，而是先求出完整的前缀和，然后得出为0的个数，再针对每个区间，看为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;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n=scan.nextInt();
        int m=scan.nextInt();

        int[] l=new int[m];
        int[] r=new int[m];
        int[] b=new int[n+2];
        int[] c=new int[n+1];

        b[0]=0;
        for(int j=0;j<m;j++)
        {
          l[j]=scan.nextInt();
          r[j]=scan.nextInt();
          b[l[j]]++;
          b[r[j]+1]--;
        }

        int base=0;
        for(int i=1;i<n+1;i++)
        {
          b[i]+=b[i-1];
          if(b[i]==0)
          {
            base++;
          }
        }

        for(int k=1;k<=n;k++)
        {
          c[k]=c[k-1]+(b[k]==1?1:0);
        }

        for(int q=0;q<m;q++)
        {
          int cnt=c[r[q]]-c[l[q]-1];
          System.out.println(base+cnt);
        }

        scan.close();
    }
}

20.直线

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上， 那么这些点中任意两点确定的直线是同一条。

给定平面上 2 × 3 个整点(x,y)∣0≤x<2,0≤y<3,x∈Z,y∈Z，即横坐标 是 0 到 1 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含 0 和 2) 之间的整数的点。这些点一共确定了 11 条不同的直线。

给定平面上 20×21 个整点 (x,y)∣0≤x<20,0≤y<21,x∈Z,y∈Z，即横坐标是 0 到 19 (包含 0 和 19) 之间的整数、纵坐标是 0 到 20 (包含 0 和 20) 之间的整数的点。

请问这些点一共确定了多少条不同的直线。

题解

通过计算斜率和截距，将其以字符串的形式放在集合中，打印出集合的大小并加上垂直的直线来找出非重复的直线

代码

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
import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Set<String> lines = new HashSet<>();
        for(int x1 = 0; x1 < 20; x1++) 
        {
            for(int x2 = 0; x2 < 20; x2++) 
            {
                for(int y1 = 0; y1 < 21; y1++) 
                {
                    for(int y2 = 0; y2 < 21; y2++) 
                    {
                        if(x1 == x2 || y1 == y2 ) 
                        {
                            continue;
                        }
                        
                        String line = "y = ";
                        int y = y2 - y1; 
                        int x = x2 - x1;
                        int d = gcd(x, y);
                        String k = y / d + "/" + x / d; 
                        line += k + "x + " ;
                        
                        int m = y2 * x1 - y1 * x2;
                        int n = gcd(m, x);
                        line += m / n + "/" + x / n;
                        
                        lines.add(line);
                        
                    }
                }
            }
          }

        System.out.println(lines.size() + 21 + 20);
    }
    
    public static int gcd(int x, int y) {
        return x % y == 0 ? y : gcd(y, x % y);
    }
}

21.数组分割

问题描述

小蓝有一个长度为 N 的数组 A=[A0,A1,...,AN−1A_0,A_1,...,A_{N−1}]。现在小蓝想要从 A 对应的数组下标所构成的集合 I=0,1,2,…,N−1 中找出一个子集 R1R_1 ，那么 R1R_1 在 I 中的补集为 R2R_2。记 S1=∑r∈R1ArS_1=∑_{r∈R_1}A_r ，S2=∑r∈R2ArS_2=∑_{r∈R_2}A_r ，我们要求 S1和S2S_1 和 S_2 均为偶数，请问在这种情况下共有多少种不同的 R1R_1 。当 R1R_1 或 R2R_2 为空集时我们将 S1S_1 或 S2S_2 视为 0。

输入格式

第一行一个整数 T，表示有 T 组数据。

接下来输入 T 组数据，每组数据包含两行：第一行一个整数 N，表示数组 A 的长度；第二行输入 N 个整数从左至右依次为 A0,A1,...,AN−1A_0,A_1,...,A_{N−1}，相邻元素之间用空格分隔。

输出格式

对于每组数据，输出一行，包含一个整数表示答案，答案可能会很大，你需要将答案对 1000000007进行取模后输出。

样例输入

1
2
3
4
5
2
2
6 6
2
1 6

样例输出

1
2
4
0

样例说明

对于第一组数据，答案为 4。（注意：大括号内的数字表示元素在数组中的下标。）

R1=0,R2=1R_1=0,R_2=1 ；此时 S1=A0=6S_1=A_0=6为偶数, S2=A1=6S_2=A_1=6 为偶数。

R1=1,R2=0R_1=1,R_2=0；此时 S1=A1=6S_1=A_1=6 为偶数, S2=A0=6S_2=A_0=6 为偶数。

R1=0,1,R2=R_1=0,1,R_2= ；此时 S1=A0+A1=12S_1=A_0+A_1=12为偶数, S2=0S_2=0 为偶数。

R1=,R2=0,1R_1=,R_2=0,1 ；此时 S1=0S_1=0 为偶数, S2=A0+A1=12S_2=A_0+A_1=12 为偶数。

对于第二组数据，无论怎么选择，都不满足条件，所以答案为 0。

题解

从数学角度来考虑，只有奇数加偶数才会得到奇数，所有关键在于奇数的个数，如果奇数的个数为奇数个那么一定不成立，只有为偶数个的时候才能时累加为偶数。求出奇数和偶数的个数后，对于每个偶数都有取和不取两种情况，所以对于k个偶数有2k2^k种情况。对于奇数，如果奇数的个数为0那么就是偶数的情况，如果不为0，那么对于k个奇数，随意选取会有2k2^k种情况，但是要选择的时候只能选择偶数个，在2k2^k种情况中有一半是奇数个元素，有一半是偶数个元素，即2k−12^{k-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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        int[] ans = new int[T];
        for (int i = 0; i < T; ++i) 
        {
            int N = scanner.nextInt();
            int evenCount = 0, oddCount = 0;
            for (int j = 0; j < N; ++j) 
            {
                int e = scanner.nextInt();
                if (e % 2 == 0) ++evenCount;
                else ++oddCount;
                if (oddCount % 2 == 0)
                {
                  ans[i] = (int) (Math.pow(2, evenCount) * Math.pow(2, oddCount == 0 ? 0 : oddCount - 1) % 1000000007);
                }
                else 
                {
                  ans[i] = 0;
                }
            }
        }
        for (int e : ans) 
        {
          System.out.println(e);
        }
        scanner.close();
        
    }
}

22.调手表

题目描述

小明买了块高端大气上档次的电子手表，他正准备调时间呢。

在 M78 星云，时间的计量单位和地球上不同，M78 星云的一个小时有 n 分钟。

大家都知道，手表只有一个按钮可以把当前的数加一。在调分钟的时候，如果当前显示的数是 0 ，那么按一下按钮就会变成 1，再按一次变成 2 。如果当前的数是 n−1，按一次后会变成 0。

作为强迫症患者，小明一定要把手表的时间调对。如果手表上的时间比当前时间多 1，则要按 n−1次加一按钮才能调回正确时间。

小明想，如果手表可以再添加一个按钮，表示把当前的数加 k 该多好啊…

他想知道，如果有了这个 +k按钮，按照最优策略按键，从任意一个分钟数调到另外任意一个分钟数最多要按多少次。

注意，按 +k 按钮时，如果加 k 后数字超过 n−1,则会对 n 取模。

比如，n=10,k=6 的时候，假设当前时间是 0，连按 2 次 +k 按钮，则调为 2。

输入描述

一行两个整数 n,k （0<k<n≤10510^5），意义如题。

输出描述

输出一行一个整数，表示按照最优策略按键，从一个时间调到另一个时间最多要按多少次。

输入输出样例

示例

输入

1
5 3

输出

1
2

样例解释

如果时间正确则按 0 次。否则要按的次数和操作系列之间的关系如下：

1：+1

2：+1, +1

3：+3

4：+3, +1

题解

有两种选择，加1和加k。用dp的时候要先将dp数组初始化，会有两种初始化，一种是只加1，另种是只加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
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n=scan.nextInt();
        int k=scan.nextInt();

        int[] dp=new int[n];
        for(int i=0;i<n;i++)
        {
          dp[i]=i;
        }

        for(int j=0;j<n;j++)
        {
          int ks=(int)(((long)j*k)%n);
          dp[ks]=Math.min(dp[ks],j); 
        }

        for(int i=0;i<n;i++)
        {
          dp[i]=Math.min(dp[i],Math.min(dp[(i-1+n)%n]+1,dp[(i-k+n)%n]+1));
        }

        int ans=0;

        for(int x:dp)
        {
          ans=Math.max(ans,x);
        }

        System.out.print(ans);

        scan.close();
    }
}

23.有理数的循环节

题目描述

1/7 = 0.142857142 ⋯⋯ 是个无限循环小数。

任何有理数都可以表示为无限循环小数的形式。

题目要求即是：给出一个数字的循环小数表示法。

输入描述

输入一行，两个整数。

每个整数范围均为：1 ~ 1000。

输出描述

输出两个整数做除法产生的小数或无限循环小数（循环节用方括号括起）。

输入输出样例

示例

输入

1
1,7

输出

1
0.[142857]

题解

首先题目的输入中带有一个逗号，所以要先用nextLine存到一个字符串中，再用split按逗号分隔再存到一个字符数组中，然后分别取出转成整数存到对应变量。先把整数部分求出。然后判断是否循环，就是要看取余数后得到的这个数字是否出现过。这里用哈希map，用put将余数存到对应位置，同时将这个余数存到StringBuiler中，在存之前还要判断是否已经出现过，用containsKey来判断。

代码

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
import java.util.Scanner;
import java.util.HashMap;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        String line=scan.nextLine();
        String[] s=line.split(",");
        int n=Integer.parseInt(s[0]);
        int m=Integer.parseInt(s[1]);

        StringBuilder sb=new StringBuilder();

        HashMap<Integer,Integer> map=new HashMap<>();

        int integer=n/m;
        System.out.print(integer);
        System.out.print(".");
        
        int reminder=n%m;
        while(reminder!=0)
        {
          
          if(map.containsKey(reminder))
          {
            break;
          }

          map.put(reminder,sb.length());
          
          reminder=reminder*10;
          int t=reminder/m;
          sb.append(t);
          reminder=reminder%m;

        }
        if(reminder==0)
        {
          System.out.print(sb.toString());
          return;
        }
        if(sb.length()>0)
        {
          System.out.print("[");
          System.out.print(sb.toString());
          System.out.print("]");
        }

        scan.close();
    }
}

24.X 进制减法

问题描述

进制规定了数字在数位上逢几进一。

X 进制是一种很神奇的进制, 因为其每一数位的进制并不固定！例如说某种 X 进制数, 最低数位为二进制, 第二数位为十进制, 第三数位为八进制, 则 X 进制数 321 转换为十进制数为 65 。

现在有两个 X 进制表示的整数 A 和 B, 但是其具体每一数位的进制还不确定, 只知道 A 和 B 是同一进制规则, 且每一数位最高为 N 进制, 最低为二进制。请你算出 A−B 的结果最小可能是多少。

请注意, 你需要保证 A 和 B 在 X 进制下都是合法的, 即每一数位上的数字要小于其进制。

输入格式

第一行一个正整数 N, 含义如题面所述。

第二行一个正整数 MaM_a, 表示 X 进制数 A 的位数。

第三行 MaM_a 个用空格分开的整数, 表示 X 进制数 A 按从高位到低位顺序各 个数位上的数字在十进制下的表示。

第四行一个正整数 MbM_b, 表示 X 进制数 B 的位数。

第五行 MbM_b 个用空格分开的整数, 表示 X 进制数 B 按从高位到低位顺序各 个数位上的数字在十进制下的表示。

请注意, 输入中的所有数字都是十进制的。

输出格式

输出一行一个整数, 表示 X 进制数 A−B 的结果的最小可能值转换为十进 制后再模 1000000007 的结果。

样例输入

1
2
3
4
5
11
3
10 4 0
3
1 2 0

样例输出

1
94

样例说明

当进制为: 最低位 2 进制, 第二数位 5 进制, 第三数位 11 进制时, 减法得到的差最小。此时 A 在十进制下是 108,B 在十进制下是 14 , 差值是 94。

题解

一个正常的三位数进制数，其第二位是z，则说明是有第一位上的z*进制数个，同理第三位上是y，则是第二位上的y*进制数，则第一位上就有y*进制数*进制数个，那么最终就可以写为y*进制数*进制数+z*进制数的十进制数。这里的x进制也同理可以求出其十进制。为了使相减结果最小，要使进制尽可能的小，每次都取相同数位上的最大值加1。同时可能存在数位并不相同的情况，所以要从低位开始取。都取出后用循环将两个数都用上述方法求出十进制数。但是在循环中取模的时候可能会存在，a比取模数略大，b比取模数略小，取模之后反而a比b小了，所以在最后计算前要将a加上取模数，保证a大于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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int N=scan.nextInt();

        int aNum=scan.nextInt();
        long[] a=new long[aNum];
        for(int i=0;i<aNum;i++)
        {
          a[i]=scan.nextInt();
        }

        int bNum=scan.nextInt();
        long[] b=new long[bNum];
        for(int i=0;i<bNum;i++)
        {
          b[i]=scan.nextInt();
        }

        long[] carry=new long[aNum];
        for(int i=1;i<aNum;i++)
        {
          if(bNum-i<0)
          {
            carry[aNum-i]=Math.max(a[aNum-i]+1,2);
            continue;
          }
          carry[aNum-i]=Math.max(Math.max(a[aNum-i],b[bNum-i])+1,2);
        }

        long aD=0;
        long bD=0;
        for(int i=0;i<aNum-1;i++)
        {
          aD=(aD+a[i])*carry[i+1]%1000000007; 
        }
        aD=aD+a[aNum-1]+1000000007;

        for(int i=0;i<bNum-1;i++)
        {
          bD=(bD+b[i])*carry[i+1]%1000000007; 
        }
        bD=bD+b[bNum-1];

        System.out.print((aD-bD)%1000000007);

        scan.close();
    }
}

25.三国游戏

问题描述

小蓝正在玩一款游戏。游戏中魏(X)、蜀(Y)、吴(Z)三个国家各自拥有一定数量的士兵X,Y,Z（一开始可以认为都为 0）。游戏有 n 个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 i 个事件发生时会分别让 X,Y,Z 增加Ai,Bi,CiA_i,B_i,C_i。

当游戏结束时（所有事件的发生与否已经确定），如果 X,Y,Z 的其中一个大于另外两个之和，我们认为其获胜。例如，当 X>Y+Z 时，我们认为魏国获胜。小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?如果不存在任何能让某国获胜的情况，请输出 −1。

输入格式

输入的第一行包含一个整数 n。

第二行包含 n 个整数表示 AiA_i，相邻整数之间使用一个空格分隔。

第三行包含 n 个整数表示 BiB_i，相邻整数之间使用一个空格分隔。

第四行包含 n 个整数表示 CiC_i，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

1
2
3
4
3
1 2 2
2 3 2
1 0 7

样例输出

1
2

题解

先求出每个事件分别对单个国家所产生的贡献，对这些贡献进行排序，再循环累加判断贡献是否会大于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
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.util.Arrays;

public class Main {
    public static void main(String[]atgs) {
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int[]a=new int[n];
        int[]b=new int[n];
        int[]c=new int[n];
        for(int x=0;x<n;x++) 
        {
            a[x]=scan.nextInt();
        }
        for(int y=0;y<n;y++) 
        {
            b[y]=scan.nextInt();
        }
        for(int z=0;z<n;z++) 
        {
            c[z]=scan.nextInt();
        }
        for(int i=0;i<n;i++) 
        {
            int m=a[i];
            int e=b[i];
            int f=c[i];
            a[i]=m-e-f;
            b[i]=e-m-f;
            c[i]=f-m-e;
        }
        Arrays.sort(a);
        Arrays.sort(b);
        Arrays.sort(c);
        int d=-1;long sum=0,sun=0,sus=0;

        for(int i=n-1;i>=0;i--) 
        {
            sum+=a[i];
            sun+=b[i];
            sus+=c[i];
            if(sum>0||sun>0||sus>0) 
            {
                d=n-i;
            }
        }
        System.out.println(d);
    }
}

26.冰雹数

题目描述

任意给定一个正整数 N，

如果是偶数，执行： N/2；

如果是奇数，执行： N×3+1，

生成的新的数字再执行同样的动作，循环往复。

通过观察发现，这个数字会一会儿上升到很高，一会儿又降落下来。

就这样起起落落的，但最终必会落到"1"，这有点像小冰雹粒子在冰雹云中翻滚增长的样子。

比如 N=9，

9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1

可以看到，N=9 的时候，这个"小冰雹"最高冲到了 52 这个高度。

输入描述

输入一个正整数 N（N<10610^6）。

输出描述

输出一个正整数，表示不大于 N 的数字，经过冰雹数变换过程中，最高冲到了多少。

输入输出样例

示例

输入

1
10

输出

1
52

题解

正常思路循环即可

代码

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;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        long N=scan.nextLong();
        long max=N;
        for(long i=1;i<=N;i++)
        {
          long p=i;
          while(p!=1)
          {
            if(p%2==0)
            {
              p=p/2;
            }
            else
            {
              p=p*3+1;
            }
            max=Math.max(max,p);
          }
        }
       
        System.out.print(max);

        scan.close();
    }
}

27.最优分组

问题描述

小蓝开了一家宠物店，最近有一种 X 病毒在动物之间进行传染，小蓝为了以防万一打算购买测试剂对自己的宠物进行病毒感染测试。

为了减少使用的测试剂数目，小蓝想到了一个好方法：将 N 个宠物平均分为若干组，使得每组恰好有 K 只宠物，这样对同一组的宠物进行采样并混合后用一个试剂进行检测，如果测试结果为阴性则说明组内宠物都未感染 X 病毒；如果是阳性的话则需要对组内所有 K 只宠物单独检测，需要再消耗 K 支测试剂（当 K=1 时，就没必要再次进行单独检测了，因为组内只有一只宠物，一次检测便能确认答案）。

现在我们已知小蓝的宠物被感染的概率为 p，请问 K 应该取值为多少才能使得期望的测试剂的消耗数目最少？如果有多个答案输出最小的 K。

输入格式

第一行，一个整数 N 。

第二行，一个浮点数 p 。

输出格式

输出一行，一个整数 K 表示答案。

样例输入

1
2
1000
0.05

样例输出

1
5

题解

概率为p，则未感染的概率为(1−p)k(1-p)^k，对于一组宠物来说，需要(1−p)k∗1+(1−(1−p)k)∗(k+1)(1-p)^k*1+(1-(1-p)^k)*(k+1)个试剂，一共n/k组

先算出有感染和无感染的概率，再用概率乘对应所需的试剂数并相加，即为一组的所需，再乘组数。最开始将所需要的试剂数设置为最大值，然后循环和算出来的试剂数比较，如果小或等于（因为是从大到小遍历k的值，所以即使相等也要赋值），则给所需试剂数赋值，并且给k赋当前值，直到k=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
import java.util.*;

public class Main {
    static Scanner input=new Scanner(System.in);
    public static void main(String[] args) {
        int N=input.nextInt();
        int minK=Integer.MAX_VALUE;
        double p=input.nextDouble();
        double miny=Double.MAX_VALUE;
        for(int K=N; K>=1; K--)
        {
            if(N%K==0)
            {
                double P=Math.pow(1-p,K);
                double E=(P+(1-P)*(K+1))*N/K;
                if(K==1) 
                {
                  E=N;
                }
                if(E<=miny)
                {
                    miny=E;
                    minK=K;
                }
            }
        }
        System.out.println(minK);
    }
}

28.子矩阵

问题描述

给定一个 n×m （n 行 m 列）的矩阵。设一个

矩阵的价值为其所有数中的最大值和最小值的乘积。求给定矩阵的所有大小为 a×b （a 行 b 列）的子矩阵的价值的和。

答案可能很大，你只需要输出答案对 998244353 取模后的结果。

输入格式

输入的第一行包含四个整数分别表示 n，m，a，b，相邻整数之间使用一个空格分隔。接下来

n 行每行包含 m 个整数，相邻整数之间使用一个空格分隔，表示矩阵中的每个数 Ai,jA_{i,j}。

输出格式

输出一行包含一个整数表示答案。

样例输入

1
2
3
2 3 1 2
1 2 3
4 5 6

样例输出

1
58

样例说明

1×2+2×3+4×5+5×6=58。

题解

这道题目涉及到滑动窗口，而且是二维的滑动窗口，可以分为横着和竖着的两个一维滑动窗口。

代码

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
import java.util.Scanner;

public class Main {
    static final int MOD = 998244353;

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        int m = scan.nextInt();
        int a = scan.nextInt();
        int b = scan.nextInt();

        int[][] arr = new int[n][m];
        
        int[][] Maxarr=new int[n][m-b+1];
        int[][] Minarr=new int[n][m-b+1];
        
        for (int i = 0; i < n; i++) {
            int temp=0;
            for (int j = 0; j < m; j++) {
                arr[i][j] = scan.nextInt();
                
                if(j>b-2) {
                    int max=Integer.MIN_VALUE;
                  int min=Integer.MAX_VALUE;
                  for(int k=j;k>j-b;k--) {
                      max=Math.max(max,arr[i][k]);
                      min=Math.min(min,arr[i][k]);
                  }
                  Minarr[i][temp]=min;
                  Maxarr[i][temp++]=max;
                }
            }
        }

        int result = 0;
        for (int i = 0; i <= n - a; i++) {
            for (int k = 0; k < m - b + 1; k++) {
                int max = Integer.MIN_VALUE;
                int min = Integer.MAX_VALUE;
                for (int j = i; j < i + a; j++) {
                    max = Math.max(max, Maxarr[j][k]);
                    min = Math.min(min, Minarr[j][k]);
                }
                result = (result + ((max % MOD) * (min % MOD)) % MOD) % MOD;
            }
        }
        System.out.println(result);

    }
}

29.统计子矩阵

问题描述

给定一个 N×M 的矩阵 A, 请你统计有多少个子矩阵 (最小 1×1, 最大 N×M) 满足子矩阵中所有数的和不超过给定的整数 K ?

输入格式

第一行包含三个整数 N,M 和 K.

之后 N 行每行包含 M 个整数, 代表矩阵 A.

输出格式

一个整数代表答案。

样例输入

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

样例输出

1
19

样例说明

满足条件的子矩阵一共有 19 , 包含:

大小为 1×1 的有 10 个。

大小为 1×2 的有 3 个。

大小为 1×3 的有 2 个。

大小为 1×4 的有 1 个。

大小为 2×1 的有 3 个。

题解

用列的前缀和加上滑动窗口可以解决（如果使用二维前缀和加上枚举子矩阵会导致超时，但也能完成70%）。先将列做成前缀和。然后开始用双指针滑动窗口，每次右边界向右一个，左边界不动并统计和，如果和超过给定值，就左边界向右移

代码

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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
        int[][] s = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                s[i][j] = s[i-1][j] + sc.nextInt();
            }
        }
        long res = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                for(int l = 1, r = 1, sum = 0 ; r<=m ; r++){
                    sum += s[j][r] - s[i-1][r];
                    while (sum>k){
                        sum -= s[j][l] - s[i-1][l];
                        l++;
                    }
                    res += r - l + 1;
                }
            }
        }
        System.out.println(res);
        sc.close();


    }
}