补题A-D-Codeforces-Round-961-Div.-2
目录
补题A-D Codeforces Round 961 (Div. 2)
A. Diagonals
原题链接：
模拟。
#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)
原题链接：
排序后滑动窗口。
#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)
原题链接：
非常典的模拟。
先尝试买尽可能多的花瓣数为
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
原题链接：
每次都是平方。
如果存储没个数平方后的结果，那么容易爆
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
原题链接：
一个硬控我两天半的集合状压
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;
}