怎样开发游戏_苏州工业园区官网_百度推广怎么运营_哪家网站优化公司好

题目描述

小明玩一个游戏。

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

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

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

输入描述

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

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

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

输出描述

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

数据限制

• $1\le n\le 1000$

• $1\le 牌上的整数\le 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

说明

两组输入。第一组小明牌的数字为7，再发了6张牌。第1、2两张牌数字和为14，可以整除7，输出1，第二组小明牌的数字为11，再发了10张牌，这10张牌数字和为10，无法整除11，输出0。

题解

暴力求解， 使用前缀和加快计算速度

源码 Java

public class XnMk {static Input input;static {input = new Input("6 7\n" +"2 12 6 3 5 5\n" +"10 11\n" +"1 1 1 1 1 1 1 1 1 1");}public static void main(String[] args) {while (input.hasNextLine()) {String[] ss = input.nextLine().split(" ");String[] cards = input.nextLine().split(" ");int n = Integer.parseInt(ss[0]);int target = Integer.parseInt(ss[1]);int sum = 0;int[] intCards = new int[n+1];for (int i = 1; i <= n; i++) {sum += Integer.parseInt(cards[i-1]);intCards[i] = sum;}boolean found = false;outer:for (int i = 1; i <= n; i++) {for (int j = i+1; j <= n; j++) {if ((intCards[j] - intCards[i] ) % target == 0) {System.out.println(1);found = true;break outer;}}}if (!found) {System.out.println(0);}}}
}