题解 | 手串

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(int n, int m, int c, vector<vector<int>>& beads) {
        // 记录每种颜色的出现位置
        vector<vector<int>> colorPos(c + 1);
        for (int i = 0; i < n; i++) {
            for (int color : beads[i]) {
                colorPos[color].push_back(i);
            }
        }
        
        int invalid = 0;
        // 检查每种颜色
        for (int color = 1; color <= c; color++) {
            if (colorPos[color].empty()) continue;
            
            // 检查是否在连续m个串珠中出现超过一次
            for (int i = 0; i < colorPos[color].size(); i++) {
                for (int j = i + 1; j < colorPos[color].size(); j++) {
                    int dist = colorPos[color][j] - colorPos[color][i];
                    if (dist < m || (n - dist) < m) {
                        invalid++;
                        i = colorPos[color].size();  // 跳出外层循环
                        break;
                    }
                }
            }
        }
        
        return invalid;
    }
};

int main() {
    int n, m, c;
    cin >> n >> m >> c;
    
    vector<vector<int>> beads(n);
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        beads[i].resize(num);
        for (int j = 0; j < num; j++) {
            cin >> beads[i][j];
        }
    }
    
    Solution solution;
    cout << solution.solve(n, m, c, beads) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public int solve(int n, int m, int c, List<List<Integer>> beads) {
            // 记录每种颜色的出现位置
            List<List<Integer>> colorPos = new ArrayList<>(c + 1);
            for (int i = 0; i <= c; i++) {
                colorPos.add(new ArrayList<>());
            }
            
            for (int i = 0; i < n; i++) {
                for (int color : beads.get(i)) {
                    colorPos.get(color).add(i);
                }
            }
            
            int invalid = 0;
            // 检查每种颜色
            for (int color = 1; color <= c; color++) {
                if (colorPos.get(color).isEmpty()) continue;
                
                List<Integer> positions = colorPos.get(color);
                // 检查是否在连续m个串珠中出现超过一次
                outer:
                for (int i = 0; i < positions.size(); i++) {
                    for (int j = i + 1; j < positions.size(); j++) {
                        int dist = positions.get(j) - positions.get(i);
                        if (dist < m || (n - dist) < m) {
                            invalid++;
                            break outer;
                        }
                    }
                }
            }
            
            return invalid;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int c = sc.nextInt();
        
        List<List<Integer>> beads = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            List<Integer> colors = new ArrayList<>();
            for (int j = 0; j < num; j++) {
                colors.add(sc.nextInt());
            }
            beads.add(colors);
        }
        
        Solution solution = new Solution();
        System.out.println(solution.solve(n, m, c, beads));
        
        sc.close();
    }
}

class Solution:
    def solve(self, n, m, c, beads):
        # 记录每种颜色的出现位置
        color_pos = [[] for _ in range(c + 1)]
        for i in range(n):
            for color in beads[i]:
                color_pos[color].append(i)
        
        invalid = 0
        # 检查每种颜色
        for color in range(1, c + 1):
            if not color_pos[color]:
                continue
                
            # 检查是否在连续m个串珠中出现超过一次
            for i in range(len(color_pos[color])):
                for j in range(i + 1, len(color_pos[color])):
                    dist = color_pos[color][j] - color_pos[color][i]
                    if dist < m or (n - dist) < m:
                        invalid += 1
                        i = len(color_pos[color])  # 跳出外层循环
                        break
                if i == len(color_pos[color]):
                    break
        
        return invalid

# 读取输入
n, m, c = map(int, input().split())
beads = []
for _ in range(n):
    nums = list(map(int, input().split()))
    beads.append(nums[1:] if nums[0] > 0 else [])

solution = Solution()
print(solution.solve(n, m, c, beads))