作为一个手串艺人,有金主向你订购了一条包含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<iostream>
#include<stdio.h>
#include<string>
#include<cstring>
#include<string.h>
#include<vector>
using namespace std;
int main()
{
int n,m,c;
cin>>n>>m>>c;
vector<vector<int>> col(c+1,vector<int>());//col[i]表示第i中颜色的出现情况
int res=0;//不符合要求的情况数量
for(int i=1;i<=n;i++) {
int sum;
cin>>sum;
while(sum--) {
int x;
cin>>x; //当前颜色
col[x].push_back(i);
}
}
for(int i=0;i<=c;i++) {
int len=col[i].size();
if(len<=1)
continue; //只出现1次或未出现,不可能有连续m时重复的情况
for(int j=0;j<len;j++) {
if((col[i][j]-col[i][(j+len-1)%len]+n)%n<m) {
//该颜色出现的第j个珠子与上一个出现该颜色的珠子在连续m范围内
res++;
break;
}
}
}
cout<<res<<endl;
return 0;
} //主要思想就是:对于每种颜色,找到在哪个珠子上出现,记录下下标,对下标进行判断,看是否满足相邻下标>=m。#include<iostream>
#include<set>
#include<vector>
using name space std;
int main() {
int n, m, c;
cin >> n >> m >> c;
vector<set<int>> data;//每个珠子为vector的一个元素,使用set记录每个珠子有的颜***r /> int *num=new int[n];
for (int i = 0; i < n; i++) {
cin >> num[i];
set<int> s;
int *p = new int[num[i]];
for (int j = 0; j < num[i]; j++) {
cin >> p[j];
s.insert(p[j]);
}
data.push_back(s);
}
int res = 0;
for (int k = 1; k <= c; k++) {
vector<int> v;
for (int d = 0; d < data.size(); d++) {
if (data[d].find(k) != data[d].end()) {//查找每种颜色各在哪颗珠子出现,记录下标,
v.push_back(d+1);
}
}
if (v.size() > 1) {
if (v[v.size() - 1] + m - n > v[0]) res++;//对下标进行判断,判断该颜色是否满足要求
else {
for (int w = 0; w < v.size() - 1; w++) {
if (v[w + 1] - v[w] < m) {
res++;
break;
}
}
}
}
}
cout << res;
return 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();
int sum = 0;
int[] num = new int[c+1];
int[] early = new int[c+1];
Set<Integer> set = new HashSet<>();
for(int i1=1;i1<=n;i1++){
int t = sc.nextInt();
if(t==0) continue;
for(int i=0;i<t;i++){
int tmp = sc.nextInt();
if(early[tmp]==0) early[tmp] = i1;
if(num[tmp]>0&&i1-num[tmp]+1<=m) set.add(tmp);
if(i1+m-1>n&&early[tmp]<=(i1+m-1)%n) set.add(tmp);
num[tmp]=i1;
}
}
System.out.println(set.size());
sc.close();
}
} n,m,c = map(int,input().split())
color = {}
for i in range(n):
zhu = list(map(int,input().split()[1:]))
for j in zhu:
if j not in color:
color[j] = [i]
else:
color[j].append(i)
if i<m:
color[j].append(i+n)
cnt = 0
for i in color:
val = color[i]
val.sort()
for i in range(1,len(val)):
if val[i]-val[i-1]<m:
cnt+=1
break
print(cnt)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m, c, t, x, s=0, a[51], b[51];
bool mp[51]={false};
memset(a, -1, sizeof(a));
scanf("%d%d%d", &n, &m, &c);
for(int i=0;i<n;i++){
scanf("%d", &t);
for(int j=0;j<t;j++){
scanf("%d", &x);
if(mp[x])
continue;
if(a[x]!=-1 && i-a[x]<m){
s++;
mp[x] = true;
}
if(a[x]==-1)
b[x] = i;
a[x] = i;
}
}
for(int i=1;i<=c;i++){
if(mp[i] || b[i]==a[i])
continue;
if(n-a[i]+b[i] < m)
s++;
}
printf("%d\n", s);
return 0;
} import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt(),c=sc.nextInt();
sc.nextLine();
//相当于建立二维数组,第一维是颜色,第二维是有该颜色的珠子数组
List<List<Integer>> lists=new ArrayList<>();
for(int i=0;i<c;i++){
lists.add(new ArrayList<Integer>());
}
//添加数据
for(int i=0;i<n;i++){
int a=sc.nextInt();
for(int j=0;j<a;j++){
lists.get(sc.nextInt()-1).add(i);
}
sc.nextLine();
}
int ans=0;
//遍历数据
for(int i=0;i<c;i++){
List<Integer> l=lists.get(i);
for(int k=0;k<l.size();k++){
int sub=l.get((k+1)%lists.get(i).size())-l.get(k);
if(sub<m&&sub>0){
ans++;
break;
}
}
}
System.out.println(ans);
}
} 枚举颜色,然后判断
#include <iostream>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <vector>
using namespace std;
int n, m, c;
map<int, vector<int>> A;
void solve() {
int ans = 0;
for(int i = 1; i <= c; ++i) {
int sz = A[i].size();
bool flag = false;
for(int j = 0; j < sz; ++j) {
int cur = A[i][j], limit = (cur + m - 1) % n;
int next = A[i][(j+1)%n];
if(cur < limit && next <= limit && next > cur) flag = true;
else if(cur > limit && (next > cur || next <= limit)) flag = true;
if(flag) break;
}
if(flag) ++ans;
}
printf("%d\n", ans);
}
int main() {
scanf("%d%d%d",&n, &m, &c);
for(int i = 0; i < n; ++i) {
int k, a;
scanf("%d", &k);
for(int j = 0; j < k; ++j) {
int color;
scanf("%d", &color);
A[color].push_back(i);
}
}
if(m > n)
printf("%d\n", c);
else if(m == 1)
printf("0\n");
else
solve();
}
#include
int b[100001];
int a[100001][51];
int main()
{
int n, m, c, num, color, cnt = 0;
int i, j, k, l;
scanf("%d %d %d", &n, &m, &c);
for (i = 0; i < n; i++)
{
scanf("%d", &num);
for (j = 0; j < num; j++)
{
scanf("%d", &color);
a[i][color] = 1;
}
}
int flag;
for (j = 1; j <= c; j++)
{
k = 0;
flag = 0;
for (i = 0; i < n; i++)
{
if (a[i][j] == 1)
{
k++;
b[k] = i + 1;
//printf("b[%d]=%d\n", k, b[k]);
}
}
//printf("k=%d\n", k);
if (k != 1)
{
for (i = 1; i < k; i++)
{
//printf("b[%d]-b[%d]=%d\n", i + 1, i, b[i + 1] - b[i]);
if ( b[i + 1] - b[i] < m)
{
cnt++;
flag = 1;
//printf("color:%d \n", j);
//printf("b[%d]-b[%d]=%d\n", i + 1, i, b[i + 1] - b[i]);
break;
}
}
/* */
if (b[k] + m > n && b[1] < m - (n - b[k]) && flag == 0)
{
cnt++;
//printf("color: %d \n", j);
//printf("b[%d]-b[%d]=%d\n", i + 1, i, b[i + 1] - b[i]);
}
}
}
printf("%d", cnt);
return 0;
}
let sameColor = {}
let [n, m, c] = readline().split(' ').map((value) => Number(value))
//按照每种颜色,创建一个对象数组存储手串的索引
for (let i = 0; i < n; i++) {
let ballArr = readline().split(' ').map((value) => Number(value))
for (let j = 1; j < ballArr[0]+1; j++) {
if (!sameColor[ballArr[j]]) {
sameColor[ballArr[j]] = []
}
sameColor[ballArr[j]].push(i + 1)
}
}
let res = 0
//遍历每种颜色
for (let color of Object.keys(sameColor)){
//判断同一个颜色是否出现在连续的m个手串中
let indexArr = sameColor[color]
if(indexArr.length == 1) continue
let flag = true //判断当前颜色是否还需要判断
// 遍历每一种颜色中的手串位置
for(let i = 0;i < indexArr.length && flag == true;i++){
for(let fanwei = 1; fanwei < m; fanwei ++){
let num = (indexArr[i] + fanwei)%n //处理手串循环问题
if (indexArr.includes(num) == true) {
flag = false
res ++
break
}
}
}
}
console.log(res) 菜鸟的js代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,c;
cin>>n>>m>>c;
vector<int> cnt[51];
for(int i=0;i<=50;i++) cnt[i].clear();
for(int i=0;i<n;i++){
int num;
cin>>num;
for(int j=0;j<num;j++){
int x;
cin>>x;
cnt[x].push_back(i);
}
}
int res=0;
for(int i=1;i<=c;i++){
if(cnt[i].size()<=1) continue;
for(int j=0;j<cnt[i].size();j++){
int l=cnt[i][j],r=cnt[i][(j+1)%cnt[i].size()];
int len1=(max(l,r)-min(l,r)+1);
int len2=n-len1+2;
if(min(len1,len2)<=m) {
res++;
break;
}
}
}
cout<<res<<endl;
} #include <iostream>
#include <cstdio>
#include <cstdbool>
using namespace std;
bool nums[51][10001];
int main() {
int n,m,c;
scanf("%d%d%d", &n, &m, &c);
for(int i = 1;i <= n;i++){
int num_i;
scanf("%d", &num_i);
while(num_i--){
int color;
scanf("%d", &color);
nums[color][i] = true;
}
}
int result = 0;
for(int i = 1;i <= c;i++){
int last_true = -10000;
bool flag = true;
for(int j = 1;j <= n;j++){
if(nums[i][j]){
if(j - last_true >= m){
last_true = j;
}
else{
result++;
flag = false;
break;
}
}
}
if(nums[i][n] && nums[i][m - 1] && flag){
result++;
}
}
printf("%d", result);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
vector<int> colors[10010];
int counts[55];
int main(){
int n, m, c;
cin>>n>>m>>c;
set<int> ans;
for(int i=0;i<n;i++){
int nn;
cin>>nn;
for(int j=0;j<nn;j++){
int c;
cin>>c;
colors[i].push_back(c);
if(i<m){
if(++counts[c]>=2) ans.insert(c);
}
}
}
for(int i=1; i<n;i++){
for(int c: colors[i-1]){
counts[c] --;
}
//cout<<i<<endl;
for(int c: colors[(i+m-1)%n]){
if(++counts[c]>=2) ans.insert(c);
//cout<<c<<" "<<counts[c]<<endl;
}
}
cout<<ans.size();
} //滑动窗口法
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
#define N 55
bool colorVisual[N] = { false };
int main() {
int n, m, c;
cin >> n >> m >> c;
vector<vector<int>> pearColors(n, vector<int>());
unordered_map<int, int> colorCountInWin;
for (int i = 0; i < n; i++) {
int colorCount;
cin >> colorCount;
for (int j = 0; j < colorCount; j++) {
int colorValue;
cin >> colorValue;
pearColors[i].push_back(colorValue);
}
}
int left = 0;
int right = 0;
while (left < n) {
for (int i = 0; i < pearColors[right % n].size(); i++) {
colorCountInWin[pearColors[right % n][i]]++;
}
right++;
while ((right - left) == m) {
for (auto it = colorCountInWin.begin(); it != colorCountInWin.end(); it++) {
if (it->second >= 2) {
colorVisual[it->first] = true;
}
}
for (int i = 0; i< pearColors[left].size(); i++) {
colorCountInWin[pearColors[left][i]]--;
}
left++;
}
}
int ans = 0;
for (int i = 1; i <= c; i++) {
if (colorVisual[i]) {
ans++;
}
}
cout << ans << endl;
//system("Pause");
return 0;
}
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main(){
int n,m,c,sico,co,times=0,finum=0;
vector<int>nlist,indelist;
map<int,int> comdic,findic;
cin>>n>>m>>c;
for (int i =0;i<c;i++){
comdic[i+1]=0;
findic[i+1]=0;
}
for (int i=0;i<n;i++){
cin>>sico;
indelist.push_back(times);
for (int j=0;j<sico;j++){
cin>>co;
times+=1;
nlist.push_back(co);
}
}
indelist.push_back(times);
int loc=m;
for (int i=0;i<indelist[m];i++){
comdic[nlist[i]]+=1;
if (comdic[nlist[i]]>1)
findic[nlist[i]]=1;
}
for (int i=0;i<n;i++){
//cout<<comdic[48]<<endl;
if (i==0)
continue;
else if (i<n-m+1){
for (int j=indelist[i-1];j<indelist[i];j++){
comdic[nlist[j]]-=1;
}
for (int j=indelist[m+i-1];j<indelist[m+i];j++){
comdic[nlist[j]]+=1;
if (comdic[nlist[j]]>1)
findic[nlist[j]]=1;
}
}
else
{
for (int j=indelist[i-1];j<indelist[i];j++){
comdic[nlist[j]]-=1;
}
for (int j=indelist[m+i-1-n];j<indelist[m+i-n];j++){
comdic[nlist[j]]+=1;
if (comdic[nlist[j]]>1)
findic[nlist[j]]=1;
}
}
}
for (int i=1;i<=c;i++){
if (findic[i]==1){
finum+=1;
//cout<<i<<endl;
}
}
//for(int i=0;i<indelist.size();i++)
//cout<<indelist[i]<<endl;
cout<<finum<<endl;
}