1995(961div2)

A. Diagonals

给 Vitaly 503 一个方格棋盘，棋盘上有 $n$ 和 $k$ 个筹码。他意识到所有这些 $k$ 芯片都需要放置在棋盘的单元格上（一个单元格上不能放置超过一个芯片）。

让我们把 $i$ /th 行和 $j$ /th 列中的单元格表示为 $(i, j)$ 。对角线是指 $i + j$ 值相同的单元格集合。例如， $(3, 1)$ 、 $(2, 2)$ 和 $(1, 3)$ 位于同一条对角线上，而 $(1, 2)$ 和 $(2, 3)$ 不在同一条对角线上。如果一条对角线上至少有一个棋子，那么这条对角线就被称为 "被占 "对角线。

请计算在所有放置 $k$ 的筹码中，被占对角线的最少数目。

易得此处的对角线是指副对角线，则有 $1 (n) + 2 (n - 1) + 2 (n - 2) + \dots, + 2 = 2 (n - 1) + 1 = 2 n - 1$ 条对角线

按照从中间往外面贪心的占对角线即可。

void solve() {
    int n, k;cin >> n >> k;
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        if (k >= n - i + 1)cnt++, k -= n - i + 1;
        if (i != 1 && k >= n - i + 1)cnt++, k -= n - i + 1;
    }
    cout << cnt << '\n';
}

B1. Bouquet (Easy Version)

这是问题的简单版本。唯一不同的是，在这个版本中，花朵是通过枚举来指定的。

一个女孩准备过生日，她想买一束最漂亮的花。商店里一共有 $n$ 种花，每种花的特征是花瓣数，一朵有 $k$ 个花瓣的花需要花费 $k$ 个硬币。女孩决定花束中任何两朵花的花瓣数之差不能超过 1。同时，女孩希望花束的花瓣数尽可能多。不幸的是，她只有 $m$ 枚金币，无法再花费更多。她能组合的花束的花瓣总数最多是多少？

这个题太可惜了！一秒钟有思路，双指针(滑动窗口)，就是细节没考虑到

法一：滑动窗口

#define int long long
void solve() {
    int n, m;cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    sort(a.begin() + 1, a.end());
    int l = 1, r = 1, ans = 0, sum = 0;
    while (r <= n && a[r] <= m) {
        while (r <= n && sum + a[r] <= m && abs(a[r] - a[l]) <= 1) {
            sum += a[r];r++;
            ans = max(ans, sum);
            if (r > n) {
                cout << ans << '\n';return;
            }
        }
        while (l < r && abs(a[r] - a[l]) > 1) {
            sum -= a[l];l++;
            ans = max(ans, sum);
        }
        while (l < r && sum + a[r] > m) {
            sum -= a[l];l++;
            ans = max(ans, sum);
        }
    }
    cout << ans << '\n';
}

法二：官方题解

官方题解

首先，我们可以将花瓣数为 $x$ 的花朵数汇总为 $c_{x}$ （例如，对数组进行排序，然后创建数组对 $(x, c_{x})$ ，其中 $c_{x}$ 是元素长度等于 $x$ 的段。(例如，对数组排序，然后创建数组对 $(x, c_{x})$ ，其中 $c_{x}$ 是元素等于 $x$ 的段长度）。

请注意 $\sum_{x} c_{x} = n$ 。还要注意的是，每 $x$ 朵花所需的花瓣数不会超过 $⌊ \frac{m}{x} ⌋$ （否则花瓣总数将超过 $m$ ）。

然后我们遍历所有的 $x$ 。假设我们想要组合一束有 $x, x + 1$ 个花瓣的花束。我们可以在 $O (c_{x})$ 中暴力破解有 $x$ 个花瓣的花朵数量。如果我们有 $0 \leq k_{1} \leq m i n (c_{x}, ⌊ \frac{m}{x} ⌋)$ 朵花和 $x$ 片花瓣，那么我们就已经有了 $k_{1} * x$ 片花瓣。还有 $m - k_{1} * x$ 枚硬币可以用来购买有 $x + 1$ 个花瓣的花朵。我们最多可以买到 $k_{2} = m i n (c_{x + 1}, ⌊ \frac{m - k_{1} * x}{x + 1} ⌋)$ 朵带有 $x + 1$ 个花瓣的花。因此我们需要找出所有这些 $k_{1} * x + k_{2} * (x + 1)$ 的最大值。

求最大值的总复杂度为 $O (\sum_{x} c_{x}) = O (n)$ ，排序的总复杂度为 $O (n \log n)$ 。

#define int long long
void solve() {
    int n, m;cin >> n >> m;
    map<int, int>mp;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;mp[x]++;
    }
    int ans = 0;
    for (auto [x, y] : mp) {
        ans = max(ans, x * min(y, m / x));
        if (mp.count(x + 1)) {
            int z = mp[x + 1];
            for (int i = 1;i <= min(y, m / x);i++) {
                ans = max(ans, i * x + (x + 1) * min(z, (m - i * x) / (x + 1)));
            }
        }
    }
    cout << ans << '\n';
}

