淄博做网站建设的公司,国内wordpress有名的网站,深圳洛可可设计公司,最全的百度网盘搜索引擎正题
题目链接:https://www.luogu.com.cn/problem/CF1427F 题目大意
有一个1∼6n1\sim 6n1∼6n的序列#xff0c;两个人轮流操作#xff0c;每次取走连续的三个数字。
现在给出先手取走的数字集合#xff0c;要求构造方案。
保证有解 1≤n≤2001\leq n\leq 2001≤n≤200…正题
题目链接:https://www.luogu.com.cn/problem/CF1427F 题目大意
有一个1∼6n1\sim 6n1∼6n的序列两个人轮流操作每次取走连续的三个数字。
现在给出先手取走的数字集合要求构造方案。
保证有解
1≤n≤2001\leq n\leq 2001≤n≤200 解题思路
我们给先手取的颜色标为000后手的颜色标为111。
我们考虑一下能不能求出哪些牌是在一次中取走的这个取法很像一个括号匹配也就是一次取走的东西中不会产生交叉而如果不会产生交叉那么我们按照括号匹配的找法去找也是对的。
所以我们可以用一个栈存按顺序存牌当栈顶三个颜色相同时就弹出这三个表示这三个是在同一次中取走的。
并且我们还能建立一些依赖关系形如取走xxx之前必须yyy这些依赖关系能构成一个森林。
现在相当于给出这样一棵森林每次取走一个叶子要求颜色是010101交错的。
我们找一下这个森林的性质会发现每个节点的颜色都和父节点的不同还有000和111的数量相等。
一种取法是000和111都随便取但是111必须留下一个根到最后取现在我们证明这种取法的正确性
首先如果用这种取法正确那么一个有解的状态就是存在一个为111的根并且存在一个当前要取的颜色的叶子。然后我们证明所有有解状态都能转移到有解状态即可。 假设现在要取000那么此时010101数量相同。假设随便一个000后就没有了111的叶子此时111的数量比000多111并且有一个为111的根因为没有为111的叶子应该每个111都能找到一个为000的儿子但是111的数量比000多所以显然不合法假设不成立。 假设现在要取111那么此时取走随便一个不是最后一个根的111后010101数量相同假设此时没有为000的儿子。我们每个000去找儿子中的一个111理论上也应该找得到但是因为有一个111是根所以至少有一个000找不到这样一个儿子所以假设不成立。
所以我们的取法就是除了最后一个为111的根以外其他的都随便取。
时间复杂度O(n)O(n)O(n) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#includequeue
#includestack
using namespace std;
const int N1500;
int n,cnt,wrt,v[N],_v[N],T[N],p[N],s[N],nrt[N];
vectorint ans,G[N],prt[N];
dequeint q[2];
void dfs(int x){if(!G[x].size())q[_v[x]].push_back(x);for(int i0;iG[x].size();i){int yG[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);nn*6;for(int i1;in;i)v[i]1;for(int i1,x;in/2;i)scanf(%d,x),v[x]0;int top0;stackint z;for(int i1;in;i){s[top]i;if(top2v[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 c0;for(int i1;icnt;i)if(!nrt[i])dfs(i),c_v[i];for(int i1;in/6;i){rel(q[0].front());q[0].pop_front();if(in/6){if(wrt)ans.push_back(wrt);else rel(q[1].front());}else{int xq[1].front();c-(_v[x]1!nrt[x]);if(!nrt[x]_v[x]1!c){wrtx;q[1].pop_front();}rel(q[1].front());q[1].pop_front();}}for(int i0;ians.size();i,putchar(\n))for(int j0;j3;j)printf(%d ,prt[ans[i]][j]);return 0;
}
