当前位置：首页 > news >正文

打卡信奥刷题（3075）用C++实现信奥题 P7006 [NEERC 2013] Kabaleo Lite

news 2026/6/15 11:03:25

P7006 [NEERC 2013] Kabaleo Lite

题目描述

有一种棋盘游戏：棋盘上有nnn个格子，每个格子上可以堆叠若干个有颜色的筹码，只有每个格子中最上方的筹码的颜色是可见的。

参加游戏的每个玩家都有各自不同的一个目标颜色，以及一些彩色筹码。每个人只知道自己的目标颜色，但各自拥有的筹码颜色和数量都是公开的。每个回合中，所有玩家轮流在棋盘上选一个格子放置筹码，同时覆盖下方的筹码。游戏结束后，数出棋盘上可见筹码数最多的颜色，以该颜色为目标颜色的玩家即获胜。若该颜色不是任何玩家的目标颜色，或者棋盘上出现最多的颜色不唯一，则游戏平局。

现在，一局游戏进行到了最后，你和其他所有玩家都只剩最后一个筹码。现在恰好轮到你操作，在不知道其他人的目标颜色的前提下，你想知道你一共有哪些操作可以保证必胜。

输入格式

第一行444个整数n,p,c,hn,p,c,hn,p,c,h，分别表示棋盘格数、玩家数、筹码颜色总数和你的目标颜色；

第二行nnn个整数bib_ibi，表示棋盘上现有的筹码颜色，棋盘格编号从111开始；

第三行ppp个整数lil_ili，表示每个玩家的最后一枚筹码的颜色，玩家编号从你开始。

输出格式

第一行111个整数www，表示你有多少种必胜操作。

第二行www个整数mim_imi，表示你应该把筹码放在哪个格子上。顺序不限。

输入输出样例 #1

输入 #1

6 3 4 2 2 1 2 3 2 2 2 1 1

输出 #1

1 2

说明/提示

1≤n≤1061\leq n\leq 10^61≤n≤106，1≤p≤c≤1061\leq p\leq c\leq 10^61≤p≤c≤106，1≤h,bi,li≤c1\leq h,b_i,l_i\leq c1≤h,bi,li≤c。

C++实现

#include<bits/stdc++.h>#defineR(i,a,b)for(inti=(a),i##E=(b);i<=i##E;i++)#defineL(i,a,b)for(inti=(b),i##E=(a);i>=i##E;i--)usingnamespacestd;intn,p,c,h;intb[1111111],cnt[1111111];intl[1111111];vector<int>ans;intmx,mmx,cy;inlineintcheck(intx){if(n==1&&l[p]==h)return1;--cnt[b[x]];++cnt[l[1]];intdel=cnt[h]-cy;boolok=1;if(del<=0)ok=0;if(cnt[mx]>=del)ok=0;if(cnt[mmx]>=del)ok=0;if(l[1]!=h&&cnt[l[1]]>=del)ok=0;++cnt[b[x]];--cnt[l[1]];returnok;}signedmain(){ios::sync_with_stdio(false);cin.tie(NULL);cin>>n>>p>>c>>h;R(i,1,n)cin>>b[i],++cnt[b[i]];R(i,1,p)cin>>l[i];R(i,2,p)if(l[i]!=h)++cy,++cnt[l[i]];R(i,1,c)if(i!=h){if(cnt[i]>cnt[mx])mmx=mx,mx=i;elseif(cnt[i]>cnt[mmx])mmx=i;}R(i,1,n)if(check(i))ans.emplace_back(i);cout<<ans.size()<<endl;for(intx:ans)cout<<x<<' ';cout<<endl;}