作为一个手串艺人,有金主向你订购了一条包含n个杂色串珠的手串——每个串珠要么无色,要么涂了若干种颜色。为了使手串的色彩看起来不那么单调,金主要求,手串上的任意一种颜色(不包含无色),在任意连续的m个串珠里至多出现一次(注意这里手串是一个环形)。手串上的颜色一共有c种。现在按顺时针序告诉你n个串珠的手串上,每个串珠用所包含的颜色分别有哪些。请你判断该手串上有多少种颜色不符合要求。即询问有多少种颜色在任意连续m个串珠中出现了至少两次。
作为一个手串艺人,有金主向你订购了一条包含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 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颗串珠是透明的。
import java.util.*; public class Main{ public static void main(String[] args){ Scanner input = new Scanner(System.in); int numOfRing = input.nextInt(); int numOfNear = input.nextInt(); int numOfColor = input.nextInt(); Map<Integer, List<Integer>> map = new HashMap<>(); for(int i = 0; i < numOfRing; i++){ int length = input.nextInt(); for(int j = 0; j < length; j++){ int color = input.nextInt(); if(!map.containsKey(color)){ List<Integer> list = new ArrayList<>(); list.add(i); map.put(color, list); }else{ List<Integer> list = map.get(color); list.add(i); } } } int sum = 0; int[] flag = new int[numOfColor]; for(int i = 0; i < numOfColor; i++){ List<Integer> list = map.get(i+1); if(list != null){ int length = list.size(); for(int j = 1; j < length; j++){ if(list.get(j) - list.get(j-1) < numOfNear){ flag[i] = 1; } } if(list.get(0) - list.get(length-1) + numOfRing < numOfNear){ flag[i] = 1; } } if(flag[i] == 1){ sum++; } } System.out.println(sum); } }
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt();//用户的数量 int m = sc.nextInt(); int c = sc.nextInt(); int[][] arr = new int[n][c]; for (int i = 0; i < n; i++) { int temp= sc.nextInt(); for (int j = 0; j <temp; j++) { int temp1 = sc.nextInt(); arr[i][temp1-1]=temp1;//有颜色的位置元素为1; } } int res=0; for (int i = 0; i <c; i++) {//按列查询,总共C列 for (int j = 0; j <arr.length-1; j++) {//查询每列的具体元素 if(arr[0][i]==arr[arr.length-1][i]){//判断首尾是否相同 res++; break; } if(arr[j][i]!=0){ // pre=j; for (int k = j+1; k <arr.length-1; k++) {//从当前位置的下一个位置开始查找 if(arr[k][i]!=0){//如果该位置元素不为1,且位置下标<前一不为0元素的下标+m; if(k<j+m){ //则不满足要求;结果+1; res++; j=arr.length-1;//直接遍历下一列; break; } } } } } } System.out.println(res); }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int c = sc.nextInt(); int[][] arr = new int[n][c]; int temp, lie; for (int i = 0; i < n; i++) { temp = sc.nextInt(); while (temp-- != 0) { lie = sc.nextInt(); arr[i][lie - 1] = lie; } } int count = 0; int pre; outer: for (int i = 0; i < c; i++) { pre = -1; for (int j = 0; j < n; j++) { if (arr[j][i] != 0 && (j-pre>m || pre == -1)) { pre = j; }else if(arr[j][i] != 0 && j - pre < m){ count++; continue outer; } if (j == n - 1 && j - pre < m - 1) { temp = 0; while (j - pre + temp < m - 1) { if (arr[temp][i] != 0){ count++; break; } temp++; } } } } System.out.println(count); } }
#include <iostream> #include <string> #include <map> #include <vector> #include <functional> #include <algorithm> #include <stack> #include <queue> #include <sstream> #include <set> #include <cstdio> #include <cstdlib> #include <cmath> #include <limits> int main() { int n, m, C; std::cin >> n >> m >> C; std::map<int, std::vector<int> > cmap; for (int i = 0; i < n; i++) { int x; std::cin >> x; for (int j = 0; j < x; j++) { int c; std::cin >> c; if (c != 0) { if (cmap.find(c) != cmap.end()) cmap[c].push_back(i); else { std::vector<int> a; a.push_back(i); cmap[c] = a; } } } } int ans = 0; for (auto it = cmap.begin(); it != cmap.end(); it++) { std::vector<int>& a = it->second; if (a.size() >= 2) { if ((* a.rbegin() + 1) % n == *a.begin()) { ans += 1; } else { for (size_t p1 = 0, p2 = 1; p2 < a.size(); p1++, p2++) { if (a[p2] - a[p1] < m) { ans += 1; break; } } } } } std::cout << ans; return 0; }
// // Created by qdl on 2021/7/12. // #include "vector" #include "iostream" #include "map" using namespace std; map<int,int>mp; int main(){ // 读入 int N,M,C; cin>>N>>M>>C; bool bead[N][C]={0}; // 输入珠子颜色 for(int i=0;i<N;i++){ int num; cin>>num; for(int j =0;j<num;j++){ int color; cin>>color; bead[i][color-1]= true;//对含有某种颜色的珠子记录它的序号 } } // 遍历所有颜色 for (int i = 0; i < C; ++i) { // 遍历所有珠子 for (int j = 0; j < N; ++j) { if(bead[j][i]==true){//这个判断条件很重要,判断当前珠子是否含有第i种颜色 int k = j+1;//从这颗珠子的下一颗开始寻找与他含有同种颜色的珠子 for (; k < j+N -1; ++k) { int second = k % N;//由于手串是环状的,所以需要求余来确定与上一颗珠子的距离 //如果找到了含有同种颜色的珠子并且与上一颗同颜色的珠子的距离小于或者等于M if(bead[second][i]==true&&(k-j+1)<=M){ //记录这种颜色是不符合规则的 mp[i] = 1; break; } } //此时已经发现了第i种颜色不符合规则,需要跳出遍历珠子的循环 if(k<j+N-1) break; } } } cout<<mp.size();//输出mp里面的颜色的数目 return 0; };
import java.util.Scanner; import java.util.ArrayList; import java.util.HashMap; import java.util.PriorityQueue; public class Main{ public static void main(String[] args){ Scanner s = new Scanner(System.in); int n=s.nextInt(); int m=s.nextInt(); int c=s.nextInt(); ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); for(int i=0;i<n;i++){ int temp=s.nextInt(); list.add(new ArrayList<Integer>()); for(int j=0;j<temp;j++){ list.get(i).add(s.nextInt()); } } HashMap<Integer,PriorityQueue<Integer>> map = new HashMap<Integer,PriorityQueue<Integer>>(); for(int i=0;i<list.size();i++){ for(int j=0;j<list.get(i).size();j++){ int cur=list.get(i).get(j); if(!map.containsKey(cur))map.put(cur,new PriorityQueue<Integer>()); map.get(cur).add(i); } } int count=0; for(int a: map.keySet()){ int x=map.get(a).peek(); int y=0; if(map.get(a).size()<2)continue; while(!map.get(a).isEmpty()){ y=map.get(a).poll(); if(!map.get(a).isEmpty()&&(map.get(a).peek()-y)<m){ count++; break; } } if(map.get(a).isEmpty()){ if(x+n-y+1<=m){ count++; } } } System.out.println(count); } }hashmap存储每种颜色出现的序号,使用priorityqueue存储序号,比较poll出的序号和peek序号之差
#include<cstdio> #include<algorithm> #include<map> using namespace std; typedef long long ll; int n, m, c; ll a[20005]; int solve(int id) { ll bitmask = (1LL << id); int cnt = 0; for(int i = 1; i <= m; ++i) cnt += ((a[i] & bitmask) != 0); if(cnt >= 2) return 1; for(int j = m + 1; j <= 2 * n; ++j) { cnt += ((a[j] & bitmask) != 0); cnt -= ((a[j - m] & bitmask) != 0); if(cnt >= 2) return 1; } return 0; } int main() { scanf("%d%d%d", &n, &m, &c); for(int i = 1; i <= n; ++i) { int x; scanf("%d", &x); ll tmp = 0LL; while(x--) { int id; scanf("%d", &id); tmp |= (1LL << id); } a[i] = tmp; a[i + n] = tmp; } int ans = 0; for(int i = 1; i <= c; ++i) ans += solve(i); printf("%d\n", ans); return 0; }颜色数只有50种,分50次扫描即可。每次扫描暴力尺取。
import java.util.Scanner; import java.util.HashMap; import java.util.HashSet; public class Main{ public static void main(String[] args){ Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int m=scanner.nextInt(); int c=scanner.nextInt(); HashMap<Integer, HashSet<Integer>> map=new HashMap<>(); for(int i=1; i<n+1; i++){ int colors=scanner.nextInt(); for(int j=0; j<colors; j++){ int cid=scanner.nextInt(); if(!map.containsKey(cid)) map.put(cid, new HashSet<Integer>()); map.get(cid).add(i); } } int ans=0; for(int i=0; i<c+1; i++){ if(count(n, m, map.getOrDefault(i, new HashSet<Integer>()))) ans++; } System.out.println(ans); } private static boolean count(int n, int m, HashSet<Integer> set){ for(int i:set){ for(int j:set){ if(i==j) continue; int min=i, max=j; if(i>j){ int t=max; max=min; min=t; } if(max-min<=m-1||n-max+min<=m-1) return true; } } return false; } }
import java.util.Scanner; public class Test{ public static void main(String[] args){ Scanner input=new Scanner(System.in); int n=input.nextInt(); int m=input.nextInt(); int c=input.nextInt(); Color color[]=new Color[n]; for(int i=0;i<n;i++){ color[i]=new Color(); color[i].num=i; color[i].cNum=input.nextInt(); color[i].newColor(color[i].cNum,input); } int[] overNum=new int[c+1]; for(int i=0;i<n;i++){ int[] overTwo=new int[c+1]; int index=i; for(int j=0;j<=m;j++,index++){ if (index<color.length){ overTwo=reC(color[index],overTwo); }else{ index=0; overTwo=reC(color[index],overTwo); } } for(int j=0;j<=c;j++){ //System.out.println(overTwo[j]); if(overTwo[j]>2){ overNum[j]=1; } } } int xx=0; for(int j=0;j<=c;j++){ if(overNum[j]==1){ xx++; } } System.out.print(xx); } public static int[] reC(Color c1,int[] over){ if(c1.colorArry!=null){ for(int i=0;i<c1.cNum;i++){ int c=c1.colorArry[i]; int temp=over[c]; temp++; over[c]=temp; } } return over; } } class Color{ public int num; public int cNum; public int[] colorArry; public void newColor(int cNum,Scanner in){ if(cNum==0){ colorArry=null; return; } colorArry=new int[cNum]; for(int i=0;i<cNum;i++){ colorArry[i]=in.nextInt(); } } }为啥我输出来大于两个的就对了,大于等于两个就不对
import java.util.*; public class ColorMap { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); int c=sc.nextInt(); int res=0; Map<Integer,ArrayList<Integer>> map=new HashMap<>(); for(int i=1;i<n+1;i++){ int diversity=sc.nextInt(); if(diversity==0){ continue; } for(int j=diversity;j>0;j--){ int color=sc.nextInt(); if(map.containsKey(color)){ ArrayList<Integer> list=map.get(color); list.add(i); } else{ ArrayList<Integer> list=new ArrayList<>(); list.add(i); map.put(color, list); } } } for(int i=1;i<=50;i++){ if(map.containsKey(i)){ c--; ArrayList<Integer> li=map.get(i); Iterator<Integer> ltr=li.iterator(); int fir=ltr.next(); int now=fir; int pre; while(ltr.hasNext()){ pre=now; now=ltr.next(); if((now-pre)<m&&(li.size()-now+fir)<m){ res++; break; } } if(c==0){ break; } } } System.out.println(res); sc.close(); } }
(now-pre)<m&&(li.size()-now+fir)<m
import java.util.Scanner;public class Main{public static void main(String args[]){Scanner sc=new Scanner(System.in);while(sc.hasNext()){int n=sc.nextInt();int m=sc.nextInt();int c=sc.nextInt();int count[]=newint[n];int kinds[][]=newint[n][c];boolean colors[][]=newboolean[c][n];for(int i=0;i<c;i++)for(int j=0;j<n;j++)colors[i][j]=false;for(int i=0;i<n;i++){count[i]=sc.nextInt();for(int j=0;j<count[i];j++){kinds[i][j]=sc.nextInt();colors[kinds[i][j]-1][i]=true;}}boolean o[]=newboolean[c];for(int i=0;i<c;i++){boolean color[]=newboolean[n];for(int j=0;j<colors[i].length;j++)color[j]=colors[i][j];o[i]=panduan(color,m);}int res=0;for(int i=0;i<c;i++)if(!o[i])res++;System.out.println(res);}}public static boolean panduan(boolean color[],intm){boolean o=true;for(int i=0;i<color.length;i++){if(color[i]){for(intk=i+1;k<i+m;k++){int x=k%color.length;if(color[x]){o=false;break;}}}}return o;}}
java的常规代码,分析题意,把已有的数据形式kinds转换为利于分析的数据形式colors,判断后统计次数即可。
importjava.util.ArrayList; import java.util.HashMap; import java.util.Hashtable; import java.util.Scanner; public class Main {public static void main(String[] args){ Scanner sc = newScanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int c = sc.nextInt(); int[][] a = new int[c+1][n]; int[] k = new int[c+1]; for(inti =0; i<= c;i++){ k[i] =0; } for(inti =1; i <= n;i++){ intnum_i = sc.nextInt(); for(intj =0; j < num_i;j++){ intcolor = sc.nextInt(); int x = k[color]; a[color][x] = i; k[color]++; } } for(inti =1; i <= c;i++){ for(intj =0; j < k[i];j++) System.out.print(a[i][j] + " "); System.out.println(); } intillegel_color =0; for(inti =1;i <= c;i++){ bgm:for(intj =0; j < k[i];j++){ for(intp = j +1; p < k[i];p++){ if(a[i][p] - a[i][j] < m || n - Math.max(a[i][p],a[i][j]) + Math.min(a[i][p],a[i][j]) < m){ System.out.println("i = "+ i); System.out.println("p = "+ p); illegel_color++; break bgm; } } } } System.out.println(illegel_color); } }