题解：游戏

一、题目分析

本题中小(L)计划进行(n)场游戏，每场游戏使用一张地图，小(L)有三辆赛车(A)、(B)、(C)，地图有四种(x)、(a)、(b)、(c)，且不同赛车不适合某些特定地图。同时小(L)对游戏有一些特殊要求，用四元组((i, h_i, j, h_j))表示若在第(i)场使用型号为(h_i)的车子，则第(j)场游戏要使用型号为(h_j)的车子。要求为小(L)选择每场游戏使用的赛车，若有多种方案输出任意一种，若无解输出“(-1)”。

二、解题思路

本题通过将问题转化为2-SAT问题，利用Tarjan算法求强连通分量来求解。

（一）变量与图的构建

• 对于每场游戏(i)，设两个布尔变量：
  • 变量(x_i)表示选择一种赛车（通过后续函数映射确定具体赛车）。
  • 变量(\neg x_i)表示选择另一种赛车（同样通过函数映射确定具体赛车）。
• 构建有向图：
  • 遍历每个游戏要求四元组((i, h_i, j, h_j))：
    • 若第(i)场游戏的地图不限制(h_i)这辆车（即不是对应不适合的地图），且第(j)场游戏的地图也不限制(h_j)这辆车，则根据规则添加有向边。
    • 若第(i)场游戏的地图不限制(h_i)这辆车，但第(j)场游戏的地图限制(h_j)这辆车，则添加特殊的有向边来保证条件成立。
• 由于地图(x)适合所有赛车，最多有(d)张，对这(d)张地图进行状态枚举（将其分别设为(a)或(b)），每种状态下都构建图并检查是否有解。

（二）辅助函数

• get函数：根据游戏场次(x)、选择的赛车(b)以及一个标志位(t)，结合地图类型，返回对应的节点编号。若当前地图和选择的赛车不冲突（通过特定计算判断）且标志位为某种情况，或者冲突且标志位为另一种情况，则返回(x + n)，否则返回(x)。
• put函数：根据游戏场次(x)和一个标志位(t)，结合地图类型，返回应该选择的赛车字符。

（三）Tarjan算法求强连通分量

与常规2-SAT问题中的Tarjan算法使用方式一致：
1. 初始化：定义时间戳(ts)、栈(stk)、数组(dfn)（记录首次访问时间）、(low)（记录能追溯到的最早首次访问时间）等。
2. 深度优先搜索：从每个未访问的节点(u)开始深度优先搜索。访问(u)时初始化相关变量，将(u)入栈并标记在栈中。遍历(u)的出边，根据边指向节点的访问情况更新(low[u])。
3. 确定强连通分量：当(low[u] = dfn[u])时，从栈中弹出节点并标记它们属于同一个强连通分量。

（四）判断是否有解及输出方案

• 判断是否有解：对于每场游戏(i)，若(x_i)和(\neg x_i)（即节点(i)和(i + n)）在同一个强连通分量中，则无解。
• 输出方案：若有解，对于每场游戏(i)，比较节点(i)和(i + n)所在强连通分量的编号。若(id[i] < id[i + n])，通过put函数确定并输出一种赛车；否则通过put函数确定并输出另一种赛车。

三、代码实现细节

（一）头文件与全局变量

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int n, d, m;
char s[N];
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts, stk[N], top;
int id[N], cnt;
bool ins[N];
int pos[10];

struct Op
{
    int x, y;
    char a, b;
}op[M];

• 引入输入输出、字符串操作、算法相关头文件。
• 定义常量(N)和(M)表示节点数和边数上限。
• 定义变量(n)为游戏场数，(d)为地图(x)的数量，(m)为游戏要求的数量，以及存储地图序列的字符数组(s)。
• 定义邻接表相关数组(h)、(e)、(ne)、(idx)，Tarjan算法相关数组(dfn)、(low)、(ts)、(stk)、(top)、(id)、(cnt)和标记数组(ins)。
• 定义数组(pos)存储地图(x)在序列中的位置，以及结构体(Op)存储游戏要求的四元组信息。

（二）get函数

int get(int x, char b, int t)
{
    char a = s[x] - 'a';
    b -= 'A';
    if (((a + 1) % 3 != b) ^ t) return x + n;
    return x;
}

