1928(924div2)

Dec 16, 2024 11:44 AM

Jan 13, 2025 12:47 PM

A. Rectangle Cutting

给出 $a, b (1 \leq a, b \leq 10^{9})$ ,看是否能按照要求获得另外一个矩形

void solve() {
    int a, b;cin >> a >> b;
    int x = a, y = b;
    if (a > b)swap(a, b);//不能去掉
    if (a % 2 == 0) {
        a /= 2;
        b *= 2;
    } else if (b % 2 == 0) {
        b /= 2;
        a *= 2;
    }
    if (x == a || x == b) {
        cout << "no\n";
    }else{
        cout << "yes\n";
    }
}

if (a > b)swap(a, b); 不能去掉，HACK：12 6 不去掉就会输出no

void solve() {
    int a, b;cin >> a >> b;
    if (a % 2 == 0 && b % 2 == 0) {
        cout << "yes\n";
    } else if (a == 2 * b || 2 * a == b) {
        cout << "no\n";
    } else if (a % 2 == 0 || b % 2 == 0) {
        cout << "yes\n";
    } else {
        cout << "no\n";
    }
}

B. Equalize

给出一个长度为 $n$ 的数组，要求在这个数组基础上加上一个 $1 - n$ 的排列，问在加上排列后的数组中相同元素的最大值。

易得相同的元素加上排列之后必然不相同，所以可以去重。

void solve() {
    int n;cin >> n;
    vector<int> a;
    set<int> s;
    for (int i = 0;i < n;i++) {
        int x;cin >> x;
        s.insert(x);
    }
    for (auto x : s)
        a.push_back(x);
    int ans = 0, j = 0;
    for (int i = 0;i < s.size();i++) {
        while (j < s.size() && a[j] - a[i] < n)j++;//j>=i
        ans = max(ans, j - i);
    }
    cout << ans << '\n';
}

C. Physical Education Lesson

每个人都排成一排，并被要求站在 "第 $k$ 个 "的位置上。

$1 \sim k, k - 1 \sim 2, 1 \sim k, k - 1 \sim 2, \dots$ 以此类推。这样，每隔 $2 k - 2$ 个位置就重复一次。( $k \neq 1$ )

给出在队伍中的位置 $n$ 结算时得到的数字 $x$ ,输出有多少个符合条件的 $k$ 。

eg
$n = 10, x = 2$ ， $\to k$ = $2, 3, 5, 6$ 。

解决这些问题的例子是 $k$ ：

$k$ / №	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$2$	$1$	$2$	$1$	$2$	$1$	$2$	$1$	$2$	$1$	$2$
$3$	$1$	$2$	$3$	$2$	$1$	$2$	$3$	$2$	$1$	$2$
$5$	$1$	$2$	$3$	$4$	$5$	$4$	$3$	$2$	$1$	$2$
$6$	$1$	$2$	$3$	$4$	$5$	$6$	$5$	$4$	$3$	$2$

Solution

当在左边部分的时候：只需要满足 $n % (2 k - 2) = x$ 即可(当为 0 时需要特判为 2)
反之满足 $2 k - n % (2 k - 2) = x$ 即可

暴力做法：(TLE)由于是 $O (n)$ ( $n \leq 10^{9}$ )的做法肯定会 T

void solve() {
    int n, x;cin >> n >> x;
    int ans = 0;
    for (int k = 2;k <= n;k++) {
        int m = n % (2 * k - 2);
        if (!m) m = 2;
        if (m <= k) {
            if (m == x) ans++;
        } else {
            m = 2 * k - m;
            if (m == x) ans++;
        }
    }
    cout << ans << '\n';
}

由上文： $k$ 满足 $(2 k - 2) \times t + x = n \cup (2 k - 2) \times t + 2 k - x = n$

可以变形为： $(2 k - 2) | (n - x) \cup (2 k - 2) | (n + x - 2 k) \to (2 k - 2) | (n + x - 2)$

所以只需要判断哪些数是 $(n - x) \cup (n + x - 2)$ 的偶数 (由于(2k-2)一定是偶数) 因子，即代表 $(2 k - 2)$ ，所以存入的时候存 $k$ 即 $\frac{i}{2} + 1$ 。

$k$ 与 $x$ 还满足 $k \geq x$

NOTE: 试除法：要找到某个数的所有因子只需要 $\sqrt{n}$ 在 $i$ 是因子的情况下加入 $i,$ $\frac{n}{i}$ 即：

(不过当 $n$ 为平方数的时候会有重叠，将 vector 换为 set 去重即可)

