时间限制：1秒
空间限制：65536K
题目描述
作为一个手串艺人，有金主向你订购了一条包含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
输入
5 2 2
3 1 2 3
0
2 2 3
1 2
1 3
输出
2
说明
第一种颜色出现在第1颗串珠，与规则无冲突。
第二种颜色分别出现在第1，3，4颗串珠，第3与第4颗串珠相邻，所以不合要求。
第三种颜色分别出现在第1，3，5颗串珠，第5颗串珠的下一个是第1颗，所以不合要求。
总计有2中颜色的分布是有问题的。
这里第2颗串珠是透明的。
解题思路：由于数据并非很大，10000*1000可以在接受范围内，所有对于每没一个串珠都往后遍历m个判断是否有相同的颜色，并把相同颜色做标记之后遇到相同颜色直接continue，还有个优化情况就是当不符合的颜色达到c的时候就可以直接停止了。注意的问题是遍历到最后的时候要往返到第一个重新遍历直到数量达到m个，还有其它一些m>=n之类的边界条件。
这里不用两边都访问，因为全部都访问一边就可以保证所有的情况都在内了。
#include <iostream>#include <cstring>#include <vector>using namespace std;bool color[55];vector<int> V[10005];int main(){int n, m, c, num, x;while(cin >> n >> m >> c){memset(color, 0, sizeof(color));for(int i = 0; i < n; ++i)V[i].clear();for(int i = 0; i < n; ++i){cin >> num;while(num--){cin >> x;V[i].push_back(x);}}if(m==1){cout << 0 << endl;continue;}if(m>=n){cout << c << endl;continue;}int ans = 0;for(int i = 0; i < n; ++i){if(ans==c)break;for(int j = 0; j < V[i].size(); ++j){if(color[V[i][j]])continue;int tmp = 1;int k = i+1;while(tmp<m){if(k==n)k = 0;for(int l = 0; l < V[k].size(); ++l)if(V[k][l]==V[i][j] && !color[V[i][j]]){color[V[i][j]] = true;ans++;}k++;tmp++;}}}cout << ans << endl;}return 0;}/*5 2 23 1 2 302 2 31 21 3*/