B2. Bouquet (Hard Version)

**这是问题的困难版本。唯一不同的是，在这个版本中，不是列出每种花的花瓣数，而是为所有类型的花设置花瓣数和商店中的花的数量。

一个女孩准备过生日，想买一束最漂亮的花。店里一共有 $n$ 种不同类型的花，每种花的花瓣数和数量都有相应的特征。一朵有 $k$ 个花瓣的花的价格是 $k$ 个金币。女孩决定，她用来装饰蛋糕的任何两朵花的花瓣数之差都不能超过 1。同时，女孩还想用尽可能多的花瓣组合成一束花。不幸的是，她只有 $m$ 枚金币，无法再花费更多。她能组合的花束花瓣总数最多是多少？

Solution

总的来说和 B1 做法相似，但是不能暴力做了。

首先尽量让 $x$ 装满，将剩余的给 $x + 1$ 装了直到装不下为止，这样之后若 $m$ 还有剩余，可能可以将 $x$ 替换为 $x + 1$ ，这样就可以让答案净赚 1。若无法再替换，则 $(x, x + 1)$ 此处达到最优。

将 $x$ 替换为 $x + 1$ 的条件有：

场上还有 $x$ 剩余
预备的 $x + 1$ 还有剩余
手里的金币还有剩余

#define int long long
void solve() {
    int n, m;cin >> n >> m;
    vector<int> a(n + 1), c(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    map<int, int>mp;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x; mp[a[i]] = x;
    }
    int ans = 0;
    for (auto [x, y] : mp) {
        ans = max(ans, x * min(y, m / x));
        if (mp.count(x + 1)) {
            int z = mp[x + 1];
            int k1 = min(y, m / x);
            int k2 = min(z, (m - k1 * x) / (x + 1));
            int coins = m - k1 * x - k2 * (x + 1);
            int r = min({k1, coins, z - k2});
            ans = max(ans, k1 * x + k2 * (x + 1) + r);
        }
    }
    cout << ans << '\n';
}

C. Squaring

ikrpprpp 发现了一个由整数组成的数组 $a$ 。他想让 $a$ 不递减。为此，他可以在数组的索引 $1 \leq i \leq n$ 上执行一个公正的操作，将 $a_{i}$ 替换为 $a_{i}^{2}$ （位置 $i$ 的元素及其平方）。

要使数组不递减，最少需要多少次正义行动？

Solution

法一：正常思路做：

当 $a_{i - 1} > a_{i}$ 时：说明这个时候并不满足要求，需要（计算出） $c u r$ 次才能使得 $a_{i - 1} \leq a_{i}$ ，这时候才满足要求

当 $a_{i - 1} ≪ a_{i}$ ，即至少 $a_{i - 1}^{2} \leq a_{i}$ ，这个时候 $a_{i}$ 又分为两种情况：(先计算出 $a_{i - 1} \geq a_{i}$ 需要操作几次)

设到达 $a_{i}$ 时的虚拟最大值是 $t m p$