auto find = [&](int n) {
	vector<int> ans;
	for (int i = 1;i * i <= n;i++) {
		if (n % i == 0) {
			ans.push_back(i);
			ans.push_back(n / i);
		}
	}
	return ans;
};

unordered_set 可换为 set。但是 unordered_set 的插入是 $O (1)$ 的

void solve() {
    int n, x;cin >> n >> x;
    unordered_set<int> can;
    auto find = [&](int a) {
        unordered_set<int> ans;
        for (int i = 1;i * i <= a;i++) {
            if (a % i == 0) {
                if (i % 2 == 0)can.insert(1 + i / 2);
                if ((a / i) % 2 == 0)can.insert(1 + (a / i) / 2);
            }
        }
        return ans;
    };
    for (auto i : find(n - x))can.insert(i);
    for (auto i : find(n + x - 2))can.insert(i);
    int ans = 0;
    for (auto i : can) {
        if (i >= x)ans++;
    }
    cout << ans << '\n';
}

D. Lonely Mountain Dungeons

中土世界居民的军队将由几个小队组成。众所周知，每一对同种族的生物分属不同的小队，军队的总兵力就会增加 $b$ 个单位。但由于提摩西很难领导一支由大量小队组成的军队，因此由 $k$ 个小队组成的军队的总兵力会减少 $(k - 1) \cdot x$ 个单位。注意，军队总是由个至少一个班组成。

有 $n$ 个种族，而 $i$ 个种族的生物数量等于 $c_{i}$ 。确定他们所能组建的军队的最大兵力。

Solution

三分（先单增，再单减）组合数

注意：long long 的计算稍不注意就会wa

三分法 (待更 $\dots$ )

codeforces round 924 (Div2) A-E 思路分享_哔哩哔哩_bilibili

对于计算分成 $k$ 个队伍时的战斗力(每个种族其实是独立的，所以可以分开计算)：

先算出 $\frac{i}{k}$ 的整数部分，意味着每个队伍都至少有 $⌊ \frac{i}{k} ⌋$ 个人

当每个队伍都是 $⌊ \frac{i}{k} ⌋$ 个人，这时的贡献： $\frac{⌊ \frac{i}{k} ⌋ \times (k - 1) \times ⌊ \frac{i}{k} ⌋ \times k}{2}$

对于一个人来说，其他队伍的人都有助于贡献： $⌊ \frac{i}{k} ⌋ \times (k - 1)$

对于和他同一个队伍的人来说： $⌊ \frac{i}{k} ⌋ \times (k - 1) \times ⌊ \frac{i}{k} ⌋$

其他队伍的也是一样，所以这时的贡献： $\frac{⌊ \frac{i}{k} ⌋ \times (k - 1) \times ⌊ \frac{i}{k} ⌋ \times k}{2}$

余数部分，只有部分队伍仅有 1 人，贡献： $\frac{i % k \times (i % k - 1)}{2}$

余数和整数部分的接壤：则贡献： $(k - 1) \times ⌊ \frac{i}{k} ⌋ \times i % k$

对于后加入的余数部分，之前整数部分和他不在同一个队伍的 $(k - 1) \times ⌊ \frac{i}{k} ⌋$ 个人需要算上贡献

则该种族的战斗力： $\frac{⌊ \frac{i}{k} ⌋ \times (k - 1) \times ⌊ \frac{i}{k} ⌋ \times k}{2} + \frac{i % k \times (i % k - 1)}{2} + (k - 1) \times ⌊ \frac{i}{k} ⌋ \times i % k - (k - 1) \times x$

void solve() {
    int n, b, x;cin >> n >> b >> x;
    vector<int> c(n);for (int i = 0;i < n;i++)cin >> c[i];
    auto check = [&](ll k) {//计算分成k个队伍时的战斗力
        ll ans = 0;
        for (auto i : c) {
            ll t = i / k, tt = i % k, res = 0;
            res += t * t * k * (k - 1) / 2;
            if (tt > 0) {//可忽略这个条件
                res += tt * (tt - 1) / 2;
                res += tt * t * (k - 1);
            }
            ans += res * b;
        }
        ans -= (k - 1) * x;
        return ans;
    };
    ll l = 1, r = *(max_element(c.begin(), c.end()));
    while (r - l + 1 > 3) {//这段代码的主要目的是将l,r区间缩小到足够小了方便之后枚举
        ll lmid = l + (r - l + 1) / 3;
        ll rmid = r - (r - l + 1) / 3;
        if (check(lmid) > check(rmid))r = rmid;//目的为了缩减区间长度
        else l = lmid;
    }
    ll ans = 0;
    for (ll i = l;i <= r;i++)ans = max(ans, check(i));
    cout << ans << '\n';
}

