今日头条2018校园招聘后端方向-编程题一

发表于 | 分类于 ，

题目

描述

有一条手链上有 n 个串珠,每个串珠有不同的颜色,也可以是无色,
颜色一共有 c 种,但是有个规定,在连续的 m 个串珠里颜色不能能重复,
求重复的颜色有多少

输入

第 1 行 n,m,c
第 2 到 n+1 行,
每行第一个数为串珠的颜色数 ci,
后跟 ci 个数为串珠的颜色
1<=n<=10000,1<=m<=1000,1<=c<=50

输出

重复的颜色的种类数

Example

Input

5 2 3
3 1 2 3
0
2 2 3
1 2
1 3

Output

2

题解

滑动窗口

  • 颜色转为二进制存储
  • 使用滑动窗口遍历,窗口大小为 m,判断窗口内的重复情况
  • 时间复杂度 O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>

#define ll long long

using namespace std;

int n,m,c,tc,tt,bad;
ll balls[10000];

int main(){
    cin>>n>>m>>c;
    memset(balls,0,sizeof balls);
    for(int i=0;i<n;++i)
    {
        scanf("%d",&tc);
        for(int j=0;j<tc;++j)
        {
            scanf("%d",&tt);
            balls[i]|=(1<<tt);
        }
    }
    if(m==1) cout<<0;
    else
    {
        ll badCF=0,flag=0;
        for(int l=0,r=0;m>n?r<n:l<n;++r%=n)
        {
            if((r-l+n)%n+1>m)
                flag^=balls[l],++l;
            badCF|=(flag&balls[r]);
            flag^=balls[r];
        }
        bad=0;
        while(badCF)
            badCF&=(badCF-1),++bad;
        cout<<bad;
    }
}