首页 > 试题广场 >

手串

[编程题]手串

热度指数：2285 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

作为一个手串艺人，有金主向你订购了一条包含n个杂色串珠的手串——每个串珠要么无色，要么涂了若干种颜色。为了使手串的色彩看起来不那么单调，金主要求，手串上的任意一种颜色（不包含无色），在任意连续的m个串珠里至多出现一次（注意这里手串是一个环形）。手串上的颜色一共有c种。现在按顺时针序告诉你n个串珠的手串上，每个串珠用所包含的颜色分别有哪些。请你判断该手串上有多少种颜色不符合要求。即询问有多少种颜色在任意连续m个串珠中出现了至少两次。

输入描述:

第一行输入n，m，c三个数，用空格隔开。(1 <= n <= 10000, 1 <= m <= 1000, 1 <= c <= 50) 接下来n行每行的第一个数num_i(0 <= num_i <= c)表示第i颗珠子有多少种颜色。接下来依次读入num_i个数字，每个数字x表示第i颗柱子上包含第x种颜色(1 <= x <= c)

输出描述:

一个非负整数，表示该手链上有多少种颜色不符需求。

示例1

输入

输出

说明

第一种颜色出现在第1颗串珠，与规则无冲突。
第二种颜色分别出现在第 1，3，4颗串珠，第3颗与第4颗串珠相邻，所以不合要求。
第三种颜色分别出现在第1，3，5颗串珠，第5颗串珠的下一个是第1颗，所以不合要求。
总计有2种颜色的分布是有问题的。 
这里第2颗串珠是透明的。

算法知识视频讲解

Python

L-TOK

通过所有测试用例，还有不足之处，望指教~

import collections
# 获取n，m，c三个数
arr = list(map(int, input().split()))
# 定义一个字典存储同一颜色出现的串珠序号
d = collections.defaultdict(set)
# 根据n依次获取第i颗珠子的颜色并存到d中
for i in range(arr[0]):
    m = list(map(int, input().split()))
    # 条件过滤了无色的珠子
    if len(m) > 1:
        for j in range(len(m)-1):
            # 从第二项开始取颜色，m[j+1]是颜色的编号，i+1表示珠子序号（从1开始）
            d[m[j+1]].add(i+1)
res = 0
# 遍历字典中的键名取相应的键值
for k in d:
    # 对键值排序，从小到大
    tmp = sorted(list(d[k]))
    count = 0
    # 条件过滤了k号颜色只有一个键值的情况
    if len(tmp) > 1:
        for n in range(len(tmp)):
            # f在(n+1, len(tmp))是确保不重复遍历前面的值，进行重复比较
            for f in range(n+1, len(tmp)):
                # 判断是否存在头尾有同一颜色
                if tmp[len(tmp)-1] == arr[0] and tmp[n] == 1 and arr[1] > 1:
                    count += 1
                    break
                # 判断连续区间内是否有同一颜色
                if tmp[f] - tmp[n] < arr[1]:
                    count += 1
                    break
                else:
                    # 因为键值已排序，所以当遍历中第f项不满足前两个条件时，后面的值也不会符合，就跳出循环
                    break
        # 题目是有多少种颜色在任意连续m个串珠中出现了至少两次，所以这里只需判断一个颜色内是否有重复的就行，而不是重复多少次
        if count != 0:
            res += 1

print(res)

编辑于 2020-03-14 19:14:38 回复(0)