第十三届蓝桥杯省赛JavaC组真题——详细答案对照(完整版)-阿里云开发者社区

前言

本次题目我认为还是比较难的，有人做了一个分析，我们来看看啊。

话说真的对于大专生来说已经是非常难的了呢，能拿到省一的基本上都是万里挑一的孩子呢。

试题 A: 排列字母

【问题描述】

小蓝要把一个字符串中的字母按其在字母表中的顺序排列。

例如，LANQIAO 排列后为 AAILNOQ。

又如，GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY。

请问对于以下字符串，排列之后字符串是什么？

WHERETHEREISAWILLTHEREISAWAY

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

对照代码

package com.item.action;
import java.util.Arrays;
public class Demo6 {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    String s = "WHERETHEREISAWILLTHEREISAWAY";
    char[] arr = s.toCharArray();
    Arrays.sort(arr);
    System.out.println(arr);
  }
}

试题 B: 特殊时间

【问题描述】

2022 年 2 月 22 日 22:20 是一个很有意义的时间，年份为 2022，由 3 个 2 和 1 个 0 组

成，如果将月和日写成 4 位，为 0222，也是由 3 个 2 和 1 个 0 组成，如果将时间中的时和

分写成 4 位，还是由 3 个 2 和 1 个 0 组成。

小蓝对这样的时间很感兴趣，他还找到了其它类似的例子，比如 111 年 10 月 11 日

01:11，2202 年 2 月 22 日 22:02 等等。

请问，总共有多少个时间是这种年份写成 4 位、月日写成 4 位、时间写成 4 位后由 3

个一种数字和 1 个另一种数字组成。注意 1111 年 11 月 11 日 11:11 不算，因为它里面没有

两种数字。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

对照答案1

package com.item.action;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.List;
public class Demo6 {
  public static void main(String[] args) {
    SimpleDateFormat sdf = new SimpleDateFormat("yyyyMMddHHmm");
    // 严格计算日期
    // 如果不写这个，那么 222322232223 会通过SimpleDateFormat.parse 不会被catch
    sdf.setLenient(false);
    List<String> resultList = new ArrayList<>();
    // 先看看 两个不同的数字有多少种组合
    for (int i = 0; i < 10; i++) {
      // 0001 0010 0100 1000
      // 1110 1101 1011 0111
      // 共有这8种情况
      // 下面分为两个for循环来讨论，哪个数是3个，哪个数是1个
      // 两个for循环可以提出去坐公共方法，避免冗余，在这里为了说明效果，就不进行分离了
      for (int j = i + 1; j < 10; j++) {
        List<String> list = new ArrayList<>();
        list.add(i + "" + i + "" + i + "" + j);
        list.add(i + "" + i + "" + j + "" + i);
        list.add(i + "" + j + "" + i + "" + i);
        list.add(j + "" + i + "" + i + "" + i);
        // 因为是由 年 月日 时分 三个组成，所以直接做了3个for循环用来拼接
        for (int m = 0; m < list.size(); m++) {
          for (int n = 0; n < list.size(); n++) {
            for (int p = 0; p < list.size(); p++) {
              // 这里借用SimpleDateFormat来判断是否是正常时间
              String date = list.get(m) + list.get(n) + list.get(p);
              try {
                sdf.parse(date);
              } catch (ParseException e) {
                // 遇到非正常时间直接跨过，
                continue;
              }
              // 正确的时间给添加到list中，用来统计
              resultList.add(date);
            }
          }
        }
        // 和上面的情况同理
        list = new ArrayList<>();
        list.add(j + "" + j + "" + j + "" + i);
        list.add(j + "" + j + "" + i + "" + j);
        list.add(j + "" + i + "" + j + "" + j);
        list.add(i + "" + j + "" + j + "" + j);
        for (int m = 0; m < list.size(); m++) {
          for (int n = 0; n < list.size(); n++) {
            for (int p = 0; p < list.size(); p++) {
              String date = list.get(m) + list.get(n) + list.get(p);
              try {
                sdf.parse(date);
              } catch (ParseException e) {
                continue;
              }
              resultList.add(date);
            }
          }
        }
      }
    }
    // 最后打印一下效果
    System.out.println(resultList.size());
  }
}

