题解 P3034 【[USACO11DEC]牛摄影Cow Photography】

· · 题解

我又来发第一个题解辣～【以下代码省略头文件】

本题要考虑相对位置而不是绝对位置。。。其实很容易想到：如果5张照片中有大于或等于3张照片里牛A在牛B的前面，那么开始序列中牛A一定在牛B之前。这样我们就很容易得到了下面的代码：

int n;
int p,ans[20005];
map<int,int>r[10];
bool cmp(int x,int y)
{
    int f=0;
    for(int i=1;i<=5;i++)
    {
        if(r[i][x]<r[i][y])f++;
    }
    return f>=3;
}
int main()
{
    cin>>n;
    for(int k=1;k<=5;k++)
    {
        for(int i=1;i<=n;i++)
        {
            cin>>p;
            ans[i]=p;
            r[k][p]=i;
        }
    }
    sort(ans+1,ans+n+1,cmp);
    for(int i=1;i<=n;i++)cout<<ans[i]<<endl; 
    return 0;
}

这个代码在USACO官网提交是AC的，USACO标程也差不多这样，但是在洛谷上只能拿80分，TLE后两个大数据，这是为什么呢？我也在这里卡了很久，不知其为啥TLE。（插叙：于是我傻逼的与kkk争论了起来，kkk说是STL-sort常数大，说改成手写版就AC了～这是有道理的，但是我有更好的办法，只需改一点点2333，最终还比kkk总共快500ms左右，想知道的继续看下去！）其实这段代码本身就是超时的，USACO开了O2所以能过。你可能会说这程序sort是nlogn，所以复杂度就是O(nlogn)，可以过啊～但是别忘了map是很慢的，map速度是logn，其中n是节点个数。我们可以精确计算下上面代码的时间复杂度：5*nlogn*2*logn=10*n*(logn)^2，n取200000，所以算一下就知道大约是578000000，这还只是算了sort的cmp函数里的复杂度啊就早爆了！所以立马就得到用map不行，那么秒想到用哈希啊！（注意要解决哈希冲突）很容易得到了以下代码：

int n;
int p,ans[20005];
vector<pair<int,int> >r[10][9975];
bool cmp(int x,int y)
{
    int f=0;
    for(int i=1;i<=5;i++)
    {
        int num1=0,num2=0;
        int kkk1=x%9973,kkk2=y%9973;
        for(int j=0;j<r[i][kkk1].size();j++)
        {
            if(r[i][kkk1][j].first==x)num1=r[i][kkk1][j].second;
        }
        for(int j=0;j<r[i][kkk2].size();j++)
        {
            if(r[i][kkk2][j].first==y)num2=r[i][kkk2][j].second;
        }
        if(num1<num2)f++;
    }
    return f>=3;
}
int main()
{
    cin>>n;
    for(int k=1;k<=5;k++)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&p);
            ans[i]=p;
            r[k][p%9973].push_back(make_pair(p,i));
        }
    }
    sort(ans+1,ans+n+1,cmp);
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
}

虽然长了一些，但相比kkk的方法修改幅度小很多。我们再算下时间复杂度：忽略常数是5*nlogn，n取200000，算出来得：17000000，显然之虽然仅是STL-sort的cmp函数内时间复杂度，但是就算加上其他的复杂度也不会有问题嘚～所以这题就轻松搞定啦！23333 这也告诉我们C++党：不能依赖STL，特别是map之类狂慢的。。。也一定要算算时间复杂度，不能盲目地觉得AC就提交了～