题目描述

作为一个手串艺人，有金主向你订购了一条包含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，3，4颗串珠，第3颗与第4颗串珠相邻，所以不合要求。
第三种颜色分别出现在第1，3，5颗串珠，第5颗串珠的下一个是第1颗，所以不合要求。
总计有2种颜色的分布是有问题的。 
这里第2颗串珠是透明的。

解题思路

1. 首先输入了珠子个数n 要求连续珠串不能重复的个数是m，串珠颜色有c种
2. 这道题也是需要设计一个良好的数据结构才能求解
3. 我们可以把这个串珠和颜色设计为一个二维矩阵，行向量是每一个串珠，列向量是串珠颜色
，列向量总数为c，如果在i行j列上的这个数对应的串珠的位置没有这个颜色那么置0.简言之，
就是将每个串珠的颜色都扩充为一样的c种，原本拥有的就为1，没有的就为0，那么就可以设计
为一个0-1表示的二维矩阵，如下图中所示
4. 其次，再研究研究输出结果，是要求不满足m个串珠连续的颜色总和，那么这个问题就转变为了我对每种颜色检查是否符合结果
5. 针对每一种颜色检查的是否有连续个m个串珠针对同一种颜色同时出现了两个1（针对矩阵而言），因为需要针对同一种颜色从第一个串珠（第一行）检查到最后一个串珠(最后一行)，那么整体的遍历结束就会结束于n+m（因为到达最后一行相邻的串珠是第一行开始到n-1）
6. 依次检查每一列是否符合要求即可得到最后的总数

示例图（转载请附链接）

Java源代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int c = sc.nextInt();
        byte[][] matrix = new byte[n][c];
        for (int i=0; i<n; i++) {
            int total = sc.nextInt();
            for (int j=0; j<total; j++) {
                int k = sc.nextInt();
                matrix[i][k-1] = 1;
            }
        }
        byte[] result = new byte[c];
        for (int i=0; i<c; i++) {
            int lastIndex = -1;
            int end = n+m-1;
            //System.out.println("end is:" + end);
            for (int j=0; j<end; j++) {
                int row = j%n;
                if(matrix[row][i]==1) {
                    if (lastIndex==-1) lastIndex = j;
                    else {
                        if (j-lastIndex < m) result[i] = 1;
                        else {
                            lastIndex = j;
                        }
                    }
                }
            }
        }
        int sum = 0;
        for (int i=0; i<c; i++) {
            if (result[i] ==1) sum++;
        }
        System.out.println(sum);
    }
}