noip2023 三值逻辑题解

gapeqi · 2023-11-19 11:08:22 · 题解

写一篇给萌新看的题解。

先看题。注意到每个变量的终态是只与初始态有关的，且只关于一个变量。

例如 x_i=\lnot x_j，这里我表示的意思是，左边是终态（最终的值），右边是初始的值（即一开始赋的初值）。

可以发现先预处理出来没有影响，而这就涉及到我们的第一个数组（为了易懂，标出所有重要变量与数组的功能和名称，加粗）了：

名称：val
功能：标记 x_{1\sim n} 的终态由哪个初始值产生。
记录：val[i]=j 代表：

当 j=n+1 时，最后 val[i] 被赋成了 T，与其他变量无关。
当 j=n+2 时，最后 val[i] 被赋成了 F，与其他变量无关。
当 j=n+3 时，最后 val[i] 被赋成了 U，与其他变量无关。
当 1\le j\le n 时，最后 val[i] 被赋成了 val[j]（初值），与其他变量无关。
当 -n\le j\le 1 时，最后 val[i] 被赋成了非 val[j]（初值），与其他变量无关。

代码：

cin>>op>>x; // 这里写的是读入每一个赋值操作的代码
if(op=='+') // 直接赋值
{
    cin>>y;
    val[x]=val[y]; // x 的值变成赋值给 y 的初值
}
if(op=='-') // 取非赋值
{
    cin>>y;
    if(abs(val[y])<=n) // 如果是变量
        val[x]=-val[y]; // 直接取非
    else // 否则是值，直接照抄
    {
        if(val[y]==n+1)
            val[x]=n+2;
        if(val[y]==n+2)
            val[x]=n+1;
        if(val[y]==n+3)
            val[x]=n+3;
    }
}
if(op=='T') // 也是照抄
    val[x]=n+1;
if(op=='F')
    val[x]=n+2;
if(op=='U')
    val[x]=n+3;

我们做好了题目中给的一大任务：变量的赋值。

那么现在如何去处理这些变量？这里我们思考，val 的值如何与变量的比较有关系。

这个不难，val 是 n+1\sim n+3 代表是一个值，否则 val 正就直接赋值，val 负就取非再赋值。

我们把 x 与 val[x]，其中 abs(val[x])<=n 时，称它为一个“等价关系”（虽然数学老师不喜欢看见这种定义），把可以用“等价关系”联通的极大点集叫做一个连通块。

注意到连通块之间相互不影响，对于每个连通块分别处理即可。

首先，对于每个连通块，可以认为（按照题目的输入的 +，-）只有两种“等价关系”：+，-。

那么，由于 U 怎么运算都是 U，那么如果一个连通块里有赋值为 U 的节点，这个连通块就对答案没有贡献，就消掉了。（这里的消打引号，意思是无用，下同）这是因为这样的连通块中，只能全是 U。

接下来考虑无 U 连通块，这里先考虑“等价关系”，注意到任意一个连通块，如果“等价关系”的逻辑错误（例如全 - 三元环的）存在，这个连通块也消掉了。（即只能全是 U 了）。

如果没有逻辑错误呢？这时候可以钦定一个节点为 T，先搜索一遍，这样就可以确定每个节点的值了。搜索后再看一遍“等价关系”是否正确，这样就可以清理掉“等价关系”的逻辑错误。

最后一个问题就是，搜完一遍之后，每个 val[x]=n+1,n+2 结点的值与原来不符怎么办？这个也很好解决，它们的值要么全不同于搜完的值，要么全相同于搜完的值（这是因为我们钦定了一个节点是 T），最后统计一遍即可，这样就清除掉了最后一种消掉的情况。

思维部分，结束，下面开始代码部分。

先总结一下我们还没整理到的要做的事（分布于刚刚的黑体字中）：

搜索一遍。
连通块有 U 的情形，消掉连通块。
“等价关系”的逻辑错误，消掉连通块。
val[x]=n+1,n+2 结点的值不符，消掉连通块。
将没有被消掉的连通块大小相加。

接下来按每个部分整理：