对照答案2

package com.item.action;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
public class Demo6 {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    DateTimeFormatter d1 = DateTimeFormatter.ofPattern("MMdd");
        DateTimeFormatter d2 = DateTimeFormatter.ofPattern("HHmm");
        LocalDateTime start = LocalDateTime.of(0000, 01, 01, 00, 00);
        LocalDateTime end = LocalDateTime.of(0000, 12, 31, 23, 59);
        int[] buff = new int[128];
        int ans = 0;
        for (; start.compareTo(end) <= 0; start = start.plusMinutes(1)) {
            for (char i = '0'; i <= '9'; ++i) buff[i] = 0;
            for (byte b : start.format(d1).getBytes()) ++buff[b];
            boolean flag1 = true, flag3 = true;
            for (char i = '0'; i <= '9'; ++i)
                if (buff[i] == 1) flag1 = false;
                else if (buff[i] == 3) flag3 = false;
            if (flag1 || flag3) continue;
            for (byte b : start.format(d2).getBytes()) --buff[b];
            for (char i = '0'; i <= '9'; ++i)
                if (buff[i] != 0) flag1 = true;
            if (!flag1) ++ans;
        }
        System.out.println(4 * ans);
  }
}

试题 C: 纸张尺寸

【问题描述】

在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm × 841mm，将 A0 纸沿长边对折

后为 A1 纸，大小为 841mm × 594mm，在对折的过程中长度直接取下整（实际裁剪时可能

有损耗）。将 A1 纸沿长边对折后为 A2 纸，依此类推。

输入纸张的名称，请输出纸张的大小。

【输入格式】

输入一行包含一个字符串表示纸张的名称，该名称一定是 A0、A1、A2、 A3、A4、

A5、A6、A7、A8、A9 之一。

【输出格式】

输出两行，每行包含一个整数，依次表示长边和短边的长度。

【样例输入 1】

A0

【样例输出 1】

1189

841

【样例输入 2】

A1

【样例输出 2】

841

594

我找了个A4的，一会也能测试一下。

对照代码1

package com.item.action;
import java.util.Scanner;
public class Demo6 {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int [][]arr=new int[10][2];
        Scanner sc=new Scanner(System.in);
        int a=1189,b=841;
        arr[0][0]=1189;
        arr[0][1]=841;
        for (int i=1;i<10;i++){
            arr[i][0]=Math.min(a,b);
            if (a>b) {
                a /= 2;
            }
            else{
                b/=2;
            }
            arr[i][1]=Math.min(a,b);
        }
        String str=sc.next();
        sc.close();
        int re=str.charAt(1)-'0';
        System.out.println(arr[re][0]);
        System.out.println(arr[re][1]);
  }
}

对照代码2

package com.item.action;
import java.util.Scanner;
public class Demo6 {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    // A0尺寸
    int a = 1189;
    int b = 841;
    String c = sc.next();
    sc.close();
    for (int i = 0; i < c.charAt(1) - 48; i++) {
      if (a >= b) {
        a /= 2;
      } else {
        b /= 2;
      }
    }
    if (a >= b) {
      System.out.println(a);
    }
    System.out.println(b);
    if (a < b) {
      System.out.println(a);
    }
  }
}

试题 D: 求和

【问题描述】

给定 n 个整数 a1, a2, · · · , an ，求它们两两相乘再相加的和，即 S = a1 · a2 + a1 · a3

+ · · · + a1 · an + a2 · a3 + · · · + an−2 · an−1 + an−2 · an + an−1 · an.

【输入格式】

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

第二行包含 n 个整数 a1, a2, · · · an。

【输出格式】

输出一个整数 S，表示所求的和。请使用合适的数据类型进行运算。

【样例输入】

4

1 3 6 9

【样例输出】

117

【评测用例规模与约定】

对于 30% 的数据，1 ≤ n ≤ 1000，1 ≤ ai ≤ 100。

对于所有评测用例，1 ≤ n ≤ 200000，1 ≤ ai ≤ 1000。

