Boring Card Game

kiritokazuto · 2022-09-28 08:58:26 · 题解

Boring Card Game

我愿意称之为最水的黑题。

• 一看题目，唉，这不大模拟嘛？然后无脑敲了 200 行左右，维护了五个链表，拿了 10 分？？？

• 好了，不是大模拟，那我们就可以好好思考这道题了。

• 首先我们可以很明显的发现，每一张牌应该由谁取是已经确定了的，所以我们可以先标记出哪张牌属于谁，然后考虑如何进行处理，让牌能被拿出来。

• 我们记 1 为先手 0 为后手。

• 对于一种情况，例如 1 1 0 0 0 1 显然我们应该先取完中间的三个零再取这些一，因为这样他们才可以连起来，我们称这样的点具有依赖关系，当然，因为每个人都一次取三个，所以我以三个为一块，那么对于这种依赖关系，我们就将他们所属的块连边，然后跑拓扑，就可以很好地去解决这个问题了。

• 不过我在这里写了一个魔改的拓扑，我是用出度为零跑的，所以我在连边的时候父子关系是相反的，有点别扭，大家可以看代码理解。

• 所以如果这样建图的话，显然我们只有在处理叶子之后才能处理根，也就是一个反着来的拓扑，不过其实本质一样。

• 那么我们可以发现，因为数据保证有解，总数也是一个确定的偶数，那么最后一次一定是后手拿牌，所以如果我们不是最后一次拿牌的话，应时刻保留一个后手作为根的节点(作为根是因为它最后拿，那么应该处理完所有的依赖关系)。

  • 例如，我们如果不保留 4 节点这个零，那么显然之后我们会陷入让先手最后取的困境，就无解了，所以我们应该先取完 3 和 2 这两个零节点，最后再取 4 才是有解的。

• 下边我们考虑如何建出这个森林(不一定是一整颗树)。

  • 我们可以维护一个栈，如果这个栈顶元素和我不同，我们就新加入一个块(可以放三个节点那种)，否则，我就放在栈顶元素所在块里，当然，如果栈顶元素所在块够了三个节点，我们可以将这个块弹出，并将它的依赖关系维护一下。

• 我们可以模拟一下这个过程。

  • 例如 0 0 1 1 0 1 1 1 0 0 1 0。从左到右依次编号为 1 \sim 12。

  • 首先我们建了一个新块，放入了 1 和 2 两个点，并且我们记录块 1 是属于 0 的后手。

  • 之后我们又建了一个新块，放入了 3 和 4 两个点，并且我们记录块 2 是属于 1 的先手。

  • 之后我们又又又建了一个新块，放入了 5 一个点，并且我们记录块 3 是属于 0 的后手。

  • 之后我们又双叒叕建了一个新块，放入了 6 7 8 三个点，并且我们记录块 4 是属于 1 的先手。

  • 终于遇到了够三个点的块，所以我们可以开始弹栈了，弹出并建边。

  • 此时块 3 也够了，继续弹。

  • 块 2 够了， 弹。

  • 最终块 1 也够了，栈也空了。

• 最后就可以拓扑输出答案了。

• 对于如何进行拓扑，因为我是反着建图的，所以在这里我是跑的出度为零的点，然后把它父亲的度数删掉。

• 这里讲一下最下边那个输出的循环，最外层是现在处理了几个块了，实际上就是用来给我转换每一次需要的卡牌的类型的循环(转换 now)，里层的循环是用来找到现在可以输出的块，也就是没有被访问过，同时出度为零并且和我要的类型一样的节点。

• 这里还应该像上文说的一样，如果不是最后一轮(最后一轮就可以将它输出了)，我们应该时刻保证存在一个后手类型的根节点，以保证有解，所以我有一个 continue 。

• 剩下就没有了，这个黑题就被切掉了。

• 学校的 linux 没有画图，图全是用 wps 画的，呜呜呜。

#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; x ++)
#define fp(x, y, z)for(Re x = y; x >= z; x --)
#define delfr(x, y, z)for(Re x = y; x < z; x ++)
#define delfp(x, y, z)for(Re x = y; x > z; x --)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr(x, y) pair<x, y>
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define re(x) return x
#define sec second
#define fst first

using namespace std;
namespace kiritokazuto{
    auto read = [](){
        LL x = 0;
        int f = 1;
        char c;
        while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
        do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
        return x * f;
    };
    template  <typename T> fuc(void, write)(T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10); putchar(x % 10 | '0');
    }
}

using namespace kiritokazuto;

const int maxn = 2000 + 5, maxm = 6e5+ 5, Mod = 993244853;
const LL Inf = 0x7fffffffffff;

int stk[maxn];
int bel[maxn];//块里点的类型
int top;
int n;
int deg[maxn];
int fa[maxn];
int rem[maxn][4];
int type[maxn];//1 先手 0 后手
int q[maxn], l, r;//topo
int tot[maxn];//一个块里有几个点
int num;//总共有多少块
int now = 1;//现在谁取
int vis[maxn];
signed main() {
    n = read();
    n *= 3;
    fr(i, 1, n) type[read()] = 1;
    n <<= 1;
    fr(i, 1, n) {
        if(!top || bel[stk[top]] != type[i]) {//没块或者与栈顶不同类，加新的
            bel[++num] = type[i];
            stk[++top] = num;
            rem[num][++tot[num]] = i;
        }else {
            rem[stk[top]][++tot[stk[top]]] = i;
            if(tot[stk[top]] == 3){
                fa[stk[top]] = stk[top - 1];
                top--;
            }
        }
    }
    int mach = 0;//以0为根的点有几个
    fr(i, 1, num) {
        if(!fa[i] && !bel[i])mach ++;
        deg[fa[i]]++;//出度
    }

    fr(i, 1, num){//我当前处理第几个节点
        fr(j, 1, num) {
            if(!deg[j] && bel[j] == now && !vis[j]) {
                if(i < num && (bel[j] == 0) && mach == 1 && !fa[j])continue;
                //不是最后一个的话我们不能将最后一个作为根的后手取走
                vis[j] = 1;
                deg[fa[j]]--;
                if(!bel[j] && !fa[j])mach--;
                printf("%d %d %d\n", rem[j][1], rem[j][2], rem[j][3]);
                break;
            }
        }
        now ^= 1;
    } 
    re(0);

}