首页 > 试题广场 >

手串

[编程题]手串
  • 热度指数:797 时间限制: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颗串珠是透明的。
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int numOfRing = input.nextInt();
        int numOfNear = input.nextInt();
        int numOfColor = input.nextInt();
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i = 0; i < numOfRing; i++){
            int length = input.nextInt();
            for(int j = 0; j < length; j++){
                int color = input.nextInt();
                if(!map.containsKey(color)){
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    map.put(color, list);
                }else{
                    List<Integer> list = map.get(color);
                    list.add(i);
                }
            }
        }
        int sum = 0;
        int[] flag = new int[numOfColor];
        for(int i = 0; i < numOfColor; i++){
            List<Integer> list = map.get(i+1);
            if(list != null){
                int length = list.size();
                for(int j = 1; j < length; j++){
                    if(list.get(j) - list.get(j-1) < numOfNear){
                        flag[i] = 1;
                    }
                }
                if(list.get(0) - list.get(length-1) + numOfRing < numOfNear){
                    flag[i] = 1;
                }
            }
            if(flag[i] == 1){
                sum++;
            }
        }
        System.out.println(sum);
    }
}

发表于 2022-03-01 02:41:01 回复(0)
首先对输入数组进行一个转换,有颜色位置为1,无颜色位置为0;
其次判断在任意连续m个串珠中出现至少两次元素1的列。
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[][] arr = new int[n][c];

        for (int i = 0; i < n; i++) {
            int temp= sc.nextInt();
            for (int j = 0; j <temp; j++) {
                int temp1 = sc.nextInt();
                    arr[i][temp1-1]=temp1;//有颜色的位置元素为1;
            }
        }

         int res=0;
        for (int i = 0; i <c; i++) {//按列查询,总共C列
            for (int j = 0; j <arr.length-1; j++) {//查询每列的具体元素
                if(arr[0][i]==arr[arr.length-1][i]){//判断首尾是否相同
                    res++;
                    break;
                }
                if(arr[j][i]!=0){
//                    pre=j;
                    for (int k = j+1; k <arr.length-1; k++) {//从当前位置的下一个位置开始查找
                        if(arr[k][i]!=0){//如果该位置元素不为1,且位置下标<前一不为0元素的下标+m;
                            if(k<j+m){   //则不满足要求;结果+1;
                                res++;
                                j=arr.length-1;//直接遍历下一列;
                                break;
                            }
                        }
                    }

                }
            }
        }
        System.out.println(res);

    }


发表于 2021-07-17 10:27:52 回复(0)
遍历一次二维数组(n*c)即可,行对应于n颗串珠,列则对应于c种颜色(arr[i][j] =  0表示第i颗串珠无j颜色;arr[i][j] = j表示第i颗串珠有j颜色)
建立好二维数组后,逐列扫描,查看当前颜色是否符合要求
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();
        int[][] arr = new int[n][c];
        int temp, lie;
        for (int i = 0; i < n; i++) {
            temp = sc.nextInt();
            while (temp-- != 0) {
                lie = sc.nextInt();
                arr[i][lie - 1] = lie;
            }
        }
        int count = 0;
        int pre;
        outer:
        for (int i = 0; i < c; i++) {
            pre = -1;
            for (int j = 0; j < n; j++) {
                if (arr[j][i] != 0 && (j-pre>m || pre == -1)) {
                    pre = j;
                }else if(arr[j][i] != 0 && j - pre < m){
                    count++;
                    continue outer;
                }
                if (j == n - 1 && j - pre < m - 1) {
                    temp = 0;
                    while (j - pre + temp < m - 1) {
                        if (arr[temp][i] != 0){
                            count++;
                            break;
                        }
                        temp++;
                    }
                }
            }
        }
        System.out.println(count);
    }
}