对照代码1

package com.item.action;
import java.util.Scanner;
public class Demo6 {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int[] array = new int[a];
    long count = 0;
    for (int i = 0; i < array.length; i++) {
      array[i] = sc.nextInt();
    }
    sc.close();
    for (int i = 0; i < array.length; i++) {
      for (int j = i + 1; j < array.length; j++) {
        count += array[i] * array[j];
      }
    }
    System.out.println(count);
  }
}

对照代码2

package com.item.action;
import java.util.Scanner;
public class Demo6 {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    long s = 0;
    int n = sc.nextInt();
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
      s += arr[i];
    }
    sc.close();
    long count = 0;
    for (int i = 0; i < n; i++) {
      count += arr[i] * (s - arr[i]);
      s -= arr[i];
    }
    System.out.println(count);
  }
}

试题 E: 矩形拼接

【问题描述】

已知 3 个矩形的大小依次是 a1 × b1, a2 × b2 和 a3 × b3。用这 3 个矩形能拼出的所有

多边形中，边数最少可以是多少？

例如用 3 × 2 的矩形（用 A 表示）、4 × 1 的矩形（用 B 表示）和 2 × 4 的矩形（用 C

表示）可以拼出如下 4 边形。

例如用 3 × 2 的矩形（用 A 表示）、3 × 1 的矩形（用 B 表示）和 1 × 1 的矩形（用 C

表示）可以拼出如下 6 边形。

【输入格式】

输入包含多组数据。

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

以下 T 行，每行包含 6 个整数 a1, b1, a2, b2, a3, b3，其中 a1, b1 是第一个矩形的边

长，a2, b2 是第二个矩形的边长，a3, b3 是第三个矩形的边长。

【输出格式】

对于每组数据，输出一个整数代表答案。

【样例输入】

2

2 3 4 1 2 4

1 2 3 4 5 6

【样例输出】

4

8

【评测用例规模与约定】

对于 10% 的评测用例，1 ≤ T ≤ 5，1 ≤ a1, b1, a2, b2, a3, b3 ≤ 10，a1 = a2 = a3。

对于 30% 的评测用例，1 ≤ T ≤ 5，1 ≤ a1, b1, a2, b2, a3, b3 ≤ 10。

对于 60% 的评测用例，1 ≤ T ≤ 10，1 ≤ a1, b1, a2, b2, a3, b3 ≤ 20。

对于所有评测用例，1 ≤ T ≤ 1000，1 ≤ a1, b1, a2, b2, a3, b3 ≤ 100。

对照代码1-纯暴力

package com.item.action;
import java.util.Scanner;
public class Demo6 {
  static int[][] s = { { 0, 1, 2 }, { 0, 2, 1 }, { 1, 0, 2 }, { 1, 2, 0 }, { 2, 0, 1 }, { 2, 1, 0 } };
  static int[][] s1 = { { 0, 0, 0 }, { 0, 0, 1 }, { 0, 1, 0 }, { 0, 1, 1 }, { 1, 0, 0 }, { 1, 0, 1 }, { 1, 1, 0 },
      { 1, 1, 1 } };
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    int num = Integer.parseInt(sc.nextLine());
    String[] inPut = new String[num];
    // 输入次数
    for (int i = 0; i < num; i++) {
      inPut[i] = sc.nextLine();
    }
    sc.close();
    // 交换矩形顺序
    for (int i = 0; i < num; i++) {
      String[] l = inPut[i].split(" ");
      int[][] L = StringToInt(l);
      int[][] ans = new int[6][8];
      // 交换矩形长宽
      for (int j = 0; j < 6; j++) {
        int[][] L1 = chageL(L, s[j]);
        for (int k = 0; k < 8; k++) {
          for (int m = 0; m < 3; m++) {
            if (s1[k][m] == 1) {
              L1[m] = changeIt(L1[m]);
            }
          }
          ans[j][k] = getIt(L1);
        }
      }
      System.out.println(getMin(ans));
    }
  }
  // 交换长宽
  private static int[][] chageL(int[][] l, int[] i) {
    int[][] L = new int[3][2];
    for (int j = 0; j < l.length; j++) {
      for (int k = 0; k < l[j].length; k++) {
        L[j][k] = l[i[j]][k];
      }
    }
    return L;
  }
  // 获取最小值
  private static int getMin(int[][] ans) {
    int num = ans[0][0];
    for (int i = 0; i < ans.length; i++) {
      for (int j = 0; j < ans[i].length; j++) {
        if (num > ans[i][j]) {
          num = ans[i][j];
        }
      }
    }
    return num;
  }
  // 交换矩形顺序
  private static int[] changeIt(int[] l) {
    int[] L = new int[l.length];
    L[0] = l[1];
    L[1] = l[0];
    return L;
  }
  private static int[][] StringToInt(String[] l) {
    int[][] ans = new int[3][2];
    for (int i = 0, j = 0; i < 3; i++, j += 2) {
      ans[i][0] = Integer.parseInt(l[j]);
      ans[i][1] = Integer.parseInt(l[j + 1]);
    }
    return ans;
  }
  // 计算改顺序组成的边数量
  public static int getIt(int[][] l) {
    if ((l[0][0] == l[1][0] && l[0][0] == l[2][0]) || (l[0][0] == l[1][0] && l[0][1] + l[1][1] == l[2][0]))
      return 4;
    if ((l[0][0] == l[1][0]) || l[0][0] + l[1][0] == l[2][0])
      return 6;
    return 8;
  }
}