首先需要像建图一样建边（即“等价关系”），这里我用的是 vector。

建边的具体形式为：双向边，权值存 +-，边为 + 就存入 1，边为 - 就存入 -1。

代码：

struct node{
    int poi,op; // op 即为正负一
};
vector<node> e[100005];
......
......
for(int x=1;x<=n;x++)
    if(val[x]<=n) // 只建非直接赋 TFU 值 的边
    {
        if(val[x]>0) // +
        {
            e[x].push_back((node){val[x],1});
            e[val[x]].push_back((node){x,1});
        }
        else // -
        {
            e[x].push_back((node){-val[x],-1}); // 注意这里要 -val[x]
            e[-val[x]].push_back((node){x,-1});
        }
    }

搜索一遍。

需要用到的变量/数组有：cnt（连通块个数），siz[]（连通块大小），fh[]（每个点的符号，T 为 1，F 为 -1），belong[]（每个点属于的连通块编号）。

代码：

void dfs(int poi,int fat) // poi, father
{
    belong[poi]=cnt,siz[cnt]++; // 处理 belong, siz
    int ssiz=e[poi].size();
    for(int i=0;i<ssiz;i++)
    {
        int nxt=e[poi][i].poi;
        if(nxt==fat||belong[nxt]!=0) // 遍历到过就 continue
            continue;
        fh[nxt]=fh[poi]*e[poi][i].op; // 更新符号
        belong[poi]=cnt,dfs(nxt,poi); // 继续
    }
} 
......
......
for(int i=1;i<=n;i++) // 对于每个变量而言
    if(belong[i]==0) // 如果还没遍历到
        cnt++,fh[i]=1,dfs(i,0); // 多了一个连通块，此节点钦定为 T，开始搜索

连通块有 U 的情形，消掉连通块。

现在开始消掉连通块的过程了。

定义 bool 数组 xiao[] 表示这个连通块有没有被消掉。

那么现在只需要判断一遍，对每个 U 消掉 belong[] 的连通块即可。

代码：

for(int i=1;i<=n;i++) // 对于每个变量
    if(val[i]==n+3) // 如果是 U
        xiao[belong[i]]=1; // 消掉所属的连通块

“等价关系”的逻辑错误，消掉连通块。

对每个等价关系，判断一下，如果是 +，值应相同，反之值不相同即可。

代码：

for(int i=1;i<=n;i++) // 对于每个变量
    if(val[i]<=n) // 如果不是 TFU
    {
        if(val[i]>0) // 等价关系为 +
        {
            if(fh[i]!=fh[val[i]]) // 不等就不行
                xiao[belong[i]]=1;
        }
        else // 等价关系为 -
        {
            if(fh[i]==fh[-val[i]]) // 相等就不行
                xiao[belong[i]]=1;
        }
    }

val[x]=n+1,n+2 结点的值不符，消掉连通块。

这里定义数组 hav[]。

名称：hav
功能：标记连通块的符号。
记录：hav[i]=0/1/-1 代表：

当它为 0 时，连通块的符号与原来相符。
当它为 1 时，连通块的符号与原来不相符。
当它为 -1 时，还未赋值。

代码：

for(int i=1;i<=n;i++)
{
    if(val[i]==n+1) // 如果为 T
    {
        if(hav[belong[i]]==-1)
            hav[belong[i]]=(fh[i]==1);
        else if(hav[belong[i]]!=(fh[i]==1))
            xiao[belong[i]]=1;
    }
    if(val[i]==n+2) // 如果为 F
    {
        if(hav[belong[i]]==-1)
            hav[belong[i]]=(fh[i]==0);
        else if(hav[belong[i]]!=(fh[i]==0))
            xiao[belong[i]]=1;
    }
}

将没有被消掉的连通块大小相加。

不用说了吧。

代码：

int sum=0;
for(int i=1;i<=cnt;i++)
    if(xiao[i])
        sum+=siz[i];
cout<<sum<<endl;

综上，本题结束。

注：如果按这样写，感觉可以评黄（

noip2023 三值逻辑 题解

noip2023 三值逻辑题解