发表于 2021-04-11 16:05:34 回复(0)
#语言:Python 3 运行时间: 121 ms 占用内存:5480K 状态:答案正确
n,m,c=map(int,input().split())
cs=[0forx inrange(0,n)]
fori inrange(0,n):
    cs[i]=list(map(int,input().split()))
    cs[i].pop(0)
num=0
fori inrange(1,c+1):
    bj=[0forx inrange(0,n)]
    t=0
    forj inrange(0,n):
        ifi incs[j]:
            bj[t]=j
            ift>0andbj[t]-bj[t-1]<m:
                num=num+1
                break
            t=t+1
        ifj==n-1and(-max(bj)+min(bj)+n<m):
            num=num+1
print(num)
发表于 2018-10-01 20:43:09 回复(0)
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <functional>
#include <algorithm>
#include <stack>
#include <queue>
#include <sstream>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <limits>

int main()
{
	int n, m, C;
	std::cin >> n >> m >> C;
	std::map<int, std::vector<int> > cmap;
	for (int i = 0; i < n; i++)
	{
		int x;
		std::cin >> x;
		for (int j = 0; j < x; j++)
		{
			int c;
			std::cin >> c;
			if (c != 0)
			{
				if (cmap.find(c) != cmap.end())
					cmap[c].push_back(i);
				else
				{
					std::vector<int> a;
					a.push_back(i);
					cmap[c] = a;
				}
			}
		}
	}

	int ans = 0;
	for (auto it = cmap.begin(); it != cmap.end(); it++)
	{
		std::vector<int>& a = it->second;
		if (a.size() >= 2)
		{
			if ((* a.rbegin() + 1) % n == *a.begin())
			{
				ans += 1;
			}
			else
			{
				for (size_t p1 = 0, p2 = 1; p2 < a.size(); p1++, p2++)
				{
					if (a[p2] - a[p1] < m)
					{
						ans += 1;
						break;
					}
				}
			}
		}
	}
	std::cout << ans;
	return 0;
}

发表于 2022-09-12 17:25:01 回复(0)

此题的难点在于

1、对颜色进行遍历还是对珠子的序号进行遍历,由于一个珠子可以有多种颜色,对珠子的序号进行遍历会有大量重复数据,所以我们对颜色进行遍历
2、怎样找颜色相同且距离不大于M的珠子。题目要求不符合规则的颜色要在连续m个串珠出现了至少两次,那只要找到两个珠子都包含同一种颜色就可以记录这个颜色不符合规则了,即我们从含有这种颜色珠子的下一颗珠子开始找,判断距离是否小于或者等于M即可

题解思路:

设置一个二维数组bead[][]记录珠子的颜色和对应的序号,然后遍历珠子的颜色,比如第i种,找到含有该种颜色的珠子a,再从该珠子的下一颗珠子开始找,也是找含有这种颜色的珠子,如果找到了珠子b,且a与b的距离相差小于或者等于M,则说明颜色i不符合条件,记录下来,再继续遍历,直到遍历完所有的颜色。

代码(感谢qdl大佬提供)

//
// Created by qdl on 2021/7/12.
//
#include "vector"
#include "iostream"
#include "map"
using namespace std;
map<int,int>mp;
int main(){
    // 读入
    int N,M,C;
    cin>>N>>M>>C;
    bool bead[N][C]={0};
    // 输入珠子颜色
    for(int i=0;i<N;i++){
        int num;
        cin>>num;
        for(int j =0;j<num;j++){
            int color;
            cin>>color;
            bead[i][color-1]= true;//对含有某种颜色的珠子记录它的序号
        }
    }
    // 遍历所有颜色
    for (int i = 0; i < C; ++i) {
        // 遍历所有珠子
        for (int j = 0; j < N; ++j) {
            if(bead[j][i]==true){//这个判断条件很重要,判断当前珠子是否含有第i种颜色
                int k = j+1;//从这颗珠子的下一颗开始寻找与他含有同种颜色的珠子
                for (; k < j+N -1; ++k) {
                    int second = k % N;//由于手串是环状的,所以需要求余来确定与上一颗珠子的距离
                                       //如果找到了含有同种颜色的珠子并且与上一颗同颜色的珠子的距离小于或者等于M
                    if(bead[second][i]==true&&(k-j+1)<=M){
                                                //记录这种颜色是不符合规则的
                        mp[i] = 1;
                        break;
                    }
                }
                                //此时已经发现了第i种颜色不符合规则,需要跳出遍历珠子的循环
                if(k<j+N-1) break;
            }
        }
    }
    cout<<mp.size();//输出mp里面的颜色的数目
    return 0;
};


