昨晚打了几道题发现自己原来没有维护树中两点之间边权最值的模板，虽然不难，今天还是整理一个模板出来吧。
思想跟 LCA 差不多，用最大值为例， $mx[u][i]$ 表示 $u$ 和从 $u$ 开始，向根方向走 $2^i$ 步走到的点之间的所有边的最大值。最小值相反即可。
template <typename A, typename B>
class Lca {
public:
int n, root, lg;
vector<A> dist;
vector<int> depth;
vector<vector<int>> fa;
vector<vector<B>> mx;
vector<vector<B>> mn;
// set default inf
const B INF = ...;
//const B INF = numeric_limits<B>::max() / 2;
Lca(const vector<vector<pair<int, B>>> &g, int root) {
n = static_cast<int>(g.size());
lg = 32 - __builtin_clz(n);
fa.resize(n);
mx.resize(n);
mn.resize(n);
dist.resize(n);
depth.resize(n);
for (int i = 0; i < n; i++) {
fa[i].resize(lg);
mx[i].resize(lg);
mn[i].resize(lg);
}
depth[root] = 0;
fa[root][0] = root;
mx[root][0] = -INF;
mn[root][0] = INF;
vector<int> q;
q.push_back(root);
for (int qq = 0; qq < (int) q.size(); qq++) {
int u = q[qq];
for (int i = 1; i < lg; i++) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
mx[u][i] = max(mx[u][i - 1], mx[fa[u][i - 1]][i - 1]);
mn[u][i] = min(mn[u][i - 1], mn[fa[u][i - 1]][i - 1]);
}
for (auto &[v, w] : g[u]) {
if (v == fa[u][0]) {
continue;
}
depth[v] = depth[u] + 1;
dist[v] = dist[u] + w;
fa[v][0] = u;
mx[v][0] = w;
mn[v][0] = w;
q.push_back(v);
}
}
}
int getLca(int a, int b) const {
assert(a >= 0 && a < n && b >= 0 && b < n);
if (depth[a] < depth[b]) {
swap(a, b);
}
for (int k = lg - 1; k >= 0; k--) {
if (depth[fa[a][k]] >= depth[b]) {
a = fa[a][k];
}
}
if (a == b) {
return a;
}
for (int k = lg - 1; k >= 0; k--) {
if (fa[a][k] != fa[b][k]) {
a = fa[a][k];
b = fa[b][k];
}
}
return fa[a][0];
}
A getDist(int a, int b) const {
assert(a >= 0 && a < n && b >= 0 && b < n);
int anc = getLca(a, b);
return dist[a] + dist[b] - 2 * dist[anc];
}
B getMax(int a, int b) const {
assert(a >= 0 && a < n && b >= 0 && b < n);
int anc = getLca(a, b);
B res = -INF;
for (int bit = 0; bit < lg; bit++) {
if (((depth[a] - depth[anc]) >> bit) & 1) {
res = max(res, mx[a][bit]);
a = fa[a][bit];
}
if (((depth[b] - depth[anc]) >> bit) & 1) {
res = max(res, mx[b][bit]);
b = fa[b][bit];
}
}
return res;
}
B getMin(int a, int b) const {
assert(a >= 0 && a < n && b >= 0 && b < n);
int anc = getLca(a, b);
B res = INF;
for (int bit = 0; bit < lg; bit++) {
if (((depth[a] - depth[anc]) >> bit) & 1) {
res = min(res, mn[a][bit]);
a = fa[a][bit];
}
if (((depth[b] - depth[anc]) >> bit) & 1) {
res = min(res, mn[b][bit]);
b = fa[b][bit];
}
}
return res;
}
};
E. Masha-forgetful
题目链接： E. Masha-forgetful
题意：
给定一个字符串 $s$ 和若干模板串，问是否能够从模板串中选出若干段子串（可以重复使用或重叠），拼成 $s$ ，给出方案。
解题思路：
只需要看长度为 $2,3$ 的子串即可，在模板串中存下所有长度为 $2,3$ 子串是来自哪个模板串的哪个位置，然后 DP 找方案即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
map<string, tuple<int, int, int>> mp;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int len = 2; len <= 3; len++) {
for (int j = 0; j < m; j++) {
if (j + len <= m) {
mp[s.substr(j, len)] = make_tuple(j, j + len - 1, i);
}
}
}
}
string s;
cin >> s;
vector<bool> f(m + 1);
f[0] = true;
vector<int> g(m + 1, -1);
for (int i = 0; i < m; i++) {
if (f[i]) {
for (int len = 2; len <= 3; len++) {
if (i + len <= m) {
string t = s.substr(i, len);
if (mp.count(t)) {
f[i + len] = true;
g[i + len] = i;
}
}
}
}
}
if (!f[m]) {
cout << "-1\n";
continue;
}
vector<tuple<int, int, int>> res;
int i = m;
while (i > 0) {
int j = g[i];
string t = s.substr(j, i - j);
res.emplace_back(mp[t]);
i = j;
}
cout << (int) res.size() << '\n';
reverse(res.begin(), res.end());
for (auto &[l, r, i] : res) {
cout << l + 1 << ' ' << r + 1 << ' ' << i + 1 << '\n';
}
}
return 0;
}
F. Interacdive Problem
题目链接： F. Interacdive Problem
题意：
交互题，猜一个数 $x(1\leq x<n)$ ，每次询问给定一个 $c(1\leq c<n)$ ，此时会执行 $x=x+c$ ，并返回 $\lfloor \frac{x}{n} \rfloor$ ，最多询问 $10$ 次。
解题思路：
数据范围很敏感，容易想到二分，二分的是 $x$ 除以 $n$ 的余数 $r$ ，因为得到了 $v=\lfloor \frac{x}{n} \rfloor$ ，那么 $x=v\times n+r$ 。
一开始 $v=0$ ，二分范围是 $[0,n-1]$ ，每次询问 $n-mid$ ，如果返回值比 $v$ 大，说明余数是在较大的部分，执行 $l=mid$ ，否则是在较小的部分，执行 $r=mid-1$ ，注意每次都需要用 $n-mid$ 更新 $l,r$ 的范围。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
int l = 0, r = n - 1;
int v = 0;
while (l < r) {
int mid = (l + r + 1) >> 1;
cout << "+ " << n - mid << endl;
int y;
cin >> y;
if (y > v) {
l = mid;
v = y;
} else {
r = mid - 1;
}
// 注意
l = (l + n - mid + n) % n;
r = (r + n - mid + n) % n;
}
cout << "! " << v * n + r << endl;
return 0;
}
G. MinOr Tree
题目链接： G. MinOr Tree
题意：
求最小生成树，但最小并不是边权和最小，而是边权或操作的最小值。
解题思路：
从高位到低位枚举，对每一位，在可用的边中，只使用不含这一位的边，判断是否能够将所有点都连通，如果可以，那么说明含有这一位的边是可以舍弃的，那就舍弃掉；如果不能，说明一定要使用含有这一位的边。
代码如下：
#include <bits/stdc++.h>
using namespace std;
class Dsu {
public:
vector<int> p, sz;
int n;
Dsu(int _n) {
n = _n + 1;
p.resize(n);
sz.assign(n, 1);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
sz[y] += sz[x];
return true;
}
return false;
}
inline int getSize(int x) {
return sz[get(x)];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<int> a(m);
vector<int> b(m);
vector<int> c(m);
for (int i = 0; i < m; i++) {
cin >> a[i] >> b[i] >> c[i];
--a[i];
--b[i];
}
int res = 0;
vector<bool> alive(m, true);
for (int bit = 30; bit >= 0; bit--) {
Dsu d(n);
for (int i = 0; i < m; i++) {
if (alive[i] && ((c[i] >> bit) & 1) == 0) {
d.unite(a[i], b[i]);
}
}
if (d.getSize(0) == n) {
for (int i = 0; i < m; i++) {
if ((c[i] >> bit) & 1) {
alive[i] = false;
}
}
} else {
res |= (1 << bit);
}
}
cout << res << '\n';
}
return 0;
}
F - Reordering
题目链接： F - Reordering
题意：
给定一个字符串，选择一些字符，可以任意调换顺序，形成一个新串，问可以形成多少个不同的串。
解题思路：
因为可以打乱顺序，所以并不需要关心顺序，只需要看用了哪些字符即可。
定义 $f[c][i]$ 为只用前 $c$ 种字符，当前串长度为 $i$ 的集合，属性是个数，那么现在要往这些串加入 $j$ 个第 $c+1$ 个字符，形成的新串长度为 $i+j$ ，能够生成 $f[c][i]\times C_{i+j}^j$ 个新串，加入到 $f[c+1][i+j]$ 即可。
最后答案是 $f[26][i]\(1\leq i\leq n)$ 的和。
代码如下：
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 998244353;
// assume -mod <= x < 2 * mod
int norm(int x) {
if (x < 0) {
x += mod;
}
if (x >= mod) {
x -= mod;
}
return x;
}
template<typename T, typename U>
T qp(const T &a, const U &b) {
assert(b >= 0);
T res = 1, x = a;
U p = b;
for (; p; p /= 2, x *= x) {
if (p % 2) {
res *= x;
}
}
return res;
}
class Mint {
public:
int x;
Mint(int x = 0) : x(norm(x)) {}
int val() const {
return x;
}
Mint operator-() const {
return Mint(norm(mod - x));
}
Mint inv() const {
assert(x != 0);
return qp(*this, mod - 2);
}
Mint &operator*=(const Mint &rhs) {
x = (int) ((long long) x * rhs.x % mod);
return *this;
}
Mint &operator+=(const Mint &rhs) {
x = norm(x + rhs.x);
return *this;
}
Mint &operator-=(const Mint &rhs) {
x = norm(x - rhs.x);
return *this;
}
Mint &operator/=(const Mint &rhs) {
return *this *= rhs.inv();
}
friend Mint operator*(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res *= rhs;
return res;
}
friend Mint operator+(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res += rhs;
return res;
}
friend Mint operator-(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res -= rhs;
return res;
}
friend Mint operator/(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res /= rhs;
return res;
}
};
vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);
Mint C(int n, int k) {
if (k < 0 || k > n) {
return 0;
}
while ((int) fact.size() < n + 1) {
fact.push_back(fact.back() * (int) fact.size());
inv_fact.push_back(1 / fact.back());
}
return fact[n] * inv_fact[k] * inv_fact[n - k];
}
Mint Fact(int n) {
assert(n >= 0);
while ((int) fact.size() < n + 1) {
fact.push_back(fact.back() * (int) fact.size());
inv_fact.push_back(1 / fact.back());
}
return fact[n];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
string s;
cin >> s;
int n = (int) s.size();
const int A = 26;
vector<int> cnt(A);
for (int i = 0; i < n; i++) {
cnt[s[i] - 'a'] += 1;
}
vector<vector<Mint>> f(A + 1, vector<Mint>(n + 1));
f[0][0] = 1;
C(n + 1, n + 1);
for (int c = 0; c < A; c++) {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= cnt[c]; j++) {
if (j + i <= n) {
f[c + 1][i + j] += f[c][i] * C(i + j, j);
}
}
}
}
Mint res = 0;
for (int i = 1; i <= n; i++) {
res += f[A][i];
}
cout << res.val() << '\n';
return 0;
}
