ABC379(A-G)
A - Cyclic¶
题目大意
给你一个三位数 \(N\)，其中 \(N\) 的数位中没有 \(0\)。设 \(a\)，\(b\) 和 \(c\) 分别代表 \(N\) 的百位、十位和个位数字。输出 \(bca\) 和 \(cab\)。
参考代码
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
cin >> s;
cout << s[1] << s[2] << s[0] << ' ' << s[2] << s[0] << s[1] << endl;
return 0;
}
B - Strawberries¶
题目大意
你有 \(N\) 个牙齿排成一行，牙齿的健康状况用一个长度为 \(N\) 的字符串 \(S\) 代表。如果 \(S_i\) 是 o，表示第 \(i\) 个牙齿是健康的。如果 \(S_i\) 是 x，表示第 \(i\) 个牙齿是不健康的。当你有连续的 \(K\) 个健康的牙齿时，可以用这 \(K\) 个牙齿吃草莓，吃完草莓之后，这连续的 \(K\) 个牙齿就会变成不健康的牙齿。问：最多能吃几个草莓？
解题思路
贪心，一定是优先用靠近左边的牙齿最优，直接遍历即可。
参考代码
#include <iostream>
#include <string>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
string s;
cin >> s;
int cnt = 0, ans = 0;
for (auto c : s)
{
if (c == 'O')
{
if (++cnt == k)
{
ans++;
cnt = 0;
}
}
else
cnt = 0;
}
cout << ans << endl;
return 0;
}
C - Sowing Stones¶
题目大意
有 \(N(2 \le N \le 2 \times 10 ^ 9)\) 个格子和 \(M(1 \le M \le 2 \times 10 ^ 5)\) 堆石头，第 \(i\) 堆石头在第 \(X_i\) 个格子中，有 \(A_i\) 个。
你可以执行以下操作任意次：
- 选择第 \(i(1 \le i \le N-1)\) 个格子，如果第 \(i\) 个格子上有石头，则移动 \(1\) 个石头到第 \(i+1\) 个格子中。
问：至少要操作几次才能让 \(N\) 个格子都恰好只有 \(1\) 个石头？如果无论如何也无法做到，输出 -1
解题思路
因为石头只能向右移动，所以一定是从右往左填充每个格子的石头。但是因为有 \(N\) 个格子，必须将连续的一段一起处理才能加速。考虑我们找到了连续的某段 \([l, r]\) 目前没有石头，则需要在已有的石头堆中找到一个小于 \(l\) 的格子，由这个格子补充 \([l, r]\) 的石头，操作的次数可以用等差数列求和公式算出来。其余的细节就是考虑如何无解的判定，有两种情况：
- 石头不够的情况。
- 石头过多的情况。也就是 \([l, r]\) 处理完成后，负责补充这一段的石头剩余的石头大于 \(1\) 个，就会导致石头数量过多。
参考代码
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
using LL = long long;
int main()
{
int n, m;
cin >> n >> m;
vector<pair<int, int>> stone(m);
for(int i = 0; i < m; i++)
cin >> stone[i].first;
for(int i = 0; i < m; i++)
cin >> stone[i].second;
sort(stone.begin(), stone.end());
LL ans = 0;
int now = n, top = m - 1;
while(now && top >= 0)
{
LL cnt = stone[top].second;
if(cnt > now - stone[top].first + 1)
{
cout << -1 << endl;
return 0;
}
LL r = now - stone[top].first;
LL l = r - cnt + 1;
ans += cnt * (l + r) / 2;
now -= cnt;
top--;
}
if(now > 0)
ans = -1;
cout << ans << endl;
return 0;
}
D - Home Garden¶
题目大意
你需要维护一个集合，给你 \(Q(1 \le Q \le 2 \times 10 ^ 5)\) 个操作，有三种类型的操作：
1：给集合中添加一个数字 \(0\)，注意，集合中允许出现相同的数字。2 T：给集合中所有的数字的值加上 \(T(1 \le T \le 10 ^ 9)\)3 H：删除集合中所有大于等于 \(H\) 的数字，然后输出删除了多少个数字。
解题思路
集合中所有数字加 \(T\) 相当于后面加入的数字基准减少 \(T\)，同理操作 3 的基准也要减少 \(T\)。
这样只需要维护一个可重集（multiset）就可以了，因为每个点只会加入和删除一次，时间复杂度就是 \(O(Q\log Q)\)，不过更简单的是，注意到加入的数字一定是递减的，所以维护一个队列就可以。
参考代码
#include <iostream>
#include <queue>
using namespace std;
using LL = long long;
int main()
{
int q;
cin >> q;
LL add = 0;
queue<LL> queue;
while(q--)
{
int op;
cin >> op;
if(op == 1)
queue.push(-add);
else if(op == 2)
{
LL t;
cin >> t;
add += t;
}
else
{
LL h;
cin >> h;
int ans = 0;
while(!queue.empty() && queue.front() >= h - add)
{
queue.pop();
ans++;
}
cout << ans << endl;
}
}
return 0;
}
E - Sum of All Substrings¶
题目大意
给你一个长度为 \(N(1 \le N \le 2 \times 10 ^ 5)\) 的字符串 \(S\)，\(S\) 由数字 1 到 9 组成。定义 \(f(i, j)\) 表示 \(S\) 的子串 \(S_iS_{i+1}\cdots S_j\) 所对应的数字，求出 \(\sum\limits_{i = 1}^N\sum\limits_{j=i}^Nf(i, j)\) 的值。
解题思路
首先模拟一下第一个样例 379，假设我们固定 \(r\)，计算的过程就是：
3
37 + 7
379 + 79 + 9
设 \(g[r] = \sum\limits_{i = 1}^r f(i, r)\)，则有 \(g[r] = g[r-1] * 10 + r * S[i]\)，这样的话，看上去只需要写一个高精度就好了，但是数字太大，高精度也会 TLE。我试过避开高精度乘法，也就是将 \(g[r-1] * 10\) 拆成字符串后面补 '0'，以及 \(r * S[i]\) 拆成 to_string，即使这样，在只剩下高精度加法的情况下还是会 TLE。可能压位高精能卡过去。
正确的做法是，考虑每个数字的贡献，显然第 \(i\) 位只会影响 \(i\) 及以后的值。还是以刚刚的 379 为例：
3
37 + 7
379 + 79 + 9
第一个数字产生的贡献是 \(333\)，第二个数字产生的贡献是 \(77 + 77\)，第三个数字产生的贡献是 \(9 + 9 + 9\)，每个数字的贡献就是 \(i S[i]\times(10^0 + 10^1 + \cdots + 10^{N-i})\)，这里我们应该存所有 \(10^k\) 的贡献，这样剩下的部分 \(iS[i]\) 是很小的，用 long long 就存的下。只需要用差分数组就能维护，最后再把所有的贡献合并起来就可以了。
参考代码
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int main()
{
int n;
string s;
cin >> n >> s;
auto add = [](const string &x, const string &y) -> string
{
int n = x.size(), m = y.size();
string z(max(n, m), '0');
int i = n - 1, j = m - 1, k = z.size() - 1;
int in = 0;
for (; i >= 0 && j >= 0; i--, j--, k--)
{
int sum = (x[i] - '0') + (y[j] - '0') + in;
in = sum / 10;
sum %= 10;
z[k] = sum + '0';
}
for (; i >= 0; i--, k--)
{
int sum = (x[i] - '0') + in;
in = sum / 10;
sum %= 10;
z[k] = sum + '0';
}
for (; j >= 0; j--, k--)
{
int sum = (y[j] - '0') + in;
in = sum / 10;
sum %= 10;
z[k] = sum + '0';
}
return in ? '1' + z : z;
};
string ans = {s[0]}, g = ans;
for (int i = 1; i < n; i++)
{
int c = s[i] - '0';
g += '0';
string ic = to_string((i+1) * c);
g = add(g, ic);
ans = add(ans, g);
}
cout << ans << endl;
return 0;
}
F - Buildings 2¶
题目大意
有 \(N(2 \le N \le 2 \times 10 ^ 5)\) 个建筑排成一行，第 \(i\) 个建筑的高度是 \(H_i(1 \le H_i \le N)\)。对于数对 \((i, j)(1 \le i < j \le N)\)，建筑 \(i\) 能看到建筑 \(j\) 的条件是不存在建筑 \(k\) 满足 \(i < k < j\) 且 \(H_k > H_j\)。
给你 \(Q(2 \le Q \le 2 \times 10 ^ 5)\) 个询问，每一个询问给你两个数字 $(l_i, r_i) $，其中 \((l_i < r_i)\)，你需要回答出在建筑 \(r_i\) 的右边有多少个建筑既能被建筑 \(l_i\) 看到，也能被建筑 \(r_i\) 看到。
解题思路
假设在建筑 \(r_i\) 的右侧，第一个能同时被建筑 \(l_i\) 和建筑 \(r_i\) 看到的是建筑 \(x\)，后续能看的建筑一定是从建筑 \(x\) 开始高度递增的建筑，也就是从建筑 \(x\) 开始一直跳到右侧第一个高度大于等于自身的建筑。显然这个信息可以预处理一个单调栈，从后往前处理一个高度单调递减的栈，栈的大小就是每个元素能往后跳多少步。
下面考虑对于一个 \((l_i, r_i)\)，如何找到第一个能同时被建筑 \(l_i\) 和建筑 \(r_i\) 看到的是建筑 \(x\)。建筑 \(l_i\) 会被 \([l_i+1, r_i]\) 范围内的所有建筑遮挡视线，进一步考虑，实际是 \([l_i+1, r_i]\) 范围内最高的建筑遮挡了 \(l_i\)，设 \([l_i+1, r_i]\) 范围内最高的建筑是建筑 \(k\)，则建筑 \(l_i\) 和建筑 \(r_i\) 能同时看到的建筑就是在建筑 \(k\) 右侧的比建筑 \(k\) 还高的建筑，而这已经用单调栈解决了。至于如何求出某个区间内最高的建筑，用 ST 表即可。
参考代码
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
struct SparseTable
{
int n;
const vector<int> &h;
vector<int> lg;
vector<vector<int>> max_idx;
SparseTable(const vector<int> &h) : n(h.size()), h(h), lg(n + 1)
{
for (int i = 2; i <= n; i++)
lg[i] = lg[i >> 1] + 1;
max_idx.assign(n, vector<int>(lg[n] + 1));
for (int i = 0; i < n; i++)
max_idx[i][0] = i;
for (int k = 1, t = 1; k <= lg[n]; k++, t <<= 1)
for (int i = 0, j = t; j + t <= n; i++, j++)
{
int x = max_idx[i][k - 1], y = max_idx[j][k - 1];
max_idx[i][k] = h[x] > h[y] ? x : y;
}
}
int RMQ(int l, int r) const
{
int k = lg[r - l + 1], len = 1 << k;
int x = max_idx[l][k], y = max_idx[r - len + 1][k];
return h[x] > h[y] ? x : y;
}
};
int main()
{
int n, q;
cin >> n >> q;
vector<int> h(n);
for (int i = 0; i < n; i++)
cin >> h[i];
SparseTable st(h);
vector<int> cnt(n);
stack<int> stack;
for (int i = n - 1; i >= 0; i--)
{
while (!stack.empty() && h[i] > h[stack.top()])
stack.pop();
cnt[i] = stack.size();
stack.push(i);
}
while (q--)
{
int l, r;
cin >> l >> r;
l--, r--;
int k = st.RMQ(l + 1, r);
cout << cnt[k] << endl;
}
return 0;
}
G - Count Grid 3-coloring¶
题目大意
给你一个 \(H \times W(1 \le H \times W \le 200)\) 的网格，每个格子的字符有 1、2、3 和 ?，你需要将所有的 ? 替换成 1、2 或 3，问：有多少种替换方案能够让任意相邻的位置的数字都不相同？答案对 \(998244353\) 取模。
解题思路
一眼看上去就是一个状压的模板，看一眼数据范围，\(H \times W \le 200\)，\(200 = 10 \times 20\)，也就是说列的最小值是 \(10\)（如果行比列多，旋转一下就好），这样每一行最多有 \(10\) 格，每一格需要 \(2\text{bit}\) 存储状态，也就是 \(2^{20}\) 个状态。
定义 \(dp[i][j][s]\) 表示填到第 \(i\) 行第 \(j\) 个时，最下方的轮廓线的状态为 \(s\) 的方案数。转移的时候，只需要根据当前格是 ? 还是数字算出下一个可行的状态就好。时间复杂度 \(O(HW2^{20})\)，能过。
需要注意的是第一行的轮廓线状态的初始答案不太好直接求出来，我的办法是直接枚举 \(2^{20}\) 种情况暴力算出来。代码中的 dfs 函数就是在干这个事情。
参考代码
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
const int MOD = 998244353;
int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>> g;
if (m <= n)
{
g.assign(n, vector<int>(m));
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
for (int j = 0; j < m; j++)
g[i][j] = s[j] == '?' ? -1 : (s[j] - '1');
}
}
else
{
g.assign(m, vector<int>(n));
for (int j = 0; j < n; j++)
{
string s;
cin >> s;
for (int i = 0; i < m; i++)
g[m - i - 1][j] = s[i] == '?' ? -1 : (s[i] - '1');
}
swap(n, m);
}
unordered_map<int, int> dp[2];
unordered_map<int, int> *now = &dp[0], *pre = &dp[1];
auto dfs = [&now, &g](auto &self, int cur, int st, int last) -> void
{
if (cur == -1)
{
(*now)[st] = 1;
return;
}
if (g[0][cur] == -1)
{
for (int i = 0; i < 3; i++)
if (last != i)
self(self, cur - 1, st << 2 | i, i);
}
else
{
int x = g[0][cur];
if (last != x)
self(self, cur - 1, st << 2 | x, x);
}
};
auto get = [](int s, int i) -> int
{ return (s >> (2 * i) & 0b11); };
auto set = [](int s, int i, int x) -> int
{ return (s & ~(0b11 << (2 * i))) | x << (2 * i); };
dfs(dfs, m - 1, 0, -1);
for (int i = 1; i < n; i++)
{
for (int j = 0; j < m; j++)
{
swap(now, pre);
now->clear();
int x = g[i][j];
if (x == -1)
{
for (auto [s, cnt] : *pre)
{
int up = get(s, j), left = j ? get(s, j - 1) : -1;
for (int y = 0; y < 3; y++)
if (y != up && y != left)
{
int ns = set(s, j, y);
(*now)[ns] += cnt;
(*now)[ns] %= MOD;
}
}
}
else
{
for (auto [s, cnt] : *pre)
{
int up = get(s, j), left = j ? get(s, j - 1) : -1;
if (x != up && x != left)
{
int ns = set(s, j, x);
(*now)[ns] += cnt;
(*now)[ns] %= MOD;
}
}
}
}
}
int ans = 0;
for (auto [s, cnt] : *now)
ans = (ans + cnt) % MOD;
cout << ans << endl;
return 0;
}
创建日期: 2024-12-26