B. Base Conversion Master
题意：给你\(n, y, m\)，和\(n\)个数组，你选择一个进制\(s \in [2, m]\)，依次对\(n\)个数组进行转换操作，操作一个数组后把进制改为这个数组的结果。求最终\(s=y\)的区间。
显然大的进制得到的结果一定大于等于小的进制。
那么直接二分就行了，这个题确实很简单吧。。。榜太歪了。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, y, m;std::cin >> n >> y >> m;std::vector<std::vector<int>> a(n);for (int i = 0; i < n; ++ i) {int l;std::cin >> l;a[i].resize(l);for (int j = 0; j < l; ++ j) {std::cin >> a[i][j];}}const i64 inf = 1e9;auto check = [&](int p) -> i64 {for (auto & b : a) {i64 res = 0;for (auto & x : b) {if (x >= p) {return 0;}res = std::min(inf, res * p + x);}p = res;}return p;};int l = 1, r = m;while (l < r) {int mid = l + r >> 1;if (check(mid) >= y) {r = mid;} else {l = mid + 1;}}int L = l;l = 1, r = m;while (l < r) {int mid = l + r + 1 >> 1;if (check(mid) <= y) {l = mid;} else {r = mid - 1;}}if (check(L) != y) {std::cout << -1 << " " << -1 << "\n";return;}int R = l;std::cout << L << " " << R << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
C. Stack
题意：对一个排列进行单调栈操作，最终价值就是栈的大小的立方。求所以排列的价值和。
考虑已经放好前\([1, i - 1]\)个数，考虑第\(i\)个数怎么放，除了放在最后面的情况，插在最前面或者两个数中间都不影响单调栈的大小，也就是贡献\(i-1\)个\([1, i-1]\)排列的值。再考虑放在最后的情况，发现\([1, i - 1]\)每个排列的价值都要加一，我们记\([1, i - 1]\)这\((i-1)!\)个排列的价值依次为\(x_1, x_2, ..., x_{(i-1)!}\)，我们知道\((x+1)^3 = x^3+3x^2 + 3x + 1\)，也就是这些排列贡献的价值为\(x_1^3+3x_1^2 + 3x_1 + 1 + x_2^3+3x_2^2 + 3x_2 + 1...\)。发现既有三次幂又有偶数幂，无法直接计算。
考虑\(dp\)，记\(f[i][j]\)为前\(i\)个数\(\sum x^j\)的和。那么可得\(f[i][0] = (i - 1) \times f[i - 1][0] + f[i - 1][0]\)，也就是\(i \times f[i - 1][0]\)。同理得\(f[i][1] = i \times f[i - 1][1] + f[i][0]\)，\(f[i][2] = i \times f[i][2] + 2\times f[i][1] + f[i][0]\)，\(f[i][3] = i \times f[i-1][3] + 3\times f[i-1][2] + 3\times f[i-1][1] + f[i-1][0]\)。
那么预处理，初始化为\(f[0][0] = 1\)，然后\(f[n][3]\)就\(n\)的答案。
代码省略取模类。
点击查看代码
constexpr int P = 998244353;
using Z = MInt<P>;Z f[500010][4];void init(int n) {f[0][0] = 1;for (int i = 1; i <= n; ++ i) {f[i][0] = i * f[i - 1][0];f[i][1] = i * f[i - 1][1] + f[i - 1][0];f[i][2] = i * f[i - 1][2] + 2 * f[i - 1][1] + f[i - 1][0];f[i][3] = i * f[i - 1][3] + 3 * f[i - 1][2] + 3 * f[i - 1][1] + f[i - 1][0];}
}void solve() {int n; std::cin >> n;std::cout << f[n][3] << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;init(5e5);std::cin >> t;while (t -- ) {solve();}return 0;
}
G. Turn around
题意：一个只包含\(RL\)的数组，如果一个时刻有\(RL\)这个子串，两个这两个字符会换位置，一直操作到没有\(RL\)这个子串为止。求操作多少次，并且多组查询，每次会修改一个位置。
最后一定是所有\(L\)在左边，\(R\)在右边。
那么如果我们求得每个\(L\)走到对应位置的时间，取最大值就能得到答案。
如果求第\(j\)个\(L\)到\(j\)的时间，我们需要记一个前缀\(cnt\)，表示前缀\(R\)的数量，那么如果第\(j\)个\(L\)在\(i\)的位置，则这个\(L\)至少需要\(cnt_i\)的时间，而它可能被前面的\(L\)卡住，那么到达时间需要和前面的位置的时间加一取最大。这样可以求出不修改的答案，但如果修改，发现无法更新，因为前缀\(R\)的数量改变，需要一个一个改后面的值。
记\(f_i\)为在\(i\)看来\([i, n]\)到\(0\)的最小时间，也就是所有位置复位后都整体移到\(1\)的左边。那么对于一个\(i\)，如果不管前面的\(L\)的话需要\(i\)的时间到\(0\)，如果它后面多一个\(L\)，那么对\(i\)来说\([i, n]\)这个后缀的时间需要加\(2\)。因为后面这个\(L\)要么等前面的一步，然后再走，要么与前面的相差大于等于\(2\)，那么到\(0\)的时间自然也多\(2\)。于是我们给每个\(s_i = L\)的位置给\([1, i - 1]\)都加\(2\)。就可以求得每个位置计算出的最小时间，这些时间取\(max\)后减去\(L\)的数量就是答案。因为我们计算的到是\(0\)的时间，而其实从左到右第\(j\)个\(L\)只需要到\(j\)这个位置。
这样之所以能求得正确答案，因为最大的\(f_i\)肯定能得到最后的\(L\)到达\(0\)的时间，且最后的\(L\)肯定比前面的要慢，所以直接用最大值减\(L\)个数就是最后一个\(L\)复位的答案。
那么修改的时候只需要讨论其对前缀的贡献的更改就行了。不过还要记录后缀\(L\)的个数，这样一个\(R\)变成\(L\)的时候才能知道自己需要加多少个\(2\)，然后需要记录最左边的\(R\)的位置，前面已经复位的\(L\)不用管，查询最左边\(R\)的右边的\(L\)的值就行。
于是用线段树维护区间最大值，树状数组维护区间\(L\)的个数。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;template <class Info, class Tag>
struct LazySegmentTree {struct Node {int l, r;Info info;Tag tag;};std::vector<Node> tr;LazySegmentTree() {}LazySegmentTree(int n) {init(n);}void init(int n) {tr.assign(n << 2, {});build(0, n - 1);}void pushdown(Node & u, const Tag & tag) {u.info = u.info + tag;u.tag = u.tag + tag;}void pushdown(int u) {if (tr[u].tag.exist()) {pushdown(tr[u << 1], tr[u].tag);pushdown(tr[u << 1 | 1], tr[u].tag);tr[u].tag.clear();}}void pushup(int u) {tr[u].info = tr[u << 1].info + tr[u << 1 | 1].info;}void build(int l, int r, int u = 1) {tr[u] = {l, r, {}};if (l == r) {tr[u].info.max = -1e9;return;}int mid = l + r >> 1;build(l, mid, u << 1); build(mid + 1, r, u << 1 | 1);pushup(u);}void modify(int l, int r, const Tag & tag, int u = 1) {if (l <= tr[u].l && tr[u].r <= r) {pushdown(tr[u], tag);return;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (l <= mid) {modify(l, r, tag, u << 1);}if (r > mid) {modify(l, r, tag, u << 1 | 1);}pushup(u);}void modify(int p, int v) {int u = 1;while (tr[u].l != tr[u].r) {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (p <= mid) {u = u << 1;} else {u = u << 1 | 1;}}tr[u].info.max = v;u >>= 1;while (u) {pushup(u);u >>= 1;}}Info query(int l, int r, int u = 1) {if (l <= tr[u].l && tr[u].r <= r) {return tr[u].info;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (r <= mid) {return query(l, r, u << 1);} else if (l > mid) {return query(l, r, u << 1 | 1);}return query(l, r, u << 1) + query(l, r, u << 1 | 1);}
};struct Info {int max;
};struct Tag {int add;bool exist() {return add != 0;}void clear() {add = 0;}
};Info operator + (const Info & a, const Info & b) {Info res{};res.max = std::max(a.max, b.max);return res;
}Info operator + (const Info & a, const Tag & b) {Info res{};res.max = a.max + b.add;return res;
}Tag operator + (const Tag & a, const Tag & b) {Tag res{};res.add = a.add + b.add;return res;
}template <class T>
struct Fenwick {int n;std::vector<T> tr;Fenwick(int _n) {init(_n);}void init(int _n) {n = _n;tr.assign(_n + 1, T{});}void add(int x, const T &v) {for (int i = x; i <= n; i += i & -i) {tr[i] = tr[i] + v;}}T query(int x) {T res{};for (int i = x; i; i -= i & -i) {res = res + tr[i];}return res;}T sum(int l, int r) {return query(r) - query(l - 1);}
};void solve() {int n, q;std::cin >> n >> q;std::string s;std::cin >> s;const int inf = 1e9;LazySegmentTree<Info, Tag> tr(n + 1);std::set<int> p;int cnt = 0;Fenwick<int> tr1(n + 1);for (int i = 0; i < n; ++ i) {if (s[i] == 'L') {tr.modify(i, i + 1);tr1.add(i + 1, 1);if (i) {tr.modify(0, i - 1, Tag{2});}++ cnt;} else {tr.modify(i, -inf);p.insert(i);}}while (q -- ) {int x;std::cin >> x;-- x;if (s[x] == 'L') {tr.modify(x, -inf);if (x) {tr.modify(0, x - 1, Tag{-2});}-- cnt;p.insert(x);tr1.add(x + 1, -1);s[x] = 'R';} else {tr.modify(x, x + 1 + tr1.sum(x + 1, n) * 2);if (x) {tr.modify(0, x - 1, Tag{2});}++ cnt;p.erase(x);tr1.add(x + 1, 1);s[x] = 'L';}if (p.empty()) {std::cout << 0 << "\n";} else {std::cout << std::max(0, tr.query(*p.begin(), n - 1).max - cnt) << "\n";}}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;// std::cin >> t;while (t -- ) {solve();}return 0;
}
K. Maximum GCD
题意：一个数组，可以进行一次操作，选择一个区间和一个数\(x\)，给所有数加上\(x\)。求数组的\(gcd\)最大是多少。
如果不操作整个数组的话，显然\(gcd\)一定是\(a_1, a_n\)的因子。如果操作整个数组，记最终\(gcd\)为\(d\)，那么因为\(a_i + x \equiv a_j + x \pmod{d}\)，则\(a_i - a_j \equiv 0 \pmod{d}\)，这意味这\(d\)是一对\(a_i - a_j\)的因子。那么把这几个数的因子搞出来跑一遍看可不可行。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<int> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];}if (std::ranges::count(a, a[0]) == n) {std::cout << 0 << "\n";return;}std::vector<int> b;auto get = [&](int x) -> void {for (i64 i = 1; i * i <= x; ++ i) {if (x % i == 0) {b.push_back(i);if (x % (x / i) == 0) {b.push_back(x / i);}}}};get(a[0]);get(a[n - 1]);auto c = a;std::ranges::sort(c);int min = 2e5;for (int i = 0; i + 1 < n; ++ i) {if (c[i] != c[i + 1]) {min = std::min(min, c[i + 1] - c[i]);}}get(min);std::vector<int> pre(n + 1), suf(n + 2);for (int i = 0; i < n; ++ i) {pre[i + 1] = std::gcd(pre[i], a[i]);}for (int i = n - 1; i >= 0; -- i) {suf[i + 1] = std::gcd(suf[i + 2], a[i]);}std::ranges::sort(b);b.erase(std::unique(b.begin(), b.end()), b.end());std::ranges::reverse(b);int ans = pre[n];for (auto & d : b) {int l = 0, r = n;while (l < r) {int mid = l + r + 1 >> 1;if (pre[mid] % d) {r = mid - 1;} else {l = mid;}}int L = l;l = 1, r = n + 1;while (l < r) {int mid = l + r >> 1;if (suf[mid] % d) {l = mid + 1;} else {r = mid;}} int R = l;std::set<int> s;for (int i = L + 1; i < R; ++ i) {s.insert(a[i - 1] % d);}if (s.size() == 1) {ans = d;break;}}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
L. Minimum Parenthesis String
题意：构造一个括号序列，有\(m\)个要求：\([l_i, r_i]\)内至少一个左括号。要求字典序最小。
先构造字典序最小的括号序列，\(n\)个(加\(n\)个)。然后把要求按左端点从大到小排序，如果\([l_i, r_i]\)内没有左括号，则拿前半部分最后的左括号和\(l_i\)换位置。最后判断是不是合法的。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, m;std::cin >> n >> m;std::vector<std::pair<int, int>> a(m);for (int i = 0; i < m; ++ i) {std::cin >> a[i].first >> a[i].second;}std::string s = std::string(n, '(') + std::string(n, ')');std::ranges::sort(a, std::greater<>());int last = 2 * n;int p = n - 1;for (auto & [l, r] : a) {-- l, -- r;if (l <= p) {break;}if (r < last) {if (p < 0) {std::cout << -1 << "\n";return;}std::swap(s[p], s[l]);last = l;-- p;}}int sum = 0;for (auto & c : s) {sum += c == '(' ? 1 : -1;if (sum < 0) {std::cout << -1 << "\n";return;}}std::cout << s << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}