G. ICPC Camp

题意

给定一个整数 $n$，和两个长度分别为 $p,q$ 的数组，$a_1,a_2,…,a_p$ 和 $b_1,b_2,…,b_q$，以及一个整数 $s$。

我们现在要配对出 $n$ 个互不相同（每个 $a_j, b_k$ 只能出现在一个pair中）的pair $(a_j,b_k)$ 使得 $a_j+b_k \leq s$。

定义第 $i$ 个pair的差值为 $d_i = |a_j-b_k|$，那么我们要让 $D = \max d_i$ 的值最小。

其中，$n,p,q \leq 2 \times 10^5, 0 \leq s,a_i,b_i \leq 10^9$。

题解

一眼二分。先 sort一下 $a,b$。

二分之后呢？

假设当前二分的最大差值为 $x$。

那么对于每一个 $a_i$ 我们都可以找到所有满足条件的 $b_j$ 使得 $|a_i-b_j| \leq x$ 且 $a_i+b_j \leq s$。

这样满足条件的 $b_j$ 一定是sort后的一个连续区间。

那么问题转化为，我们有 $p$ 个这样的区间，如何在每个区间上取一个点，使得这些点互不相同，并使得取的点数尽可能多？

比如 $a_1$ 对应的是 $[b_1,b_1]$，$a_2$ 对应 $[b_1,b_2]$, $a_3$ 对应 $[b_2,b_4]$，则我们获得三个区间 $[1,1],[1,2],[2,4]$。

可以在 $[1,1]$ 内选 1 这个点，$[1,2]$ 内选 2 这个点，$[2,4]$ 内选 3 这个点，所以可以选3个点，答案为3。

我们利用贪心尽可能多选点。

我们先将所有区间按照右端点sort一下，然后每个区间 $[L,R]$ 看从 $L$ 开始，第一个没用过的点是哪个，如果它 $\leq R$，就选它。

怎么快速寻找这个没用过的点？

