自动搬运

查看原文

来自洛谷，原作者为

	Qing_s 她殺了我

搬运于2025-08-24 21:43:54，当前版本为作者最后更新于2020-11-01 16:20:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P2965 【[USACO09NOV]The Grand Farm-off S】

挺水的PJ-。

u1s1，第一眼看见题面把我吓到了。

但是！作为新时代的良好青年，要发扬不屈不挠的进取精神！

然后我就把它A了。

分析题意：

农夫约翰有 $3 * N$ (1 < N < 500000)头牛，编号依次为1..#N，每头牛都有一个整数值的体 重。约翰准备参加农场技艺大赛，向广大的农业社区展示他的奶牛. 大赛规则允许约翰带N头牛参赛.约翰给每头牛赋予了一个“有用度”Ui，它表 示了某头牛在比赛中的有用程度.约翰希望他选出的奶牛的有用度之和最大.

人话翻译：

在 $3 * N$ 个数中，每个数有对应的 $u_i$ 和 $w_i$ , 求 N 个 $u_i$ 的最大值，最大值相同时让 $w_i$ 最小 。

这不就好起来了？我们只需要使用一个结构体来存 $u_i$ 和 $w_i$ ，使用 sort 排一遍序。 然后输出前 $N$ 个 $u_i$ 的和即可。

那么我们的 $u_i$ 和 $w_i$ 怎么求呢？

题干中给出了公式：

W_i = (a*i^5+b*i^2+c) mod d 
and   U_i = (e*i^5+f*i^3+g) mod h 
 (0 <= a <= 1,000,000,000; 0 <= b <= 1,000,000,000; 0 <= c <= 1,000,000,000; 0 <= e <= 
1,000,000,000; 0 <= f <= 1,000,000,000; 0 <= g <= 1,000,000,000; 10,000,000 <= d <= 1,000,000,000; 10,000,000 <= h <= 1,000,000,000).

嗯... 还不如不给。

再让我们用人话翻译一下：

$w_i$ = ( a * $i^5$ + b * $i^2$ + c ) % d

$u_i$ = ( e * $i^5$ + f * $i^3$ + g ) % h

瞬间就清醒了呢！

代码也就很好写啦！

但是还是有 小坑点 的 ：

1. 循环的下标是从 0 开始，这点题目中没有给出来。
2. 一定一定一定要开 longlong 。
3. 注意 N 的范围是 $N≤50000$ , 但是你要求的是 $3 * N$ 的数据！所以数组要不少于 1500000 。
4. 使用 C++ 库函数 pow 会出锅（起码我是 。

除此之外就没什么问题了。

关于sort

由于我们使用结构体来存 $u_i$ 和 $w_i$ 。

所以我们要手写一个 cmd (很简单！

bool cmd( node x , node y ){
    if( x.u != y.u )
        return x.u > y.u ;//如果有用度不等，将有用度大的放前面。
    else
        return x.w < y.w ;//如果有用度相等，将体重小的放前面。
}

第一遍我是用 pow 写的，只得了 10 分（丢人 。

代码如下：

#include<bits/stdc++.h>

using namespace std ;

struct node{
    long long u ; long long w ;
}cow[1510000] ;

long long n , a , b , c , d , e , f , g , h , m ;

long long ans ;

bool cmd( node x , node y ){
    if( x.u != y.u )
        return x.u > y.u ;
    else
        return x.w < y.w ;
}

int main(){
    cin >> n >> a >> b >> c >> d >> e >> f >> g >> h >> m ;
    for( int i = 0 ; i < 3 * n ; i++ ){
        cow[i].w = ( a * pow( i , 5 ) + b * pow( i , 2 ) + c ) ;
        cow[i].w %= d ;
        cow[i].u = ( e * pow( i , 5 ) + f * pow( i , 3 ) + g ) ;
        cow[i].u %= h ;
        cout << cow[i].w << " " << cow[i].u << endl ;
    }
    sort( cow , cow + 3 * n , cmd ) ;
    for( int i = 0 ; i < n ; i++ ){
        // cout << cow[i].u << " " ;
        ans += cow[i].w ;
        ans %= m ;
    }
    cout << ans % m ;
    return 0 ;
}

然后。。。(雾

经过深刻的思索，我认为是 pow 和 数组大小还有 int 把我 残害（bushi 了。

然后改成了这样：

#include<bits/stdc++.h>

using namespace std ;

struct node{
    long long u ; long long w ;
}cow[1510000] ;

long long n , a , b , c , d , e , f , g , h , m ;

long long ans ;

bool cmd( node x , node y ){
    if( x.u != y.u )
        return x.u > y.u ;
    else
        return x.w < y.w ;
}

int main(){
    cin >> n >> a >> b >> c >> d >> e >> f >> g >> h >> m ;
    a %= d ;b %= d ; c %= d ; e %= h ; f %= h ; g %= h ;
    for( int i = 0 ; i < 3 * n ; i++ ){
        long long i1 = i % d , ii1 = i % h ;
        long long i2 = i1 * i % d , ii2 = ii1 * i % h ;
        long long i3 = i2 * i % d , ii3 = ii2 * i % h ;
        long long i4 = i3 * i % d , ii4 = ii3 * i % h ;
        long long i5 = i4 * i % d , ii5 = ii4 * i % h ;
        cow[i].w = ( a * i5 + b * i2 + c ) ;
        cow[i].w %= d ;
        cow[i].u = ( e * ii5 + f * ii3 + g ) ;
        cow[i].u %= h ;
    }
    sort( cow , cow + 3 * n , cmd ) ;
    for( int i = 0 ; i < n ; i++ ){
        ans += cow[i].w ;
        ans %= m ;
    }
    cout << ans % m ;
    return 0 ;
}

自认为做了比较多的优化。

一步取模，步步取模！

然后就A了！虽然有点慢。

这道题考察的小细节相对于其他pj-来说还是多那么一些的。

关于 pow，能不用就不用。

撒花✿✿ヽ(°▽°)ノ✿。

求通过QAQ，这是我写的最多的一篇题解。