1928(924div2)

A. Rectangle Cutting

给出 a,b(1a,b109),看是否能按照要求获得另外一个矩形

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 的数组,要求在这个数组基础上加上一个 1n 的排列,问在加上排列后的数组中相同元素的最大值

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

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 个 "的位置上。

1k,k12,1k,k12, 以此类推。这样,每隔 2k2 个位置就重复一次。( k1)

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

eg
n=10,x=2k = 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

暴力做法:(TLE)由于是 O(n) (n109)的做法肯定会 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 满足 (2k2)×t+x=n(2k2)×t+2kx=n

可以变形为:(2k2)|(nx)(2k2)|(n+x2k)(2k2)|(n+x2)

所以只需要判断哪些数是 (nx)(n+x2) 的偶数 (由于(2k-2)一定是偶数) 因子,即代表 (2k2),所以存入的时候存 ki2+1

kx 还满足 kx

NOTE: 试除法:要找到某个数的所有因子只需要 ni 是因子的情况下加入 i, ni 即:

(不过当 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 个小队组成的军队的总兵力会减少 (k1)x 个单位。注意,军队总是由个至少一个班组成。

n 个种族,而 i 个种族的生物数量等于 ci 。确定他们所能组建的军队的最大兵力。

Solution

三分(先单增,再单减)组合数

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

三分法 (待更 )

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

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

先算出 ik 的整数部分,意味着每个队伍都至少有 ik 个人

当每个队伍都是 ik 个人,这时的贡献:ik×(k1)×ik×k2

对于一个人来说,其他队伍的人都有助于贡献:ik×(k1)

对于和他同一个队伍的人来说:ik×(k1)×ik

其他队伍的也是一样,所以这时的贡献:ik×(k1)×ik×k2

余数部分,只有部分队伍仅有 1 人,贡献:i%k×(i%k1)2

余数和整数部分的接壤:则贡献:(k1)×ik×i%k

对于后加入的余数部分,之前整数部分和他不在同一个队伍的 (k1)×ik 个人需要算上贡献

则该种族的战斗力ik×(k1)×ik×k2+i%k×(i%k1)2+(k1)×ik×i%k(k1)×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,,m 互不相同 c=m(m+1)2m22×105n, O(mn)=O(nn)

注:

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 - 知乎

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

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

由于 c 有限制,所以这种方法可以在 O(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

给你两个整数 xy 。长度为 n 的序列 a 如果是 a1=x ,且对于所有 1<inai 值要么是 ai1+y 要么是 ai1mody

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

Solution

DP

暴力搜索O(2n)

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,,x+ky 的前缀,然后会有一些形如 xmody,xmody+y,,xmody+ky 的块。

我们可以从序列的所有元素中减去 xmody,然后将所有元素除以 y(所有元素最初的余数都为 xmody,因此它们都是可被 y 整除的)。设 b1=xxmodyy。那么我们的序列将以 b1,b1+1,,b1+k1 开头,然后会有形如 0,1,,ki 的块。

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

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

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

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

第一部分 x,x+y,x+k1y xx%yy,xx%yy+1,xx%yy+2,,xx%yy+k1

其余部分 x%y,x%y+y,x%y+kiy 0,1,2,ki

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

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

(待更 )

![](/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";
}