首页 > 试题广场 >

手串

[编程题]手串
  • 热度指数：2178 时间限制：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颗串珠是透明的。
算法知识视频讲解
添加回答
牛客*******号头像 牛客*******号
#include <iostream>
#include <vector>
#include <set>

using namespace std;
int main(){
    int n, m, c;
    cin >> n >> m >> c;
    vector<int> first(c+1, 0);  //记录颜色第一次出现的珠子序号
    vector<int> record(c+1, 0);  //记录颜色出现的珠子序号
    set<int> res;  //记录不符合要求的颜色的序号
    for(int i=1; i<=n; i++)
    {
        int num; cin >> num;  //珠子的颜色数量
        for(int j=0; j<num; j++)
        {  //遍历每个颜色
            int tmp; cin >> tmp;
            if(record[tmp] == 0)
            {
                record[tmp] = i;   //初始化颜色出现的位置
                first[tmp] = i;   //
            }
            else
            {
                if(i-record[tmp]<m)   //出现位置的差小于m个
                {
                    res.insert(tmp);  //记录这种颜色，不符合条件
                }
                else
                {
                    record[tmp] = i;   //符合条件就更新
                }
            }
        }
    }
    //对比颜色出现的最后一次珠子位置和出现第一次位置的距离差
    for(int i=1; i<=c; i++)
    {
        int a = record[i];
        int b = first[i];
        if(n-a+b <m)
            res.insert(i);
    }
    cout << res.size();  //返回多少个颜色不符合
    return 0;
}
发表于 2018-08-24 18:33:40 回复(0)
zhangfeng42头像 zhangfeng42 

	##Python





	##用一个窗口滑动来看目前的球，dict记录哪些颜色已经超过数量





	





	import sys





	 





	def checkSeq(seq, m, c):





	    period =[ball for ball ins eq[0:m]]





	    colors =[0 for _ in range(c)]





	    for ball in period:





	        for color in ball:





	            colors[color-1] +=1





	    ret ={}





	    for i in range(len(seq)):





	        for cid in range(len(colors)):





	            if colors[cid] >1:





	                ret[cid] =True





	        for color in period[0]:





	            colors[color-1] -=1





	        period.pop(0)





	        add =(i+m)%(len(seq))





	        for color in seq[add]:





	            colors[color-1] +=1





	        period.append(seq[add])





	    print(len(ret.keys()))





	         





	 





	if__name__ =='__main__':





	    stat =sys.stdin.readline().split()





	    N =int(stat[0])





	    M =int(stat[1])





	    M =M %N





	    C =int(stat[2])





	     





	    seq =[]





	    for i in range(N):





	        line =sys.stdin.readline().split()





	        line.pop(0)





	        ball =[int(x) for x inline]





	        seq.append(ball)





	    checkSeq(seq, M, C)
发表于 2019-03-15 15:00:15 回复(0)
C/C++
yang15671头像 yang15671
//    暴力求解。。
// 提交时间：2020-09-04 语言：C 运行时间： 274 ms 占用内存：2524K 状态：答案正确
#include <stdio.h>
int main(){
    int i,j,t,n,m,c;
    scanf("%d%d%d",&n,&m,&c);
    int num[n];
    // int b[n][c];
    int b[n+m-1][c];    
    for(i=0;i<n;i++){
        for(j=0;j<c;j++){
            b[i][j]=0;
        }
    }
    int a;
    for(i=0;i<n;i++){                    //这一步把输入颜色变成n*c的二维矩阵，且矩阵中每一行对各种颜色个数做了统计，
        scanf("%d",&num[i]);            //由于每个珠子每种颜色最多只有一种，因此这里把输入变成只有0和1的二维矩阵
        if(num[i]>0){            
            for(j=0;j<num[i];j++){
                scanf("%d",&a);
                b[i][a-1]++;
            }
        }        
    }
    for(i=0;i<m-1;i++){                    //把环变成串，串长度为n+m-1，把前m-1补到末尾
        for(j=0;j<c;j++){
            b[n+i][j]=b[i][j];
        }
    }    
    
    int temp[c];
    for(j=0;j<c;j++){                    //统计窗口内哪个颜色存在重复，并记录重复个数
        temp[j]=0;
    }    
    
    for(i=0;i<n;i++){                    //从第一个珠子开始对到n个珠子，以每个珠子为起点，加窗口分析，窗长m //前面通过增加串的长度，把环拆成串分析
        int sum[c];
        for(j=0;j<c;j++){
            sum[j]=0;
        }
        for(j=0;j<c;j++){            
            for(t=0;t<m;t++){
                sum[j]+=b[i+t][j];                    
            }
            if(sum[j]>1){
                temp[j]++;
            }
        }
    }
    
    int count=0;
    for(j=0;j<c;j++){
        if(temp[j]>1){
            count++;
        }            
    }
    printf("%d",count);
    return 0;
}
编辑于 2020-09-04 16:39:51 回复(0)
沙漠的猫头像 沙漠的猫 
def fun(params, colors):
    result = {}
    # 初始化合法颜色字典
    for i in range(params[2]):
        result[i + 1] = 1
    # 构造环形染色列表
    for i in range(params[1] - 1):
        colors.append(colors[i])
    for i in range(params[0]):
        dic = {}
        for j in range(i, i + params[1]):
            for color in colors[j]:
                if color not in dic:
                    dic[color] = 0
                elif color == 0:
                    pass
                else:
                    if color in result:
                        result[color] = 0
    return result
 
 
