title: Educational Codeforces Round#152 (Div. 2) date: 2023-08-06 13:02:41 updated: 2023-08-06 13:02:41 categories: ACM&算法 tag:
有 $a$ 个面包片，$b$ 个奶酪片，$c$ 个火腿片，要保证奶酪片和火腿片必须被两块面包片直接夹，问最多可以造多大的汉堡
很简单，就不讲了
void solve() {
int _;
cin >> _;
for (int tss = 0; tss < _; ++tss) {
int a, b, c;
cin >> a >> b >> c;
int m = min(a - 1, b + c);
cout << m * 2 + 1 << endl;
}
}
有 $n$ 个怪物，每个怪物有一定生命值 $a[i]$，每次攻击一定是对着生命值最高的怪物，并减少其生命值 $k$，若有多个则选择最左边的，问怪物的死亡顺序
当有任何怪物的生命值大于 $k$ 的时候，那就意味着不会有怪物死亡，所以可以先对所有怪物进行 mod k 操作
此时，就会有怪物出现死亡，因为会恰好降低到 $0$，需要先输出为 $0$ 的怪物，从左往右输出即可
后面，再根据剩余生命值从大到小，从左往右输出即可
void solve() {
int _;
cin >> _;
for (int tss = 0; tss < _; ++tss) {
int n, k;
cin >> n >> k;
map<int, vector<int>> res;
for (int i = 0; i < n; ++i) {
int tmp;
cin >> tmp;
tmp %= k;
res[tmp].push_back(i);
}
auto zero = res[0];
for (auto i : zero) cout << i + 1 << ' ';
for (auto iter = res.rbegin(); iter != res.rend(); ++iter) {
if (iter->first == 0) continue;
for (auto i : iter->second) cout << i + 1 << ' ';
}
cout << endl;
}
}
这题老坑人了QAQ
有一个初始字符串 $s$，仅有 0 和 1 组成。
有 $k$ 次操作，每次操作都是在这个初始字符串上进行的。每次操作选择一个区间 $[l, r]$，并使得这个区间内的值进行排序，即 $0101010 \rightarrow 0000111$
问，得到的这 $k$ 个字符串，有多少种不同的
有点蒙，但还是得找找思路
考虑到字符串种类，第一反应是做字符串 hash，这非常简单，因为字符串仅有 0 和 1，为了方便，如果当前位为 1 则取这一位的权制，否则不取，这样就有点类似 $mod$ 进制数了
接下来是如何计算 $k$ 个字符串的 hash 值，根据题目给出的数据量，看起来必须在 O(sqrt(n)) 时间之内完成。我们可以发现，每次操作后实际上有三个区间
即然某段区间存在和之前 hash 值相同的情况，那么可以通过对 hash 值前缀和的方式，使得能够快速求出任意区间的 hash 值，那么就只剩下中间的区间了
有意思的是，排序后的值恰好是一个前面为 0 后面为 1 的字符串，所以计算单独计算这段区间内的 hash 结果非常简单，只需要有一个每一位的 hash 值的前缀和，并且知道 1 从哪一位开始即可，因为最后一个一定也是 1（当然需要排除一下压根没有 1 的情况）
而需要计算某个区间内的 1 的数量，好像又可以做一次前缀和
最终，只需要三个前缀和就可以简单解决问题了
但是试了两个 hash 值都不通过，一气之下直接同时计算两个 hash 值，然后就过了
void solve() {
int _;
cin >> _;
vector<int> pw1(2e5 + 10);
vector<int> pw2(2e5 + 10);
int tmp1 = 1;
int tmp2 = 1;
int mod = 998244353;
for (int i = 1; i < pw1.size(); ++i) {
pw1[i] = (pw1[i - 1] + tmp1) % mod;
tmp1 *= 131;
tmp1 %= mod;
pw2[i] = (pw2[i - 1] + tmp2) % mod;
tmp2 *= 1331;
tmp2 %= mod;
}
for (int ts = 0; ts < _; ++ts) {
int n, k;
cin >> n >> k;
vector<int> a(n + 1), b1(n + 1), b2(n + 1);
string str(n, '0');
cin >> str;
tmp1 = 1;
tmp2 = 1;
for (int i = 0; i < n; ++i) {
a[i + 1] = a[i] + str[i] - '0';
b1[i + 1] = (b1[i] + (str[i] == '1' ? tmp1 : 0)) % mod;
tmp1 *= 131;
tmp1 %= mod;
a[i + 1] = a[i] + str[i] - '0';
b2[i + 1] = (b2[i] + (str[i] == '1' ? tmp2 : 0)) % mod;
tmp2 *= 1331;
tmp2 %= mod;
}
set<pair<int, int>> res;
for (int i = 0; i < k; ++i) {
int l, r;
cin >> l >> r;
int ls, rs;
{
int left = b1[l - 1] % mod;
int right = (b1[n] - b1[r] + mod) % mod;
int one = a[r] - a[l - 1];
int zero = r - l + 1 - one;
int from = l + zero, to = r;
int mid = (pw1[to] - pw1[from - 1] + mod) % mod;
ls = (left + right + mid) % mod;
}
{
int left = b2[l - 1] % mod;
int right = (b2[n] - b2[r] + mod) % mod;
int one = a[r] - a[l - 1];
int zero = r - l + 1 - one;
int from = l + zero, to = r;
int mid = (pw2[to] - pw2[from - 1] + mod) % mod;
rs = (left + right + mid) % mod;
}
res.insert({ls, rs});
}
cout << res.size() << endl;
}
}
有一段数组 $a$，每个值必定是 $0, 1, 2$ 其中一个，开始的时候所有值都是蓝色的，你可以进行如下操作
问，你最少需要支付多少钱才能把所有值变成红色
容易明白的是，无论如何先随便找个 $2$ 染色的一定不亏，然后这个 $2$ 就会向两侧染色，直到遇到 $0$。那么这样处理完成后，再找下一个没有被染色的 $2$，直到 $2$ 被全部耗尽
然后是 $0, 1$ 的问题了，很明显的是，在一段连续没有被染色的区间下，可以分类讨论
所以结论为，每一段没有染色的区间，需要 $max(cnt_0, cnt_part1)$ 的花费
void solve() {
int n;
cin >> n;
vector<int> data(n);
vector<bool> vis(n, false);
int res = 0;
for (int i = 0; i < n; ++i) cin >> data[i];
// 先处理 2 的情况
for (int i = 0; i < n; ++i) {
if (vis[i] || data[i] != 2) continue;
res++;
vis[i] = true;
for (int j = i - 1; j >= 0; --j) {
if (!vis[j]) {
vis[j] = true;
if (data[j] == 0) break;
} else break;
}
for (; i < n; ++i) {
vis[i] = true;
if (data[i] == 0) break;
}
}
// 再处理 1 的情况
int last = -1;
int zero = 0;
int oneP = 0;
for (int i = 0; i < n; ++i) {
if (vis[i]) {
res += max(oneP, zero);
zero = 0;
oneP = 0;
last = -1;
} else if (data[i] == 0) {
zero++;
last = 0;
} else if (last != 1) {
last = 1;
oneP++;
}
}
res += max(oneP, zero);
cout << res << endl;
}