注意到区间上的点数最多为 $q\leq 2 \times 10^5$ 个，我们先将所有的点 (从 $1$ 到 $q$）加入一个 set，然后在set上 lower_bound() 即可。

最后，如果可选的点数 $\geq n$ 就说明 $x$ 是可行的。

代码 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;

int n, p, q, s;
int a[maxn], b[maxn];

bool solve(int x) {
    vector<pii> vec;
    for (int i = 1; i <= p; i++) {
        int L = lower_bound(b+1, b+q+1, a[i]-x) - b;
        int R = upper_bound(b+1, b+q+1, min(a[i]+x, s-a[i])) - b-1;
        if (L <= R) vec.push_back({L,R});
    }

    int m = vec.size(), ans = 0;
    sort(vec.begin(), vec.end(), [](auto a, auto b) {
        return a.second < b.second;
    });

    set<int> se;
    for (int i = 1; i <= q; i++) se.insert(i);
    for (auto [L, R] : vec) {
        if (se.lower_bound(L) != se.end()) {
            int t = *se.lower_bound(L);
            if (t <= R) {
                se.erase(t);
                ans++;
            }
        }
    }
    return ans >= n;
}

int main() {
    fastio;
    cin >> n >> p >> q >> s;
    for (int i = 1; i <= p; i++) cin >> a[i];
    for (int i = 1; i <= q; i++) cin >> b[i];
    sort(a+1, a+p+1);
    sort(b+1, b+q+1);
    int low = 0, high = 1e9, ans = 1e9+1;
    while (low <= high) {
        int mid = (low + high) >> 1;
        if (solve(mid)) {
            ans = mid, high = mid-1;
        } else low = mid+1;
    }
    cout << (ans == 1e9+1 ? -1 : ans) << "\n";
}

J. Lunchtime Name Recall

题意

给定一个集合，一开始它为 $\{n\}$，现在我们有 $m$ 天，第 $i$ 天我们拥有 $a_i$ 个汉堡。

在这一天，我们需要将 $a_i$ 个汉堡全部分出去，对于一个集合中的一个元素，假设它为 $v$，那么我们如果分了 $b (0 \leq b \leq v)$ 个汉堡给这个元素，那么它会分裂成 $b, v-b$ 这两个数。

如何分配汉堡，使得 $m$ 天后，集合中元素 $1$ 的出现次数最大？

其中，$2 \leq n \leq 30, 1 \leq m \leq 10$，$a_i \in [1,n-1]$。

整数拆分

一个正整数 $n$ 的整数拆分是将它拆成一些整数的和，即求：

$$n=r_1+r_2+…+r_k,~~ r_1 \geq r_2 \geq … \geq r_k \geq 1$$

的方案数。

我们设 $f_{i,j}$ 表示将整数 $i$ 恰好拆成 $j$ 个数的方案，则有：

$$f_{i,j} = f_{i-1,j-1} + f_{i-j,j}$$

这里表示考虑最小的数是否为 $1$，如果是，就转移到 $f_{i-1,j-1}$，否则让所有数字减 $1$，得到 $f_{i-j,j}$。

由这个可以计算出 $n=30$ 的时候有 $5604$ 种拆法。

题解

暴搜！复杂度大概可以感性理解是和分拆数有关的。具体复杂度至少为 $5604^2$。

在暴搜时需要一些优化：

  1. 每天如果我们拥有 $a_i$ 个汉堡，那么等价于我们拥有 $n-a_i$ 个汉堡，所以我们取较小的那一个。
  2. 如果集合中有多个相同的数 $N_1, N_2 … N_k$ 可以分，那么我们分给 $N_i$ 的汉堡数量一定要 $\geq N_{i+1}$ 的汉堡数量（避免重复计算），当然不同的数字之间并没有任何关联。
  3. 在每一天分的时候，我们维护两个 vector<int>，一个叫 cur，一个叫 add，分别代表当前还没有分的数，和已经分好了的数，这样可以避免在同一天分了一个数两次。
  4. 使用哈希，将当前集合的状态 map 到一个hash value，并且离散化之后由整数拆分知道状态数 $\leq 5604$。
  5. 如果分汉堡的时候会分出 $0$ 的话，就不分这个值。
  6. 记得在能加引用的地方，加上引用，否则T飞。

复杂度是 $O($玄学$)$。

代码 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 35;
const int maxm = 1e5+55;

const int P = 31;

int n, m, a[maxn], cid = 0;
int dp[12][5700];  // dp[i][S]:  还剩 i 次分的机会，当前状态为 S，最多能区分出几个人
map<ull, int> hash_to_idx;  // 哈希值 map 到 index

// map<ull, vector<int>> hash_to_vec;  // 大小为 5604

// vis = 1: 更新 hash_to_vec
inline ull vec_to_hash(vector<int>& vec, bool vis) {
    sort(vec.begin(), vec.end(), greater<int>());
    ull res = 0;
    for (int i = 0; i < vec.size(); i++) {
        res = res * P + vec[i];
    }
    if (vis && hash_to_idx.count(res) == 0)  {
        hash_to_idx[res] = ++cid;
    }
    return res;
}

// 整数拆分
// 还剩下 cur，上一个拆出来的数是 last (所以这次拆的数 <= last), 现在拆出来的是 vec (vec里面的数字不会再被拆)
// void init(int cur, int last, vector<int>& vec) {
//     if (cur == 0) return;
//     vec.push_back(cur);
//     ull res = vec_to_hash(vec, 1);
//     vec.pop_back();
//     for (int i = min(cur, last); i >= 1; i--) {
//         vec.push_back(i);
//         init(cur - i, i, vec);
//         vec.pop_back();
//     }
// }

int dfs(int i, vector<int> cur);

// i: 第 i 天
// b: 还剩下 b 个汉堡可以用
// cur: 还没有分的组
// add: 已经分好的组  (此时它应该是空的？)
// lim: 如果上一个处理的组和当前 cur.back() 的组大小一致，lim 为上一个处理的组拆分的大小，这个不能比它大；如果大小不一致，lim = n (无限制)
int helper(int i, int b, vector<int>& cur, vector<int>& add, int lim) {
    if (b < 0) return 0;
    if (cur.size() == 0) {
        if (b == 0) return dfs(i+1, add);
        return 0;  // b > 0, 状态不合法
    }
    // 还剩下没分的组，开始分
    int v = cur.back();
    cur.pop_back();

    bool has_lim = (cur.size() && cur.back() == v);  // 下一个是否有限制
    int res = 0;  // 记录最大值
    for (int j = 0; j <= min({b, lim, v}); j++) {  // 用掉 j 个汉堡
        if (j > 0)
            add.push_back(j);
        if (j != v)
            add.push_back(v-j);

        res = max(res, helper(i, b-j, cur, add, has_lim ? j : n));

        add.pop_back();
        if (j > 0 && j != v)
            add.pop_back();
        
        if (res == n) {
            cout << n << "\n";
            exit(0);
        }
    }

    cur.push_back(v);
    return res;
}

// i: 第 i 天  (这一天还没开始分)
// cur: 还没有分的组
// dfs 函数默认是这一天的开始，所以拥有 a[i] 个汉堡可以分
int ans = 0;
int dfs(int i, vector<int> cur) {
    ull S = vec_to_hash(cur, 1);
    int s = hash_to_idx[S];
    if (dp[i][s] != -1) return dp[i][s];

    if (i > m) {
        int cnt = 0;
        for (int j : cur) cnt += (j == 1);
        ans = max(ans, cnt);
        return dp[i][s] = cnt;
    }

    vector<int> add;
    return dp[i][s] = helper(i, a[i], cur, add, n);  // 记忆化
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> a[i], a[i] = min(a[i], n-a[i]);
    sort(a+1, a+m+1, greater<int>());
    vector<int> vec;

    memset(dp, -1, sizeof(dp));
    vector<int> cur;
    cur.push_back(n);
    dfs(1, cur);
    cout << ans << endl;
}