if __name__ == "__main__":
    params = [int(x) for x in input().split()]
    colors = []
    for i in range(params[0]):
        color_list = [int(x) for x in input().split()]
        color_list.pop(0)
        colors.append(color_list)

    result = fun(params, colors)
    for res in result.keys():
        if result[res] == 0:
            count += 1
    print(count)
用字典做哈希，时间可满足题目要求

发表于 2019-08-08 16:54:33 回复(0)
yr201904050957596头像 yr201904050957596 
# 简单的Python方法，全通过，合理利用字典
n, m, c = [int(x) for x in input().split()]
dic = {}
result = []
for i in range(n):
    temp = [int(x) for x in input().split()]
    if temp[0] == 0:
        continue
    for j in range(1, temp[0] + 1):
        if temp[j] in dic:
            tt = dic[temp[j]]
            if i - tt[-1] <= m - 1 or (n - i - tt[0]) <= m - 1:
                if temp[j] not in result:
                    result.append(temp[j])
            dic[temp[j]].append(i)
        else:
            dic[temp[j]] = [i]

print(len(result))

发表于 2019-04-14 01:03:01 回复(1)
牛客8046156号头像 牛客8046156号
n, m, c = [int(e) for e in input().split(' ')]
group = {}
groupmin = {}
for i in range(n):
    tempList = [int(e) for e in input().split(' ')]
    for j in range(tempList[0]):
        if tempList[j+1] not in group:
            group[tempList[j+1]] = [i+1]
            groupmin[tempList[j+1]]= 40000
        else:
            groupmin[tempList[j+1]] = min(groupmin[tempList[j+1]],i+1-group[tempList[j+1]][-1])
            group[tempList[j+1]].append(i+1)
result = 0
for i in group.keys():
    if i!=0 and  groupmin[i]<40000:
        if min(groupmin[i],n-group[i][0]+group[i][-1])<m:
            result+=1
print(result)

发表于 2019-02-11 13:06:59 回复(0)
原果头像 原果 
# 队列实现，注意取模就好了
n, m, c = [int(e) for e in input().split(' ')]

list = []

for i in range(n):
    list.append([int(e) for e in input().split(' ')])
_dict = {}
for i in range(1, c + 1):
    _dict[i] = 0
left = 0
right = m - 1
count = 0
max = 99999
for i in range(m):
    for j in range(1, len(list[i])):
        if _dict[list[i][j]] != max:
            _dict[list[i][j]] += 1
            if _dict[list[i][j]] > 1:
                _dict[list[i][j]] = max
                count += 1
for i in range(n - 1):
    for j in range(1,len(list[left])):
        if _dict[list[left][j]] != max:
            _dict[list[left][j]] -= 1
    left = (left + 1) % n
    right = (right + 1) % n
    for j in range(1, len(list[right])):
        if _dict[list[right][j]] != max :
            _dict[list[right][j]] += 1
            if _dict[list[right][j]] > 1:
                _dict[list[right][j]] = max
                count += 1
print(count)


发表于 2018-08-09 01:51:36 回复(0)
白亦非w头像 白亦非w
完美AC，运行时间64ms。
用字典来存储不同类颜色的位置。
判断同一颜色任意两个珠子距离是否小于m。 
n, m, c = list(map(int,input().split()))
col = {}
for i in range(n):
    t = list(map(int,input().split()))
    if t[0] !=0:
        for j in range(t[0]):
            if t[j+1] not in col:
                col[t[j+1]] = []
            col[t[j+1]].append(i)
             
