20220727 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

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

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

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

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

转移方程：

$f_{i, s} = \min\left\{f_{i - 1, s \oplus t} + w(t) + fee_i[t \neq \varnothing] \right\}$

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

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

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

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

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

总复杂度就是 $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）

考虑维护 $\sum\limits_{i = 1}^na_i^t \ \ t \in [0, k]$ ，简单来说就是把 $0 \sim k$ 次方和全都维护出来。

再来看两种操作：

插入 $x$ ：直接枚举 $t \in [0, k]$ ， $sum_t += x^t$ 即可。
整体加 $1$ ：考虑二项式定理。

$\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(k^2)$ 维护所有的 $sum_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）

首先对 $a$ 从小到大排序，对于每个 $a$ 依次考虑对应的 $K$ 的区间。

$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$

如果不考虑可以加到一起的话，答案就是这些个区间求交。

可以加怎么办呢？把 $a_1, a_2$ 加起来看看？

$a_1 + a_2 \rightarrow K \in [\lceil\frac{a_1 + a_2}{2}\rceil, a_1 + a_2]$

由于 $a_1 \leq a_2$ ，不难发现， $\lceil\frac{a_1 + a_2}{2}\rceil \leq a_2$ 。

这样一来， $a_1 + a_2$ 对应的 $K$ 的区间就和 $a_2$ 对应的区间合并到一起了。

所以我们可以直接把 $a_2$ 对应的区间改写成这样：

$a_2 \rightarrow K \in [\lceil\frac{a_2}{2}\rceil, a_1 + a_2]$

推出：

$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）

考场上推了很久也没什么思路，一直以为要推 $\text{SG}$ 函数什么的……

事实上就一个背包就完了。

先考虑必胜条件，对于位置 $i$ ，如果有 $2^i$ 个僵尸则可以保证必胜。

此时位置 $i$ 上有 $c_i$ 只僵尸，占比就是 $\frac {c_i}{2^i}$ ，然后我们要把这些数的和分成两个数，使得两个数都大于等于 $\frac 12$ ，求方案数。

利用容斥的思想，求至少有 1 个小于 $\frac 12$ 的方案数。

为了方便实现，我们把权重全都乘上 $2^{31}$ ，然后让两个数都大于等于 $2^{30}$ 。

设 $f_{i, j}$ 表示和为 $2^i$ ，且第 $i$ 个位置上有 $j$ 个僵尸时的方案数。

转移过程中枚举从下一个位置走过来的僵尸数量背包即可。

最后的答案就是 $2^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;
}

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

# B. 数据结构（set）

# C. 商店购物（sum）

# D. 植物大战僵尸（pvz）

二维数点问题

20220729