题解 P2780 【[AHOI2016初中组]游戏】

浮尘ii · 2017-01-01 12:18:07 · 题解

官方题解

为了找出t和m的最大差，我们需要先找出所有可能的m，也就是要算出来有哪些数字可以通过在n个数字中挑选k个来得到。这一个简化版的01背包问题，记F[i][j][x]表示前i个数字中选出j个来，是否可以组成数字x。这样做时间复杂度是O(nkMAXB)的，可以通过85%的数据。

又可以发现F[i][j][x]全都是boolean型的，考虑把多个F[i][j][x]在最后一维进行压缩，例如我们可以用一个64位整数来表示64个boolean值。01背包的所有转移都可以用位运算来实现。这便可以通过100%的数据。

std

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <cmath>
using namespace std ;

const int R = 60 ;
const int MAXN = 609 ;
const int MAXB = 180009 ;
const int __MAXK = 13 ;

int n , k , a , b , x[MAXN] , k0 , sumx[MAXN] ;
long long F[MAXB][__MAXK] ;

void Init() {
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
    cin >> n >> k >> a >> b ;
    for ( int i = 1 ; i <= n ; i ++ ) cin >> x[i] ;
    sumx[0] = 0 ;
    for ( int i = 1 ; i <= n ; i ++ ) sumx[i] = sumx[i-1] + x[i] ;
}

void Solve() {
    k0 = (k+1) / R ;
    if ( R * k0 < k+1 ) k0 ++ ;
    for ( int j = 0 ; j <= b ; j ++ )
        for ( int k = 0 ; k < k0 ; k ++ )
            F[j][k] = 0 ;
    F[0][0] = 1 ;
    for ( int i = 1 ; i <= n ; i ++ )
        for ( int j = sumx[i] ; j >= 0 ; j -- )
            for ( int k = 0 ; k < k0 ; k ++ ) {
                if ( k + 1 < k0 ) F[j+x[i]][k+1] |= (F[j][k] >> (R-1)) ;
                F[j+x[i]][k] |= (F[j][k] << 1) ;
            }
    vector<int> ans ; ans.clear() ;
    for ( int j = 0 ; j <= b ; j ++ )
        if ( ((F[j][k0-1] >> (k+1 - R*(k0-1) - 1)) & 1) == 1 )
            ans.push_back(j) ;
    int ret = 0 ;
    int near2a = abs(ans[0] - a) , near2b = abs(ans[0] - b) ;
    for ( int i = 1 ; i < ans.size() ; i ++ ) {
        if ( abs(ans[i] - a) < near2a ) near2a = abs(ans[i] - a) ;
        if ( abs(ans[i] - b) < near2b ) near2b = abs(ans[i] - b) ;
        int rr = (ans[i] - ans[i-1]) / 2 ;
        if ( ( a <= ans[i-1] + rr && ans[i-1] + rr <= b ) || ( a <= ans[i] - rr && ans[i] - rr <= b ) ) {
            if ( rr > ret ) ret = rr ;
        }
    }
    if ( near2a > ret ) ret = near2a ;
    if ( near2b > ret ) ret = near2b ;
    cout << ret << "\n" ;
    fprintf(stderr,"%d\n" , ret) ;
}

int main() {
    Init() ;
    Solve() ;
}

C++福利

如果有个75000位的二进制数类型多好啊。

诶，STL好像有个bitset。

嗯，好像可以直接用……

稍微跑得比std慢的AC程序

#include <iostream>
#include <cstdio>
#include <bitset>

using namespace std;

const size_t    MaxN(251), MaxSum(75001);
const int        INF(0x7f7f7f7f);

int                    N, K, A, B;
int                    Xi, Sum;
bitset<MaxSum>        F[MaxN];
int                    L[MaxSum], R[MaxSum];
int                    Ans(-INF);

int main()
{
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);

    cin >> N >> K >> A >> B;
    F[0].set(0);
    for(int i(1); i <= N; i++) {
        scanf("%d", &Xi);
        for(int j(K); j; j--)
            F[j] |= F[j - 1] << Xi;
        Sum += Xi;
    }

    L[A] = -INF;
    for(int i(A); ~i; i--)
        if(F[K][i]) {
            L[A] = i;
            break;
        }
    for(int i(A + 1); i <= B; i++)
        L[i] = F[K][i] ? i : L[i - 1];
    R[B] = INF;
    for(int i(B); i <= Sum; i++)
        if(F[K][i]) {
            R[B] = i;
            break;
        }
    for(int i(B - 1); i >= A; i--)
        R[i] = F[K][i] ? i : R[i + 1];

    for(int i(A); i <= B; i++)
        Ans = max(Ans, min(i - L[i], R[i] - i));

    cout << Ans << endl;

    return 0;
}