counter = 0
for i in col:
    if len(col[i]) >1:
        for j in range(0,len(col[i])-1):
            if col[i][j+1]-col[i][j]<m&nbs***bsp;col[i][j]+n-col[i][j+1]<m:
                counter += 1
                break
print(counter)


发表于 2020-03-31 11:34:30 回复(0)
Yansz头像 Yansz 
n, m, c = list(map(int,input().split()))
dic = {}
result = []
for i in range(n):
    col = list(map(int,input().split()))
    for j in range(1,col[0]+1):
        try:    #创建颜色字典
             temp = dic[col[j]]  # temp表示的是颜色col[j]出现的位置列表list               
                        if i-temp[-1] <= m-1 or (n-i-temp[0]) <= m-1: #判断上次出现该颜色的珠子序号和本次的序列差是否小于m-1
                if col[j] not in result:
                    result.append(col[j])
            dic[col[j]].append(i)
        except:
            dic[col[j]] = [i]
print(len(result))

发表于 2019-08-09 14:27:15 回复(0)
孤独的西贝先森头像 孤独的西贝先森
#运用栈维护m个珠子并且用hashmap保存颜色个数，同时环问题可在数组尾部添加m-1个元素即可展成链式问题。 

n, m, c = list(map(int, input().split()))
all_color = []
for i in range(n):
    allinfo = list(map(int, input().split()))
    if allinfo[0] == 0:
        colors = []
    else:
        colors = allinfo[1:]
    all_color.append(colors)
all_color = all_color + all_color[:m-1]
 
res = 0
hash_map = dict()
stack = all_color[:m]
error_color = set()
for i in range(m):
    for j in stack[i]:
        if j not in hash_map:
            hash_map[j] = 1
        else:
            hash_map[j] += 1
            error_color.add(j)
for i in range(m, n+1):
    pre = stack.pop(0)
    for color in pre:
        hash_map[color] += -1
    cur = all_color[i]
    stack.append(cur)
    for color in cur:
        if color not in hash_map&nbs***bsp;hash_map[color] == 0:
            hash_map[color] = 1
        else:
            hash_map[color] += 1
            error_color.add(color)
print(len(error_color))
    

    
发表于 2021-03-06 12:36:14 回复(0)
八奈見杏菜头像 八奈見杏菜
首先手串是个环，所以先扩展一倍区间。先把每个珠子的颜色信息用vector存起来，然后用two pointers（又名尺取法）去遍历区间，在遍历过程中如果(r-l+1<=m),就要将新的a[r]的信息加入进来，加入的过程中判断是否ans++，条件就是1.该种颜色之前没被统计到有问题2.不是无色3.在当前序列中已经出现过了。如果（r-l+1>m)，就要删去a[l]的信息。具体实现见代码 
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int main(){
	int n,m,c,num,color;
	vector<int> a[20005];
	int b[90]={0},v[90]={0};
	cin>>n>>m>>c;
	for (int i=1; i<=n; i++){
		scanf("%d",&num);
		for (int j=0; j<num; j++){
			scanf("%d",&color);
			a[i].pb(color);
			a[i+n].pb(color);
		}
	}
	int l=1,r=1,ans=0;
	while (l<=n+m-1 && r<=n+m-1){
		  if ((r-l+1)<=m){
		  	 for (int i=0; i<a[r].size(); i++){
		  	     if (v[a[r][i]] && a[r][i]!=0 && !b[a[r][i]]){
		  	     	ans++; b[a[r][i]]=1;
				 }
				 v[a[r][i]]++;
			 }
		  	 r++;
		  }
		  else{
		  	 for (int i=0; i<a[l].size(); i++)
		  	     v[a[l][i]]--;
		  	 l++;
		  }
	}
	cout<<ans<<endl;
	return 0;
} 

