数字游戏 - 华为OD统一考试

OD统一考试（B卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

小明玩一个游戏。

系统发1+ n 张牌，每张牌上有一个整数。第一张给小明，后 n 张按照发牌顺序排成连续的一行。

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

输入描述

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

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

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

输出描述

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

备注：

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

示例1

输入：
6 7
2 12 6 3 5 5
10 11
1 1 1 1 1 1 1 1 1 1


输出：
1
0

题解

主要思路是通过累加数组 psum 计算出前缀和。然后使用两层循环遍历所有可能的连续子数组，判断其和是否可以整除 m。

Java

java">import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

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

            int[] psum = new int[n + 1];
            for (int i = 0; i < n; i++) {
                int t = scanner.nextInt();
                psum[i + 1] = psum[i] + t;
            }

            boolean rs = false;
            for (int r = n; r > 0 && !rs; r--) {
                for (int l = 0; l < r; l++) {
                    if ((psum[r] - psum[l]) % m == 0) {
                        rs = true;
                        break;
                    }
                }
            }

            System.out.println(rs ? 1 : 0);
        }
    }
}

Python

python">while True:
    try:
        n, m = map(int, input().split())
        arr = list(map(int, input().split()))

        psum = [0] * (n + 1)
        for i in range(n):
            psum[i + 1] = psum[i] + arr[i]

        rs = False
        for r in range(n, 0, -1):
            for l in range(r):
                if (psum[r] - psum[l]) % m == 0:
                    rs = True
                    break

        print(1 if rs else 0)

    except EOFError:
        break

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n,m;
    while(cin >> n) {
        cin >> m;
        vector<int> psum(n+1, 0);
        for(int i=0, t = 0; i < n; i++) {
            cin >> t;
            psum[i+1] = psum[i] + t;
        }

        bool rs = false;
        for(int r=n; r > 0 && !rs; r--) {
            for(int l=0; l < r; l++) {
                if((psum[r] - psum[l]) % m == 0) {
                    rs = true;
                    break;
                }
            }
        }

        cout << (rs ? 1 : 0) << endl;
    }

    return 0;
}