(B卷,200分)- 数字游戏（Java & JS & Python）

题目描述

小明玩一个游戏。

系统发1+n张牌，每张牌上有一个整数。

第一张给小明，后n张按照发牌顺序排成连续的一行。

需要小明判断，后n张牌中，是否存在连续的若干张牌，其和可以整除小明手中牌上的数字。

输入描述

输入数据有多组，每组输入数据有两行，输入到文件结尾结束。

第一行有两个整数n和m，空格隔开。m代表发给小明牌上的数字。

第二行有n个数，代表后续发的n张牌上的数字，以空格隔开。

输出描述

对每组输入，如果存在满足条件的连续若干张牌，则输出1;否则，输出0

备注

• 1 ≤ n ≤ 1000
• 1 ≤ 牌上的整数 ≤ 400000
• 输入的组数，不多于1000
• 用例确保输入都正确，不需要考虑非法情况。

用例

题目解析

本题考察前缀和知识，以及数学问题。

本题要求连续若干张牌的和，其实就是求区间的元素之和。

而求解任意区间和的最佳算法就是：前缀和之差，这个知识点可以看下

利用前缀和，我们可以在O(1)的时间求解出[L,R]区间和 = preSum[R] – preSum[L-1]。

那么接下来，我们是否需要双重for遍历出所有区间，然后逐一验证对应区间和是否可以整除k呢？

本题中每组用例最多n = 1000张牌，因此双重for遍历对应牌的所有连续区间的时间复杂度O(n^2)。

而本题有最多有1000组用例，因此相当于O(n^3)的时间复杂度，这是非常容易超时的。

本题优化是基于一个数学性质：

如果两个数a,b，他们的差a – b可以被k整除，则必然 a % k == b % k。

反之，如果a % k == b % k，那么 a – b 必然可以被k整除。

大家可以自行验证下这个数学性质。

验证好后，我们只需要将preSum[R]带入a，preSum[L-1]带入b 再来看看：

如果preSum[R] % k == preSum[L-1] % k，那么必然 preSum[R] – preSum[L-1] 可以被k整除。

利用这个数学性质，我们就不必双重for遍历所有区间了，只需要检查preSum数组中是否存在两个元素 % k 的结果相同，即可说明存在区间之和可以整除k。

2023.08.19 根据考友反馈，本题python代码输入获取逻辑存在问题，

本题的输入是没有截止条件的，因此我这边默认将输入空行作为截止条件。

但是考到这题的考友反馈，这题按这种逻辑处理输入是不行的，需要死循环获取输入，每获取到一组输入，就要立即输出对应解。

核心代码逻辑没问题，可以100%。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  while (true) {
    try {
      const [n, m] = (await readline()).split(" ").map(Number);
      const nums = (await readline()).split(" ").map(Number);
      console.log(isExsit(nums, m));
    } catch (error) {
      break;
    }
  }
})();

function isExsit(nums, m) {
  const remain = new Set();
  remain.add(0);

  let sum = 0;
  for (let num of nums) {
    sum += num;
    if (remain.has(sum % m)) {
      return 1;
    } else {
      remain.add(sum % m);
    }
  }

  return 0;
}

Java算法源码

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

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

    while (sc.hasNextLine()) {
      try {
        int[] tmp = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        System.out.println(isExist(nums, tmp[1]));
      } catch (Exception e) {
        break;
      }
    }
  }

  public static int isExist(int[] nums, int m) {
    HashSet<Integer> remain = new HashSet<>();
    remain.add(0);

    int sum = 0;
    for (int num : nums) {
      sum += num;
      if (remain.contains(sum % m)) {
        return 1;
      } else {
        remain.add(sum % m);
      }
    }

    return 0;
  }
}

Python算法源码

def isExist(nums, m):
    remain = set()
    remain.add(0)

    total = 0
    for num in nums:
        total += num
        if total % m in remain:
            return 1
        else:
            remain.add(total % m)

    return 0


# 输入获取
while True:
    try:
        n, m = map(int, input().split())
        nums = list(map(int, input().split()))
        print(isExist(nums, m))
    except ValueError:
        break