发表于 2021-01-23 15:39:42 回复(0)
_Chaojun_头像 _Chaojun_ 
while True:
    try:
        m, n, c = list(map(int, input().split()))
        nums_list = list()
        for i in range(m):
            nums_list.append(list(map(int, input().split())))
            
        for i in range(n):
            nums_list.append(nums_list[i])
        repeat_color = list()
        for i in range(c):
            repeat_color.append(0)
        for i in range(0, n, m):
            color_dict = dict()
            sub_nums = nums_list[i:i+m]
            for perle in sub_nums:
                perle.pop(0)
                for j in perle:
                    if j in color_dict.keys():
                        color_dict[j] += 1
                    else:
                        color_dict[j] = 1
            for key, value in color_dict.items():
                if value > 1:
                    repeat_color[key-1] = 1
        sum_repeat = sum(repeat_color)
        print(sum_repeat)
    except:
        break
求大佬指点下，这代码到底哪错了，跑测试用例都可以，一提交就报错
发表于 2020-08-22 21:16:36 回复(0)
QING0304头像 QING0304 
n,m,c = map(int, input().split())
color_list = []
for i in range(n):
    color_list.append(list(map(int, input().split())))

color_num = []
for i in range(c):
    color_num.append([])

for i in range(n):
    color = color_list[i]

    if len(color) == 1:
        continue
    co = color[1:]
    for j in co:
        color_num[j-1].append(i+1)

number = 0
for i in range(c):
    if len(color_num[i]) == 1:
        continue

    for j in range(len(color_num[i])-1):
        init_number = number

        for t in range(1, len(color_num[i])-j):

            res = abs(color_num[i][j+t] - color_num[i][j])

            if res < m or res >= (n-1):

                number += 1
                break
        if number > init_number:
            break
print(number)

发表于 2018-08-23 12:14:14 回复(0)
Slun夜心头像 Slun夜心 
if __name__ == "__main__":
    n,m,c = map(int,input().strip().split())      
    xlist = [list(map(int,input().strip().split())) for i in range(n)]
    result = 0
    cdict = dict(zip([i for i in range(1,c+1)],[0]*c))
    for i in range(m):
        for j in range(xlist[i%n][0]):
            cdict[xlist[i%n][j+1]] += 1
    ckeys = list(cdict.keys())
    for k in ckeys:
        if cdict[k] > 1:
            result += 1
            del cdict[k]
    for i in range(n-1):
        for j in range(xlist[i%n][0]):
            if xlist[i%n][j+1] in cdict:
                cdict[xlist[i%n][j+1]] -= 1
        for j in range(xlist[(m+i)%n][0]):
            if xlist[(m+i)%n][j+1] in cdict:
                cdict[xlist[(m+i)%n][j+1]] += 1
        ckeys = list(cdict.keys())
        for k in ckeys:
            if cdict[k] > 1:
                result += 1
                del cdict[k]

    print(result)

发表于 2018-08-21 15:50:49 回复(0)
Python
siyuan_see头像 siyuan_see 
n, m, c = [int(char) for char in raw_input().split()]

A = []
for i in range(n):
    A.append([int(char) for char in raw_input().split()])


falseColor = {}
for i in range(1, c+1):
    falseColor[i] = 0

oldL = 0
oldR = m
countColor = {}
for i in range(1, c+1):
    countColor[i] = 0

for number in range(oldL, oldR):
    hand = A[number]
    for i in range(1, hand[0]+1):
        countColor[hand[i]] += 1

for key in countColor:
    if countColor[key] > 1:
        falseColor[key] = 1

for left in range(1, n):

    hand = A[left-1]
    for i in range(1, hand[0]+1):
        countColor[hand[i]] -= 1

    hand = A[(left+m-1)%n]
    for i in range(1, hand[0]+1):
        countColor[hand[i]] += 1

    for key in countColor:
        if countColor[key] > 1:
            falseColor[key] = 1