发表于 2021-07-13 09:32:06 回复(0)
import java.util.Scanner;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;
public class Main{
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        int n=s.nextInt();
        int m=s.nextInt();
        int c=s.nextInt();
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<n;i++){
            int temp=s.nextInt();
            list.add(new ArrayList<Integer>());
            for(int j=0;j<temp;j++){
                list.get(i).add(s.nextInt());
            }
        }
        HashMap<Integer,PriorityQueue<Integer>> map = new HashMap<Integer,PriorityQueue<Integer>>();
        for(int i=0;i<list.size();i++){
            for(int j=0;j<list.get(i).size();j++){
                int cur=list.get(i).get(j);
                if(!map.containsKey(cur))map.put(cur,new PriorityQueue<Integer>());
                map.get(cur).add(i);
            }
        }
        int count=0;
        for(int a: map.keySet()){
            int x=map.get(a).peek();
            int y=0;
            if(map.get(a).size()<2)continue;
            while(!map.get(a).isEmpty()){
                y=map.get(a).poll();
                if(!map.get(a).isEmpty()&&(map.get(a).peek()-y)<m){
                    count++;
                    break;
                }
            }
            if(map.get(a).isEmpty()){
                if(x+n-y+1<=m){
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}
hashmap存储每种颜色出现的序号,使用priorityqueue存储序号,比较poll出的序号和peek序号之差
发表于 2020-09-12 15:03:45 回复(0)
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
 
typedef long long ll;
 
int n, m, c;
 
ll a[20005];
 
int solve(int id) {
    ll bitmask = (1LL << id);
    int cnt = 0;
    for(int i = 1; i <= m; ++i)
        cnt += ((a[i] & bitmask) != 0);
    if(cnt >= 2)
        return 1;
    for(int j = m + 1; j <= 2 * n; ++j) {
        cnt += ((a[j] & bitmask) != 0);
        cnt -= ((a[j - m] & bitmask) != 0);
        if(cnt >= 2)
            return 1;
    }
    return 0;
}
 
int main() {
    scanf("%d%d%d", &n, &m, &c);
    for(int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        ll tmp = 0LL;
        while(x--) {
            int id;
            scanf("%d", &id);
            tmp |= (1LL << id);
        }
        a[i] = tmp;
        a[i + n] = tmp;
    }
    int ans = 0;
    for(int i = 1; i <= c; ++i)
        ans += solve(i);
    printf("%d\n", ans);
    return 0;
}

颜色数只有50种,分50次扫描即可。每次扫描暴力尺取。
发表于 2020-08-08 23:27:51 回复(0)
import java.util.Scanner;
import java.util.HashMap;
import java.util.HashSet;

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();
        HashMap<Integer, HashSet<Integer>> map=new HashMap<>();
        for(int i=1; i<n+1; i++){
            int colors=scanner.nextInt();
             for(int j=0; j<colors; j++){
                 int cid=scanner.nextInt();
                if(!map.containsKey(cid))
                    map.put(cid, new HashSet<Integer>());
                map.get(cid).add(i);                 
             }
        }
        int ans=0;
        for(int i=0; i<c+1; i++){
            if(count(n, m, map.getOrDefault(i, new HashSet<Integer>())))
                ans++;
        }
        System.out.println(ans);
    }   
    
    private static boolean count(int n, int m, HashSet<Integer> set){
        for(int i:set){
            for(int j:set){
                if(i==j) continue;
                int min=i, max=j;
                if(i>j){
                    int t=max; max=min; min=t;
                }
                if(max-min<=m-1||n-max+min<=m-1)
                    return true;
            }
        }
        return false;
    }        
    
}


