第一题

计算自然数 \(n\) 至自然数 \(m\) 之间（含 \(n\)、\(m\)）所有整数中的各位数字是奇数的和。如输入 \(n\) 是 \(110\)，\(m\) 是 \(118\)，则结果为 \(1+1+1+1+1+1+1+1+1+3+1+1+1+1+5+1+1+1+1+7+1+1=34\)。

签到题，循环模拟即可。

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
public class p1 {

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

        int n, m;
        int ans = 0;

        n = sc.nextInt();
        m = sc.nextInt();
        sc.close();

        p1 p = new p1();

        for (int i = n; i <= m; i++) {
            ans += p.oddAdd(i);
        }

        System.out.println(ans);
    }

    public int oddAdd(int x) {
        int i = 0;
        while (x > 0) {
            if ((x % 10) % 2 == 1)
                i += x % 10;
            x = x / 10;
        }
        return i;
    }
}

第二题

当你输入信用卡号码的时候，有没有担心输错了而造成损失呢？其实可以不必这么担心，因为并不是一个随便的信用卡号码都是合法的，它必须通过Luhn算法来验证通过。

该校验的过程：

  1. 从卡号最后一位数字开始，逆向将奇数位（\(1, 3, 5\) 等等）相加。
  2. 从卡号最后一位数字开始，逆向将偶数位数字，先乘以 \(2\)（如果乘积为两位数，则将其减去 \(9\)），再求和。
  3. 将奇数位总和加上偶数位总和，结果应该可以被 \(10\) 整除。

例如，卡号是：5432123456788881

则奇数、偶数位（用斜体标出）分布：5 4 3 2 1 2 3 4 5 6 7 8 8 8 8 1

奇数位和 \(= 35\)

偶数位乘以 \(2\)（有些要减去 \(9\)）的结果：\(1\ 6\ 2\ 6\ 1\ 5\ 7\ 7\)，求和 \(= 35\)。

最后 \(35+35=70\) 可以被 \(10\) 整除，认定校验通过。

请编写一个程序，从键盘输入卡号，然后判断是否校验通过。通过显示：“成功”，否则显示“失败”。

比如，用户输入：356827027232780

程序输出：成功

签到题，分奇偶循环模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class p2 {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      String str = sc.nextLine();
      sc.close();

      int sum = 0;
      for (int i = str.length() - 1; i >= 0; i -= 2) {
         sum += Integer.parseInt(str.charAt(i) + "");
      }

      for (int i = str.length() - 2; i >= 0; i -= 2) {
         int temp = Integer.parseInt(str.charAt(i) + "") * 2;
         sum += temp > 9 ? temp - 9 : temp;
      }

      if (sum % 10 == 0)
         System.out.println("成功");
      else
         System.out.println("失败");
   }
}

第三题

整数的分划问题。

如，对于正整数 \(n=6\)，可以分划为：

\(6\)

\(5+1\)

\(4+2, 4+1+1\)

\(3+3, 3+2+1, 3+1+1+1\)

\(2+2+2, 2+2+1+1, 2+1+1+1+1\)

\(1+1+1+1+1+1+1\)

现在的问题是，对于给定的正整数 \(n\)，编写算法打印所有划分。

用户从键盘输入 \(n\) （范围 \(1 \sim 10\)）

程序输出该整数的所有划分。

递归枚举入门题，关于重复的情况我是做了一个判断，比较当前整数剩余部分和上一个值的大小，循环从较小值开始倒序的话，就不会重复了。

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
public class p3 {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      sc.close();

      p3 p = new p3();

      String ans = "";
      p.divide(n, n, ans);
   }

   public void divide(int n, int prev, String ans) {
      if (n == 0)
         System.out.println(ans);
      else {
         for (int i = prev < n ? prev : n; i > 0; i--) {
            if (ans.isEmpty()) {
               divide(n - i, i, ans + i);
            } else {
               divide(n - i, i, ans + "+" + i);
            }
         }
      }
   }
}

第四题

给定一个长度为 \(n\) 的正整数数列 \(A_1, A_2, \dots, A_n\) 和一个非负整数 \(x\)，给定 \(m\) 次查询，每次询问能否从区间 \([k, r]\) 中选择两个数使得它们的异或等于 \(x\)。

输入格式：

输入第一行包含三个整数 \(n, m, x\)。

第二行包含 \(n\) 个正整数 \(A_1, A_2, \dots, A_n\)。

接下来 \(m\) 行，每行两个整数 \(k, r\) 表示询问区间 \([k, r]\)。

输出格式：

对于每个查询，如果该区间内存在两个数的异或为 \(x\) 则输出 yes，否则输出 no。

输入样例：

4 4 1

1 2 3 4

1 4

1 2

2 3

3 3

输出样例：

yes

no

yes

no

难点在于异或，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
public class p4 {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int m = sc.nextInt();
      int x = sc.nextInt();

      p4 p = new p4();

      int[] array = new int[n];

      for (int i = 0; i < n; i++) {
         array[i] = sc.nextInt();
      }

      for (int i = 0; i < m; i++) {
         int a = sc.nextInt() - 1;
         int b = sc.nextInt() - 1;
         boolean suc = false;
         for (int j = a; j <= b; j++) {
            for (int k = a; k <= b; k++) {
               if (j != k && p.xor(array[j], array[k]) == x) {
                  System.out.println("yes");
                  suc = true;
                  break;
               }
            }
            if (suc)
               break;
         }

         if (!suc) {
            System.out.println("no");
         }
      }
      sc.close();
   }

   public int xor(int a, int b) {
      int i = 0;
      int sum = 0;
      while (a > 0 || b > 0) {
         if (a % 2 == 0 && b % 2 == 1 || a % 2 == 1 && b % 2 == 0)
            sum += Math.pow(2, i);
         a /= 2;
         b /= 2;
         i++;
      }
      return sum;
   }
}

