作为一个手串艺人,有金主向你订购了一条包含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颗串珠是透明的。
/*判断手串珠子颜色不合格*/ var line1 = readline().split(' '); var n = line1[0], m = line1[1], c = line1[2]; var obj = {}; var arr = []; var cnt = 0; for(var i=0;i<n;i++){ arr[i] = readline().split(' '); for(var j=1;j<=arr[i][0];j++){ if(obj[arr[i][j]]){ obj[arr[i][j]].push(i+1); }else{ obj[arr[i][j]] = [i+1]; } } } var temp = Object.values(obj); for(var i=0;i<temp.length;i++){ for(var j=0;j<temp[i].length-1;j++){ if((temp[i][j+1] - temp[i][j]) < m){ cnt++; break; } } if(n-temp[i][temp.length-1]+temp[i][0] < m){ cnt++; break; } } print(cnt);
#include <bits/stdc++.h> using namespace std; vector<int> a[20010]; int vis[60]; int main() { int n,m,c; cin>>n>>m>>c; for(int i = 1; i <= n; i++) { int t; cin>>t; for(int j = 0; j < t; j++) { int x;cin>>x; a[i].push_back(x); } } int tot = 1; for(int i = n + 1;i <= n + m; i++) a[i] = a[tot++]; map<int,int> color; int out = 1; for(int i = 1; i <= m; i++) { for(int j = 0; j < a[i].size(); j++) { color[a[i][j]]++; } } int ans = 0; for(int i = m + 1; i <= n + m + 1; i++) { map<int,int>::iterator it; for(it = color.begin(); it != color.end(); ++it) { int fi = it->first; int se = it->second; if(se >= 2) { if(!vis[fi]) ans++; vis[fi] = 1; } } for(int j = 0; j < a[out].size(); j++) color[a[out][j]]--; out++; for(int j = 0; j < a[i].size(); j++) color[a[i][j]]++; //printf("%d\n",ans); } cout<<ans<<endl; return 0; }
n,m,c=list(map(int, input().split())) ls=[list(map(int, input().split()))[1:] for _ in range(n)] lc=[[] for _ in range(c)] for i in range(n): for cn in ls[i]: lc[cn-1]+=[i] ans=0 if n > 1:lc=list(map(lambda y:y+list(map(lambda x:x+n,y)),lc)) for i in range(c): lc[i].sort() for j in range(1,len(lc[i])): if lc[i][j]-lc[i][j-1]<m: ans+=1 break print(ans)
// 初始化串珠总个数,连续的串珠个数,颜色种类数,所有串珠的颜色信息数组, 同一颜色的串珠数组, 不合格的颜色个数 let ballNums, linkNums, colorNums, ballColor = [], sameColorBall = [], count = 0; [ballNums, linkNums, colorNums] = readline().split(' ').map(item => Number(item)); // 依次保存每个串珠所用颜色信息 // 数组的每个元素都是一个数组,元素数组的第一位代表颜色个数,后续代表所用颜色 for(let i = 0; i < ballNums; ++i) { ballColor[i] = readline().split(' ').map(item => Number(item)) } // 将同一颜色出现的串珠序号进行收集 ballColor.forEach((item, index) => { // 若该串珠所用颜色种类大于0 // console.log(item, 'item'); if(item[0] > 0) { let colorArr = item.slice(1) // 下面的item代表不同的颜色种类 colorArr.forEach(color => { // 如果之前已经保存过使用某颜色的串珠序号,则直接将其添加到数组中去 if(sameColorBall[color]) { sameColorBall[color].push(index + 1) } else { sameColorBall[color] = [index + 1] } }) } }) sameColorBall.forEach(item => { // sameColorBall[0]代表使用‘0’这种颜色的所有串珠的序号数组,这里的序号是按顺序排列的 for(let i = 0; i < item.length - 1; ++i) { if(item[i+1] - item[i] < linkNums) { ++count; break; } if(ballNums - item[item.length - 1] + item[0] < linkNums) { ++count; break; } } }) console.log(count);
#include <stdio.h> #include <malloc.h> #include <vector> #include <algorithm> #include <iostream> using namespace std; int main() { int n,m,c,numi,tmp,count=0; vector<int> color[50]; scanf("%d %d %d", &n, &m, &c); for(int i = 0; i < n; i++) { scanf("%d", &numi); for(int j = 0; j < numi; j++) { scanf("%d", &tmp); color[tmp-1].push_back(i); } } for(int i = 0; i < c; i++) { if(color[i].size() == 0) continue; sort(color[i].begin(), color[i].end()); for(int j = 0; j < color[i].size()-1; j++) { if(color[i][j + 1] - color[i][j] < m || color[i][j] + n - color[i][j + 1] < m) { count++; break; } } } printf("%d\n", count); return 0; }
/** * 构建hashmap,颜色作为key,所有拥有改颜色的珠子的位置列表作为value * 这么做的目的是分离颜色和位置,否则搞在一起很麻烦,最后返回不符合要求的颜色个数就可以了 * 对于hashmap的各个value们,也就是拥有同样颜色的珠子的位置列表,我们这么处理 * 首先用后一个位置的值前去前一个位置的值,如果差值小于m,就说明这个两个同色珠子挨得比较近,这个颜色不符合要求,直接break * 如果遍历完这个列表,还没有找出相邻的两个值之差小于m,我们就去看看最后一个和第一个值的差 * 由于手串是环形的,所以第一个位置的值需要加上手串长度n,然后再减去列表中最后一个值,看看差值是否小于m * 列表中的相邻位置具有特殊意义,除了表示相同颜色珠子在原始手串中的位置,而且,任何相邻两个之差表示它们在原始手串之中的距离 * 考虑到手串是个环,可能需要把第一个值加上手串长度减去最后一个值,首尾相接 * 如果不用上述思路,每一次都遍历一遍m相当耗时,这个方法就是通过过程中相邻位置判断距离之差和m的关系,快速判断是否符合要求 */ import java.util.*; 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(); HashMap<Integer, List<Integer>> colors_list = new HashMap<>(); // 外层循环表示每一行输入,也就是每一个珠子的着色情况 for (int i = 0; i < n; i++) { int colors = sc.nextInt(); // 无色的就不讨论了 if (colors != 0) { // 内层循环对每一颗珠子的颜色进行处理 for (int j = 0; j < colors; j++) { int color = sc.nextInt(); // 如果hashmap里面没有以color为键的, if (! colors_list.containsKey(color)) { List<Integer> color_list = new ArrayList<>(); colors_list.put(color, color_list); } // 相同颜色的珠子位置放进一个列表中,我这里习惯从1开始编号 colors_list.get(color).add(i+1); } } } // 用户编号我们从1开始,难点在于环形数组的处理 int count = 0; for (List<Integer> perlist : colors_list.values()) { int size = perlist.size(); if (size > 1) { // circled表示是否需要首尾相接判断一次,如果在遍历过程中发现有两颗之间的距离小于m,就直接break了,不会进行 // 首尾判断。如果从左到右遍历完列表,还是没有发现距离小于m的,那就首位相接判断一下 boolean circled = false; for (int i = 0; i < size -1; i++) { if (perlist.get(i+1) - perlist.get(i) < m) { circled = true; count ++; break; } } if (!circled) { if (perlist.get(0) + n - perlist.get(size-1) < m) { count ++; } } } } System.out.println(count); } }
let ballNums=0,linkNums=0,colorNums=0,ballColor=[],sameColorBall = [], count = 0; [ballNums, linkNums, colorNums] = readline().split(' ').map(item => Number(item)); for(let i = 0;i<ballNums;i++){ ballColor[i] = readline().split(' ').map(item => Number(item)); } let set1 = new Set(); for(let i = 0;i<ballColor.length;i++){ let set = new Set(); for(let j = 1;j<ballColor[i].length;j++){ set.add(ballColor[i][j]); } for(let k = i+1;k<i+linkNums;k++){ if(k<ballColor.length){ for(let l = 1;l<ballColor[k].length;l++){ if(set.has(ballColor[k][l])) set1.add(ballColor[k][l]); } for(let f= 1;f<ballColor[k].length;f++){ set.add(ballColor[k][f]); } } } } console.log(set1.size)
nmc=[int(i) for i in input().split()] n=nmc[0] m=nmc[1] c=nmc[2] ring=[] count=0 for i in range(n): data=[int(k) for k in input().split()] N=data[0] if N>0: ring.append(data[1::]) else: ring.append([]) for i in range(n): j=(i+1)%n for k in ring[i]: if k in ring[j]: count+=1 print(count)自测能通过,机判不通过,求问问题在哪
#include <iostream> #include <vector> using namespace std; vector<int> g[51]; int main(){ int n,m,c; scanf("%d %d %d",&n,&m,&c); int n1,n2; for (int i=0;i<n;i++){ scanf("%d",&n1); for (int j=0;j<n1;j++){ scanf("%d",&n2); g[n2].push_back(i); } } int n3=0,n4; for (int i=1;i<=c;i++){ //printf("%d %d\n",i,g[i].size()); n4=g[i].size(); for (int j=0;j<n4;j++){ g[i].push_back(g[i][j]+n); } for (int j=0;j<g[i].size()-1;j++){ if (g[i][j+1]-g[i][j]+1<=m){ n3++; break; } } } printf("%d",n3); return 0; }
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { int findDuplicate() { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); //n个珠子 int m = sc.nextInt(); //每m个珠子不得重复颜色 int c = sc.nextInt(); //共c种颜色 int k = 0; //第k颗串珠 int wrongNum = 0; //分布有问题的颜色数量 List<List<Integer>> colorList = new ArrayList<>(c); for (int i = 0; i < c; i++) { colorList.add(new ArrayList<>()); } //每个串珠分别存进颜色数组 for (int i = 0; i < n; i++) { k++; sc.nextLine(); int colorNum = sc.nextInt(); for (int j = 0; j < colorNum; j++) { colorList.get(sc.nextInt() - 1).add(k); } } //判断每个颜色是否有问题 for (int i = 0; i < c; i++) { List<Integer> thisList = colorList.get(i); for (int j = 0; j < thisList.size(); j++) { //如果连续两个之间的间隔小于m,则错误颜色数目+1.且该颜色判断完毕break if (j < thisList.size() - 1 && thisList.get(j + 1) - thisList.get(j) < m) { wrongNum++; break; } //判断最后一个和第一个之间的间隔 if (j == thisList.size() - 1 && (thisList.get(j) + thisList.get(0)) % n < m) { wrongNum++; } } } sc.close(); return wrongNum; } public static void main(String[] args) { int wrongNum = new Main().findDuplicate(); System.out.println(wrongNum); } }
import collections # 获取n,m,c三个数 arr = list(map(int, input().split())) # 定义一个字典存储同一颜色出现的串珠序号 d = collections.defaultdict(set) # 根据n依次获取第i颗珠子的颜色并存到d中 for i in range(arr[0]): m = list(map(int, input().split())) # 条件过滤了无色的珠子 if len(m) > 1: for j in range(len(m)-1): # 从第二项开始取颜色,m[j+1]是颜色的编号,i+1表示珠子序号(从1开始) d[m[j+1]].add(i+1) res = 0 # 遍历字典中的键名取相应的键值 for k in d: # 对键值排序,从小到大 tmp = sorted(list(d[k])) count = 0 # 条件过滤了k号颜色只有一个键值的情况 if len(tmp) > 1: for n in range(len(tmp)): # f在(n+1, len(tmp))是确保不重复遍历前面的值,进行重复比较 for f in range(n+1, len(tmp)): # 判断是否存在头尾有同一颜色 if tmp[len(tmp)-1] == arr[0] and tmp[n] == 1 and arr[1] > 1: count += 1 break # 判断连续区间内是否有同一颜色 if tmp[f] - tmp[n] < arr[1]: count += 1 break else: # 因为键值已排序,所以当遍历中第f项不满足前两个条件时,后面的值也不会符合,就跳出循环 break # 题目是有多少种颜色在任意连续m个串珠中出现了至少两次,所以这里只需判断一个颜色内是否有重复的就行,而不是重复多少次 if count != 0: res += 1 print(res)
let [n,m,c] = readline().split(' '), arr = []; for(let i=0;i<n;i++){ arr.push(readline().split(' ')) } //1、以颜色为索引,分好每个颜色所在的珠子。题目说不包含无色,就>0 let arrC = []; for(let i=0;i<=c;i++){ arrC[i] = [] } for (let i = 0; i < arr.length; i++) { if(arr[i][0] > 0){ for (let j = 1; j <= arr[i][0]; j++) { if(arrC[ arr[i][j] ]){ arrC[ arr[i][j] ].push( i+1 ) }else{ arrC[arr[i][j]] = [ index+1 ] } } } } //2、判断相邻 let count = 0; for(let i=1;i<arrC.length;i++){ let len = arrC[i].length; for(let j = 0; j<len-1;j++){ if( (arrC[i][j+1] - arrC[i][j]) < m){ count++ break } if(arrC[i][0] == 1 && arrC[i][len-1] == n){ count ++ break } } } print(count)
遍历查询