题解 | #手串#

思路1：最直观的想法是，不用存储每个串珠对应的颜色数组，直接存储每种颜色出现的串珠位置，使用colors存储每种颜色出现的串珠位置！遍历每种颜色并判断连续m个是否出现重复：首先判断首尾出现的位置差，由于是按照顺序填充数组，故colors[i]有序，那么可以使用(start+n-end)<m进行判断；接着判断每个相邻位置差，一旦发现连续m个出现重复，就直接判断下一种颜色。

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n, m, c;
    int ans = 0;
    cin >> n >> m >> c;
    //存储颜色出现的串珠位置
    vector<int> colors[c + 1];
    int num, color;
    for (int i = 0; i < n; i++) {
        cin >> num;
        for (int j = 0; j < num; j++) {
            cin >> color;
            colors[color].push_back(i);
        }
    }
    // for(int i=1;i<=c;i++)
    // {
    //   for(int j=0;j<colors[i].size();j++)
    //   {
    //     cout<<colors[i][j]<<" ";
    //   }
    //   cout<<endl;
    // }
    //判断连续m个是否出现重复
    //只需对每个颜色判断同颜色相邻的位置差是否小于m
    for (int i = 1; i <= c; i++) {
        //先判断首尾出现的位置差
        if (colors[i][0] + n - colors[i][colors[i].size() - 1] < m) {
            ans++;
            continue;
        }
        //判断每个相邻位置差
        for (int j = 0; j < colors[i].size() - 1; j++) {
            if (colors[i][j + 1] - colors[i][j] < m) {
                ans++;
                break;
            }
        }
    }
    cout << ans;
    return 0;
}

总结：注意，如果直接vector<vector<int>> colors(n)，那么会生成n乘以n的二维数组喔！建议使用vector<int> colors[n]，那么即是n个vector<int>。