ABC384(A-G)
A - aaaadaa¶
题目大意
给你一个长度为 \(N\) 的字符串 \(S\) 以及两个字符 \(c_1\) 和 \(c_2\)，将 \(S\) 中所有不是 \(c_1\) 的字符替换成 \(c_2\)
参考代码
#include <iostream>
#include <string>
using namespace std;
int main()
{
int n;
char c1, c2;
string s;
cin >> n >> c1 >> c2 >> s;
for(auto ch : s)
cout << (ch == c1 ? c1 : c2);
return 0;
}
B - ARC Division¶
题目大意
ARC 有两个级别：
- Div. 1：所有积分位于\([1600, 2799]\) 的参赛者的表现都会影响积分。
- Div. 2：所有积分位于\([1200, 2399]\) 的参赛者的表现都会影响积分。
你打算参加 \(N\) 场 ARC，第 \(i\) 场的级别是 Div. \(D_i\)，在这场 ARC 中你的表现是 \(A_i\)。
如果参赛前你的积分落在对应的区间上，那么你的积分将会受到比赛中的表现所影响，具体来说，如果参赛前你的积分是 \(T\)，那么在比赛结束后你的积分会变成 \(T + A_i\)。
问：\(N\) 场比赛结束后，你的积分是多少？
参考代码
#include <iostream>
using namespace std;
int main()
{
int n, r;
cin >> n >> r;
auto div1 = [](int x) -> bool
{ return x >= 1600 && x <= 2799; };
auto div2 = [](int x) -> bool
{ return x >= 1200 && x <= 2399; };
while(n--)
{
int d, a;
cin >> d >> a;
if(d == 1)
{
if(div1(r))
r += a;
}
else
{
if(div2(r))
r += a;
}
}
cout << r << endl;
return 0;
}
C - Perfect Standings¶
题目大意
你举办了一场编程竞赛，里面有五道题 ABCDE，A 题分数是 \(a\)，B 题分数是 \(b\)，C 题分数是 \(c\)，D 题分数是 \(d\)，E 题分数是 \(e\)，其中 \(100 \le a \le b \le c \le d \le e \le 2718\)。
一共来了 \(31\) 位参赛选手，每位参赛选手都至少答对了 \(1\) 道题，且所有参赛选手的答对的题目情况都不一样。可以用一个字符串代表答对了哪些题，例如 ABCDE 表示答对了所有题目的选手，ACE 表示答对了 ACE 三道题的选手。你需要给这些选手答题情况的字符串排名：
- 首先，根据答题情况的字符串，计算出选手的总得分，得分高的选手排名更考前。
- 如果有同分的情况，则字符串字典序更小的排名更靠前，
解题思路
dfs 模板。
参考代码
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int main()
{
vector<pair<int, string>> ans;
vector<int> score(5);
for (int i = 0; i < 5; i++)
cin >> score[i];
auto dfs = [&ans, &score](auto &self, int cur, int sum, string name) -> void
{
if (cur == 5)
{
if(sum)
ans.push_back({sum, name});
return;
}
self(self, cur + 1, sum + score[cur], name + char('A' + cur));
self(self, cur + 1, sum, name);
};
dfs(dfs, 0, 0, "");
sort(ans.begin(), ans.end(), [](const pair<int, string> &x, const pair<int, string> &y) -> bool
{ return x.first > y.first || (x.first == y.first && x.second < y.second); });
for(auto &[sum, name] : ans)
cout << name << endl;
return 0;
}
D - Repeated Sequence¶
题目大意
有一个周期为 \(N(1 \le N \le 2 \times 10 ^ 5)\) 的无限循环序列 \(A\)，前 \(N\) 项为 \((A_1, A_2, ..., A_N)\)，其中 \(1 \le A_i \le 10 ^ 9\)。
判断在 \(A\) 中是否存在一个连续的子序列和等于 \(S(1 \le S \le 10 ^ {18})\)。
解题思路
首先求出 \(M = \sum\limits_{i=1}^N\)，因为是无限循环序列，所以答案一定是某一段区间和加上若干循环的部分。
例如，我们可以找出某一段 \((A_l, A_{l+1}, ..., A_r)\)，这一段区间和等于 \(S \bmod M\)，剩下的部分重复 \(\lfloor\frac{S}{M}\rfloor\) 次循环就好。因此问题等价于找出 \(A_1\) 到 \(A_N\) 是否存在区间和等于 \(S \bmod M\)。
但是还有一种情况会漏掉，例如 \(N = 4\)，\(A_1A_2A_3\underline{A_4A_1A_2A_3A_4A_1}A_2A_3A_4\)，其中下划线表示和等于 \(S\) 的字符串，这里实际实际要找的字符串是 \(A_4A_1\)，这一段不是连续的子区间，而是一段后缀拼前缀的形式，因为无限循环，所以这个情况也要考虑到。
有两种处理办法：
- 将 \(A_1\) 到 \(A_N\) 扩展成 \(A_1\) 到 \(A_{2N}\)，在里面找是否有区间和等于 \(S \bmod M\)。
- 注意到这是后缀拼前缀的形式，所以可以找出是否存在一个区间和等于 \(M - S \bmod M\)，相当于在上面的例子中找出 \(A_2A_3\)，\(A_2A_3\) 的区间和等于 \(M - S \bmod M\)，所以剩下的部分就能通过后缀拼前缀的方式得到 \(S \bmod M\)。
两种办法都是找某个区间和等于某个值，因为 \(A_i\) 都是正数，所以直接双指针就好，不过如果有负数的话，就要用哈希表了。
下面的代码是第一种做法。
参考代码
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
int main()
{
int n;
LL s;
cin >> n >> s;
vector<LL> pre(2 * n + 1);
for (int i = 1; i <= n; i++)
{
cin >> pre[i];
pre[n + i] = pre[i];
pre[i] += pre[i - 1];
}
for (int i = n + 1; i <= 2 * n; i++)
pre[i] += pre[i - 1];
s %= pre[n];
for (int l = 0, r = 1; r <= 2 * n; r++)
{
while (pre[r] - pre[l] > s)
l++;
if (pre[r] - pre[l] == s)
{
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
return 0;
}
E - Takahashi is Slime 2¶
题目大意
有一个 \(H \times W(1 \le H, W \le 500)\) 的网格，每个网格 \((i, j)\) 都有一个史莱姆，强度为 \(S_{i,j}(1 \le S_{i, j} \le 10 ^ {12})\)。
史莱姆王的初始位置是 \((P, Q)\)，其他史莱姆和史莱姆王是敌对关系。史莱姆王想不断的吞并周围的史莱姆，设史莱姆王当前的强度为 \(A\) ，如果在他的身体周围上下左右 \(1\) 格有一个史莱姆的的强度是 \(B\)，且 \(A > XB\)，则史莱姆王可以吸收这个史莱姆，其中 \(X(1 \le X \le 10 ^ 9)\) 是一个给定的常数。当史莱姆王吸收了这个史莱姆之后，史莱姆王的强度将增加 \(B\)，且被吸收的史莱姆所在的位置也会成为史莱姆王身体的一部分。史莱姆王身体的所有部分具有相同的强度。
问：史莱姆王最多可以达到多少强度？
解题思路
显然是优先吸收身体周围强度比较弱的史莱姆，用一个小顶堆维护所有身体周围的史莱姆，不断的向外扩展就好。
不过这道题要注意一下 \(X \le 10 ^ 9\) 和 \(S_{i, j} \le 10 ^ {12}\)，所以 \(X\times S_{i,j}\) 会爆 long long，用除法就好。
参考代码
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using LL = long long;
const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};
struct Node
{
int r, c;
LL s;
bool operator>(const Node &other) const { return s > other.s; }
};
int main()
{
int h, w, p, q;
LL x;
cin >> h >> w >> x >> p >> q;
p--, q--;
vector<vector<LL>> g(h, vector<LL>(w));
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
cin >> g[i][j];
auto in_lim = [h, w](int r, int c) -> bool
{ return r >= 0 && r < h && c >= 0 && c < w; };
priority_queue<Node, vector<Node>, greater<Node>> heap;
LL now = g[p][q];
g[p][q] = -1;
for (int i = 0; i < 4; i++)
{
int nr = p + dr[i], nc = q + dc[i];
if (in_lim(nr, nc) && g[nr][nc] != -1)
{
heap.push({nr, nc, g[nr][nc]});
g[nr][nc] = -1;
}
}
while (!heap.empty())
{
auto [r, c, s] = heap.top();
heap.pop();
if (now / x < s || (now / x == s && now % x == 0))
break;
now += s;
g[r][c] = -1;
for (int i = 0; i < 4; i++)
{
int nr = r + dr[i], nc = c + dc[i];
if (in_lim(nr, nc) && g[nr][nc] != -1)
{
heap.push({nr, nc, g[nr][nc]});
g[nr][nc] = -1;
}
}
}
cout << now << endl;
return 0;
}
F - Double Sum 2¶
题目大意
定义 \(f(x) = \left\{\begin{matrix}f(\frac{x}{2}), & \text{if } x \equiv 0 \bmod 2\\x, & \text{if } x \equiv 1 \bmod 2 \end{matrix}\right.\)
给你一个长度为 \(N(1 \le N \le 2 \times 10 ^ 5)\) 的序列 \(A = (A_1, A_2, ..., A_N)\)，其中 \(1 \le A_i \le 10 ^ 7\) 求出 \(\sum\limits_{i=1}^N\sum\limits_{j=i}^Nf(A_i + A_j)\)
解题思路
可以发现，对于 \(f(a+b)\)：
- 如果 \(a\) 和 \(b\) 一奇一偶，则 \(f(a+b) = a+b\)
- 如果 \(a\) 和 \(b\) 都是偶数，则 \(f(a+b) = \frac{a}{2}+\frac{b}{2}\)
- 如果 \(a\) 和 \(b\) 都是奇数，则 \(f(a + b) = \lfloor\frac{a}{2}\rfloor + \lfloor\frac{b}{2}\rfloor + 1\)
设 \(g[i] = \sum\limits_{j=1}^if(A_i + A_j)\)，考虑怎么算出 \(g[i]\)，\(g[i]\) 实际固定了 \(A_i\)，因此还需要分类讨论：
- 如果 \(A_i\) 是偶数，首先要加上前面所有的奇数。然后还剩下偶数的部分，根据刚刚的推论，偶数需要除以 \(2\)，此时我们需要继续讨论 \(\frac{a}{2}\) 的奇偶性：如果 \(\frac{a}{2}\) 是偶数，就加上所有偶数且除以一次 \(2\) 之后是奇数的部分（相当于一次性加上多个 \(\frac{b}{2}\)），然后针对除以一次 \(2\) 之后是偶数的部分继续分类讨论......；如果 \(\frac{a}{2}\) 是奇数，转到 \(A_i\) 是奇数的讨论。
分析到这里可以发现，我们需要知道所有初始是奇数（二进制后缀是 \(1\)）的和、所有初始是偶数且除以一次 \(2\) 之后是奇数（二进制后缀是 \(10\)）的和，这可以通过一个 01Trie 树维护。
- 如果 \(A_i\) 是奇数，首先要加上前面所有的偶数。然后还剩下奇数的部分，根据刚刚的推论，奇数实际是变成 \(\lfloor\frac{a}{2}\rfloor + \lfloor\frac{b}{2}\rfloor + 1\) ，此时我们需要继续讨论 \(\lfloor\frac{a}{2}\rfloor + 1\) 的奇偶性：如果 \(\lfloor\frac{a}{2}\rfloor + 1\) 是奇数，就加上所有奇数且除以一次 \(2\) 之后是偶数的部分（相当于一次性加上多个 \(\lfloor\frac{b}{2}\rfloor\)），然后针对除以一次 \(2\) 之后是奇数的部分继续分类讨论......；如果 \(\lfloor\frac{a}{2}\rfloor + 1\) 是偶数，转到 \(A_i\) 是偶数的讨论。
因为 \(1 \le A_i \le 10 ^ 7\)，所以上述递归最多发生 \(\lceil \log_2(\max(A_i))\rceil\) 次，因为超出这个范围之后都是 \(0\)，就没必要走下去了。
实现的时候要注意一下，实际要让 \(a \leftarrow \frac{a+1}{2}\)，这样可以同时处理奇数和偶数的情况。
参考代码
#include <cmath>
#include <iostream>
using namespace std;
using LL = long long;
const int MAXA = 1E7;
const int LEN = ceil(log2(MAXA));
struct Trie
{
struct Node
{
Node *ne[2];
LL sum;
int cnt;
Node *at_or_new(int ch) { return ne[ch] == nullptr ? ne[ch] = new Node() : ne[ch]; }
Node *at(int ch) const { return ne[ch]; }
};
Node *root = new Node();
void insert(LL x)
{
Node *p = root;
for (int i = 0; i <= LEN; i++)
{
int ch = x & 1;
p = p->at_or_new(ch);
p->sum += x;
p->cnt++;
x >>= 1;
}
}
LL search(LL x) const
{
Node *p = root;
LL ans = 0;
while (p != nullptr)
{
int ch = x & 1;
Node *p_xor = p->at(ch ^ 1);
if(p_xor != nullptr)
ans += p_xor->cnt * x + p_xor->sum;
p = p->at(ch);
x = (x + 1) >> 1;
}
return ans;
}
};
int main()
{
int n;
cin >> n;
Trie t;
LL ans = 0;
while(n--)
{
LL a;
cin >> a;
t.insert(a);
ans += t.search(a);
}
cout << ans << endl;
return 0;
}
G - Abs Sum¶
题目大意
给你两个长度为 \(N(1 \le N \le 10 ^ 5)\) 的序列 \(A = (A_1, A_2, ..., A_N)\) 和 \(B = (B_1, B_2, ..., B_N)\)，其中 \(0 \le A_i, B_j \le 2 \times 10 ^ 8\)。
给你 \(Q(1 \le Q \le 10 ^ 4)\) 个询问，第 \(k\) 个询问给你两个数字 \(X_k(1 \le X_k \le N)\) 和 \(Y_k(1 \le Y_k \le N)\)，求出 \(\sum\limits_{i=1}^{X_k}\sum\limits_{j=1}^{Y_k}|A_i - B_j|\)。
解题思路
我们可以构造一个 \(N \times N\) 的矩阵，矩阵的第 \(i\) 行第 \(j\) 列表示 \(|A_i-B_j|\) 的值，一个询问 \((X_k, Y_k)\) 相当于求以 \((1, 1)\) 为左上角，\((X_k, Y_k)\) 为右下角的矩阵和。
假设我们已经有以 \((X, Y)\) 为右下角的矩阵和，考虑如何扩展到 \((X+1, Y)\)，这样会增加一行，也就是增加 \(\sum\limits_{j=1}^Y|A_{X+1} - B_j|\) 的值，显然要拆成 \(A_{X+1} \ge B_j\) 和 \(A_{X+1} < B_j\) 两个部分，这可以用树状数组维护 \(B\) 中每个数字出现的次数，以及前缀和，同理，还需要一个树状数组维护 \(A\) 的相关信息。考虑到 \(0 \le A_i, B_j \le 2 \times 10 ^ 8\)，需要离散化，这样树状数组的下标对应的是数字的排名。
每一次扩展或者收缩矩阵需要 \(\log N\) 的时间，为了减少扩展的次数，将所有的查询按照莫队排序即可，取块长度 \(S = \frac{N}{\sqrt Q}\) 即可。
参考代码
#include <algorithm>
#include <cmath>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
using LL = long long;
struct FenwickTree
{
int n;
vector<int> cnt;
vector<LL> sum;
FenwickTree(int n) : n(n), cnt(n + 1), sum(n + 1) {}
int lowbit(int x) const { return x & -x; }
pair<int, LL> prefix(int x) const
{
int c = 0;
LL s = 0;
for (; x; x -= lowbit(x))
{
c += cnt[x];
s += sum[x];
}
return {c, s};
}
pair<int, LL> query(int l, int r) const
{
auto [cr, sr] = prefix(r);
auto [cl, sl] = prefix(l - 1);
return {cr - cl, sr - sl};
}
void add(int x, LL num)
{
for (; x <= n; x += lowbit(x))
{
cnt[x]++;
sum[x] += num;
}
}
void sub(int x, LL num)
{
for (; x <= n; x += lowbit(x))
{
cnt[x]--;
sum[x] -= num;
}
}
};
struct Query
{
int x, y, b, id;
bool operator<(const Query &other) const { return b != other.b ? b < other.b : (b % 2 == 0 ? y < other.y : y > other.y); }
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<LL> a(n), b(n);
for (auto &x : a)
cin >> x;
for (auto &x : b)
cin >> x;
vector<LL> val = a;
val.insert(val.end(), b.begin(), b.end());
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
int len = val.size() + 1;
for (auto &x : a)
x = lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
for (auto &x : b)
x = lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
FenwickTree ta(len), tb(len);
int k;
cin >> k;
int block_size = max(1, (int)(n / sqrt(k)));
vector<Query> q(k);
for (int i = 0; i < k; i++)
{
auto &[x, y, b, id] = q[i];
cin >> x >> y;
x--, y--;
b = x / block_size;
id = i;
}
sort(q.begin(), q.end());
LL sum = 0, sum_a = 0, sum_b = 0;
int x = -1, y = -1;
auto inc_x = [&]() -> void
{
int rk = a[++x];
LL num = val[rk - 1];
auto [left_cnt, left_sum] = tb.query(1, rk);
sum += left_cnt * num - left_sum;
sum += (sum_b - left_sum) - num * (y + 1 - left_cnt);
ta.add(rk, num);
sum_a += num;
};
auto dec_x = [&]() -> void
{
int rk = a[x--];
LL num = val[rk - 1];
auto [left_cnt, left_sum] = tb.query(1, rk);
sum -= left_cnt * num - left_sum;
sum -= (sum_b - left_sum) - num * (y + 1 - left_cnt);
ta.sub(rk, num);
sum_a -= num;
};
auto inc_y = [&]() -> void
{
int rk = b[++y];
LL num = val[rk - 1];
auto [left_cnt, left_sum] = ta.query(1, rk);
sum += left_cnt * num - left_sum;
sum += (sum_a - left_sum) - num * (x + 1 - left_cnt);
tb.add(rk, num);
sum_b += num;
};
auto dec_y = [&]() -> void
{
int rk = b[y--];
LL num = val[rk - 1];
auto [left_cnt, left_sum] = ta.query(1, rk);
sum -= left_cnt * num - left_sum;
sum -= (sum_a - left_sum) - num * (x + 1 - left_cnt);
tb.sub(rk, num);
sum_b -= num;
};
vector<LL> ans(k);
for (auto [qx, qy, _, id] : q)
{
while (x < qx)
inc_x();
while (y < qy)
inc_y();
while (x > qx)
dec_x();
while (y > qy)
dec_y();
ans[id] = sum;
}
for (auto x : ans)
cout << x << '\n';
return 0;
}
创建日期: 2025-01-02