手串繰り返し色判定
3948 ワード
手文字列色判定テーブル 問題説明 入出力説明 例 コード実装
問題の説明
手串芸能人として、金主がn個の雑色のビーズを含む手串を注文しました.各ビーズは無色か、いくつかの色を塗っています.手串の色をそんなに単調に見せるために、金主は、手串の任意の色(無色を含まない)を、任意の連続したm個のビーズの中に1回だけ現れるように要求した(ここで手串は環状であることに注意).手串の色は全部でc種類あります.次に、n個のビーズの手串に、各ビーズに含まれる色でそれぞれどれらがあるかをタイミング針順に教えてあげます.この手の串に何色が要求に合わないか判断してください.すなわち、任意の連続m個のビーズに少なくとも2回現れた色が何色あるかを尋ねる.
入出力説明
1行目にn,m,cの3つの数を入力し、スペースで区切ります.(1<=n<=10000,1<=m<=1000,1<=c<=50)次のn行の各行の最初の数num_i(0<=num_i<=c)は、i番目のビーズが何色あるかを示す.次にnum_を順番に読み込みますi番目の柱にx番目の色(1<=x<=c)が含まれていることを示すi個の数字
出力の説明:チェーンに何色が必要とされていないかを示す非負の整数.
例
入力例1:5 2 3 3 1 2 3 0 2 3 1 1 3
出力例1:2
例説明1:1番目の色は1番目のビーズに現れ、ルールと衝突しない.第2の色はそれぞれ第1,3,4ビーズに現れ,第3ビーズは第4ビーズに隣接しているため,要求に合わない.3つ目の色はそれぞれ1、3、5つ目のビーズ、5つ目のビーズの次が1つ目なので、要求に合いません.合計2色の分布に問題があります.ここで2番目のビーズは透明です.
コード実装
問題の説明
手串芸能人として、金主がn個の雑色のビーズを含む手串を注文しました.各ビーズは無色か、いくつかの色を塗っています.手串の色をそんなに単調に見せるために、金主は、手串の任意の色(無色を含まない)を、任意の連続したm個のビーズの中に1回だけ現れるように要求した(ここで手串は環状であることに注意).手串の色は全部でc種類あります.次に、n個のビーズの手串に、各ビーズに含まれる色でそれぞれどれらがあるかをタイミング針順に教えてあげます.この手の串に何色が要求に合わないか判断してください.すなわち、任意の連続m個のビーズに少なくとも2回現れた色が何色あるかを尋ねる.
入出力説明
1行目にn,m,cの3つの数を入力し、スペースで区切ります.(1<=n<=10000,1<=m<=1000,1<=c<=50)次のn行の各行の最初の数num_i(0<=num_i<=c)は、i番目のビーズが何色あるかを示す.次にnum_を順番に読み込みますi番目の柱にx番目の色(1<=x<=c)が含まれていることを示すi個の数字
出力の説明:チェーンに何色が必要とされていないかを示す非負の整数.
例
入力例1:5 2 3 3 1 2 3 0 2 3 1 1 3
出力例1:2
例説明1:1番目の色は1番目のビーズに現れ、ルールと衝突しない.第2の色はそれぞれ第1,3,4ビーズに現れ,第3ビーズは第4ビーズに隣接しているため,要求に合わない.3つ目の色はそれぞれ1、3、5つ目のビーズ、5つ目のビーズの次が1つ目なので、要求に合いません.合計2色の分布に問題があります.ここで2番目のビーズは透明です.
コード実装
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
/**
*
*/
/**
* @author Administrator
* @date 2018 8 25
*/
public class Main2 {
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int m=in.nextInt();
int c=in.nextInt();
HashMap> map=new HashMap<>();
for(int i=0;iint num_i=in.nextInt();
for(int j=0;jint key=in.nextInt();
if(map.containsKey(key))
{
map.get(key).add(i);
}
else
{
ArrayList list=new ArrayList<>();
list.add(i);
map.put(key, list);
}
}
}
int count=0;
for(Integer key:map.keySet())
{
ArrayList list=map.get(key);
if(list!=null&&list.size()>1)
{
int len=list.size();
int flag=0;
for(int i=0;i1;i++)
{
if(list.get(i+1)-list.get(i)break;
}
}
if(flag==1)
count++;
}
}
System.out.println(count);
}
}