18936 手串

18936 手串

字节跳动2018校招Android方向（第二批） 
作为一个手串艺人，有金主向你订购了一条包含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)
输出格式
一个非负整数，表示该手链上有多少种颜色不符需
输入样例
5 3 3
3 1 2 3
0
0
1 1
1 2
输出样例
2

解题思路：当你不知道如何下手时，先思考人是怎么处理这个问题的，将人处理问题的方法实现出来就是“模拟”，在模拟算法的基础上进行优化。

对样例进行人工法：先检查颜色1，我们发现颜色1出现在1,4两个位置，在环结构距离正好是3，不符合要求。颜色2:出现在位置1和5，在环结构同样不符合要求。颜色3只出现一次，符合要求。

手写一个更高端点数据。

10 3 6
3 4 3 1 
5 1 4 2 3 5 
1 3 
5 6 5 3 4 1 
3 6 4 3 
6 6 5 2 4 3 1 
4 1 2 5 6 
0 
3 6 4 2 
5 5 4 3 1 2 

人眼扫描颜色1的位置：1,2,4,6,7,10，不符合，人眼继续扫描颜色2位置：.................

（一）模拟法

读入所有数据，可以存储在一个a[10005][55]数组里，颜色c小于50，所以枚举每一种颜色，在a数组中检查这种颜色出现的全部位置，检查位置是否满足条件，时间复杂度O(c*n*c)，按题目数据，这种方法应该可以AC。

这类问题，在检查位置时，新发现的位置只需和它前一个位置进行比对，如果不符合要求循环可以立刻停止。只有最后一个位置需要和它前一个，以及第一个位置进行两次比较，问题在于处理过程中并不知道当前找到是不是最后一个，所以对于每一个新发现位置，都和第一个进行环的距离计算。

（二）进阶算法

利用数组的随机存取特性，当颜色x出现时，用数组记录其下标。此处定义了两个数组pre数组记录x颜色前一次出现的下标，first数组记录颜色第一次出现的下标。这样一边读数据一边检查，时间复杂度O（c*n），具体思路可看代码。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,m,c,pre[55],first[55],v[55],ans=0;
int main() /**< pre数组记录第i颜色前一次出现的位置，first数组记录第一次出现的位置 */
{ios::sync_with_stdio(0),cin.tie(0);int i,j,x,len;cin>>n>>m>>c;for(i=1; i<=n; i++){cin>>len;for(j=1; j<=len; j++){cin>>x;if(pre[x]==0) /**< x颜色首次出现 */first[x]=i;else if(i-pre[x]<m||first[x]+n-i<m) /**< 检查位置i与前一次出现，和第一次出现位置的距离 */v[x]=1;/**< 将x颜色标记为不符合 */pre[x]=i;}}for(i=1;i<=c;i++) /**< 循环找到所有不符合要求颜色 */ans+=v[i];cout<<ans;return 0;
}