https://codeforces.com/contest/1995

A. Diagonals

原题链接：https://codeforces.com/contest/1995/problem/A

模拟。

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
const int N = 2e5 + 5, MOD = 998244353;
#define pii pair<int, int>
int n, k;
void solve() {
    cin >> n >> k;
    int ans = 0;
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= (i == n ? 1 : 2); j++) {
            if (k >= i) {
                k -= i;
                ans++;
            }
        }
    }
    cout << ans << endl;
}

signed main() {
    IOS;
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

B1. Bouquet (Easy Version)

原题链接：https://codeforces.com/contest/1995/problem/B1

排序后滑动窗口。

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
const int N = 2e5 + 5, MOD = 998244353;
#define pii pair<int, int>
ll n, m;
int a[N];
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + 1 + n);
    ll ans = 0;
    ll hwc = 0;
    for (int r = 1, l = 1; r <= n; r++) {
        hwc += a[r];
        while (l <= r && (hwc > m || a[r] - a[l] > 1)) {
            hwc -= a[l];
            l++;
        }
        ans = max(ans, hwc);
    }
    cout << ans << endl;
}

signed main() {
    IOS;
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

B2. Bouquet (Hard Version)

原题链接：https://codeforces.com/contest/1995/problem/B2

非常典的模拟。

先尝试买尽可能多的花瓣数为x的花。

然后尝试买尽可能多的花瓣数为x+1的花。

然后尝试尽可能多的把花瓣数为x的花转化为x+1。

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
const int N = 2e5 + 5, MOD = 998244353;
#define pii pair<int, int>
ll n, m;
ll a[N], c[N];
int id[N];
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    iota(id + 1, id + 1 + n, 1);
    sort(id + 1, id + 1 + n, [&](int l, int r) { return a[l] < a[r]; });
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ll n1 = min(m / a[id[i]], c[id[i]]);
        ll s1 = n1 * a[id[i]];
        ll rem = m - s1;
        ll sum = s1;
        if (i + 1 <= n && a[id[i + 1]] == a[id[i]] + 1) {
            int n2 = min(rem / a[id[i + 1]], c[id[i + 1]]);
            ll s2 = n2 * a[id[i + 1]];
            sum += s2;
            rem -= s2;
            ll remn2 = c[id[i + 1]] - n2;
            sum += min({n1, remn2, rem});
        }
        ans = max(ans, sum);
    }
    cout << ans << endl;
}

signed main() {
    IOS;
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

C. Squaring

原题链接：https://codeforces.com/contest/1995/problem/C

每次都是平方。

如果存储没个数平方后的结果，那么容易爆longlong。

对于数字a[i]，只需要关注：

• 数字a[i-1]放缩了多少倍
• 数字a[i]放缩多少倍可以不小于a[i-1]

a[i]可能一开始就不小于a[i-1]，a[i-1]平方几次也不会超过a[i]。

这部分次数可以用来抵消a[i-1]已放缩的倍数。

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
const int N = 2e5 + 5, MOD = 998244353;
#define pii pair<int, int>
int n;
int a[N];

int calc(ll a, ll b) {
    int cnt = 0;
    if (a > b) {
        while (a > b) {
            b *= b;
            cnt += 1;
        }
    } else {
        while (a < b) {
            a *= a;
            cnt -= 1;
        }
        if (a > b)
            cnt += 1;
    }
    return cnt;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    ll ans = 0, lst = 0;
    for (int i = 2; i <= n; i++) {
        if (a[i] == 1 && a[i - 1] > 1) {
            cout << -1 << endl;
            return;
        }
        if (a[i - 1] == 1) {
            lst = 0;
            continue;
        }
        int t = calc(a[i - 1], a[i]);
        if (-t >= lst) {
            lst = 0;
        } else {
            lst = t + lst;
        }
        ans += lst;
    }
    cout << ans << endl;
}

signed main() {
    IOS;
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

D. Cases

原题链接：https://codeforces.com/contest/1995/problem/D

一个硬控我两天半的集合状压DP。

题目要求每个字符串长度至多为k。

意味着每连续的k个字符，至少有一个被选中，作为T中的一个元素。

• 设T为最终选择的末尾元素集合。

设$ S_i $为下标i开始的，长度为k的滑动窗口的，可能作为T中元素的，字符集合。

对于$ S_{1} $到$ S_{n-k+1} $，因为：每连续的k个字符，至少有一个被选中

• 所以T与每个$ S_i $都一定有交集。

我们最终关心的，是T中不同的字符个数，最小。

所以S维护的，也是字符种类。

• 显然可能存在两个区间，S维护的字符种类相同
• T要与这两个区间有交集
• T中必然存在元素，存在于S中，具体是哪个，无关紧要。
• 只需要保证有交集，并且求出所有满足条件的T中，字符种类的最小值。

S可以通过一遍滑动窗口求出。

如何通过S求出候选T，然后在候选T中选出最终的最优T？

枚举每个可能T与每个S是否有交集，时间复杂度是$ 2^c\cdot n $，时间复杂度会爆炸。

时间复杂度分为两部分：

• $ 2^c $：枚举每个可能集合
• n：验证所枚举集合，与每个S是否有交集

可以把n优化掉。

候选T与每个S有交集，意味着，每个S，都不是候选T的补集的子集。

可以求出，每个S所有的超集，标记为1。

当一个集合没有被标记为1时，对于每个S都满足：

• 该集合不是S的超集
• 该集合取反，一定与S有交集
• 该集合取反，可以作为候选的T

构造S的过程，还应注意，S的语义，是，末尾下标字符的集合。

原字符串的最后一个字符，一定会作为末尾下标字符。

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
const int N = 2e5 + 5, MOD = 998244353;
#define pii pair<int, int>
int n, c, k;
string s;
int dp[1 << 19];
void solve() {
    cin >> n >> c >> k;
    cin >> s;
    s = ' ' + s + ' ';
    int cnt[26]{};
    int state = 0;
    for (int i = 0; i < 1 << c; i++)
        dp[i] = 0;
    dp[1 << s[n] - 'A'] = 1;
    for (int i = 1, j = 0; i + k - 1 <= n; i++) {
        if (i - 1) {
            int x = s[i - 1] - 'A';
            if (--cnt[x] == 0) {
                state ^= 1 << x;
            }
        }
        while (j + 1 <= i + k - 1) {
            int x = s[++j] - 'A';
            if (cnt[x]++ == 0) {
                state ^= 1 << x;
            }
        }
        dp[state] = 1;
    }
    for (int i = 0; i < 1 << c; i++) {
        for (int j = 0; j < c; j++) {
            if (i >> j & 1)
                dp[i] |= dp[i ^ 1 << j];
        }
    }
    int ans = 1e9;
    int mask = (1 << c) - 1;
    for (int i = 0; i < 1 << c; i++) {
        if (dp[i] == 0)
            ans = min(ans, __builtin_popcount(mask ^ i));
    }
    cout << ans << endl;
}

signed main() {
    IOS;
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}