当前位置:网站首页>CF1427F-Boring Card Game【贪心】
CF1427F-Boring Card Game【贪心】
2022-08-10 23:38:00 【QuantAsk】
正题
题目链接:https://www.luogu.com.cn/problem/CF1427F
题目大意
有一个 1 ∼ 6 n 1\sim 6n 1∼6n的序列,两个人轮流操作,每次取走连续的三个数字。
现在给出先手取走的数字集合,要求构造方案。
保证有解
1 ≤ n ≤ 200 1\leq n\leq 200 1≤n≤200
解题思路
我们给先手取的颜色标为 0 0 0,后手的颜色标为 1 1 1。
我们考虑一下能不能求出哪些牌是在一次中取走的,这个取法很像一个括号匹配,也就是一次取走的东西中不会产生交叉,而如果不会产生交叉,那么我们按照括号匹配的找法去找也是对的。
所以我们可以用一个栈存按顺序存牌,当栈顶三个颜色相同时就弹出这三个,表示这三个是在同一次中取走的。
并且我们还能建立一些依赖关系,形如取走 x x x之前必须 y y y,这些依赖关系能构成一个森林。
现在相当于给出这样一棵森林,每次取走一个叶子,要求颜色是 01 01 01交错的。
我们找一下这个森林的性质,会发现每个节点的颜色都和父节点的不同,还有 0 0 0和 1 1 1的数量相等。
一种取法是 0 0 0和 1 1 1都随便取,但是 1 1 1必须留下一个根到最后取,现在我们证明这种取法的正确性:
首先如果用这种取法正确,那么一个有解的状态就是存在一个为 1 1 1的根并且存在一个当前要取的颜色的叶子。然后我们证明所有有解状态都能转移到有解状态即可。
假设现在要取 0 0 0,那么此时 01 01 01数量相同。假设随便一个 0 0 0后就没有了 1 1 1的叶子,此时 1 1 1的数量比 0 0 0多 1 1 1,并且有一个为 1 1 1的根,因为没有为 1 1 1的叶子,应该每个 1 1 1都能找到一个为 0 0 0的儿子,但是 1 1 1的数量比 0 0 0多,所以显然不合法,假设不成立。
假设现在要取 1 1 1,那么此时取走随便一个不是最后一个根的 1 1 1后 01 01 01数量相同,假设此时没有为 0 0 0的儿子。我们每个 0 0 0去找儿子中的一个 1 1 1,理论上也应该找得到,但是因为有一个 1 1 1是根,所以至少有一个 0 0 0找不到这样一个儿子,所以假设不成立。
所以我们的取法就是除了最后一个为 1 1 1的根以外其他的都随便取。
时间复杂度: O ( n ) O(n) O(n)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
const int N=1500;
int n,cnt,wrt,v[N],_v[N],T[N],p[N],s[N],nrt[N];
vector<int> ans,G[N],prt[N];
deque<int> q[2];
void dfs(int x){
if(!G[x].size())q[_v[x]].push_back(x);
for(int i=0;i<G[x].size();i++){
int y=G[x][i];
dfs(y);T[y]=x;
}
return;
}
void rel(int x){
ans.push_back(x);
if(!T[x])return;G[T[x]].pop_back();
if(G[T[x]].empty())q[_v[T[x]]].push_front(T[x]);
return;
}
int main()
{
scanf("%d",&n);n=n*6;
for(int i=1;i<=n;i++)v[i]=1;
for(int i=1,x;i<=n/2;i++)
scanf("%d",&x),v[x]=0;
int top=0;stack<int> z;
for(int i=1;i<=n;i++){
s[++top]=i;
if(top>2&&v[s[top]]==v[s[top-1]]&&v[s[top]]==v[s[top-2]]){
++cnt;p[s[top-2]]=cnt;_v[cnt]=v[s[top]];
prt[cnt].push_back(s[top-2]);
prt[cnt].push_back(s[top-1]);
prt[cnt].push_back(s[top]);
while(!z.empty()&&z.top()>s[top-2])
G[cnt].push_back(p[z.top()]),nrt[p[z.top()]]=1,z.pop();
z.push(s[top-2]);top-=3;
}
}
int c=0;
for(int i=1;i<=cnt;i++)
if(!nrt[i])dfs(i),c+=_v[i];
for(int i=1;i<=n/6;i++){
rel(q[0].front());q[0].pop_front();
if(i==n/6){
if(wrt)ans.push_back(wrt);
else rel(q[1].front());
}
else{
int x=q[1].front();c-=(_v[x]==1&&!nrt[x]);
if(!nrt[x]&&_v[x]==1&&!c)
{
wrt=x;q[1].pop_front();}
rel(q[1].front());q[1].pop_front();
}
}
for(int i=0;i<ans.size();i++,putchar('\n'))
for(int j=0;j<3;j++)
printf("%d ",prt[ans[i]][j]);
return 0;
}
边栏推荐
- HGAME 2022 Week3 writeup
- Blue Hat Cup 2022 web/misc writeup
- 进程和线程
- Is there a way out in the testing industry if it is purely business testing?
- Multilingual Translation - Multilingual Translation Software Free
- 2022下半年软考「高项」易混淆知识点汇总(2)
- 编程语言为什么有变量类型这个概念?
- 基于SSM实现手机销售商城系统
- call,apply,bind指定函数的this指向详解,功能细节,严格和非严格模式下设定this指向
- 翻译软件哪个准确度高【免费】
猜你喜欢
随机推荐
How to recover data from accidentally deleted U disk, how to recover deleted data from U disk
缓存知识总结
ROS Experiment Notes - Validation of UZH-FPV Dataset
部分准备金银行已经过时
Kubernetes 选举机制HA
14. Thymeleaf
Kubernetes你不知道的事
CSDN21天学习挑战赛之折半插入排序
基于SSM实现手机销售商城系统
C3604环保黄铜带
C194铜合金C19400铁铜合金
逮到一个阿里 10 年老 测试开发,聊过之后收益良多...
Easy-to-use translation plug-in - one-click automatic translation plug-in software
3. 容器功能
打开老项目项目的报错(以高德地图demo为例)
MySQL数据库基础操作
后疫情时代,VR全景营销这样玩更加有趣!
N1BOOK writeup
推进牛仔服装的高质量发展
[C language articles] Expression evaluation (implicit type conversion, arithmetic conversion)