print(sum(falseColor.values()))
发表于 2018-08-13 17:19:42 回复(0)
灰灰_123头像 灰灰_123 
#include <iostream>
#include <vector>
using namespace std;
void update(vector<vector<int>> &color_vec,vector<int> onebead,int num)
{
    //color_vec[i]表示第i种颜色出现在了哪些珠子上
    if(onebead.size()==0)
        return;
    int color;
    for(int i=0;i<onebead.size();i++)
    {
        color=onebead[i];
        if (color_vec[color].size()==0)
        {
            color_vec[color].emplace_back(num);
        }
        else if(color_vec[color][color_vec[color].size()-1]!=num)
        {
            color_vec[color].emplace_back(num);
        }
    }
    return;
}
bool judge(vector<int> onecolor,int n,int m)
{
    //判断一种颜色所出现在的所有珠子中，相邻两颗的序号是否满足小于等于m-1，即在连续m颗
    //珠子里面至少出现了两次
    bool res=false;
    int num=onecolor.size();
    for(int i=1;i<num;++i)
    {
        if(onecolor[i]-onecolor[i-1]<=m-1)
            {
                res=true;
                break;
            }
        if(i==num-1)
        {
            int a=n-onecolor[i]+1;
            int b=onecolor[0];
            if(a+b<=m)
            {
                res=true;
                break;
            }
        }
    }
    
    return res;
}
int main()
{
    int n,m,c;
    cin>>n>>m>>c;
    vector<vector<int>> color_vec(c+1);
    for (int i=0;i<n;++i)
    {
        vector<int> onebead;
        int num;cin>>num;
        for(int j=0;j<num;++j)
        {
            int temp;cin>>temp;
            onebead.emplace_back(temp);
        }
        update(color_vec,onebead,i+1);
    }
    int res=0;
    for(int i=1;i<=c;++i)
    {
        bool flag=judge(color_vec[i],n,m);
        if (flag==true)
            res++;
    }
    cout<<res<<endl;
    return 0;
}
发表于 2018-06-03 11:47:53 回复(0)
牛客1659416头像 牛客1659416 

	#include <iostream>





	#include <vector>





	 





	usingnamespacestd;





	 





	intmain()





	{





	    intn,m,c;





	    while(cin>>n>>m>>c)





	    {





	        vector<vector<int> > vv;





	        vv.resize(n+m-1);





	        for(inti=0; i<=n-1; i++)





	        {





	            intnum_i;





	            cin>>num_i;





	            vv[i].push_back(num_i);





	            for(intj=1; j<=num_i; j++)





	            {





	                inttemp;





	                cin>>temp;





	                vv[i].push_back(temp);





	            }





	        }





	        for(inti=n; i<n+m-1; i++)





	        {





	            vv[i]=vv[i-n];





	        }





	        intsum=0;





	        for(inti=1; i<=c; i++)





	        {





	            intsign=0;





	            for(intj=0; j<=n-1; j++)





	            {





	                intcounts=0;





	                for(intk=j; k<=j+m-1; k++)





	                {





	                    for(intl=1; l<=vv[k][0]; l++)





	                    {





	                        if(vv[k][l]==i)





	                            counts+=1;





	                    }





	                }





	                if(counts>=2)





	                {





	                    sign=1;





	                    break;





	                }





	            }





	            if(sign==1)





	                sum+=1;





	        }





	        cout << sum << endl;





	    }





	    return0;





	}

发表于 2018-03-23 16:19:14 回复(0)
just_sort头像 just_sort
//模拟题没啥说的。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
vector <int> v[maxn];
int n, m, c;
int find_key(int color, int key){
    for(int i=0;i<v[color].size();i++){
        if(v[color][i]==key) return 1;
    }
    return 0;
}
int main(){
    while(~scanf("%d%d%d",&n,&m,&c)){
        for(int i=0;i<maxn;i++) v[i].clear();
        for(int i=1;i<=n;i++){
            int num,x;
            scanf("%d",&num);
            while(num--){
                scanf("%d",&x);
                v[x].push_back(i);
            }
        }
        for(int i=1;i<=c;i++){
            if(v[i].empty()) continue;
            vector <int> temp;
            for(int j=0; j<v[i].size(); j++) temp.push_back(v[i][j]);
            for(int j=0;j<temp.size();j++) v[i].push_back(temp[j]+n);
        }
//        for(int i=1;i<=c;i++){
//            if(v[i].empty()) continue;
//            cout<<v[i].size()<<endl;
//            for(int j=0;j<v[i].size();j++) cout<<v[i][j]<<" ";
//            cout<<endl;
//        }
        int ans = 0;
        for(int i=1;i<=c;i++){
            if(v[i].empty()) continue;
            int l=1,r=1,sum=find_key(i,1);
            for(;l+m<=n*2;l++){
                while(r-l+1<m){
                    ++r;
                    sum+=find_key(i,r);
                }
                if(sum>1){
                    ans++;
                    break;
                }
                sum-=find_key(i,l);
            }
        }
        printf("%d\n", ans);
    }
}

发表于 2018-01-01 20:02:34 回复(0)
提交观点

问题信息

模拟 字符串 算法工程师 2018 哈希 字节跳动 查找
上传者：小小
难度：
18条回答 4740浏览

热门推荐

通过挑战的用户

相关试题

手串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号