P6378 Riddle 做题记录

· · 个人记录

由于 2-SAT 的学习报告太长了，所以单独写成文章。

我们看到题干，每个点可以选或不选，看得出是 2-SAT 问题，边就如果这点不选，那另一个必选，但问题是点集，如果一个选，其他都不选，建边时间复杂度是 O(n^2) 的，这能过才有鬼了。
但还是打了，然后发现是链式前向星空间爆了，但是假如我们特判，如果空间要爆直接随机输出呢？
然后发现 RE 那几个点输出都是 TAK，然后 AC 了。

这道题正解要用什么前缀建边优化，等我去学一下，当前时间：2025年5月8日21:08:31。

现在时间：2025年5月8日21:21:32。

我们来看一下这个图： 我们发现，这样建图是 n^2 的，那么有什么优化方式吗？我们又发现，每个点连的边是从那个点集自己的左边和右边都全部连满（这里假设图里的三点是同一个点集的，不过还是废话），也就是说 1 点和 2 点都要到 3 点，而它们到 3 点都各自连了一条边，如果可以省掉这一条边就好了……于是，前缀优化建图出场了： 带箭头的单向边画图没有，只能这么搞了……
我们新建 2n 个节点，按图中顺序连接，每个点集读入后也按图中所示建边，这样边数不超过 6n 个。

AC 代码（别忘了开四倍的数组，循环枚举也得用四倍的，其实两倍也行）：

//Just Sayori
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <random>
#define ll long long
#define rnt register int
#define gr getchar
#define pr putchar
#define N 4000005
#define M 1000000007
using namespace std;

inline ll read()
{
    ll x = 0, f = 1;
    char ch = gr();
    while (ch < '0' || ch > '9')
        ch == '-' ? f = -1, ch = gr() : ch = gr();
    while (ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = gr();
    return x * f;
}

inline void write(ll x)
{
    static int sta[39], top = 0;
    if (x < 0)
        pr('-'), x = -x;
    do
        sta[++top] = x % 10, x /= 10;
    while (x);
    while (top)
        pr(sta[top--] ^ 48);
}

struct edge
{
    int v, next;
} e[N << 3];
int head[N], cnt;

inline void add(int u, int v)
{
    e[++cnt] = {v, head[u]}, head[u] = cnt;
}
int n, m, k, u, v, p, bcc, top;
int a[N], dfn[N], low[N], num[N], vis[N], stack[N];

void tarjan(int u)
{
    dfn[u] = low[u] = ++cnt;
    vis[u] = 1, stack[++top] = u;
    for (rnt i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v;
        if (!dfn[v])
            tarjan(v), low[u] = min(low[u], low[v]);
        else if (vis[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        bcc++;
        while (stack[top + 1] != u)
            num[stack[top]] = bcc, vis[stack[top--]] = 0;
    }
}

int main()
{
    n = read(), m = read(), k = read();
    srand(time(0));
    for (rnt i = 1; i <= m; i++)
    {
        u = read(), v = read();
        add(u + n, v);
        add(v + n, u);
    }
    for (rnt j = 1; j <= k; j++)
    {
        p = read();
        for (rnt i = 1; i <= p; i++)
        {
            a[i] = read();
            add(a[i], a[i] + 2 * n), add(a[i] + 3 * n, a[i] + n);
        }
        for (rnt i = 2; i <= p; i++)
        {
            add(a[i - 1] + 2 * n, a[i] + 2 * n);
            add(a[i] + 3 * n, a[i - 1] + 3 * n);
            add(a[i - 1] + 2 * n, a[i] + n);
            add(a[i], a[i - 1] + 3 * n);
        }
    }
    for (rnt i = 1; i <= 4 * n; i++)
        if (!dfn[i])
            tarjan(i);
    for (rnt i = 1; i <= n; i++)
        if (num[i] == num[i + n])
            return puts("NIE"), 0;
    puts("TAK");
    return 0;
}

当然，我们还有动态开点板，更加泛用更加快速！

//Just Sayori
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
#define rnt register int
#define gr getchar
#define pr putchar
#define N 2000005
#define M 1000000007
using namespace std;

inline ll read()
{
    ll x = 0, f = 1;
    char ch = gr();
    while (ch < '0' || ch > '9')
        ch == '-' ? f = -1, ch = gr() : ch = gr();
    while (ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = gr();
    return x * f;
}

inline void write(ll x)
{
    static int sta[39], top = 0;
    if (x < 0)
        pr('-'), x = -x;
    do
        sta[++top] = x % 10, x /= 10;
    while (x);
    while (top)
        pr(sta[top--] ^ 48);
}

struct edge
{
    int v, next;
} e[N << 3];
int head[N << 1], cnt;

inline void add(int u, int v)
{

    e[++cnt] = {v, head[u]}, head[u] = cnt;
}
int n, m, k, a, b, bcc, top, tot, now1, now2, last1, last2;
int dfn[N << 1], low[N << 1], num[N << 1], vis[N << 1], stack[N << 1];

void tarjan(int u)
{
    dfn[u] = low[u] = ++cnt;
    vis[u] = 1, stack[++top] = u;
    for (rnt i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v;
        if (!dfn[v])
            tarjan(v), low[u] = min(low[u], low[v]);
        else if (vis[v])
            low[u] = min(low[v], dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        bcc++;
        while (stack[top + 1] != u)
            num[stack[top]] = bcc, vis[stack[top--]] = 0;
    }
}

int main()
{
    n = read(), m = read(), k = read(), tot = 2 * n;
    for (rnt i = 1; i <= m; i++)
        a = read(), b = read(), add(a + n, b), add(b + n, a);
    for (rnt i = 1; i <= k; i++)
    {
        b = read();
        for (rnt i = 1; i <= b; i++)
        {
            a = read();
            now1 = ++tot, now2 = ++tot;
            add(a, now1), add(now2, a + n);
            if (i > 1)
            {
                add(last1, now1), add(now2, last2);
                add(a, last2), add(last1, a + n);
            }
            last1 = now1, last2 = now2;
        }
    }
    cnt = 0;
    for (rnt i = 1; i <= 2 * n; i++)
        if (!dfn[i])
            tarjan(i);
    for (rnt i = 1; i <= n; i++)
        if (num[i] == num[i + n])
            return puts("NIE"), 0;
    puts("TAK");
    return 0;
}

甚至还有炒鸡错解！甚至最优解第一！