首页 模拟赛

状压 dp + 枚举子集，二项式定理，贪心，思维 + 背包

# A. 机房的新生活委员（cen）

由于把这道题看成 T4，只来得及写 40pts\text{40pts} 的暴力 /kk

非常板子的状压 dp\text{dp}，先考虑暴力，设 fi,sf_{i, s} 表示前 ii 家商店，买了状态为 ss 的物品最小花费。每家商店都是可买可不买。

转移方程：

fi,s=min⁡{fi−1,s⊕t+w(t)+feei[t≠∅]}f_{i, s} = \min\left\{f_{i - 1, s \oplus t} + w(t) + fee_i[t \neq \varnothing] \right\}

枚举在第 ii 个商店买了什么，转移就行了。

但是直接枚举两个集合的话复杂度是 O(22m)O(2^{2m}) 的，我们先枚举 ss 再枚举 ss 的子集，就变成 O(3m)O(3^m) 了。

现在外面还有个 O(n)O(n) 的枚举，里面 w(t)w(t) 暴力计算的话还要再多一个 O(m)O(m)。

事实上我们可以预处理 valsval_s 表示状态 ss 的物品在 nn 个商店中的最小花费。注意要加上 feeifee_i，因为是在 dp\text{dp}，所以多加了也无所谓。

预处理的复杂度是 O(nm2m)O(nm2^m)，可以接受。

总复杂度就是 O(nm2m+3m)O(nm2^m + 3^m).

#include <bits/stdc++.h>
#define pb push_back
#define pc putchar
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 110;
const int M = (1 << 16) + 10;
const int inf = 1e9;
int n, m;
int w[N], c[N][20];
int f[M], g[N][M], val[M], id[M];
signed main(){
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    n = read(), m = read();
    for(int i = 1; i <= n; ++i){
        w[i] = read();
        for(int j = 1; j <= m; ++j) c[i][j] = read();
    }
    int sta = (1 << m) - 1;
    for(int i = 1; i <= n; ++i)
        for(int s = 0; s <= sta; ++s){
            g[i][s] = w[i];
            for(int j = 1; j <= m; ++j)
                if(s & (1 << (j - 1))) g[i][s] += c[i][j];
        }
    for(int s = 0; s <= sta; ++s) g[0][s] = inf;
    for(int s = 1; s <= sta; ++s){
        int p = 0;
        for(int i = 1; i <= n; ++i)
            if(g[i][s] < g[p][s]) p = i;
        val[s] = g[p][s], id[s] = p;
    }
    memset(f, 0x3f, sizeof(f));
    for(int i = 0; i <= sta; ++i) f[i] = val[i];
    for(int s = 1; s <= sta; ++s)
        for(int t = s; t; t = (t - 1) & s)
            f[s] = min(f[s], f[s ^ t] + val[t]);
    write(f[sta]), puts("");
    return 0;
}
# B. 数据结构（set）
考虑维护 ∑i=1naitt∈[0,k]\sum\limits_{i = 1}^na_i^t \ \ t \in [0, k]，简单来说就是把 0∼k0 \sim k 次方和全都维护出来。
再来看两种操作：
  • 插入 xx：直接枚举 t∈[0,k]t \in [0, k]，sumt+=xtsum_t += x^t 即可。
  • 整体加 11：考虑二项式定理。
    ∑i=1naik⇒∑i=1n(ai+1)k=∑i=1n(∑j=0kaij(kj))=∑i=1n(sumj(kj))\begin{aligned} \sum_{i = 1}^na_i^k \Rightarrow \sum_{i = 1}^n(a_i + 1)^k =& \sum_{i = 1}^n(\sum_{j = 0}^ka_i^j\dbinom kj) \\ =& \sum_{i = 1}^n(sum_j\dbinom kj) \end{aligned}
    O(k2)O(k^2) 维护所有的 sumtsum_t 即可。
