[BZOJ2018]&&[Usaco2009 Nov] 农场技艺大赛

2014-09-25
竞赛题解 / 模拟
BZOJUSACO

描述 Description

农夫约翰有 3N(1 ≤ N ≤ 500000) 头牛，编号依次为 1..3N，每头牛都有一个整数值的体重 Wi(l ≤ Wi ≤ d). 约翰准备参加农场技艺大赛， 向广大的农业社区展示他的奶牛.

大赛规则允许约翰带 N 头牛参赛. 约翰给每头牛赋予了一个 “有用度”Ui(l ≤ Ui ≤ h) ， 它表示了某头牛在比赛中的有用程度. 约翰希望他选出的奶牛的有用度之和最大.

有可能选出很多组的 N 头牛都能达到有用度最大和. 约翰害怕选出的 N 头牛的总重量会给大赛带来震撼，所以，要考虑优先选择体重轻的奶牛.

帮助约翰选出 N 头总重量最轻， 并且有用度之和最大的奶牛. 输出体重模 M(107 ≤ M ≤ 109) 后的余数.

在意: 为了使输入更快，约翰使用了一个多项式来生成每头牛的体重和有用度，对每头牛 I，体重和有用度的计算公式为：

\[ W_{I}=(aI^{5}+bI^{2}+c) mod d \ U_{I}=(eI^{5}+fI^{3}+g) mod h \]

各个系数的取值范围为：0 ≤ a,b,c,d,e,f,g ≤ 109，107 ≤ d,h ≤ 109. 这个多项式有时会生成重复的数，你的程序要正确处理这种情况.

输入格式 InputFormat

第 1 行：10 个空格分开的整数: N, a, b, c, d, e, f, g, h, M

输出格式 OutputFormat

第 1 行：满足总重量最轻，且用度之和最大的 N 头奶牛的总体重模 M 后的余数。

样例输入 SampleInput

222500 23637582 79462751 57479383 82737269 91983785 89849583 36429858 95372257 17222153

样例输出 SampleOutput

15270656

来源 Source

Silver

BZOJ 2018

代码 Code

注意编号是从 0 开始的 = =。。。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t;
long long n,m,l,r,k,z,y,x;
const int maxn=500005;
struct cow
{
    long long w,u;
    bool operator < (const cow& temp) const
    {
        return (u!=temp.u)?(u>temp.u):(w<temp.w);
    }
}co[3*maxn];
long long a,b,c,d,e,f,g,h,ans;
inline void make_data()
{
    long long i,j;
    long long t[6];
    for (i=0;i<n*3;i++)
    {
        for (t[1]=i%d,j=2;j<=5;j++) t[j]=(i*t[j-1])%d;
        co[i].w=((a*t[5])%d+(b*t[2])%d+c%d)%d;
        for (t[1]=i%h,j=2;j<=5;j++) t[j]=(i*t[j-1])%h;
        co[i].u=((e*t[5])%h+(f*t[3])%h+g%h)%h;
    }
}
int main()
{
    scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d,&e,&f,&g,&h,&m);
    make_data();
    sort(co,co+3*n);
    ans=0;
    for (i=0;i<n;i++) ans=(ans+co[i].w)%m;
    printf("%lld\n",ans);
    return 0;
}