作为一个手串艺人,有金主向你订购了一条包含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颗串珠是透明的。
##Python##用一个窗口滑动来看目前的球,dict记录哪些颜色已经超过数量import sysdef checkSeq(seq, m, c):period =[ball for ball ins eq[0:m]]colors =[0 for _ in range(c)]for ball in period:for color in ball:colors[color-1] +=1ret ={}for i in range(len(seq)):for cid in range(len(colors)):if colors[cid] >1:ret[cid] =Truefor color in period[0]:colors[color-1] -=1period.pop(0)add =(i+m)%(len(seq))for color in seq[add]:colors[color-1] +=1period.append(seq[add])print(len(ret.keys()))if__name__ =='__main__':stat =sys.stdin.readline().split()N =int(stat[0])M =int(stat[1])M =M %NC =int(stat[2])seq =[]for i in range(N):line =sys.stdin.readline().split()line.pop(0)ball =[int(x) for x inline]seq.append(ball)checkSeq(seq, M, C)
def fun(params, colors): result = {} # 初始化合法颜色字典 for i in range(params[2]): result[i + 1] = 1 # 构造环形染色列表 for i in range(params[1] - 1): colors.append(colors[i]) for i in range(params[0]): dic = {} for j in range(i, i + params[1]): for color in colors[j]: if color not in dic: dic[color] = 0 elif color == 0: pass else: if color in result: result[color] = 0 return result if __name__ == "__main__": params = [int(x) for x in input().split()] colors = [] for i in range(params[0]): color_list = [int(x) for x in input().split()] color_list.pop(0) colors.append(color_list) result = fun(params, colors) for res in result.keys(): if result[res] == 0: count += 1 print(count)用字典做哈希,时间可满足题目要求
# 简单的Python方法,全通过,合理利用字典 n, m, c = [int(x) for x in input().split()] dic = {} result = [] for i in range(n): temp = [int(x) for x in input().split()] if temp[0] == 0: continue for j in range(1, temp[0] + 1): if temp[j] in dic: tt = dic[temp[j]] if i - tt[-1] <= m - 1 or (n - i - tt[0]) <= m - 1: if temp[j] not in result: result.append(temp[j]) dic[temp[j]].append(i) else: dic[temp[j]] = [i] print(len(result))
# 队列实现,注意取模就好了 n, m, c = [int(e) for e in input().split(' ')] list = [] for i in range(n): list.append([int(e) for e in input().split(' ')]) _dict = {} for i in range(1, c + 1): _dict[i] = 0 left = 0 right = m - 1 count = 0 max = 99999 for i in range(m): for j in range(1, len(list[i])): if _dict[list[i][j]] != max: _dict[list[i][j]] += 1 if _dict[list[i][j]] > 1: _dict[list[i][j]] = max count += 1 for i in range(n - 1): for j in range(1,len(list[left])): if _dict[list[left][j]] != max: _dict[list[left][j]] -= 1 left = (left + 1) % n right = (right + 1) % n for j in range(1, len(list[right])): if _dict[list[right][j]] != max : _dict[list[right][j]] += 1 if _dict[list[right][j]] > 1: _dict[list[right][j]] = max count += 1 print(count)
n, m, c = list(map(int,input().split())) col = {} for i in range(n): t = list(map(int,input().split())) if t[0] !=0: for j in range(t[0]): if t[j+1] not in col: col[t[j+1]] = [] col[t[j+1]].append(i) counter = 0 for i in col: if len(col[i]) >1: for j in range(0,len(col[i])-1): if col[i][j+1]-col[i][j]<m&nbs***bsp;col[i][j]+n-col[i][j+1]<m: counter += 1 break print(counter)
n, m, c = list(map(int,input().split())) dic = {} result = [] for i in range(n): col = list(map(int,input().split())) for j in range(1,col[0]+1): try: #创建颜色字典 temp = dic[col[j]] # temp表示的是颜色col[j]出现的位置列表list if i-temp[-1] <= m-1 or (n-i-temp[0]) <= m-1: #判断上次出现该颜色的珠子序号和本次的序列差是否小于m-1 if col[j] not in result: result.append(col[j]) dic[col[j]].append(i) except: dic[col[j]] = [i] print(len(result))
n, m, c = list(map(int, input().split())) all_color = [] for i in range(n): allinfo = list(map(int, input().split())) if allinfo[0] == 0: colors = [] else: colors = allinfo[1:] all_color.append(colors) all_color = all_color + all_color[:m-1] res = 0 hash_map = dict() stack = all_color[:m] error_color = set() for i in range(m): for j in stack[i]: if j not in hash_map: hash_map[j] = 1 else: hash_map[j] += 1 error_color.add(j) for i in range(m, n+1): pre = stack.pop(0) for color in pre: hash_map[color] += -1 cur = all_color[i] stack.append(cur) for color in cur: if color not in hash_map&nbs***bsp;hash_map[color] == 0: hash_map[color] = 1 else: hash_map[color] += 1 error_color.add(color) print(len(error_color))
#include<bits/stdc++.h> #define pb push_back using namespace std; int main(){ int n,m,c,num,color; vector<int> a[20005]; int b[90]={0},v[90]={0}; cin>>n>>m>>c; for (int i=1; i<=n; i++){ scanf("%d",&num); for (int j=0; j<num; j++){ scanf("%d",&color); a[i].pb(color); a[i+n].pb(color); } } int l=1,r=1,ans=0; while (l<=n+m-1 && r<=n+m-1){ if ((r-l+1)<=m){ for (int i=0; i<a[r].size(); i++){ if (v[a[r][i]] && a[r][i]!=0 && !b[a[r][i]]){ ans++; b[a[r][i]]=1; } v[a[r][i]]++; } r++; } else{ for (int i=0; i<a[l].size(); i++) v[a[l][i]]--; l++; } } cout<<ans<<endl; return 0; }
while True: try: m, n, c = list(map(int, input().split())) nums_list = list() for i in range(m): nums_list.append(list(map(int, input().split()))) for i in range(n): nums_list.append(nums_list[i]) repeat_color = list() for i in range(c): repeat_color.append(0) for i in range(0, n, m): color_dict = dict() sub_nums = nums_list[i:i+m] for perle in sub_nums: perle.pop(0) for j in perle: if j in color_dict.keys(): color_dict[j] += 1 else: color_dict[j] = 1 for key, value in color_dict.items(): if value > 1: repeat_color[key-1] = 1 sum_repeat = sum(repeat_color) print(sum_repeat) except: break求大佬指点下,这代码到底哪错了,跑测试用例都可以,一提交就报错
n,m,c = map(int, input().split()) color_list = [] for i in range(n): color_list.append(list(map(int, input().split()))) color_num = [] for i in range(c): color_num.append([]) for i in range(n): color = color_list[i] if len(color) == 1: continue co = color[1:] for j in co: color_num[j-1].append(i+1) number = 0 for i in range(c): if len(color_num[i]) == 1: continue for j in range(len(color_num[i])-1): init_number = number for t in range(1, len(color_num[i])-j): res = abs(color_num[i][j+t] - color_num[i][j]) if res < m or res >= (n-1): number += 1 break if number > init_number: break print(number)
if __name__ == "__main__": n,m,c = map(int,input().strip().split()) xlist = [list(map(int,input().strip().split())) for i in range(n)] result = 0 cdict = dict(zip([i for i in range(1,c+1)],[0]*c)) for i in range(m): for j in range(xlist[i%n][0]): cdict[xlist[i%n][j+1]] += 1 ckeys = list(cdict.keys()) for k in ckeys: if cdict[k] > 1: result += 1 del cdict[k] for i in range(n-1): for j in range(xlist[i%n][0]): if xlist[i%n][j+1] in cdict: cdict[xlist[i%n][j+1]] -= 1 for j in range(xlist[(m+i)%n][0]): if xlist[(m+i)%n][j+1] in cdict: cdict[xlist[(m+i)%n][j+1]] += 1 ckeys = list(cdict.keys()) for k in ckeys: if cdict[k] > 1: result += 1 del cdict[k]print(result)
n, m, c = [int(char) for char in raw_input().split()]
A = []
for i in range(n):
A.append([int(char) for char in raw_input().split()])
falseColor = {}
for i in range(1, c+1):
falseColor[i] = 0
oldL = 0
oldR = m
countColor = {}
for i in range(1, c+1):
countColor[i] = 0
for number in range(oldL, oldR):
hand = A[number]
for i in range(1, hand[0]+1):
countColor[hand[i]] += 1
for key in countColor:
if countColor[key] > 1:
falseColor[key] = 1
for left in range(1, n):
hand = A[left-1]
for i in range(1, hand[0]+1):
countColor[hand[i]] -= 1
hand = A[(left+m-1)%n]
for i in range(1, hand[0]+1):
countColor[hand[i]] += 1
for key in countColor:
if countColor[key] > 1:
falseColor[key] = 1
print(sum(falseColor.values()))
#include <iostream> #include <vector> using namespace std; void update(vector<vector<int>> &color_vec,vector<int> onebead,int num) { //color_vec[i]表示第i种颜色出现在了哪些珠子上 if(onebead.size()==0) return; int color; for(int i=0;i<onebead.size();i++) { color=onebead[i]; if (color_vec[color].size()==0) { color_vec[color].emplace_back(num); } else if(color_vec[color][color_vec[color].size()-1]!=num) { color_vec[color].emplace_back(num); } } return; } bool judge(vector<int> onecolor,int n,int m) { //判断一种颜色所出现在的所有珠子中,相邻两颗的序号是否满足小于等于m-1,即在连续m颗 //珠子里面至少出现了两次 bool res=false; int num=onecolor.size(); for(int i=1;i<num;++i) { if(onecolor[i]-onecolor[i-1]<=m-1) { res=true; break; } if(i==num-1) { int a=n-onecolor[i]+1; int b=onecolor[0]; if(a+b<=m) { res=true; break; } } } return res; } int main() { int n,m,c; cin>>n>>m>>c; vector<vector<int>> color_vec(c+1); for (int i=0;i<n;++i) { vector<int> onebead; int num;cin>>num; for(int j=0;j<num;++j) { int temp;cin>>temp; onebead.emplace_back(temp); } update(color_vec,onebead,i+1); } int res=0; for(int i=1;i<=c;++i) { bool flag=judge(color_vec[i],n,m); if (flag==true) res++; } cout<<res<<endl; return 0; }
#include <iostream>#include <vector>usingnamespacestd;intmain(){intn,m,c;while(cin>>n>>m>>c){vector<vector<int> > vv;vv.resize(n+m-1);for(inti=0; i<=n-1; i++){intnum_i;cin>>num_i;vv[i].push_back(num_i);for(intj=1; j<=num_i; j++){inttemp;cin>>temp;vv[i].push_back(temp);}}for(inti=n; i<n+m-1; i++){vv[i]=vv[i-n];}intsum=0;for(inti=1; i<=c; i++){intsign=0;for(intj=0; j<=n-1; j++){intcounts=0;for(intk=j; k<=j+m-1; k++){for(intl=1; l<=vv[k][0]; l++){if(vv[k][l]==i)counts+=1;}}if(counts>=2){sign=1;break;}}if(sign==1)sum+=1;}cout << sum << endl;}return0;}