首页 > 试题广场 >

手串

[编程题]手串
  • 热度指数:5324 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

作为一个手串艺人,有金主向你订购了一条包含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)


输出描述:
一个非负整数,表示该手链上有多少种颜色不符需求。
示例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颗串珠是透明的。
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)

发表于 2019-02-17 13:00:57 回复(7)
#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;
}

发表于 2021-05-05 19:33:28 回复(0)
#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;
}

发表于 2020-12-11 00:38:11 回复(0)
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,m,c;cin>>n>>m>>c;
    vector<vector<int>> C(55);
    for(int i=0;i!=n;++i){
        int t;cin>>t;
        for(int j=0;j!=t;++j){//不用处理无色
            int k;cin>>k;
            C[k].push_back(i+1);
        }
    }
    int res=0;
    for(int i=0;i!=55;++i){
        /*for(auto c:C[i]){
            cout<<c<<' ';
        }
        cout<<endl;*/
        if(C[i].size()<2) continue;
        for(int j=1;j!=C[i].size();++j){
            if(C[i][j]-C[i][j-1]<m) {res++;break;}
            //回环
            if(j==C[i].size()-1){
                if(n-C[i][j]+C[i][0]<m)
                    res++;
            }
        }
    }
    cout<<res;
}
发表于 2019-05-07 09:31:32 回复(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;
}


发表于 2019-06-14 21:48:20 回复(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();
    }
}
发表于 2020-04-20 11:01:12 回复(0)
将每个珠子的颜色用二进制数保存,对应位置为1则表示有这个颜色,
如珠子i包含1,2,3个颜色,则num_i[i]=7,即二进制111
采用二进制与运算来检测对应颜色有没有重复的。在每趟m个珠子内进行比较颜色时,定义一个modle来保存该趟内出现过的颜色,每次只需将珠子与modle做与运算即可得到重复的颜色,然后将其结果与用来记录重复颜色的res做或运算就可以更新res,同时还要更新modle,再进行下一次比较。
最后res的二进制表示中有多少个1则代表有多少个重复颜色
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int m=scanner.nextInt();
int c=scanner.nextInt();
long[] num_i=new long[n];
long res=0,res_num=0;
for(int i=0;i<n;i++) {
int t=scanner.nextInt();
for(int j=0;j<t;j++) {
num_i[i]+=(long)Math.pow(2, scanner.nextDouble()-1);
}
}
for(int k=0;k<n;k++) {
long modle=0;
for(int i=k;i<m+k;i++) {
if((num_i[i%n]&modle)!=0) {
res=res|(num_i[i%n]&modle);
}
modle=modle|num_i[i%n];
}
}
long t;
while(res>0) {
t=res%2;
if(t==1) {
res_num++;
}
res=res/2;
}
System.out.println(res_num);
}
}
编辑于 2019-04-02 13:56:18 回复(1)
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);
    }
}

发表于 2022-09-01 20:58:14 回复(0)

枚举颜色,然后判断

#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();
}
发表于 2022-05-15 19:19:20 回复(0)
package main

import(
    "fmt"
)

func main(){
    n,m,c := 0,0,0
    fmt.Scan(&n,&m,&c)
    colorDarr := [][]int{}
    cnt:=n
//     解析输入
    for cnt > 0{
        times := 0
        fmt.Scan(&times)
        colorArr := []int{}
        if times == 0{
            colorArr = append(colorArr,0)
        }
        for i:=0;i<times;i++{
            color := 0
            fmt.Scan(&color)
            colorArr = append(colorArr,color)
        }
        colorDarr = append(colorDarr,colorArr)
        cnt--
    }
    
//   逐个判断每种颜色出现的位置
    res:=0
    for colorIdx := 1; colorIdx <= c; colorIdx++{
        dp := make([]bool,n)
        for i:=0;i<n;i++{
            for _,v:=range colorDarr[i]{
                if v == colorIdx{
                    dp[i]=true
                }
            }
           
        }
        
//      判断是否满足相邻情况  
        flag:=false
        for i:=0;i<n;i++{
            cnt:=0
            for j:=i;j<m+i;j++{
                tmp:=j
                if tmp>=n{
                    tmp=tmp-n
                }
              
                if dp[tmp]==true{
                    cnt++
                }
            }
            if cnt>1{
                flag=true
            }
        }
        if flag{
            res++
        }  
    }
    fmt.Println(res)   
}
发表于 2022-04-08 14:58:20 回复(0)
#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;
}
发表于 2021-09-11 14:54:01 回复(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代码
发表于 2021-08-14 21:00:25 回复(0)
#include<bits/stdc++.h>
using namespace std;

int main(void) {
    int n, m, c;
    cin >> n >> m >> c;
    vector<vector<int>>sum(c, vector<int>(n+1, 0));
    for(int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        for(int j = 0; j < c; j ++) {
            sum[j][i] = sum[j][i-1];
        }
        
        for(int j = 1; j <= x; j ++) {
            int y;
            cin >> y;
            sum[y-1][i] = sum[y-1][i-1] + 1;
        }
    }
    int ans = 0;
    for(int i = 0; i < c; i ++) {
        int a = 0;
        for(int j = 1; j <= n; j ++) {
            a = 0;
            int u = j+m-1;
            if (u <= n) {
                a = sum[i][u] - sum[i][j-1];
                if(a >= 2) {
                    break;
                }
            }
            else {
                u %= n;
                a = sum[i][u] + sum[i][n] - sum[i][j-1];
                if(a >= 2) {
                    break;
                }
            }
        }
        if(a >= 2) ans += 1;
    }
    cout << ans << endl;
    return 0;
}

使用前缀和 O(1)计算连续m个柱子的某一颜色出现次数
发表于 2021-05-15 01:00:04 回复(0)
环形的珠子,所以除了记录所有Color的下标之外,还需要增加一个辅助位置Color1+len来做越过判断
发表于 2021-03-16 10:27:52 回复(0)
#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;
}

发表于 2021-03-06 17:19:31 回复(0)
用二维数组存输入信息,二维数组的纵向表示第几种颜色,横向表示该颜色出现在第几个串珠上,出现的则对应位置为true,然后遍历该二维数组即可
#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;
}

发表于 2021-02-26 16:48:57 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool comp(const int &a,const int &b){
    return a<b;
}
//判断是否符合要求
int testfun(vector<int> &num,int m,int l){
    int n=num.size();
    if(n==0||n==1) return 0;
    for(int i=0;i<n-1;i++){
        if(num[i+1]-num[i]<m) return 1;
    }
    if(num[0]<num[n-1]+m-l) return 1;
    return 0;
}
int main(){
    int n,m,c;
    cin>>n>>m>>c;
    vector<vector<int>> num(c+1);
    //进行输入,将包含每种颜色的下标存在对应的颜色中
    for(int i=0;i<n;i++){
        int cnum;
        cin>>cnum;
        for(int j=0;j<cnum;j++){
            int tem;
            cin>>tem;
            num[tem].push_back(i);
        }
    }
    //开始遍历每种颜色,检查是否符合要求
    int res=0;
    for(int i=1;i<=c;i++){
        //从小到达进行排序
        sort(num[i].begin(),num[i].end(),comp);
        res+=testfun(num[i],m,n);
    }
    cout<<res<<endl;
    return 0;
}
发表于 2020-09-10 01:38:33 回复(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();
}


发表于 2020-08-13 22:23:21 回复(0)
//滑动窗口法
#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;
}

发表于 2020-06-30 10:13:09 回复(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;
    }
         
         

发表于 2020-06-21 17:30:45 回复(1)