根据输入的游戏场次(x)、赛车字符(b)和标志位(t)，结合当前游戏的地图类型，判断是否冲突并返回对应的节点编号。

（三）put函数

char put(int x, int t)
{
    int y = s[x] - 'a';
    return 'A' + ((y + t) % 3);
}

根据游戏场次(x)和标志位(t)，结合当前游戏的地图类型，返回应该选择的赛车字符。

（四）添加边函数add

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

用于向邻接表中添加一条从节点(a)到节点(b)的有向边。

（五）Tarjan算法函数tarjan

void tarjan(int u)
{
    dfn[u] = low[u] = ++ ts;
    stk[ ++ top] = u, ins[u] = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (ins[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        int y;
        cnt ++ ;
        do
        {
            y = stk[top -- ], ins[y] = false, id[y] = cnt;
        } while (y != u);
    }
}

• 开始时初始化(dfn[u])和(low[u])，将(u)入栈并标记在栈中。
• 遍历(u)的出边，根据节点(j)的访问情况更新(low[u])。
• 当(low[u] = dfn[u])时，弹出栈中节点并标记它们属于同一个强连通分量。

（六）work函数

bool work()
{
    memset(h, -1, sizeof h);
    memset(dfn, 0, sizeof dfn);
    idx = ts = cnt = 0;

    for (int i = 0; i < m; i ++ )
    {
        int x = op[i].x - 1, y = op[i].y - 1;
        char a = op[i].a, b = op[i].b;
        if (s[x] != a + 32)
        {
            if (s[y] != b + 32) add(get(x, a, 0), get(y, b, 0)), add(get(y, b, 1), get(x, a, 1));
            else add(get(x, a, 0), get(x, a, 1));
        }
    }

    for (int i = 0; i < n * 2; i ++ )
        if (!dfn[i])
            tarjan(i);

    for (int i = 0; i < n; i ++ )
        if (id[i] == id[i + n])
            return false;

    for (int i = 0; i < n; i ++ )
        if (id[i] < id[i + n]) putchar(put(i, 1));
        else putchar(put(i, 2));

    return true;
}

• 初始化邻接表和Tarjan算法相关变量。
• 遍历游戏要求四元组，根据规则在图中添加有向边。
• 对每个未访问的节点调用Tarjan算法，求出强连通分量。
• 检查每场游戏对应的两个节点是否在同一个强连通分量中，判断是否有解。
• 若有解，输出每场游戏选择的赛车。

（七）main函数

int main()
{
    scanf("%d%d", &n, &d);
    scanf("%s", s);
    for (int i = 0, j = 0; i < n; i ++ )
        if (s[i] == 'x')
            pos[j ++ ] = i;

    scanf("%d", &m);
    for (int i = 0; i < m; i ++ )
        scanf("%d %c %d %c", &op[i].x, &op[i].a, &op[i].y, &op[i].b);

    for (int k = 0; k < 1 << d; k ++ )
    {
        for (int i = 0; i < d; i ++ )
            if (k >> i & 1) s[pos[i]] = 'a';
            else s[pos[i]] = 'b';

        if (work()) return 0;
    }

    puts("-1");
    return 0;
}

• 读取游戏场数(n)、地图(x)的数量(d)和地图序列(s)，记录地图(x)的位置。
• 读取游戏要求的数量(m)和具体的游戏要求四元组。
• 对地图(x)的状态进行枚举（(2^d)种状态），每种状态下修改地图序列并调用work函数检查是否有解。
• 若所有状态下都无解，输出“(-1)”。

四、时间复杂度和空间复杂度

（一）时间复杂度

• 建图与枚举阶段：对于(2^d)种地图(x)的状态枚举，每次枚举后遍历(m)个游戏要求建图，时间复杂度为(O(2^d \times m))。
• Tarjan算法阶段：对图中的每个节点和边进行一次访问，图中节点数为(2n)，边数最多为(O(m))，每次Tarjan算法时间复杂度为(O(2n + m))，总时间复杂度为(O(2^d \times (2n + m)))。
• 因此，总的时间复杂度为(O(2^d \times (2n + m)))。

（二）空间复杂度

• 邻接表存储图的边信息，最多有(O(m))条边，空间复杂度为(O(m))。
• 其他辅助数组如(dfn)、(low)、(id)等，大小为(2n)，空间复杂度为(O(n))。
• 所以，总的空间复杂度为(O(m + n))。