1928(924div2)

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\) 以此类推。这样，每隔 \(2k - 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(2k-2)\times t+2k-x=n\)

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

所以只需要判断哪些数是 \((n-x)\cup(n+x-2)\) 的偶数 (由于(2k-2)一定是偶数) 因子，即代表 \((2k-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}\) 的整数部分，意味着每个队伍都至少有 \(\lfloor{\frac{i}{k}}\rfloor\) 个人

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

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

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

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

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

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

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

则该种族的战斗力：\(\textcolor{green}{\frac{\lfloor{\frac{i}{k}}\rfloor\times(k-1)\times \lfloor{\frac{i}{k}}\rfloor\times k}{2}+\frac{i\%k\times(i\%k-1)}{2}+(k-1)\times \lfloor{\frac{i}{k}}\rfloor\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\times10^5\in n\), \(\to O(mn)=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]\) 时对答案的贡献，对于 \(\left[ c_{i},\sum c \right]\) 区间贡献是确定的，可以使用静态区间加实现。

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

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 \le n\) 的 \(a_{i}\) 值要么是 \(a_{i-1} + y\) 要么是 \(a_{i-1} \bmod y\)

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

Solution

DP

先写了一下暴力搜索（肯定是超时的）\(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, \ldots, x+k\cdot y\) 的前缀，然后会有一些形如 \(x \bmod y, x \bmod y+y, \ldots, x \bmod y+k\cdot y\) 的块。

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

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

现在，我们可以遍历形如 \(b_1, b_1+1,\ldots,b_1+k_1\) 的第一个块的长度。然后我们就知道剩余块的和，并利用预先计算的 \(dp\)，我们可以确定是否能够形成所需的序列。

(待更 \(\dots\))