#P3252. 数字游戏(200分)
-
1000ms
Tried: 89
Accepted: 21
Difficulty: 3
所属公司 :
华为od
数字游戏(200分)
题面描述
小塔玩一个游戏。
系统发 1+n 张牌,每张牌上有一个整数。
- 第一张牌给小塔,数字为 m。
- 后 n 张牌按照发牌顺序排成连续的一行,数字分别为 a1,a2,…,an。
小塔需要判断,在后 n 张牌中,是否存在连续的若干张牌,其和可以被小塔手中牌上的数字 m 整除。
解题思路
要判断在后 n 张牌中是否存在一个连续的子序列,其和可以被小塔手中的数字 m 整除。考虑到:
-
前缀和与模运算:
- 计算前缀和数组
prefix_sum,其中prefix_sum[i]表示前 i 张牌的总和。 - 对每个前缀和取模 m,即
prefix_sum[i] % m。 - 如果存在两个前缀和
prefix_sum[i]和prefix_sum[j]满足prefix_sum[i] % m == prefix_sum[j] % m,且 i<j,则子序列从 i+1 到 j 的和可以被 m 整除。
- 计算前缀和数组
-
使用哈希表记录模值:
- 使用一个哈希表(或数组)来记录每个模值首次出现的位置。
- 遍历前缀和的模值,如果当前模值已经存在于哈希表中,则说明存在满足条件的子序列,输出
1。 - 如果遍历完所有前缀和后都未找到满足条件的子序列,输出
0。
-
边界情况处理:
- 如果某个前缀和本身就可以被 m 整除,即
prefix_sum[i] % m == 0,则从第 1 张牌到第 i 张牌的和可以被 m 整除。
- 如果某个前缀和本身就可以被 m 整除,即
-
时间与空间复杂度:
- 每组测试用例的时间复杂度为 O(n),适合 n≤1000 和测试用例数不超过 1000 的情况。
- 使用数组记录模值时,空间复杂度为 O(m),但由于 m 可能较大(400000),可考虑使用哈希表以节省空间。
cpp
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
while(cin >> n >> m){
vector<long long> cards(n);
for(int i=0; i<n; ++i){
cin >> cards[i];
}
// 使用哈希表记录前缀和的模值是否出现过
unordered_set<long long> seen;
long long prefix = 0;
bool found = false;
seen.insert(0); // 处理子序列从第一张开始的情况
for(int i=0; i<n; ++i){
prefix += cards[i];
long long mod = prefix % m;
// 如果当前模值已经出现过,说明存在子序列
if(seen.find(mod) != seen.end()){
found = true;
break;
}
seen.insert(mod);
}
if(found){
cout << "1\n";
}
else{
cout << "0\n";
}
}
return 0;
}
python
def main():
import sys
input = sys.stdin.read
data = input().strip().splitlines()
results = []
index = 0
while index < len(data):
# 读取 n 和 m
n, m = map(int, data[index].split())
index += 1
# 读取后续 n 张牌的数字
cards = list(map(int, data[index].split()))
index += 1
# 使用集合记录前缀和的模值
seen = set()
prefix = 0
found = False
seen.add(0) # 处理子序列从第一张开始的情况
for i in range(n):
prefix += cards[i]
mod = prefix % m
# 如果当前模值已经出现过,说明存在子序列
if mod in seen:
found = True
break
seen.add(mod)
if found:
results.append("1")
else:
results.append("0")
# 输出所有结果
print("\n".join(results))
if __name__ == "__main__":
main()
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()) {
// 读取第一行,提取 n 和 m 的值
int[] tmp = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// 读取第二行,提取后续 n 张牌的数字
int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// 调用 isExist 方法判断是否存在满足条件的子序列,输出结果
System.out.println(isExist(nums, tmp[1]));
}
}
// 判断在 nums 数组中是否存在连续子序列的和可以被 m 整除
public static int isExist(int[] nums, int m) {
HashSet<Integer> remain = new HashSet<>(); // 用于存储模值
remain.add(0); // 初始化时添加模值 0,以处理子序列从开头开始的情况
int sum = 0; // 前缀和
// 遍历每张牌
for (int num : nums) {
sum += num; // 更新前缀和
// 检查当前前缀和的模值是否已存在
if (remain.contains(sum % m)) {
return 1; // 如果存在,返回 1
} else {
// 否则,将当前模值添加到集合中
remain.add(sum % m);
}
}
return 0; // 如果遍历结束后没有找到,返回 0
}
}
题目内容
小红玩一个游戏。
系统发 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
说明
两组输入。第一组小红牌的数字为 7 ,再发了 6 张牌。第 1、2 两张牌数字和为 14 ,可以整除 7,输出 1,第二组小明牌的教字为 11,再发了 10 张牌,这 10 张牌数字和为 10 ,无法整除 11 ,输出 0 。