题解 | #手串#

题目要求我们判断手串中不符合条件的颜色。显然这道题目有两个元素，一个是珠子的位置，一个是颜色所在珠子的位置。
思路：按颜色索引，用二维vector存储每种颜色所在位置，再依次判断每种颜色的位置是否合法。难点在于，珠子是成环状的，那么如何判断两个位置在环的条件下是否符合条件呢？事实上，画图分析后很容易发现，珠子i和j的位置实际上有两个，一个是abs(i-j)，一个是n-abs(i-j)。这样就很明显了，当两个位置中有任意一个小于等于m时，即为非法。

#include <iostream>
#include <vector>

using namespace std;

int n, m, c, num_i, kind, sum;

bool check(int n, int m, vector<int>& posi){
    if(posi.size() == 1){
        return true;
    }
    for(int i = 0; i < posi.size(); i++){
        for(int j = i + 1; j < posi.size(); j++){
            int dis = abs(posi[i]-posi[j]);
          //判断位置合法与否
            if( dis <= m-1 || n - dis <= m-1){
                //cout<<posi[i]<<" "<<posi[j]<<endl;
                return false;
            }
        }
    }
    return true;
    
}
int main()
{
    cin >> n >> m >> c;
    vector<vector<int>> pos(c + 1);

    for (int i = 1; i <= n; i++) {
        cin>>num_i;
        while(num_i--){
            cin>>kind;
            pos[kind].push_back(i);
        }
    }

    for(int i = 1; i <= c; i++ ){
      //逐个颜色进行check
        if(!check(n,m,pos[i])){
            sum++;
        }
    }
    cout<<sum<<endl;
    return 0;
}