作为一个手串艺人,有金主向你订购了一条包含n个杂色串珠的手串——每个串珠要么无色,要么涂了若干种颜色。为了使手串的色彩看起来不那么单调,金主要求,手串上的任意一种颜色(不包含无色),在任意连续的m个串珠里至多出现一次(注意这里手串是一个环形)。手串上的颜色一共有c种。现在按顺时针序告诉你n个串珠的手串上,每个串珠用所包含的颜色分别有哪些。请你判断该手串上有多少种颜色不符合要求。即询问有多少种颜色在任意连续m个串珠中出现了至少两次。
作为一个手串艺人,有金主向你订购了一条包含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)
一个非负整数,表示该手链上有多少种颜色不符需求。
5 2 3 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颗串珠是透明的。
#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)
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int c = sc.nextInt(); byte[][] matrix = new byte[n][c]; for (int i=0; i<n; i++) { int total = sc.nextInt(); for (int j=0; j<total; j++) { int k = sc.nextInt(); matrix[i][k-1] = 1; } } //用来标记 byte[] result = new byte[c]; for (int i=0; i<c; i++) { int lastIndex = -1; int end = n+m-1; //System.out.println("end is:" + end); for (int j=0; j<end; j++) { int row = j%n; if(matrix[row][i]==1) { if (lastIndex==-1) lastIndex = j; else { if (j-lastIndex < m) result[i] = 1; else { lastIndex = j; } } } } } int sum = 0; for (int i=0; i<c; i++) { if (result[i] ==1) sum++; } System.out.println(sum); } }
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;}