P8899题解

· · 题解

看不懂楼上下神犇做法的来这里！！！

//这个题解可以让您以最快的时间读完，有重点加粗标记
//是作者以1个小时调程序+2个小时写题解的心血
//诣在讲透讲懂本题，让您理解
//完全聚焦本题重难点
//还在等什么？快来看吧！

看了诸位大佬的题解，本人认为对于我们这些蒟蒻有些简短的残忍，于是写一个亲民又朴实的题解，分析清楚楼上大佬的做法。

楼上叙述的做法是：枚举每一位，将这一位是 1 和 0 的分别考虑。如果某一位是 1 的答案都一样，那么这一位上所有为 1 或 0 的语句都可以删除。如果最后被删光了就可以，否则就说谎了。

----------------------------------------------------------------好好理解上面的方法才能继续----------------------------------------------------------------

那么我这个蒟蒻就开始不理解为什么了，有两点：

  1. 这么做的道理是啥，看起来有点投机取巧
  2. 就算这有道理，好像顺序还不大对啊，题目没说固定啊

No.1Problem

我研究了一会儿，第一点懂了，下面画个图：

如此我们就完美的掉入了坑中，注意 return true/false 是有结束程序的功能的，所以在已经被删除的语句我们要不考虑了，于是正确的图：

所以这些语句就都被删掉了。那么这样的原理？因为如果顺序固定正向，碰到了位置上一样且答案一样的就有充分的证据说明这里可以作为一个判断语句，注意我们是构造不是求解，不需要唯一正确，所以就一定能删掉。

于是其实就是一次模拟，最后查一遍如果没有删完，那么说明到了最后一个语句都没办法判断完成，就是在说谎。

No.2Problem

最玄学的问题来了，但是其实有了上一问题的深刻理解，这个也不难参透。假设有数语句不可以在正序下删除，令他们为集合 q，那么我们首先分析出 q 都有至少一位相同，且 q 内的语句答案都相同，于是满足假设的情况只能是：当正向删除的时候有一些语句，令他们为集合 p ，那么 p 的答案全部不同于 q 的答案，且 p 与 q 有且仅有一位都相同，而不同方向可以提前删掉 p。再分析，得到 q 中的语句必然相同的位都在 p 的相同位之前，要不然别的位还可以完成，又有 p 中的相同位上 q 必然都不等于 p 的对应位要不就提前删了，于是得到 q 在 p 的相同位上也都相同且不等于 q 的对应位，那么事实上我们就可以在正序的情况下在该位同时删掉 p 和 q，假设不成立，证毕！

图总是最清楚明了的：

----------------------------------------------------------------喘口气我们继续----------------------------------------------------------------

那么终于证完了，下面就是代码实现了！

我的代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n , t , p[105] , f[105] , m;
string s[105];
bool y[105][105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL) , cout.tie(NULL);
    cin >> t;
    while ( t-- )
    {
        cin >> m >> n;
        bool flag[n + 1] , e = 1 , k[n + 1];
        for ( int i = 1; i <= n; i++ )  cin >> s[i] >> p[i] , flag[i] = 0;
        for ( int j = 1; j <= m; j++ )
            for ( int l = 0; l < m; l++ )
            {
                int k[2] = { 0 , 0 } , buck[2] = { 2 , 2 };
                for ( int i = 1; i <= n; i++ )
                {
                    y[i][l] = ( s[i][l] == '1' );
                    if ( flag[i] )  continue;
                    if ( buck[y[i][l]] == 2 )   buck[y[i][l]] = p[i];
                    else    if ( buck[y[i][l]] != p[i] )    k[y[i][l]] = 1;
                }
                for ( int i = 1; i <= n; i++ )  if ( !k[y[i][l]] )  flag[i] = 1;
            }
        for ( int i = 1; i <= n; i++ )  if ( !flag[i] ) e = 0;
        if ( e )    cout << "OK" << endl;
        else    cout << "LIE" << endl;
    }
    return 0;
}

//希望这篇题解对您有帮助，也希望推动洛谷和谐友爱的学习交流环境，望您支持，谢谢！