时间限制:C/C++ 1秒,其他语言2秒空间限制:C/C++ 64M,其他语言128M
链接:https://www.nowcoder.com/questionTerminal/0bb1fad52f474bdaa4d7636ca3a98244
来源:牛客网


首先遇到这一题是在字节跳动的一个前端试卷里,看上去不难,似乎就是一个数组+简单查找的问题。但是我一直报错,测试样例过了,提交代码就一直0分。

气死了,遂上CSDN查找题解,作为一个底层C选手,让我找到了一篇C++的题解,看懂之后,这不跟我的思路一样吗?这位博主提供了一个C++的AC代码,但我发现缺少环的判断啊,但是——当我把他的代码CTRL C+V到答题区域之后,测试样例没过,提交却AC了?

最后发现是题错了!题目要求注意这里手串是一个环形,字节你是把它吃了吗?去掉环的判断就能AC了,然而连测试样例都过不了你是认真的吗?

练习结束之后我不甘心,上牛客网搜这道题,搜出一毛一样的题之后提交了我的带环判断 的代码,顺利AC,再找到那位博主的代码CTRL C+V,就0分。

我还是不甘心,遂把卷子翻出来重做,删掉我最后的环形判断的代码,嘿,AC了。

我宝贵的一个半小时就浪费在一个错题上!!看到这篇博客的小伙伴们别再踩坑了,呜呜呜。


题目描述

作为一个手串艺人,有金主向你订购了一条包含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比较大,c比较小,可以定义一个a[n][c]的数组,表示第c号颜色是否存在于第n颗珠子上。存在则为1,不存在则为0。

当然,如果你喜欢,可以定义为a[c][n],含义一样。

接着就是一个用一个数组来存对于每个颜色的珠子的位置,我的代码里是b[]

接下来就是条件判断:b[i + 1] - b[i] < m表示它在m颗内有重复出现,我们提前定义一个flag,表示这个颜色是否违规。(环判断要用上)

违规一经发现,就要被抓走(break

环判断:对于最后出现位置b[k](k是b的长度),判断它离尾部的距离是否小于m,如果小于m,看b[1]出现的位置。

如果b[k] + m > n && b[1] < m - (n - b[k]) && flag == 0则表示在首位出游违规现象发生,抓走!


题解

#include <stdio.h>
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;
            }

        }
        if (k != 1)
        {
            for (i = 1; i < k; i++)
            {
                if ( b[i + 1] - b[i] < m)
                {
                    cnt++;
                    flag = 1;
                    break;
                }

            }
            /* */
            if (b[k] + m > n && b[1] < m - (n - b[k]) && flag == 0)
            {
                cnt++;
            }

        }

    }

    printf("%d", cnt);
    return 0;
}

友好起见,在此还是附上前文提到的那位C++的AC选手,注意只在字节(今日头条)笔试题里有效。
当然我不是鼓励读者去复制代码!
链接:今日头条笔试之手串问题