/ ALGORITHM

2015 Southwestern Europe Regional Contest (SWERC) B

Problem Information

source: It’s from the kattis

Description

用 $26$ 个大写字母分别表示嫌疑人的代号,其中有三个人是 “Black Vienna”,除去这三个人后剩下的 $23$ 张标识有字母的扑克牌被随机分到了两名玩家的手中(允许有人一张牌都没有),现在对这两人做 $n$ 次查询,每次对其中一个人查询指定的某两张扑克牌中有几张在他的手中(回答可能与实际不符)。在这 $n$ 次查询的基础上,求出 “Black Vienna” 可能的集合数。

Input

3                                                                                     
AB 1 1
AC 2 1
BC 2 1
3
AB 1 2
AC 2 1
BC 1 0

Output

506                                                                                   
0

Solution

因为 $ \binom{26}{3} = 2600 $,所以 “Black Vienna” 可能的集合数最多为 $2600$,那么我们可以直接枚举集合,然后判定是否合法。
所以问题转换为在 $26$ 张扑克牌中,有指定的 $3$ 张两个玩家谁都没有,再有 $n$ 个查询,每个查询说明其中一个玩拥有这次查询的两张牌中的 $0/1/2$ 张,最后需要判断这个情况是否合法。那么这就是一道很明显的 2-SAT 问题了
我们定义 $ node(i,p)$ 为玩家 $p$ 拥有扑克牌 $i$,$FALSE$ 为辅助变量表示错误。

  • $FALSE$ 表示错误,即 $ FALSE \rightarrow \neg FALSE$
  • 指定的嫌疑人卡片$i$,两个玩家都没有:
    $ ( node(i ,p_1) \rightarrow FALSE) \wedge ( node(i, p_2) \rightarrow FALSE ) $
  • 除此之外的其它牌不是在玩家1手中就是在玩家2手中:$( \neg node(i ,p_1) \rightarrow node(i ,p_2) ) \wedge ( node(i ,p_1) \rightarrow \neg node(i ,p_2) ) $
  • 查询操作:
    • 两张卡牌都没有:$ ( node(i_1 ,p) \rightarrow FALSE) \wedge ( node(i_2, p) \rightarrow FALSE ) $
    • 只有其中一张牌:$ (node(i_1 ,p) \rightarrow \neg node(i_2, p) ) \wedge ( \neg node(i_1 ,p) \rightarrow node(i_2, p) )$
    • 两张卡牌都拥有:$( \neg node(i_1 ,p) \rightarrow FALSE) \wedge (\neg node(i_2, p) \rightarrow FALSE) $
      转换为析取式子:$ (a \rightarrow b) = (\neg a \vee b) $ 建边 $ < \neg a, b > $,然后 tarjan 缩点后,判断$\neg a$ 和 $a$ 是否在同一个连通块中来决定是否有解。

AC code

struct Node                                                                           
{
    char a,b;
    int c,d;
}node[55];

int main()
{
    int N;
    while(~scanf("%d", &N))
    {
        for(int i=1;i<=N;i++)
        {
            scanf(" %c%c %d %d", &node[i].a, &node[i].b, &node[i].c, &node[i].d);
        }
        int sum = 0,FALSE = 53;
        for(int a=1;a<=26;a++)
        {
            for(int b=a+1;b<=26;b++)
            {
                for(int c=b+1;c<=26;c++)
                {
                    TS.init(53);
                    TS.add_clause(FALSE, false, FALSE , false);
                    for(int i=0;i<2;i++)
                    {
                        TS.add_clause( i*26+a, false, FALSE, true);
                        TS.add_clause( i*26+b, false, FALSE, true);
                        TS.add_clause( i*26+c, false, FALSE, true);
                    }
                    for(int i=1;i<=26;i++)
                    {
                        if(i==a || i==b || i==c) continue;
                        TS.add_clause(i, true,  26+i, true);
                        TS.add_clause(i, false, 26+i, false);
                    }
                    for(int i=1;i<=N;i++)
                    {
                        int one = node[i].a-'A'+1, two = node[i].b - 'A'+1;
                        int id = node[i].c-1, num = node[i].d;
                        switch(num)
                        {
                        case 0: 
                            TS.add_clause(id*26+one, false, FALSE, true);
                            TS.add_clause(id*26+two, false, FALSE, true);
                            break;
                        case 1:
                            TS.add_clause(id*26+one, true, id*26+two, true);
                            TS.add_clause(id*26+one, false,id*26+two, false);
                            break;
                        case 2:
                            TS.add_clause(id*26+one, true, FALSE, true);
                            TS.add_clause(id*26+two, true, FALSE, true);
                        }
                    }
                    sum+=(TS.solve());
                }
            }            
        }
        printf("%d\n", sum);
    }
}