以上为Java代码,
易错点,count子函数中,当i>j的时候不能直接交换i和j的值,因为这样会修改set中的内容。
另外,HashMap中的set其实也可以用list代替,用list就可以指定位置了,循环的时候还可以指定i<j之类的,避免同样的颜色对检查两遍。
发表于 2020-04-30 15:53:07 回复(0)
import java.util.Scanner;
public class Test{
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int m=input.nextInt();
        int c=input.nextInt();
        Color color[]=new Color[n];
        for(int i=0;i<n;i++){
            color[i]=new Color();
            color[i].num=i;
            color[i].cNum=input.nextInt();
            color[i].newColor(color[i].cNum,input);
        }
        int[] overNum=new int[c+1];
        for(int i=0;i<n;i++){
            int[] overTwo=new int[c+1];
            int index=i;

            for(int j=0;j<=m;j++,index++){
                if (index<color.length){
                    overTwo=reC(color[index],overTwo);
                }else{
                    index=0;
                    overTwo=reC(color[index],overTwo);
                }
            }
            for(int j=0;j<=c;j++){
                //System.out.println(overTwo[j]);
                if(overTwo[j]>2){
                    overNum[j]=1;
                }
            }
        }
        int xx=0;
        for(int j=0;j<=c;j++){
            if(overNum[j]==1){
                xx++;
            }
        }
        System.out.print(xx);
    }
    public static int[] reC(Color c1,int[] over){
        if(c1.colorArry!=null){
        for(int i=0;i<c1.cNum;i++){

                int c=c1.colorArry[i];
                int temp=over[c];
                temp++;
                over[c]=temp;
            }
        }
        return over;
    }
}
class Color{
    public int num;
    public int cNum;
    public int[] colorArry;
    public void newColor(int cNum,Scanner in){
        if(cNum==0){
            colorArry=null;
            return;
        }
        colorArry=new int[cNum];
        for(int i=0;i<cNum;i++){
            colorArry[i]=in.nextInt();
        }
    }
}
为啥我输出来大于两个的就对了,大于等于两个就不对
发表于 2020-04-08 06:01:54 回复(0)
import java.util.*;
public class ColorMap {     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 res=0;
        Map<Integer,ArrayList<Integer>> map=new HashMap<>();
        for(int i=1;i<n+1;i++){
            int diversity=sc.nextInt();
            if(diversity==0){
                continue;
            }
            for(int j=diversity;j>0;j--){
                int color=sc.nextInt();
                if(map.containsKey(color)){
                    ArrayList<Integer> list=map.get(color);
                    list.add(i);
                }
                else{
                    ArrayList<Integer> list=new ArrayList<>();
                    list.add(i);
                    map.put(color, list);
                }
            }
        }
        for(int i=1;i<=50;i++){
            if(map.containsKey(i)){
                c--;
                ArrayList<Integer> li=map.get(i);
                Iterator<Integer> ltr=li.iterator();
                int fir=ltr.next();
                int now=fir;
                int pre;
                while(ltr.hasNext()){
                    pre=now;
                    now=ltr.next();
                    if((now-pre)<m&&(li.size()-now+fir)<m){
                        res++;
                        break;
                    }
                }
                if(c==0){
                    break;
                }
            }
        }
        System.out.println(res);
        sc.close();     }

}
用Map存储如下键值对:<颜色,拥有该颜色的珠子序号>
用迭代器遍历每个珠子的序号,如果差值小于m或者最后一个和第一个有该颜色的珠子距离差小于m,则不符合要求
(now-pre)<m&&(li.size()-now+fir)<m
发表于 2019-03-15 11:30:09 回复(2)
import java.util.Scanner;
public class Main{
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext())
        {
            int n=sc.nextInt();
            int m=sc.nextInt();
            int c=sc.nextInt();
            int count[]=newint[n];
            int kinds[][]=newint[n][c];
            boolean colors[][]=newboolean[c][n];
            for(int i=0;i<c;i++)
                for(int j=0;j<n;j++)
                    colors[i][j]=false;
            for(int i=0;i<n;i++)
            {
                count[i]=sc.nextInt();
                for(int j=0;j<count[i];j++)
                {
                    kinds[i][j]=sc.nextInt();
                    colors[kinds[i][j]-1][i]=true;
                }
            }
            boolean o[]=newboolean[c];
            for(int i=0;i<c;i++)
            {
                boolean color[]=newboolean[n];
                for(int j=0;j<colors[i].length;j++)
                    color[j]=colors[i][j];
                o[i]=panduan(color,m);
            }
            int res=0;
            for(int i=0;i<c;i++)
                if(!o[i])
                    res++;
            System.out.println(res);
        }
    }
    public static boolean panduan(boolean color[],intm)
    {
        boolean o=true;
        for(int i=0;i<color.length;i++)
        {
            if(color[i])
            {
                for(intk=i+1;k<i+m;k++)
                {
                    int x=k%color.length;
                    if(color[x])
                    {
                        o=false;
                        break;
                    }
                }
            }
        }
        return o;
    }
}
java的常规代码,分析题意,把已有的数据形式kinds转换为利于分析的数据形式colors,判断后统计次数即可。