对照代码2

package com.item.action;
import java.util.Scanner;
public class Demo6 {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] b = new int[n];
    for (int i = 0; i < n; i++) {
      int[][] squares = new int[3][2];
      for (int j = 0; j < 3; j++) {
        squares[j][0] = sc.nextInt();
        squares[j][1] = sc.nextInt();
      }
      boolean matchingSides = false;
      for (int j = 0; j < 3; j++) {
        for (int k = 0; k < 3; k++) {
          if (j != k && (squares[j][0] == squares[k][0] || squares[j][0] == squares[k][1]
              || squares[j][1] == squares[k][0] || squares[j][1] == squares[k][1])) {
            matchingSides = true;
            break;
          }
        }
        if (matchingSides) {
          break;
        }
      }
      b[i] = matchingSides ? 4 : 6;
    }
    sc.close();
    for (int i = 0; i < n; i++) {
      System.out.println(b[i]);
    }
  }
}

试题 F: 选数异或

【问题描述】

给定一个长度为 n 的数列 A1, A2, · · · , An 和一个非负整数 x，给定 m 次查询, 每次询

问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x 。

【输入格式】

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

第二行包含 n 个整数 A1, A2, · · · , An 。

接下来 m 行，每行包含两个整数 li ,ri 表示询问区间 [li ,ri ] 。

【输出格式】

对于每个询问, 如果该区间内存在两个数的异或为 x 则输出 yes, 否则输出 no。

【样例输入】

4 4 1

1 2 3 4

1 4

1 2

2 3

3 3

【样例输出】

yes

no

yes

no

【样例说明】

显然整个数列中只有 2, 3 的异或为 1。

【评测用例规模与约定】

对于 20% 的评测用例，1 ≤ n, m ≤ 100；

对于 40% 的评测用例，1 ≤ n, m ≤ 1000；

对于所有评测用例，1 ≤ n, m ≤ 100000 ，0 ≤ x < 2^20 ，1 ≤ li ≤ ri ≤ n ， 0 ≤ Ai < 2^20。

对照代码·我在网上找到的，不太好理解，需要用点心，别问我，我没搞明白，讨厌异或。

package com.item.action;
import java.util.Scanner;
public class Demo6 {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int x = sc.nextInt();
    int a = 0;
    int dep[] = new int[n + 1];// 储存数列某个位置，至少存在一对数异或等于x的最大左下标。
    int map[] = new int[1 << 20];// 储存数列中任意一个元素的位置。大小为2^20
    for (int i = 1; i <= n; i++) {
      a = sc.nextInt();
      dep[i] = Math.max(dep[i - 1], map[a ^ x]);// 数列前一个元素也可能有满足条件的下标，取最大即可。
      map[a] = i;// 写在最后是防止有a^a=x,的可能出现。
      // 如果map[a^x]>a,由于还没有输入过a^x,所以map[a^x]实际上是默认值0
    }
    for (int j = 0; j < m; j++) {
      int l = sc.nextInt();
      int r = sc.nextInt();
      System.out.println(dep[r] >= l ? "yes" : "no");
    }
    sc.close();
  }
}

