手串

	#include <stdio.h>



	#include <vector>



	#include <iostream>



	using namespace std;



	



	//把结果记录为以颜色为行，珠子编号为列的矩阵



	//对每一行进行遍历，记录上一个出现的位置，每次记录差值，小于m则记录并剪枝



	



	int main(){



	    intn,n2,m,c;



	    cin>>n>>m>>c;



	    n2 = n;



	    vector<vector<bool>> v(c+1,vector<bool>(n+1,false));



	    intid=1;



	    while(n--!=0) {



	        intk,color;



	        cin>>k;



	        while(k--!=0) {



	            cin>>color;



	            v[color][id] = true;



	        }



	        id++;



	    }



	    intres = 0;



	    for(inti=1; i<=c; i++){



	        intlast = -1,start = -1,flag = 0;



	        for(intj=1; j<=n2; j++) {



	            if(!v[i][j])    continue;



	            if(last == -1){



	                last = j;



	                start = j;



	                continue;



	            }



	            if(j-last < m){



	                res ++;



	                flag = 1;



	                break;



	            }



	            last = j;



	        }



	        if(flag==0&&n2-last+start<m)  res++;



	    }



	    cout<<res<<'\n';



	    return0;



	}

#先统计颜色出现在各个珠子上的情况，然后判断这种颜色是不是符合要求
n,m,c=input().split()
n=int(n)
m=int(m)
c=int(c)
col_dic=dict()
output=0
def judgecolor(list_1):
        list_1.append(list_1[0]+n)   #只需要加上颜色第一次出现的时候的索引
        for j in range(len(list_1)-1):
            if list_1[j+1]-list_1[j]<m:
                return 1
        else:
            return 0
for i in range(c+1):
    col_dic[i]=[]
for j in range(n):
    array=list(map(int,input().split()))
    del array[0]
    for each in array:
        col_dic[each].append(j+1)
for i in range(1,c+1):
    if judgecolor(col_dic[i]):
        output+=1
print(output)

test = list(map(int,input().split()))
aaa = []
n = test[0]
m = test[1]
c = test[2]
count = 0
for _ in range(n):
    a = list(map(int,input().split()))
    aaa.append(a)
for s in range(1,c+1): # 遍历每种颜色
    check = 0 #标记当前颜色是否有错误
    para = [] #记录当前颜色出现的珠子的位置
    for i in range(n): # 遍历每颗珠子
        num_i = aaa[i][0] # 当前珠子的颜色总数
        for j in range(1,num_i+1): # 遍历当前珠子的每一种颜色
            if s == aaa[i][j]: # 检查当前珠子是否出现当前颜色，出现则记录位置
                para.append(i+1) 
    for q in range(len(para)-1):# 遍历当前颜色记录的位置
        if para[q+1] - para[q] < m : # 是否小于规定距离
            check += 1  # 错误颜色计数
    if para[0] == 1 and para[-1] == n: # 检查首尾颜色是否相同（相近颜色相同一定不满足距离）
        check += 1
    if check > 0: # 出现错误的颜色计数
        count += 1
print(count)

//将手串看着一个链环，从头结点向尾节点依次统计m-连续的链表节点的颜色频数，在每次统计下一个m-连续链表时，去除前一个头结点频数信息
//同时加入为下一个尾节点频数信息，最后统计这n个m-连续链表颜色频数，频数>=2的颜色即符合要求；
//提交时间：2019-03-14 语言：C++ 运行时间： 14 ms 占用内存：3228K 状态：答案正确 

	#include <iostream>



	#include <vector>



	using namespace std;



	struct ListNode



	{



	    int colornum;



	    vector<int> color;



	    ListNode *next;



	    ListNode(int n, vector<int> &c, ListNode *nex) : colornum(n), color(c), next(nex){}



	};



	class Solution



	{



	public:



	    void color_cnt(vector<int> &cnt, ListNode *ball)



	    {



	        for(int i = 0; i < ball->color.size(); i++) cnt[ball->color[i]-1]++;



	    }



	    void color_cnt_set(vector<int> &cnt, ListNode *ball)



	    {



	        for(int i = 0; i < ball->color.size(); i++) cnt[ball->color[i]-1]--;



	    }



	    void unsubjectnum(int &num, vector<vector<int>> &all_cnt, int c)



	    {



	        int i, j, flag;



	        for(i = 0; i < c; i++)



	        {



	            flag = 0;



	            for(j = 0; j < all_cnt.size(); j++)



	            {



	                if(all_cnt[j][i] >= 2) {



	                    flag = 1;



	                    break;



	                }



	            }



	            if(flag == 1) num++;



	        }



	    }



	    int func(ListNode *head, int m, int c)



	    {



	        vector<int> cnt(c, 0);



	        vector<vector<int>> all_cnt;



	        ListNode *p, *q, *r;



	        int i, num = 0;



	        for(i = 1, q = head; i <= m; i++, q = q->next) color_cnt(cnt, q);



	        all_cnt.push_back(cnt);



	        if(head->next != head) color_cnt_set(cnt, head);



	        for(p = head->next; p != head; p = p->next, q = q->next) {



	            color_cnt(cnt, q);



	            all_cnt.push_back(cnt);



	            color_cnt_set(cnt, p);



	        }



	        unsubjectnum(num, all_cnt, c);



	        return num;



	    }



	};



	int main(void)



	{



	    vector<int> color;



	    ListNode *head, *p;



	    int n, m, c, cn, x, i;



	    cin >> n >> m >> c;



	 



	    cin >> cn;



	    for(int i = 0; i < cn; i++) {



	        cin >> x;



	        color.push_back(x);



	    }



	    head = new ListNode(cn, color, head);



	 



	    for(i = 1, p = head; i < n; i++)



	    {



	        cin >> cn;



	        color.clear();



	        for(int i = 0; i < cn; i++) {



	            cin >> x;



	            color.push_back(x);



	        }



	        p->next = new ListNode(cn, color, head);



	        p = p->next;



	    }



	    class Solution s;



	    cout << s.func(head, m, c);



	    return 0;



	}