#include <bits/stdc++.h>
#define pb push_back
#define pc putchar
#define int long long
using namespace std;
namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int n, k, a;
inline int add(int x) {return x >= mod ? x - mod : x;}
inline int sub(int x) {return x < 0 ? x + mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}
inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = mul(res, a);
        a = mul(a, a), b >>= 1;
    }
    return res;
}
inline int inv(int x) {return qpow(x, mod - 2);}
int c[60][60], sum[60];
inline void init(int n){
    for(int i = 0; i <= n; ++i) c[i][0] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= i; ++j)
            c[i][j] = add(c[i - 1][j - 1] + c[i - 1][j]);
}
inline void solve_0(int x){
    for(int i = 0; i <= k; ++i) sum[i] = add(sum[i] + qpow(x, i));
}
int tmp[60];
inline void solve_1(){
    for(int i = 0; i <= k; ++i){
        tmp[i] = 0;
        for(int j = 0; j <= i; ++j)
            tmp[i] = add(tmp[i] + mul(c[i][j], sum[j]));
    }
    for(int i = 0; i <= k; ++i) sum[i] = tmp[i];
}
signed main(){
    // double st = clock();
    n = read(), k = read(), init(50);
    for(int i = 1; i <= n; ++i){
        int op = read(), x;
        if(!op) solve_0(read());
        else solve_1();
        write(sum[k]), puts("");
    }
    // double ed = clock();
    // cerr << ed - st << endl;
    return 0;
}
# C. 商店购物（sum）
首先对 aa 从小到大排序，对于每个 aa 依次考虑对应的 KK 的区间。
a1→K∈[⌈a12⌉,a1]a2→K∈[⌈a22⌉,a2]⋮a_1 \rightarrow K \in [\lceil\frac{a_1}{2}\rceil, a_1] \\ a_2 \rightarrow K \in [\lceil\frac{a_2}{2}\rceil, a_2] \\ \vdots
如果不考虑可以加到一起的话，答案就是这些个区间求交。
可以加怎么办呢？把 a1,a2a_1, a_2 加起来看看？
a1+a2→K∈[⌈a1+a22⌉,a1+a2]a_1 + a_2 \rightarrow K \in [\lceil\frac{a_1 + a_2}{2}\rceil, a_1 + a_2]
由于 a1≤a2a_1 \leq a_2，不难发现，⌈a1+a22⌉≤a2\lceil\frac{a_1 + a_2}{2}\rceil \leq a_2。
这样一来，a1+a2a_1 + a_2 对应的 KK 的区间就和 a2a_2 对应的区间合并到一起了。
所以我们可以直接把 a2a_2 对应的区间改写成这样：
a2→K∈[⌈a22⌉,a1+a2]a_2 \rightarrow K \in [\lceil\frac{a_2}{2}\rceil, a_1 + a_2]
推出：
ai→K∈[⌈ai2⌉,sumi]a_i \rightarrow K \in [\lceil\frac{a_i}{2}\rceil, sum_i]
不难证明，这样的区间并是不会漏的，所以排序做个前缀和再求区间并就完了。
#include <bits/stdc++.h>
#define pb push_back
#define pc putchar
#define int long long
using namespace std;
namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 1e5 + 10;
int n, ans;
int a[N], sum[N];
signed main(){
    // freopen("sum.in", "r", stdin);
    // freopen("sum.out", "w", stdout);
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i];
    ans = a[1] - (a[1] + 1) / 2 + 1;
    int mx = a[1];
    for(int i = 2; i <= n; ++i){
        if(mx >= (a[i] + 1) / 2) ans += sum[i] - mx;
        else ans += sum[i] - (a[i] + 1) / 2 + 1;
        mx = sum[i];
    }
    write(ans), puts("");
    return 0;
}
# D. 植物大战僵尸（pvz）
考场上推了很久也没什么思路，一直以为要推 SG\text{SG} 函数什么的……
事实上就一个背包就完了。
先考虑必胜条件，对于位置 ii，如果有 2i2^i 个僵尸则可以保证必胜。
此时位置 ii 上有 cic_i 只僵尸，占比就是 ci2i\frac {c_i}{2^i}，然后我们要把这些数的和分成两个数，使得两个数都大于等于 12\frac 12，求方案数。
利用容斥的思想，求至少有 1 个小于 12\frac 12 的方案数。
为了方便实现，我们把权重全都乘上 2312^{31}，然后让两个数都大于等于 2302^{30}。
设 fi,jf_{i, j} 表示和为 2i2^i，且第 ii 个位置上有 jj 个僵尸时的方案数。
转移过程中枚举从下一个位置走过来的僵尸数量背包即可。
最后的答案就是 2n−2×f30,02^n - 2 \times f_{30, 0}。
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }
    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 2010;
const int mod = 1e9 + 7;
int T, n;
ll sum;
int a[N], buk[40], f[40][N], c[N][N];
//f [i][j]: 僵尸个数 <= 2^i 且第 i 个位置上有 j 个僵尸的方案数
inline int add(int x) {return x >= mod ? x - mod : x;}
inline int sub(int x) {return x < 0 ? x + mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}
inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = mul(res, a);
        a = mul(a, a), b >>= 1;
    }
    return res;
}
inline void init(int n){
    for(int i = 0; i <= n; ++i) c[i][0] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= i; ++j) c[i][j] = add(c[i - 1][j - 1] + c[i - 1][j]);
}
inline void solve(){
    memset(buk, 0, sizeof(buk));
    memset(f, 0, sizeof(f));
    n = read(), sum = 0;
    for(int i = 1; i <= n; ++i) a[i] = read(), buk[31 - a[i]]++;
    for(int i = 1; i <= 30; ++i) sum += (1ll << i) * buk[i];
    if(sum < (1ll << 31)) return puts("0"), void();
    f[0][0] = 1; // 容斥，计算分成两半至少有一边僵尸 <= 2^30 的方案数
    for(int i = 1; i <= 30; ++i)
        for(int j = 0; j <= buk[i]; ++j)
            for(int k = 0; k <= 2000; ++k){
                int x = j + k / 2;
                f[i][x] = add(f[i][x] + mul(f[i - 1][k], c[buk[i]][j]));
            }
    write(sub(qpow(2, n) - mul(2, f[30][0]))), puts("");
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    T = read(), init(2000);
    while(T--) solve();
    return 0;
}
 更新于   阅读次数  次