作为一个手串艺人，有金主向你订购了一条包含n个杂色串珠的手串——每个串珠要么无色，要么涂了若干种颜色。为了使手串的色彩看起来不那么单调，金主要求，手串上的任意一种颜色（不包含无色），在任意连续的m个串珠里至多出现一次（注意这里手串是一个环形）。手串上的颜色一共有c种。现在按顺时针序告诉你n个串珠的手串上，每个串珠用所包含的颜色分别有哪些。请你判断该手串上有多少种颜色不符合要求。即询问有多少种颜色在任意连续m个串珠中出现了至少两次。
[编程题]手串
- 热度指数：6331 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
输入描述:
第一行输入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 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 <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int n,m,c;
cin >> n >> m >> c;
// 3 1 2 3
// 0
// 2 2 3
// 1 2
// 1 3
// 每种颜色出现在哪些珠子上
unordered_map<int, vector<int>> clr_strings;
for(int i=1; i<=n; i++) {
int count;
cin >> count; // 第i颗珠子多少种颜色
int clr;
for(int j=1; j<=count; j++) { // 颜色
cin >> clr;
clr_strings[clr].push_back(i); // 这种颜色放到这个珠子上
}
}
// 遍历每种颜色，重复的珠子是否存在
int res = 0;
for(auto it = clr_strings.begin(); it != clr_strings.end(); it++) {
vector<int> strs = it->second;
int lens = strs.size();
if(strs[lens-1] + strs[0] == n) { // 首尾相邻不符合要求
res++; continue;
}
for(int i=1; i<lens; i++) {
if(strs[i] - strs[i-1] < m) { // 前后相邻不符合要求
res++; break;
}
}
}
cout << res << endl;
return 0;
}
编辑于 2020-03-14 19:18:43
回复(1)
思想：比较通俗易懂,统计每一个颜色出现的位置，使用数据结构Map<颜色，LinkedList颜色的位置>
然后统计每一种颜色是否出错，如果出错，就break，error+1，
importjava.util.HashMap;importjava.util.LinkedList;importjava.util.Map;importjava.util.Scanner;publicclassMain {publicstaticvoidmain(String[] args) {Scanner scanner = newScanner(System.in);intn = scanner.nextInt();// n个手串intm = scanner.nextInt();// 间隔为mintc = scanner.nextInt();// 有c种颜色Map<Integer, LinkedList<Integer>> map = newHashMap<Integer, LinkedList<Integer>>();for(inti = 1; i <= c; i++) {map.put(i, newLinkedList<Integer>());}inttotal = 1;while(total <= n) {intnum = scanner.nextInt();// 表示有多少顔色for(inti = 0; i < num; i++) {intcolor = scanner.nextInt();LinkedList<Integer> linkedList = map.get(color);// 得到某種顔色的位置linkedList.add(total);// 再加上此位置map.put(color, linkedList);}total++;}interror = 0;for(inti = 1; i <= c; i++) {LinkedList<Integer> linkedList = map.get(i);// 得到某種顔色的位置int[] array = newint[linkedList.size()];intk = 0;for(intj : linkedList) {array[k++] = j;}for(intj = 0; j < array.length; j++) {if(j + 1< array.length && array[j + 1] - array[j] < m) {error++;break;} elseif(j + 1== array.length && array[0] + n - array[j] < m) {error++;break;}}}System.out.println(error);}}
编辑于 2018-03-21 21:15:20
回复(6)
python解法，基于哈希表
num_pearl, limit, num_colors = list(map(int, input().strip().split()))
hashmap = {}
for pearl_index in range(num_pearl):
line = list(map(int, input().strip().split()))
num = line[0]
if num == 0:
continue
colors = line[1:]
for i in range(len(colors)):
if colors[i] == 0:
continue
if colors[i] in hashmap:
hashmap[colors[i]].append(pearl_index)
else:
hashmap[colors[i]] = [pearl_index]
count = 0
for key in hashmap.keys():
indexes = hashmap[key]
if len(indexes) == 1:
continue
diff = num_pearl - indexes[-1]
if abs(indexes[0] - diff) < limit:
count += 1
continue
for i in range(len(indexes) - 1):
if abs(indexes[i] - indexes[i+1]) < limit:
count += 1
break
print(count)
发表于 2022-05-06 03:08:19
回复(0)
from collections import Counter n, m, c = map(int, input().split()) color = [] for i in range(n): temp = list(map(int, input().split()))[1:] color.append(temp) color.append(color[0]) i = 0 res = set() while i < n: temp = color[i: i + m] t = [] for each in temp: t += each d = dict(Counter(t)) for k, v in d.items(): if v >= 2: res.add(k) i += 1 print(len(res))
发表于 2022-03-05 17:08:34
回复(1)
//为什么***写了这么多行
#include<iostream>
//#include<bits/stdc++.h>
#include<unordered_set>
#include<queue>
#include<unordered_map>
using namespace std;
int main()
{
int n,m,c;
unordered_set<int> s;
int len;
queue<int> q;
unordered_map<int,int> u_map;
unordered_map<int,int>::iterator it;
int temp;
int min_n_m;
while(cin>>n>>m>>c) {
min_n_m=min(n,m);
for(int i=0;i<min_n_m;i++) { //初始化
cin>>len;
q.push(len);
while(len>0) {
cin>>temp;
it=u_map.find(temp);
if(it!=u_map.end()) { //找到
it->second++;
}else {
u_map.insert(make_pair(temp,1));
}
q.push(temp);
len--;
}
}
for(it=u_map.begin();it!=u_map.end();it++) { //查询不符合的颜色
if((it->second>1)&&(it->first!=0))
s.insert(it->first);
}
queue<int> q_back(q);
//unordered_map<int,int> u_map_back(u_map);
int i=m;
while(i<n) {
len = q.front();
q.pop();
while(len>0) { //弹出滑动窗口最左边对应这颗珠子
it=u_map.find(q.front());
it->second--;
q.pop();
len--;
}
cin>>len;
q.push(len);
while(len>0) { //将当前颗加入滑动窗口最右边
cin>>temp;
it=u_map.find(temp);
if(it!=u_map.end()) { //找到
it->second++;
}else {
u_map.insert(make_pair(temp,1));
}
q.push(temp);
len--;
}
for(it=u_map.begin();it!=u_map.end();it++) {//查询不符合的颜色
if((it->second>1)&&(it->first!=0))
s.insert(it->first);
}
i++;
}
i=n;
while(i<n+m) {
len = q.front();
q.pop();
while(len>0) { //弹出滑动窗口最左边对应这颗珠子
it=u_map.find(q.front());
it->second--;
q.pop();
len--;
}
len=q_back.front();
q_back.pop();
q.push(len);
while(len>0) { //将backup当前颗加入滑动窗口最右边
temp=q_back.front();
q_back.pop();
it=u_map.find(temp);
if(it!=u_map.end()) { //找到
it->second++;
}else {
u_map.insert(make_pair(temp,1));
}
q.push(temp);
len--;
}
for(it=u_map.begin();it!=u_map.end();it++) {//查询不符合的颜色
if((it->second>1)&&(it->first!=0))
s.insert(it->first);
}
i++;
}
cout<<s.size()<<endl;
}
return 0;
}
发表于 2020-08-31 22:02:41
回复(0)
将数据按照颜色进行存储，定义一个二维数组，第一个维度表示颜色，第二个维度表示手串上串珠的位置下标，这样就可以对于每种颜色进行一个判断
#include <iostream>
(720)#include <stdio.h>
#define N 10001
(2529)#define C 51
using namespace std;
int data[C][N];
int n,m,c;
bool check(int colour[N]) {
int num=0,i=1;
// 统计从1~m区间，该颜色出现的次数
for (;i<=m;i++) {
if (colour[i]==1) {
num++;
}
}
if (num>1) {
return false;
}
// 让1~m这个区间向右滑动，一直到n-m+1~n，这些区间是否符合规则
for (i=1;i<=n-m;i++) {
// 在区间向右滑动之后，最右侧添加进来的位置，是否包含该颜色
if (colour[i+m]==1) {
num++;
}
// 区间向右滑动之后，最左侧移出区间的位置，是否包含该颜色
if (colour[i]==1) {
num--;
}
if (num>1) {
return false;
}
}
// 让该区间在首尾相连的情况下，继续进行判断
for (i=1;i<m;i++) {
if (colour[n-m+1]==1) {
num--;
}
if (colour[i]==1) {
num++;
}
if (num>1) {
return false;
}
}
return true;
}
int main()
{
// freopen("data.txt","r",stdin);
// 读取数据
scanf("%d %d %d",&n,&m,&c);
int i=1;
for (;i<=n;i++) {
int num_i=0,x,j=0;
scanf("%d",&num_i);
for (;j<num_i;j++) {
scanf(" %d",&x);
data[x][i]=1;
}
}
// 进行判断
int num=0;
for (i=1;i<=c;i++) {
if (!check(data[i])) {
num++;
}
}
// 输出结果
printf("%d",num);
}
发表于 2020-03-15 10:08:44
回复(0)
暴 力 爆 破
（多试几次，过不过看运气，连通过率都能浮动， 鉴定欧非
import java.util.Scanner;
import java.util.ArrayList;
public class 手环_暴力炸 {
public static void main (String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int c = sc.nextInt();
int[][] table= new int[n][c];
ArrayList<Integer> wrong = new ArrayList<Integer>();
int res = 0;
for (int j=0;j<n;j++){
int x = sc.nextInt();
for(int k=0;k<x;k++){
table[j][k] = sc.nextInt();
}
}
for (int i = 0;i<n;i++){
ArrayList<Integer> colors = new ArrayList<Integer>();
for (int t=0;t<m;t++){
int num = i+t;//一简化就必定爆
if (num>=n){
num -= n;
}
for (int k=0;k<table[num].length;k++){
if (table[num][k] != 0 && wrong.contains(table[num][k])== false ){
if (colors.contains(table[num][k])){
wrong.add(table[num][k]);
res++;
}else{
colors.add(table[num][k]);
}
}
}
}
}
System.out.println(res);
}
}
编辑于 2020-01-13 17:52:28
回复(0)
用vector容器实现#include <iostream>#include <vector>usingnamespacestd;intmain(void){intnumber = 0, m_limit = 0, color_num = 0;cin >> number >> m_limit >> color_num;vector<vector<int> > data;inti = 0, j = 0;for(i = 0; i<color_num; i++){vector<int> temp;data.push_back(temp);}intcolor = 0;inttemp_n;for(i=0; i<number; i++){cin >> temp_n;for(j=0; j<temp_n; j++){cin >> color;data[color-1].push_back(i);}}intcount = 0;for(i = 0; i<color_num; i++){inttemp = data[i].size();for(j=1; j<temp; j++){if(data[i][j] != number-1){if(data[i][j] - data[i][j-1] < m_limit-1){count++;break;}}elseif(data[i][0] == 0){count++;break;}}}cout << count;return0;}
发表于 2019-03-15 21:12:49
回复(0)
思路：先用unordered_map存储每个颜色中出现的位置
然后对每个颜色进行判断（第二个while循环每个颜色）
第二个while中第一个for循环用来将每个颜色中出现的位置延长一个用以循环如：
某颜色分别出现在第 1，3，4颗串珠 star[2][0]-star[2][3]分别为1 3 4 6（1+n）
第二个while中第二个for循环用来找不符合条件的颜色：
假设m=3；则说明三个串珠中该颜色只能出现一次，所以该颜色两个位置只差应该大于m-1;
某染色出现在1.3.4位置上的话，如果m=3，3-1=2不符合条件，所以该颜色是错误的，wrong++；
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
int main()
{
int n,m,c;
cin>>n>>m>>c;
int k=n;int i;int j;
unordered_map<int,vector<int> > star;
while(k>0)
{
k--;
int colornum;int color;
cin>>colornum;
for(i=1;i<=colornum;i++)
{
cin>>color;
star[color].push_back(n-k);
}
}
int wrong=0;k=c;
while(k>0)
{
k--;int flag=0;
int colorsize=star[c-k].size();
int x=star[c-k][0]+n;
star[c-k].push_back(x);//某颜色的位置最后加一个
for(i=0;i<colorsize;i++)
{
if((star[c-k][i+1]-star[c-k][i])<=(m-1)) {flag=1;break;}
}
if(flag==1) wrong++;
}
cout<<wrong<<endl;
return 0;
}
#include<unordered_map>
#include<vector>
using namespace std;
int main()
{
int n,m,c;
cin>>n>>m>>c;
int k=n;int i;int j;
unordered_map<int,vector<int> > star;
while(k>0)
{
k--;
int colornum;int color;
cin>>colornum;
for(i=1;i<=colornum;i++)
{
cin>>color;
star[color].push_back(n-k);
}
}
int wrong=0;k=c;
while(k>0)
{
k--;int flag=0;
int colorsize=star[c-k].size();
int x=star[c-k][0]+n;
star[c-k].push_back(x);//某颜色的位置最后加一个
for(i=0;i<colorsize;i++)
{
if((star[c-k][i+1]-star[c-k][i])<=(m-1)) {flag=1;break;}
}
if(flag==1) wrong++;
}
cout<<wrong<<endl;
return 0;
}
发表于 2018-09-03 17:17:17
回复(1)
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n,m,c;
cin >> n >> m >> c;
vector <int> vec[c+1];
for(int i=0;i<n;i++){
int k;
cin >> k;
for(int j=0;j<k;j++){
int t;
cin >> t;
vec[t].push_back(i);
}
}
int count=0;
for(int i=1;i<=c;i++){
sort(vec[i].begin(),vec[i].end());
int size = vec[i].size();
for(int j=1;j<size;j++){
if(vec[i][j]-vec[i][j-1]<m){
count++;
break;
}
if((j==size-1) &&(vec[i][j]+m)%n>vec[i][0]){
count++;
break;
}
}
}
cout << count << endl;
}
#include<vector>
using namespace std;
int main(){
int n,m,c;
cin >> n >> m >> c;
vector <int> vec[c+1];
for(int i=0;i<n;i++){
int k;
cin >> k;
for(int j=0;j<k;j++){
int t;
cin >> t;
vec[t].push_back(i);
}
}
int count=0;
for(int i=1;i<=c;i++){
sort(vec[i].begin(),vec[i].end());
int size = vec[i].size();
for(int j=1;j<size;j++){
if(vec[i][j]-vec[i][j-1]<m){
count++;
break;
}
if((j==size-1) &&(vec[i][j]+m)%n>vec[i][0]){
count++;
break;
}
}
}
cout << count << endl;
}
发表于 2018-03-23 19:52:51
回复(0)
详细 题解链接：
http://blog.csdn.net/bobbymly/article/details/79289575
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<algorithm>
using namespace std;
int main(){
int ans=0,n,m,c,times,color,i,j;
scanf("%d %d %d",&n,&m,&c);
int last_pos[c+1]; //每种颜色上一次出现的位置
int first_pos[c+1]; //每种颜色第一次出现的位置
bool ok[c+1]; //每种颜色是否满足题意
memset(first_pos,0,sizeof(first_pos));
memset(last_pos,0,sizeof(last_pos));
memset(ok,1,sizeof(ok));
for(i=1;i<=n;i++){
scanf("%d",×);
for(int j=0;j<times;j++){
scanf("%d",&color);
if(ok[color]){
if(!first_pos[color])first_pos[color]=i; //记录第一次出现的位置
else if(i-last_pos[color]<m)ok[color]=false; //判断非环形情况
last_pos[color]=i; //更新上一次出现的位置
}
}
}
for(i=1;i<=c;i++){
if(ok[i]&&first_pos[i]+n-last_pos[i]<m)ans++; //用头尾判断环形情况
if(!ok[i])ans++; //统计非环形情况
}
printf("%d",ans);
return 0;
}
编辑于 2018-02-16 12:53:00
回复(0)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
public class BraceletsTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //n个串珠
int m = sc.nextInt(); //手串上的任意一种颜色（不包含无色），在任意连续的m个串珠里至多出现一次
int c = sc.nextInt(); //颜色一共有c种
int count = 0;
Map<Integer,List<Integer>> map = new HashMap<>();
for(int i=0;i < n;i++) {
int num = sc.nextInt();
for(int j=0;j < num;j++) {
int key = sc.nextInt();
if(!map.containsKey(key)) {
List<Integer> list = new ArrayList<>();
list.add(i);
map.put(key, list);
}
else {
List<Integer> list = map.get(key);
list.add(i);
}
}
}
for(int i=1;i <= c;i++) {
boolean flag = false;
List<Integer> list = map.get(i);
if(list.size() == 1) {
continue;
}
else {
for(int j=0;j < list.size()-1;j++) {
if(list.get(j+1) - list.get(j) < m) {
count++;
flag = true;
break;
}
}
if(!flag) {
if((n-list.get(list.size()-1)+list.get(0)) < m){
count++;
}
}
}
}
System.out.println(count);
}
}
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
public class BraceletsTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //n个串珠
int m = sc.nextInt(); //手串上的任意一种颜色（不包含无色），在任意连续的m个串珠里至多出现一次
int c = sc.nextInt(); //颜色一共有c种
int count = 0;
Map<Integer,List<Integer>> map = new HashMap<>();
for(int i=0;i < n;i++) {
int num = sc.nextInt();
for(int j=0;j < num;j++) {
int key = sc.nextInt();
if(!map.containsKey(key)) {
List<Integer> list = new ArrayList<>();
list.add(i);
map.put(key, list);
}
else {
List<Integer> list = map.get(key);
list.add(i);
}
}
}
for(int i=1;i <= c;i++) {
boolean flag = false;
List<Integer> list = map.get(i);
if(list.size() == 1) {
continue;
}
else {
for(int j=0;j < list.size()-1;j++) {
if(list.get(j+1) - list.get(j) < m) {
count++;
flag = true;
break;
}
}
if(!flag) {
if((n-list.get(list.size()-1)+list.get(0)) < m){
count++;
}
}
}
}
System.out.println(count);
}
}
发表于 2018-04-06 03:25:00
回复(0)
| 将所有的颜色当作map的key，value为所有拥有这个颜色珠子的下标 然后通过下标之差判断是否在M范围内出现两次 importjava.util.*; publicclassMain { publicstaticintmethod(intm,Map<Integer,ArrayList<Integer>> map,intc) { intresult=0; for(inti =0;i <=c ;i++) { ArrayList<Integer> item=map.get(i); for(intj =0;j<item.size()-1;j++) { if(item.get(j+1)-item.get(j)<= m-1) { result++; break; } } } returnresult; } publicstaticvoidmain(String[] args) { Scanner in=newScanner(System.in); intn,m,c; n=in.nextInt(); m=in.nextInt(); c=in.nextInt(); Map<Integer,ArrayList<Integer>> map=newHashMap<>(); for(inti =0;i <= c;i++) { map.put(i,newArrayList()); } for(inti=0;i<n;i++) { intnumber=in.nextInt(); for(intj=0;j<number;j++) { intcolor=in.nextInt(); ArrayList<Integer> item= map.get(color); item.add(i); } } intresult=method(m,map,c); System.out.println(result); } } |
发表于 2019-03-14 14:55:35
回复(1)
用 last 数字记录每种颜色上次出现的位置，判断成功后加入哈希集合，最后的答案就是哈希集合中元素的数量。
由于是环形的，所以需要使用环形数组。
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt(), c = in.nextInt();
List<List<Integer>> ls = new ArrayList<>();
for (int i = 0; i < n; ++i) {
List<Integer> lss = new ArrayList<>();
int x = in.nextInt();
for (int j = 0; j < x; ++j) lss.add(in.nextInt());
ls.add(lss);
}
int[] last = new int[c + 1];
Arrays.fill(last, Integer.MIN_VALUE / 2);
Set<Integer> s = new HashSet<>();
for (int i = 0; i < ls.size() * 2; ++i) {
List<Integer> colors = ls.get(i % ls.size());
for (int color: colors) {
if (i - last[color] + 1 <= m) s.add(color);
last[color] = i;
}
}
System.out.println(s.size());
}
}
编辑于 2023-12-21 21:33:53
回复(0)
line1 = list(map(int, input().split(" ")))
n = line1[0]
m = line1[1]
c = line1[2]
#store the colors in each ball
colors = []
for _ in range(n):
line = list(map(int, input().split(" ")))
if line[0] == 0:
colors.append([])
continue
colors.append(line[1:])
#print(colors)
##################
#store the color count in slide window
#change it to array
hashmap = [0] * (c + 1)
booleans = [0] * (c + 1)
#initail hashmap
for i in range(0-m+1,m):
for col in colors[i]:
hashmap[col] += 1
#loop through all balls
for j in range(n):
#print(j)
#print(hashmap)
#check all colors in this ball
for b in colors[j]:
if hashmap[b] > 1:
booleans[b] = 1
#remove first
#print(colors[j-m+1])
for b in colors[j-m+1]:
hashmap[b] -= 1
#add last
#print(colors[(j+m)%n])
for b in colors[(j+m)%n]:
hashmap[b] += 1
print(sum(booleans))
发表于 2022-08-19 04:05:06
回复(0)
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();
boolean[][] flag = new boolean[n+1][c+1];
for(int i=1;i<flag.length;i++){
int count = sc.nextInt();
while(count-->0){
int color = sc.nextInt();
flag[i][color] = true;
}
}
//分别检验颜***r /> int res = 0;
for(int i=1;i<flag[0].length;i++){
int pre = 0;
int last = 0;
for(int j=1;j<flag.length;j++){
if(flag[j][i]){
if(pre==0){
pre=j;
last = j;
}else{
last =j;
}
}
if(last-pre>=m){
pre = last;
}
if(last!=pre){
res++;
break;
}
}
}
System.out.println(res);
}
}
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();
boolean[][] flag = new boolean[n+1][c+1];
for(int i=1;i<flag.length;i++){
int count = sc.nextInt();
while(count-->0){
int color = sc.nextInt();
flag[i][color] = true;
}
}
//分别检验颜***r /> int res = 0;
for(int i=1;i<flag[0].length;i++){
int pre = 0;
int last = 0;
for(int j=1;j<flag.length;j++){
if(flag[j][i]){
if(pre==0){
pre=j;
last = j;
}else{
last =j;
}
}
if(last-pre>=m){
pre = last;
}
if(last!=pre){
res++;
break;
}
}
}
System.out.println(res);
}
}
发表于 2022-05-30 17:07:49
回复(0)
类似对图处理一样 最后对每个一维数组排序
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, color, ans = 0;
cin >> n >> m >> color;
vector<vector<int>> co(color + 1, vector<int> ());
for (int i = 1; i <= n; i++) {
int num_cnt;
cin >> num_cnt;
for (int j = 0; j < num_cnt; j++) {
int tmp;
cin >> tmp;
co[tmp].emplace_back(i % n);
}
}
for (int i = 1; i <= color; i++) {
sort(co[i].begin(), co[i].end());
}
for (int i = 1; i <= color; i++) {
for (int j = 0; j < co[i].size() - 1; j++) {
if (co[i][j + 1] - co[i][j] < m) {
ans++;
break;
}
}
}
cout << ans << endl;
return 0;
}
发表于 2022-04-14 19:23:29
回复(0)
/*设置一个大小为wnd(m)的滑动窗口，vis向量记录窗口内珠子颜色的种类及其次数，
窗口每次向右吸纳新一个珠子前将最左边珠子的颜色信息删除，这样可以避免重复计算，
由于是环形，设置left=i%n可以做到窗口包含第一个和最后一个珠子，当vis[i]>=2
时，说明该颜色已经记录到结果中了，不用管它，继续检查下一种颜色*/
#include<iostream>
#include<stdlib.h>
#include<vector>
using namespace std;
int main(){
int n,wnd,color,res=0;
vector<vector<int>> vec;
cin>>n;
cin>>wnd;
cin>>color;
vector<int> vis(color+1,0);
int tmp1;
while(cin>>tmp1){
vector<int> num;
for(int i=0;i<tmp1;i++){
int tmp2;
cin>>tmp2;
num.push_back(tmp2);
}
vec.push_back(num);
num.clear();
}
for(int i=0;i<n+wnd;i++){
if(i>=wnd){
for(int j=0;j<vec[i-wnd].size();j++){
if(vis[vec[i-wnd][j]]==1)
vis[vec[i-wnd][j]]--;
}
}
int left=i%n;
for(int j=0;j<vec[left].size();j++){
if(vis[vec[left][j]]<2)//vis[a]只能是等于0，1，2或者3
vis[vec[left][j]]++;
if(vis[vec[left][j]]==2){
res++;
vis[vec[left][j]]++;
}
}
}
cout<<res<<endl;
return 0;
}
发表于 2022-02-25 09:41:12
回复(0)
根据题意，暴力也能过
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,c;
cin>>n>>m>>c;
map<pair<int,int>,int> mp;
for(int i=0;i<n;i++){
int size;
cin>>size;
for(int j=0;j<size;j++){
int color;
cin>>color;
mp[make_pair(i,color)]++;
}
}
vector<int> ans(c);
for(int i=0;i<n;i++){
for(int j=1;j<=c;j++){
//j就是颜色
if(mp[make_pair(i,j)]==0) continue;
int count=1;
while(count<m){
int pos=i+count;
if(pos>n-1) pos-=n;
if(mp[make_pair(pos,j)]>0) ans[j-1]++;
count++;
}
}
}
int res=0;
for(int i=0;i<c;i++){
if(ans[i]>0) res++;
}
cout<<res<<endl;
return 0;
}
发表于 2021-12-28 16:53:35
回复(0)
# n,m,c = map(int,input().strip().split()) # L = [[] for i in range(0, c+1)] # def color_m(list1,m,r): # list1.sort() # l = len(list1) # for i_1 in range(l): # for j_1 in range(i_1+1,l): # if (list1[j_1]-list1[i_1]+1)<=m or (list1[i_1]+n-list1[j_1]+1) <= m: # # print("i:",r,list1[j_1],list1[i_1]) # return 1 # return 0 # for i in range(n): # index = [int(o) for o in input().split()] # num = len(index) # if(index[0]==0):L[0].append(i) # else: # for j in range(1,index[0]+1): # L[index[j]].append(i) # ans = 0 # # print(L) # for i_2 in range(1,c+1): # ans = ans + color_m(L[i_2],m,i_2) # # print(i_2) # # print(ans)
n,m,c = map(int,input().strip().split()) L = [[] for i in range(0, c+1)] def color_m(list1,m,r): list1.sort() l = len(list1) for i_1 in range(l): for j_1 in range(i_1+1,l): if (list1[j_1]-list1[i_1]+1)<=m&nbs***bsp;(list1[i_1]+n-list1[j_1]+1) <= m: return 1 return 0 for i in range(n): index = [int(o) for o in input().split()] num = len(index) if(index[0]==0):L[0].append(i) else: for j in range(1,index[0]+1): L[index[j]].append(i) ans = 0 for i_2 in range(1,c+1): ans = ans + color_m(L[i_2],m,i_2) print(ans)
发表于 2020-10-10 23:04:19
回复(0)
问题信息
通过挑战的用户
-
2023-03-12 00:33:58 -
2023-02-23 21:16:54
-
2022-12-17 19:18:00 -
2022-11-13 23:30:40
-
2022-11-08 23:30:40
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
