重测真快乐

~~请原谅我看着一个个80分感到十分快乐。~~

我造了几组数据让老K加上去重测了一下..只不过只造了四组，所以还是可能被奇怪的做法过掉..

目前的几种正解：

$P_{i,j}=\begin{cases}a_i<a_j&\min(a_i,b_j)=\min(a_j,b_i)\\\min(a_i,b_j)<\min(a_j,b_i)&otherwise\end{cases}$
$P_{i,j}=\begin{cases}b_i>b_j&\min(a_i,b_j)=\min(a_j,b_i)\\\min(a_i,b_j)<\min(a_j,b_i)&otherwise\end{cases}$
令 $d_i=\begin{cases}1&(a_i>b_i)\\0&(a_i=b_i)\\-1&(a_i<b_i)\end{cases}$ ， $P_{i,j}=\begin{cases}d_i<d_j&(d_i\ne d_j)\\a_i<a_j&(d_i=d_j\le0)\\b_i>b_j&(d_i=d_j=1)\end{cases}$

任选一个作为比较函数 sort 一下就可以了。（本人不太喜欢第三种做法，虽然网上几乎全是第三种做法，但它实在是太麻烦了而且不直观难以想到。）

如果需要测试一个函数能否作为此题的比较函数，可以将下面代码中的 cmp 函数替换，然后运行。

如果输出“Good job! This function can be used to solve this problem!”，就是字面意思，这个做法是对的；否则的话，就会显示为什么错，并举例说明。

错误有四种类型：

Not the best：你的比较函数不能保证排序后是最优解。即，当 $cmp(i,j)=true$ 时，并不总有 $\min(a_i,b_j)\le\min(a_j,b_i)$ 。这种情况下会举例 $a[i],b[i],a[j],b[j]$ 说明。
No irreflexivity：你的比较函数不具有非自反性。即：存在 $i$ 使得 $cmp(i,i)=true$ 。这种情况下会举例 $a[i],b[i]$ 说明。
No transitivity：你的比较函数不具有传递性。即：存在 $i,j,k$ 使得 $cmp(i,j)=cmp(j,k)=true,\,cmp(i,k)=false$ 。这种情况下会举例 $a[i],b[i],a[j],b[j],a[k],b[k]$ 说明。
No transitivity of incomparability：你的比较函数不具有不可比性的传递性。即：存在 $i,j,k$ 使得 $cmp(i,j)=cmp(j,i)=cmp(j,k)=cmp(k,j)=false,\,cmp(i,k)=true$ 。这种情况下会举例 $a[i],b[i],a[j],b[j],a[k],b[k]$ 说明。

关于这道题，还可以参考我在洛谷写的题解以及另一篇文章。

注：实际上，通过下面这份代码的测试是正解的充分条件，大约不是必要条件..但正常的正解都能通过下面的测试。

CPP

#include <cstdio>
#include <algorithm>

using namespace std;

int a[10],b[10];

bool cmp(int i,int j)
{
    return min(a[i],b[j])==min(a[j],b[i])?a[i]<a[j]:min(a[i],b[j])<min(a[j],b[i]);
}

int main()
{
    for (a[0]=1;a[0]<=6;++a[0])
    {
        for (b[0]=1;b[0]<=6;++b[0])
        {
            if (cmp(0,0))
            {
                printf("No irreflexivity:%d %d\n",a[0],b[0]);
                return 0;
            }
            for (a[1]=1;a[1]<=6;++a[1])
            {
                for (b[1]=1;b[1]<=6;++b[1])
                {
                    if (cmp(0,1)&&min(a[0],b[1])>min(a[1],b[0]))
                    {
                        printf("Not the best:%d %d %d %d\n",a[0],b[0],a[1],b[1]);
                        return 0;
                    }
                    for (a[2]=1;a[2]<=6;++a[2])
                    {
                        for (b[2]=1;b[2]<=6;++b[2])
                        {
                            if (cmp(0,1)&&cmp(1,2)&&!cmp(0,2))
                            {
                                printf("No transitivity:%d %d %d %d %d %d\n",a[0],b[0],a[1],b[1],a[2],b[2]);
                                return 0;
                            }
                            if (!cmp(0,1)&&!cmp(1,0)&&!cmp(1,2)&&!cmp(2,1)&&(cmp(0,2)||cmp(2,0)))
                            {
                                printf("No transitivity of incomparability:%d %d %d %d %d %d\n",a[0],b[0],a[1],b[1],a[2],b[2]);
                                return 0;
                            }
                        }
                    }
                }
            }
        }
    }
    
    printf("Good job! This function can be used to solve this problem!");

    return 0;
}

讨论操作

回复

相关推荐

重测真快乐