试题 G: GCD

【问题描述】

给定两个不同的正整数 a, b，求一个正整数 k 使得 gcd(a + k, b + k) 尽可能大，其中

gcd(a, b) 表示 a 和 b 的最大公约数，如果存在多个 k，请输出所有满足条件的 k 中最小的那

个。

【输入格式】

输入一行包含两个正整数 a, b，用一个空格分隔。

【输出格式】

输出一行包含一个正整数 k。

【样例输入】

5 7

【样例输出】

1

【评测用例规模与约定】

对于 20% 的评测用例，a < b ≤ 10^5 ；

对于 40% 的评测用例，a < b ≤ 10^9 ；

对于所有评测用例，1 ≤ a < b ≤ 10^18 。

对照代码1

package com.item.action;
import java.util.Scanner;
public class Demo6 {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int x1 = sc.nextInt();
    int x2 = sc.nextInt();
    sc.close();
    int Min = x1 > x2 ? gcd(x1, x2) : gcd(x2, x1);
    int k = 1, temp = 0, Ma = 0, Mi = 0;
    if (x1 > x2) {
      temp = gcd(x1 + k, x2 + k);
      Ma = x1 + k;
      Mi = x2 + k;
    } else {
      temp = gcd(x2 + k, x1 + k);
      Ma = x2 + k;
      Mi = x1 + k;
    }
    while (temp <= Min) {
      k++;
      temp = gcd(Ma + k, Mi + k);
    }
    System.out.println(k);
  }
  public static int gcd(int a, int b) {
    if (a == 0 || b == 0) {
      return 0;
    }
    return a % b == 0 ? b : gcd(b, a % b);
  }
}

参照代码2·很神奇的想法

package com.item.action;
import java.util.Scanner;
public class Demo6 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long a = sc.nextLong();
    long b = sc.nextLong();
    sc.close();
    long max = Math.abs(a - b);
    System.out.print(max - (a % max));
  }
}

试题 H: 青蛙过河

【问题描述】

小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。

河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每

块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 1，当石头的高

度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 0 是允许的）。

小青蛙一共需要去学校上 x 天课，所以它需要往返 2x 次。当小青蛙具有一个跳跃能力

y 时，它能跳不超过 y 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。

【输入格式】

输入的第一行包含两个整数 n, x，分别表示河的宽度和小青蛙需要去学校的天数。请注

意 2x 才是实际过河的次数。

第二行包含 n − 1 个非负整数 H1, H2, · · · , Hn−1，其中 Hi > 0 表示在河中与小青蛙的

家相距 i 的地方有一块高度为 Hi 的石头，Hi = 0 表示这个位置没有石头。

【输出格式】

输出一行，包含一个整数，表示小青蛙需要的最低跳跃能力。

【样例输入】

5 1

1 0 1 0

【样例输出】

4

【样例解释】

由于只有两块高度为 1 的石头，所以往返只能各用一块。第 1 块石头和对岸的距离为 4，如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少需要 4 的跳跃能力。

【评测用例规模与约定】

对于 30% 的评测用例，n ≤ 100；

对于 60% 的评测用例，n ≤ 1000；

对于所有评测用例，1 ≤ n ≤ 105 , 1 ≤ x ≤ 109 , 1 ≤ Hi ≤ 104。

对照代码

package com.item.action;
import java.util.Scanner;
public class Demo6 {
  private static int a, b;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    b = sc.nextInt();
    a = sc.nextInt();
    int[] z = new int[b + 10];
    int[] pre = new int[b + 10];
    for (int i = 1; i <= b - 1; i++) {
      z[i] = sc.nextInt();
      pre[i] = pre[i - 1] + z[i];
    }
    sc.close();
    int l = 1, r = b, ans = -1;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (judge(mid, pre)) {
        ans = mid;
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    System.out.println(ans);
  }
  public static boolean judge(int y, int[] pre) {
    for (int l = 1; l <= b - y; l++) {
      int r = l + y - 1;
      if (pre[r] - pre[l - 1] < 2 * a) {
        return false;
      }
    }
    return true;
  }
}

