[luogu CF1427F] Boring Card Game (nature)

Boring Card Game

Title Link: luogu CF1427F

Main idea

Give you 6n cards in order, and two people take turns to take three consecutive cards at a time.
Then give you the 3n cards that the first person wants, ensure that there is a way to get them, and ask you to output the scheme.
(this is not a game, and the two can be regarded as cooperation)

thinking

First of all, because there must be a solution, consider such a greed:
Maintain a stack from left to right, and take three identical stacks at a time. If you don't consider the order, you can do it.
And because you think about it, you will find that this is the only solution, and there is a solution, so we consider giving the order.

Then it is found that it will become something similar to a sequence of parentheses (you can give the leftmost and rightmost parentheses respectively). If a parenthesis is to be deleted, there must be nothing in it.
That is, the number of brackets should be deleted after the son is deleted, and each color should be deleted in turn. This is the construction method.

Considering the nature of searching, it is found that the colors of adjacent layers must be different.
So I thought about some ways and found that there was no way to do it. I thought about messing around and proving (bushi

If you choose indiscriminately, OK(
Let's try:
For the point to be selected first, it is not difficult for us to prove that if there is a solution, there must be a position in the leaf.
First, if there is a solution, the last one (that is, there is a root) is for the backhand.
Then we consider the counter evidence. If it is not in the leaves, then because of the color alternation, the two points on one side must have different colors. Then we can consider that each backhand point matches its father, but in this way, the backhand point of the root does not match, which is contradictory.
(it can be directly matched because there is also a property that the number of two points is the same at this time.)

Then, as long as we don't delete the last root it can delete (of course, it doesn't matter if there is only one left)

So it's OK!

code

#include<queue>
#include<cstdio>

using namespace std;

const int N = 205;
int n, x, sta[N * 6], pla[N * 6], rtnum, sons[N * 2], dy[N * 6], tot, fa[N * 6];
bool in[N * 6], col[N * 2], rt[N * 2];
vector <int> dys[N * 2];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= 6 * n; i++) in[i] = 1;
	for (int i = 1; i <= 3 * n; i++) {
		scanf("%d", &x); in[x] = 0;
	}
	
	for (int i = 1; i <= 6 * n; i++) {
		sta[++sta[0]] = i;
		if (sta[0] == 1 || in[sta[sta[0]]] != in[sta[sta[0] - 1]]) pla[i] = ++tot, col[tot] = in[sta[sta[0]]], dy[i] = tot;
			else if (sta[0] >= 3 && in[sta[sta[0]]] == in[sta[sta[0] - 1]] && in[sta[sta[0]]] == in[sta[sta[0] - 2]])
				pla[i] = -pla[sta[sta[0] - 2]], dy[i] = dy[sta[sta[0] - 1]], sta[0] -= 3;
			else dy[i] = dy[sta[sta[0] - 1]];
		dys[dy[i]].push_back(i);
	}
//	if (sta[0]) while (1);
	
	for (int i = 1; i <= 6 * n; i++) if (pla[i]) {
		if (pla[i] > 0) {
			if (!sta[0]) rtnum += in[i], rt[pla[i]] = 1;
				else fa[pla[i]] = pla[sta[sta[0]]], sons[fa[pla[i]]]++;
			sta[++sta[0]] = i;
		}
		else {
			if (!sta[0]) while (1); sta[0]--;
		}
	}
//	if (sta[0]) while (1);
	
	queue <int> q0, q1;
	while (!q0.empty()) q0.pop(); while (!q1.empty()) q1.pop();
	for (int i = 1; i <= tot; i++)
		if (!sons[i]) {
			if (col[i]) q1.push(i); else q0.push(i);
		}
	while (!q0.empty()) {
		int now = q0.front(); q0.pop(); printf("%d %d %d\n", dys[now][0], dys[now][1], dys[now][2]);
		sons[fa[now]]--; if (!sons[fa[now]]) {if (col[fa[now]]) q1.push(fa[now]); else q0.push(fa[now]);}
//		if (q1.empty()) while(1);
		now = q1.front(); q1.pop();
		if (!(q1.empty() || rtnum > 1 || !rt[now])) {
			int tmp = now; now = q1.front(); q1.pop(); q1.push(tmp);
		}
		printf("%d %d %d\n", dys[now][0], dys[now][1], dys[now][2]);
		sons[fa[now]]--; if (!sons[fa[now]]) {if (col[fa[now]]) q1.push(fa[now]); else q0.push(fa[now]);}
		if (rt[now]) rtnum--;
	}
	
	return 0;
}

Tags: greedy algorithm

Posted by Johannes80 on Sat, 10 Sep 2022 21:15:33 +0300