编辑于 2018-11-30 17:01:13 回复(0)


n,m,c=map(int,input().split())

save=[]
#都放数组里面
for i in range(n):
    save.append([int(i) for i in input().split()][1:])
save
#统计的是颜色!从题目上看到color很小,所以for 按照c的值来.
memo={}

#遍历所有珠子,遇到一个颜色就给他的index存到memo字典里面存成一个数组然后
#当这个数组长度大于1时候判断里面是否有index距离小于m.

count=0
for i in range(1,c+1):
    tmp=[]#记录颜色i的index.
    for j in range(n):
        if i in save[j]:
            tmp.append(j)
        if len(tmp)>=2  :
            if  tmp[-1]-tmp[-2]<m or n+tmp[0]-tmp[-1]<m:
                count+=1
                break
print(count)
#通过了


发表于 2018-10-02 20:44:41 回复(2)
importjava.util.ArrayList; import java.util.HashMap; import java.util.Hashtable; import java.util.Scanner;  public class Main {public static void main(String[] args){
        Scanner sc = newScanner(System.in);  int n = sc.nextInt();  int m = sc.nextInt();  int c = sc.nextInt();   int[][] a = new int[c+1][n];  int[] k = new int[c+1];   for(inti =0; i<= c;i++){
            k[i] =0;  } for(inti =1; i <= n;i++){ intnum_i = sc.nextInt();  for(intj =0; j < num_i;j++){ intcolor = sc.nextInt();  int x = k[color];  a[color][x] = i;  k[color]++;  }
        } for(inti =1; i <= c;i++){ for(intj =0; j < k[i];j++)
                System.out.print(a[i][j] + " ");  System.out.println();  } intillegel_color =0;  for(inti =1;i <= c;i++){
            bgm:for(intj =0; j < k[i];j++){ for(intp = j +1; p < k[i];p++){ if(a[i][p] - a[i][j] < m || n - Math.max(a[i][p],a[i][j]) + Math.min(a[i][p],a[i][j]) < m){
                        System.out.println("i = "+ i);  System.out.println("p = "+ p);  illegel_color++;  break bgm;  }
                }
            }
        }
        System.out.println(illegel_color);  }
}

发表于 2018-09-27 22:33:31 回复(1)