D_哔哩哔哩_bilibili
(我认为最简单的思路）：在 $c [i]$ 中会有一些重复的数字，如果依次枚举的话重复的数字就重复计算了，所以可以算出之后乘以个数即可。

复杂度：最坏情况 (有 $m$ 个种族人数不同）： $1, 2, 3, \dots, m$ 互不相同 $\sum c = \frac{m (m + 1)}{2} \in m^{2} \leq 2 \times 10^{5} \in n$ , $\to O (m n) = O (n \sqrt{n})$

注：

num 数组只能开在外面，开在里面会 T ,要将 num 数组放里面，需要将 num 的大小改为 $max (c_{i})$

vector<int> num(2e5 + 1);
void solve() {
    int n, b, x;cin >> n >> b >> x;
    unordered_set<int> c;
    for (int i = 0;i < n;i++) {
        int x;cin >> x;
        c.insert(x);
        num[x]++;
    }
    auto check = [&](ll k) {
        ll ans = 0;
        for (auto i : c) {
            ll t = i / k, tt = i % k, res = 0;
            res += t * t * k * (k - 1) / 2;
            res += tt * (tt - 1) / 2;
            res += tt * t * (k - 1);
            ans += res * b * num[i];
        }
        ans -= (k - 1) * x;
        return ans;
    };
    ll l = 1, r = *(max_element(c.begin(), c.end())), ans = 0;
    for (ll i = l;i <= r;i++)
        ans = max(ans, check(i));
    cout << ans << '\n';
    for (auto p : c)num[p] = 0;
}

Codeforces Round 924 (Div. 2) A - E - 知乎

可以看出，最佳方案肯定是将每个种族均匀分配到每个队伍中。

假设某个种族有 $c_{i}$ 个，我们可以暴力枚举队伍数为 $[1, c_{i} - 1]$ 时对答案的贡献，对于 $[c_{i}, \sum c]$ 区间贡献是确定的，可以使用静态区间加实现。

由于 $\sum c$ 有限制，所以这种方法可以在 $O (\sum c)$ 的时间内完成。

void solve() {
    int n, b, x, m = 0;cin >> n >> b >> x;
    vector<int>c(n);for (int i = 0;i < n;i++)cin >> c[i], m += c[i];
    vector<ll>d(m + 1);
    auto add = [&](int l, int r, ll x) {
        d[l] += x;
        if (r + 1 <= m)d[r + 1] -= x;
    };
    for (auto x : c) {
        for (int i = 1;i < x;i++) {
            ll sum = 1ll * x * (x - 1);
            int t = x / i, r = x % i;
            sum -= (i - r) * 1ll * t * (t - 1);
            sum -= r * 1ll * (t + 1) * t;
            add(i, i, sum / 2);
        }
        add(x, m, 1ll * x * (x - 1) / 2);
    }
    ll ans = 0;
    for (int i = 1;i <= m;i++) {
        d[i] += d[i - 1];
        ans = max(ans, d[i] * b - 1ll * (i - 1) * x);
    }
    cout << ans << '\n';
}

D_哔哩哔哩_bilibili
平均分配最优，先排序，枚举队伍数量，种族数量小的下次不算了，数量大的在算一遍，直到不会被更新

#define int long long
void solve() {
    int n, b, x;cin >> n >> b >> x;
    vector<int> a(n);for (auto& i : a)cin >> i;sort(a.begin(), a.end());
    int maxx = 1e9, divi = 0, hascal = 0;
    int ans = 0;
    for (int i = 2;divi <= n - 1 && i <= maxx;i++) {
        int res = 0;
        for (int j = divi;j <= n - 1;j++) {
            if (a[j] <= i) {
                hascal += b * (a[j] * (a[j] - 1)) / 2;
                divi++;
            } else {
                int cnt = a[j] / i, mod = a[j] % i;
                int a1 = i - mod, a2 = mod;
                res += b * a[j] * (a[j] - 1) / 2;
                res -= b * a1 * cnt * (cnt - 1) / 2;
                res -= b * a2 * (cnt + 1) * cnt / 2;
            }
        }
        res += hascal;
        res -= (i - 1) * x;
        ans = max(ans, res);
    }
    cout << ans << '\n';
}

E. Modular Sequence

给你两个整数 $x$ 和 $y$ 。长度为 $n$ 的序列 $a$ 如果是 $a_{1} = x$ ，且对于所有 $1 < i \leq n$ 的 $a_{i}$ 值要么是 $a_{i - 1} + y$ 要么是 $a_{i - 1} mod y$

判断是否存在长度为 $n$ 的模数序列，其元素之和等于 $S$ ，如果存在，请找出任何这样的序列。

Solution

暴力搜索 $O (2^{n})$

void solve() {
    int n, x, y, s;cin >> n >> x >> y >> s;vector<int> a(n, 0);a[0] = x;
    ll sum = x;
    auto dfs = [&](auto self, int i, ll currSum) -> bool {
        if (currSum > s) return false; // 前缀和剪枝
        if (i == n) return currSum == s;
        a[i] = (a[i - 1] + y) % y;
        if (self(self, i + 1, currSum + a[i])) return true;
        a[i] = a[i - 1] + y;
        if (self(self, i + 1, currSum + a[i])) return true;
        return false;
    };
    if (dfs(dfs, 1, sum)) {
        cout << "yes\n";for (int i = 0;i < n;i++)cout << a[i] << " \n"[i == n - 1];
    } else {
        cout << "no\n";
    }
}

官方题解：

我们先来看答案的形式：首先会有形如 $x, x + y, \dots, x + k \cdot y$ 的前缀，然后会有一些形如 $x mod y, x mod y + y, \dots, x mod y + k \cdot y$ 的块。

我们可以从序列的所有元素中减去 $x mod y$ ，然后将所有元素除以 $y$ （所有元素最初的余数都为 $x mod y$ ，因此它们都是可被 $y$ 整除的）。设 $b_{1} = \frac{x - x mod y}{y}$ 。那么我们的序列将以 $b_{1}, b_{1} + 1, \dots, b_{1} + k_{1}$ 开头，然后会有形如 $0, 1, \dots, k_{i}$ 的块。

现在让我们计算这些值： $d p_{i}$ 表示形如 $0, 1, \dots, k_{j}$ 且和为 $i$ 的块序列的最小长度。我们可以利用动态规划计算从 $0$ 到 $s$ 的所有数的这个值。如果我们已经处理了从 $0$ 到 $k - 1$ 的所有值，那么对于 $k$ ，我们已经计算出了最小长度，并且我们可以更新 $k + 1, k + 1 + 2, \dots$ 的 $d p$ 值，总共不超过 $s$ 的值有 $O (\sqrt{s})$ 个。在同一个 $d p$ 中，我们可以记录经过哪些值进行了重新计算，以便恢复答案。

现在，我们可以遍历形如 $b_{1}, b_{1} + 1, \dots, b_{1} + k_{1}$ 的第一个块的长度。然后我们就知道剩余块的和，并利用预先计算的 $d p$ ，我们可以确定是否能够形成所需的序列。

codeforces round 924 (Div2) A-E 思路分享_哔哩哔哩_bilibili

序列形式如下图(当全部都减去 $x % y$ ,并除以 $y$ )

第一部分 $x, x + y, \dots x + k_{1} y \to$ $\frac{x - x % y}{y}, \frac{x - x % y}{y} + 1, \frac{x - x % y}{y} + 2, \dots, \frac{x - x % y}{y} + k_{1}$

其余部分 $x % y, x % y + y, \dots x % y + k_{i} y \to$ $0, 1, 2, \dots k_{i}$

dp[x]={达到这个面积最少的长度，从哪里转移过来，最后高度}

要满足条件必须满足：dp[s][0]<=n

(待更 $\dots$ )

![](/img/user/ZZZ-Misc/Z-Attachment/images-old-ACM/Pasted image 20240215152354.png)

void solve() {
    ll n, x, y, s;cin >> n >> x >> y >> s;
    if (x + (n - 1) * (x % y) > s) {
        cout << "NO\n";return;
    }
    s -= (x % y) * n;
    vector<array<int, 3>>dp(s + 1, {INT_MAX,0,0});
    for (int ns = x - x % y, h = x - x % y, i = 1;ns <= s;i++, h += y, ns += h) {
        dp[ns] = {i,0,h};
    }
    for (int i = 0;i <= s;i++) {
        if (dp[i][0] != INT_MAX) {
            for (int j = 1, t = 0/*t代表一部分的柱子的长度*/;t + i <= s;t += j * y, j++) {
                dp[t + i] = min(dp[t + i], {dp[i][0] + j, i, (j - 1)* y});
            }
        }
    }
    if (dp[s][0] > n) {
        cout << "NO\n";return;
    }
    vector<int> ans(n);
    int v = s;
    while (v) {
        auto [i, ns, h] = dp[v];
        while (v != ns) {
            i--;
            ans[i] = h;
            v -= h, h -= y;
        }
    }
    cout << "YES\n";
    for (auto i : ans)cout << i + (x % y) << " ";cout << "\n";
}