第五题

学校大门外长度为 \(L\) 的马路上有一排树，每两棵相邻的树之间的间隔都是 \(1\) 米。可以把马路看成一个数轴，马路的一端在数轴 \(0\) 的位置，另一端在 \(L\) 的位置，数轴上的每个整数点（即 \(0, 1, 2, \dots, L\)）都有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任意区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。请计算将这些树都移走后，马路上还有多少棵树。

输入

500 3

150 300

100 200

470 471

输出

298

（表中输入数据说明：第一行第一个表示区间的总长度，第二个数表示有几个需要移动的区域：例如 500 3，表示区间的总长度为 \([0, 500]\)，需要移动的是 \(3\) 个区间，这三个区间分别是 \([150, 300]\)、\([100, 200]\)、\([470, 471]\)）

比较巧妙的一题，不过也是模版了。

可能有人想到如下的做法：

使用一个可以覆盖所有区间范围的数组，对每个区间进行标记，结果为数组中被标记元素的个数。这种方法的时间复杂度是 \(O(nm)\)。 注：\(n\) 是区间个数，\(m\) 是所有区间总的范围。

但这样的话，时间复杂度其实比较低了，一种更优的思路如下：

使用一个可以覆盖所有区间范围的数组 flg，初始化时将数组中的元素都置为 \(0\)。对于每一个区间 \([l, r]\)，将 flg[l]++，flg[r+1]--。最后使用一个累加器 cnt，初始置为 \(0\)。依次扫描数组中的每一个元素，对于第 \(i\) 个元素，cnt += flg[i]。此时，若 cnt > 0，则说明 \(i\) 在某些区间中；若 cnt == 0，则证明 \(i\) 不在任何区间中。统计 cnt == 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
public class p5 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt();
        int n = sc.nextInt();

        int cnt = 0, ret = 0;
        int[] flg = new int[l+1];

        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            flg[a]++;
            flg[b + 1]--;
        }
        for (int i = 0; i <= l; i++) {
            cnt += flg[i];
            if (cnt == 0) {
                ret++;
            }
        }

        System.out.println(ret);
        sc.close();
    }
}

第六题

一种简单的文件传输加密系统：假设明文一共有 \(m\) 个字节，加密后的密文第 \(1\) 字节和第 \(m\) 字节互换位置，第 \(2\) 字节和第 \(m-2\) 字节互换位置，第 \(3\) 字节和第 \(m-3\) 字节互换位置，以此类推。互换位置后，每一个字节的第 \(1\) 和第 \(8\) 比特，第 \(2\) 和第 \(7\) 比特，第 \(3\) 和第 \(6\) 比特，第 \(4\) 和第 \(5\) 比特互换位置。为了验证程序正确，输入一个字符串，加密一次后以整数格式输出每个字符，再加密一次后，以整数格式和字符串格式输出第二次加密的内容。

测试用例：

输入“abcde”，则运行结果如下：

edcba

-90 38 -58 70 -122

abcde

97 98 99 100 101

这题其实有点迷惑人，关键在于他题目描述的不清不楚，由于我写这道题的时候时间不多了，所以直接放弃掉了最后一题，考虑到大概率是人工阅卷，这题就按照规范一点的写法完成了。

难点在于对二进制位的处理，这里我直接按照计算逻辑硬写了。

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
public class p6 {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      String str = sc.nextLine();
      sc.close();

      p6 p = new p6();

      String newStr = p.stringReverse(str);
      for (int i = 0; i < newStr.length(); i++) {
         short temp = (short) newStr.charAt(i);
         System.out.print(temp + " ");
      }
      System.out.println();
      String newnewStr = p.stringReverse(newStr);
      System.out.println(newnewStr);
      for (int i = 0; i < newnewStr.length(); i++) {
         short temp = (short) newnewStr.charAt(i);
         System.out.print(temp + " ");
      }
   }

   public short bitReverse(int n) {
      short i = 7;
      short sum = 0;
      boolean minus;
      if (n % 2 == 1)
         minus = true;
      else
         minus = false;
      n /= 2;
      i--;
      while (n > 0) {
         if (n % 2 == 1)
            sum += Math.pow(2, i);
         n /= 2;
         i--;
      }
      if (minus)
         sum -= 128;
      return sum;
   }

   public String stringReverse(String str) {
      String newStr = new String();
      for (int i = str.length() - 1; i >= 0; i--) {
         short tempInt = bitReverse(str.charAt(i));
         char temp = (char) tempInt;
         newStr += temp;
      }
      return newStr;
   }
}

第七题

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。

小蓝的图由 \(2021\) 个结点组成，依次编号 \(1\) 至 \(2021\)。

对于两个不同的结点 \(a, b\)，如果 \(a\) 和 \(b\) 的差的绝对值大于 \(21\)，则两个结点之间没有边相连；如果 \(a\) 和 \(b\) 的差的绝对值小于等于 \(21\)，则两个点之间有一条长度为 \(a\) 和 \(b\) 的最小公倍数的无向边相连。

例如：结点 \(1\) 和结点 \(23\) 之间没有边相连；结点 \(3\) 和结点 \(24\) 之间有一条无向边，长度为 \(24\)；结点 \(15\) 和结点 \(25\) 之间有一条无向边，长度为 \(75\)。

请计算，结点 \(1\) 和结点 \(2021\) 之间的最短路径长度是多少。

这题眼熟，我拿蓝桥杯国二那年，省赛填空题压轴就是这个，这里就不给题解了，各位想了解的话直接看往年题解就行了。