对照代码2·又是一个神奇的想法

package com.item.action;
import java.util.Scanner;
public class Demo6 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long x = sc.nextLong();
    long[] arr = new long[n + 1];
    for (int i = 1; i < n; i++) {
      arr[i] = sc.nextLong() + arr[i - 1];
    }
    sc.close();
    arr[n] = arr[n - 1] + 999999999999L;
    int l = 0;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
      if (arr[i] - arr[l] >= 2L * x) {
        sum = Math.max(sum, i - l);
        l += 1;
      }
    }
    System.out.println(sum);
  }
}

试题 I: 因数平方和

【问题描述】

记 f(x) 为 x 的所有因数的平方的和。例如：f(12) = 12 + 22 + 32 + 42 + 62 + 122。

定义 g(n) = ∑n i=1 f(i) 。给定 n, 求 g(n) 除以 109 + 7 的余数。

【输入格式】

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

【输出格式】

输出一个整数表示答案 g(n) 除以 109 + 7 的余数。

【样例输入】

100000

【样例输出】

394827960(示例有误，实际答案：680584257)

【评测用例规模与约定】

对于 20% 的评测用例，n ≤ 105。

对于 30% 的评测用例，n ≤ 107。

对于所有评测用例，1 ≤ n ≤ 109。

对照代码

package com.item.action;
import java.util.Scanner;
public class Demo6 {
  public static void main(String[] args) {
    final long N = 1000000007;
    final long inv6 = 166666668;
    Scanner sc = new Scanner(System.in);
    long res = 0, temp = 0, sum = 0;
    long n, l, r, k;
    n = sc.nextInt();
    sc.close();
    for (long i = 1; i <= n; i = r + 1) {
      l = i;
      k = n / i;
      r = n / (n / l);
      temp = sum;
      sum = r * (r + (long) 1) % N * ((long) 2 * r + 1) % N * inv6 % N;
      res = (res + k * (sum - temp) + N) % N;
    }
    System.out.println(res);
  }
}

试题 J: 最长不下降子序列

【问题描述】

给定一个长度为 N 的整数序列：A1, A2, · · · , AN。现在你有一次机会，将其中连续的

K 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数列的最长不下降子序列

最长，请输出这个最长的长度。

最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。

【输入格式】

输入第一行包含两个整数 N 和 K。

第二行包含 N 个整数 A1, A2, · · · , AN。

【输出格式】

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

【样例输入】

5 1

1 4 2 8 5

【样例输出】

4

【评测用例规模与约定】

对于 20% 的评测用例，1 ≤ K ≤ N ≤ 100；

对于 30% 的评测用例，1 ≤ K ≤ N ≤ 1000；

对于 50% 的评测用例，1 ≤ K ≤ N ≤ 10000；

对于所有评测用例，1 ≤ K ≤ N ≤ 10^5，1 ≤ Ai ≤ 10^6

对照代码·参考别人的·不抬复杂。

package com.item.action;
import java.util.Scanner;
public class Demo6 {
  static int n_max = 1000000;
  static int[] arr = new int[n_max];
  static boolean[] c = new boolean[n_max];
  static long n, k;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    k = sc.nextInt();
    c[0] = true;
    for (int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
    }
    sc.close();
    for (int i = 1; i < n; i++) {
      if (arr[i] < arr[i - 1]) {
        c[i] = false;
      } else {
        c[i] = true;
      }
    }
    int max = 0;
    for (int i = 0; i < n; i++) {
      if (k > 0) {
        if (c[i]) {
          max++;
        } else {
          k--;
          max++;
        }
      } else if (k == 0) {
        if (c[i]) {
          max++;
        } else {
          System.out.println(max);
          break;
        }
      }
    }
  }
}