$a_{i}$ 非常大，以至于 $a_{i - 1}$ 本来要进行 $l s t$ 次操作，而在这里 $a_{i - 1}$ 要到达 $a_{i}$ 需要的操作已经大于等于 $l s t$ ，那么这个时候 $a_{i}$ 自热不需要进行操作 $⟹ a_{i} \geq t m p \to don’t do op$
$a_{i}$ 很大，但不至于不需要操作，即 $a_{i} \geq a_{i - 1}^{2}$ ， $a_{i - 1}$ 本来需要进行 $l s t$ 次操作，这里需要进行 $< l s t$ 次的操作, 则相减则是 $a_{i}$ 需要进行的操作次数 $⟹ a_{i - 1}^{2} \leq a_{i} < t m p \to do op and not do much op$
$a_{i}$ 不够大，即 $a_{i - 1} \leq a_{i} < a_{i - 1}^{2}$ ， $a_{i - 1}$ 本来需要进行 $l s t$ 次操作，这里不需要进行操作，则 $a_{i}$ 需要进行 $l s t$ 次操作即操作数和 $a_{i - 1}$ 相同。 $⟹ a_{i - 1} \leq a_{i} < a_{i - 1}^{2} < t m p \to do op and do the same op$

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 2;i <= n;i++) {
        if (a[i] < a[i - 1] && a[i] == 1) {
            cout << "-1\n";return;
        }
    }
    int ans = 0, lst = 0;
    for (int i = 1;i <= n;i++) {
        int cur = 0;
        int x = a[i];
        while (x < a[i - 1]) {
            x *= x;cur++;
        }
        x = a[i - 1];
        while (lst > 0 && x * x <= a[i]) {
            x *= x;lst--;
        }
        cur += lst;
        ans += cur;
        lst = cur;
    }
    cout << ans << '\n';
}

法二：浮点数做法：

这个做法也是这个 Round 的 EDU 做法

若将数组进行对数处理，即 $a_{i} := \ln a_{i}$ ，这样， $a_{i}^{2} \leftrightarrow 2 \ln a_{i}$ ，当操作次数较大的时候 $a_{i} = 2^{k} \ln a_{i}$ ， $2^{k}$ 的数量级也很大，无法用浮点数存储。

若 $a_{i} := \ln \ln a_{i}$ ，则 $a_{i}^{2} \leftrightarrow \ln 2 + \ln \ln a_{i}$ ,这样操作数较大也随便存储了。

由于 $\ln \ln 1$ 无意义，所以先将 $a_{i} = 1$ 的情况处理了。

之后的数组只需要看 $a_{i - 1}$ 和 $a_{i}$ 之间差的 $\ln 2$ 有多少个即可。即 $⌈ \frac{\ln \ln a_{i - 1} - \ln \ln a_{i}}{\ln 2} ⌉$

#define int long long
constexpr double eps = 1e-9;
void solve() {
    int n;cin >> n;
    vector<double> a(n);
    for (auto& i : a)cin >> i;
    for (int i = 1;i < n;i++) {
        if (a[i - 1] > 1 && a[i] == 1) {
            cout << "-1\n";return;
        }
    }
    for (int i = 0;i < n;i++) {
        if (a[i] == 1) {
            a.erase(a.begin());
        } else {
            break;
        }
    }
    
    for (auto& i : a)i = log(log(i));
    
    int ans = 0;
    for (int i = 1; i < a.size(); i++) {
        double need = a[i - 1] - a[i];
        if (need > eps) {
            int cnt = 1 + (need - eps) / log(2);
            ans += cnt;
            a[i] += cnt * log(2);
        }
    }
    cout << ans << '\n';
}

D. Cases

你是一名语言学家，正在研究一种神秘的古代语言。你知道

它的单词只由拉丁字母的前 $c$ 个字母组成。
每个单词都有一个大小写，可以通过其最后一个字母明确地确定（不同的字母对应不同的大小写）。例如，单词 "ABACABA "和 "ABA"（如果存在的话）在该语言中具有相同的大小写，因为它们都有相同的词尾 "A"，而 "ALICE "和 "BOB "则有不同的大小写。如果语言中没有与某个字母相对应的大小写，则表示该单词不能以该字母结尾。
每个单词的长度为 $k$ 或更少。

您有一个用这种语言写成的文本。不幸的是，由于这种语言非常古老，单词之间没有空格，所有字母都是大写。您想知道这种语言的最少大小写个数是多少。您能找出答案吗？

Solution

SOS DP ->Subset of 状压 DP

1993(963div2) 之后补

A. Diagonals

B1. Bouquet (Easy Version)

法一 ：滑动窗口

法二 ：官方题解

B2. Bouquet (Hard Version)

Solution

C. Squaring

Solution

法一 ：正常思路做：

法二 ：浮点数做法：

D. Cases

Solution

法一：滑动窗口

法二：官方题解

法一：正常思路做：

法二：浮点数做法：