Greatest of the Greatest Common Divisors
题意
给定一个长度为 $n$ 的序列 $a_i$ 和 $q$ 个询问，每个询问求出 $[l,r]$ 内所有数对的最大公约数中的最大值。
$n,q\leq10^5$ 。
思路
经典正难则反：不好直接求 GCD 就考虑约数的贡献。
然后类似扫描线的思想，离线后把时间作为一个维度处理区间信息，这里用树状数组维护区间内的最大约数。
代码
const int N = 1e5 + 10, M = 1e5;
inline ll read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
namespace Main {
int n, m;
vector <int> d[N];
int a[N];
struct Query {
int l, r, id, ans;
}q[N];
int f[N];
int t[N];
void mxe (int &x, int y) { if (x < y) x = y; }
void modify (int x, int val) { for (; x; x -= x & -x) mxe(t[x], val); }
int query (int x) { int ans = 0; for (; x <= n; x += x & -x) mxe(ans, t[x]); return ans; }
int main () {
for (int k = 1; k <= M; ++k)
for (int i = k; i <= M; i += k) d[i].emplace_back(k);
n = read();
for (int i = 1; i <= n; ++i) a[i] = read();
m = read();
for (int i = 1; i <= m; ++i)
q[i].l = read(), q[i].r = read(), q[i].id = i;
sort(q + 1, q + 1 + m, [](Query a, Query b){return a.r < b.r;});
int lst = 0, cur = 1;
for (int i = 1; i <= n; ++i) {
for (; cur <= m && q[lst + 1].r == q[cur].r && q[cur].r <= i; cur++);
for (int j : d[a[i]]) {
if (f[j]) modify(f[j], j);
f[j] = i;
}
for (++lst; lst < cur; ++lst)
q[lst].ans = query(q[lst].l);
lst = cur - 1;
}
sort(q + 1, q + 1 + m, [](Query a, Query b){return a.id < b.id;});
for (int i = 1; i <= m; ++i) printf ("%d\n", q[i].ans);
return 0;
}
}
int main () {
string str = "";
// freopen((str + ".in").c_str(), "r", stdin);
// freopen((str + ".out").c_str(), "w", stdout);
Main::main();
return 0;
}
EOF
[ICPC 2024 Yokohama R] Tree Generators
题意
规定表达式生成树的操作。根据以下过程，从一个表达式生成一棵树。
- 表达式 $\texttt{1}$ 生成一棵仅包含一个标号为 $1$ 的节点的树。
- 对于两个表达式 $E_1$ 和 $E_2$ ，表达式 $(E_1E_2)$ 按如下方式生成一棵树：
- 从 $E_1$ 生成一棵拥有 $n_1$ 个节点的树 $T_1$ ，并从 $E_2$ 生成一棵拥有 $n_2$ 个节点的树 $T_2$ 。
- 将 $T_2$ 中所有节点的标号都加上 $n_1$ 。
- 随机地各从 $T_1$ 和 $T_2$ 中选取一个节点，连接它们形成一条边，从而构造出一棵标号为 $1$ 到 $(n_1 + n_2)$ 的树，该树即为 $(E_1E_2)$ 生成的树。
现在给定两条表达式，求它们都能生成的树个数。答案对 $998244353$ 取模。
$|S|\leq 7\times 10^5$ 。
思路
两棵树要完全相同必然需要一棵树的每个边另一边也有可能连上，因此一棵树的 $\texttt{(11)}$ 限制了另一棵树相同位置的连边。
比如两个表达式 $\texttt{((1(11))1)}$ 和 $\texttt{((11)(11))}$ ，前者的 $\texttt{(11)}$ 就限定了 2 和 3 连在一起，对生成的树来说限定了第一棵树中两棵子树 $\{2\}$ 和 $\{3\}$ 连接方式、第二棵树两棵子树 $\{12\}$ 和 $\{34\}$ 的连接方式。
考虑在此基础上拓展。 $(E_1E_2)$ 意味着两棵树之间必须有条边，有 $|E_1||E_2|$ 种可能。需要考虑这一个表达式是怎么限制另一棵树连边的。假设 $E_1$ 的范围是 $[l_1,i]$ ， $E_2$ 的范围是 $[i+1,r_1]$ ，则 $(E_1E_2)$ 只能限制的另一条表达式 $(E_3E_4)$ 满足 $E_3$ 的范围是 $[l_2,i]$ ， $E_4$ 的范围是 $[i+1,r_2]$ 。换句话说，两个分割位置相同的表达式互相影响，它们生成的边对应，有 $(i-\max(l_1,l_2)+1)(\min(r_1,r_2)-i)$ 种可能。
那么预处理出 $l_1,l_2,r_1,r_2$ 即可。
代码
const int N = 7e5 + 5;
const int mod = 998244353;
inline ll read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
namespace Main {
int n, m, len;
char s[N];
int l[N], r[N];
int st[N], top;
int ch[N][2], leaf[N];
void mxe (int &x, int y) { if (x < y) x = y; }
void mne (int &x, int y) { if (x > y) x = y; }
pair<int, int> dfs (int p) {
if (leaf[p]) return make_pair(leaf[p], leaf[p]);
auto nd1 = dfs(ch[p][0]), nd2 = dfs(ch[p][1]);
mxe(l[nd1.second], nd1.first);
mne(r[nd1.second], nd2.second);
return make_pair(nd1.first, nd2.second);
}
void solve (bool op = 1) {
scanf ("%s", s + 1);
len = strlen(s + 1);
n = m = top = 0;
memset(ch, 0, sizeof ch);
memset(leaf, 0, sizeof leaf);
for (int i = 1; i <= len; ++i) {
if (s[i] == '(') {
st[++top] = ++n;
ch[st[top - 1]][ch[st[top - 1]][0] != 0] = n;
}
else if (s[i] == ')') st[top--] = 0;
else leaf[ch[st[top]][ch[st[top]][0] != 0] = ++n] = ++m;
}
if (op)
for (int i = 1; i < m; ++i) l[i] = 1, r[i] = m;
dfs(1);
}
int main () {
solve();
solve(0);
ll ans = 1;
for (int i = 1; i < m; ++i)
ans = ans * (i - l[i] + 1) % mod * (r[i] - i) % mod;
printf ("%lld\n", ans);
return 0;
}
}
int main () {
string str = "";
// freopen((str + ".in").c_str(), "r", stdin);
// freopen((str + ".out").c_str(), "w", stdout);
Main::main();
return 0;
}
EOF
题意
给定一张 $n$ 个点， $m$ 条边的无向图，有点权 $p_i$ ，边权 $q_i$ 。生成树的权值为
$$\sum_{e\in E}q_e\sum_{u\in\text{inaccessible}(e)}p_u $$
其中 $\text{inaccessible}(e)$ 表示从生成树中删除 $e$ 后，从 $1$ 出发不能到达的结点集合。
求可能的最小权值。
思路
发现从边出发考虑生成树会有瓶颈：选的边并不确定、不知道可以到达边的哪头、点集受树的形态制约。由于每个点都要选（都确定），我们不妨考虑先从点考虑，把式子转化为
$$\sum_{u\in V}p_u\sum_{e\in \text{path}(1\rightarrow u)}q_e $$
豁然开朗，里面的和式正好是从 $1$ 到 $u$ 的距离，显然最短路是最优的。
代码
const int N = 1e5 + 5;
inline ll read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
namespace Main {
int n, m;
int p[N];
ll dis[N];
typedef pair<ll, int> P;
vector<P> e[N];
priority_queue <P, vector<P>, greater<P> > q;
void dijkstra() {
memset(dis, 0x3f, sizeof dis); dis[1] = 0;
q.emplace(0ll, 1);
for (int u; !q.empty(); ) {
P x = q.top(); q.pop();
if (dis[u = x.second] < x.first) continue;
for (auto [w, v] : e[u])
if (dis[u] + w <= dis[v])
q.emplace(dis[v] = dis[u] + w, v);
}
}
int main () {
n = read(), m = read();
for (int i = 1; i <= n; ++i) p[i] = read();
for (int i = 1; i <= m; ++i) {
int u = read(), v = read(); ll w = read();
e[u].emplace_back(w, v);
e[v].emplace_back(w, u);
}
dijkstra();
ll ans = 0;
for (int i = 1; i <= n; i++) ans += dis[i] * p[i];
printf ("%lld\n", ans);
return 0;
}
}
int main () {
string str = "";
// freopen((str + ".in").c_str(), "r", stdin);
// freopen((str + ".out").c_str(), "w", stdout);
Main::main();
return 0;
}
EOF
题意
给定一种构建树的方式，给出 $n-1$ 个操作，每次操作给出 $u,v$ ，只能从 $u$ 所在的连通块内随机选一个点连向 $v$ 所在连通块内随机的点
EOF
题意
给定一个由 $n$ 个点组成的凸包， $q$ 次询问，每次询问给出一个圆，求出从凸包到圆各处最小期望长度。
$n,q\leq5000$ 。
题解
如果圆心在凸包里直接从圆心出发，否则看圆心到凸包的距离。
代码
const int N = 5010;
const ld eps = 1e-6;
inline ll read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
namespace Main {
int n, q;
int sgn(ld x) {
if (x < -eps) return -1;
if (x > eps) return 1;
return 0;
}
typedef complex<ld> vec;
ld dot(vec a, vec b) { return real(a) * real(b) + imag(a) * imag(b); }
ld cross(vec a, vec b) { return real(a) * imag(b) - imag(a) * real(b); }
vec a[N];
bool inhull(vec p) {
for (int i = 0; i < n; ++i)
if (sgn(cross(a[i] - p, a[(i + 1) % n] - p)) <= 0) return 0;
return 1;
}
ld dis(vec p, vec a, vec b) {
if (abs(b - a) > eps && sgn(dot(p - a, b - a)) >= 0 && sgn(dot(p - b, a - b)) >= 0)
return fabs(cross(p - a, b - a)) / abs(b - a);
return min(abs(p - a), abs(p - b));
}
int main () {
n = read(), q = read();
for (int i = 0; i < n; ++i) {
int x = read(), y = read();
a[i] = vec(x, y);
}
while (q--) {
int x = read(), y = read(); vec A = vec(x, y);
x = read(), y = read(); vec B = vec(x, y);
vec O = (A + B) / (ld)2.0;
ld r = abs(O - A), d = 1e18;
if (inhull(O)) d = 0;
else {
for (int i = 0; i < n; ++i)
d = min(d, dis(O, a[i], a[(i + 1) % n]));
}
printf ("%.9Lf\n", ((long double) r * r / 2 + (long double) d * d));
}
return 0;
}
}
int main () {
string str = "";
// freopen((str + ".in").c_str(), "r", stdin);
// freopen((str + ".out").c_str(), "w", stdout);
Main::main();
return 0;
}
EOF