20231015题解
T3 peace
典型树上问题。
随着运送的权值变小,可走的边一定是越来越多的。所以可以离线,按权值从大到小加边和询问。
如果加边使用冰茶姬维护联通性,则可以这么求答案:在 \([u, \operatorname{lca}(u, v)]\) 这条链上二分,找到最深的与 \(u\) 不连通的点;如果没有不连通,则在 \([\operatorname{lca}(u, v), v]\) 上二分,找到最浅的与 \(\operatorname{lca}{u, v}\) 不连通的点。如果都连通则答案就是 \(v\),否则是不连通的前一个点。时间复杂度 \(O(m \log n \alpha(n))\)。
但是我比较无脑,直接用树剖维护了一条链上最深的不可行边和最浅的不可行边,时间复杂度 \(O(m \log^2 n)\)。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
using namespace std;
const int maxn = 1e5 + 5;
struct edge { int u, v, w, id; edge() {} edge(int u, int v, int w, int id): u(u), v(v), w(w), id(id) {} };
vector<edge> e;
vector<int> tree[maxn];
int fa[maxn], son[maxn], siz[maxn], dep[maxn];
void dfs1(int u) {
siz[u] = 1;
for (int v : tree[u]) {
if (v == fa[u]) continue;
fa[v] = u, dep[v] = dep[u] + 1; dfs1(v); siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
int dfn[maxn], dfn_cnt, top[maxn], in_dfn[maxn];
void dfs2(int u) {
in_dfn[dfn[u] = ++dfn_cnt] = u;
if (son[u]) top[son[u]] = top[u], dfs2(son[u]);
for (int v : tree[u]) {
if (v == fa[u] || v == son[u]) continue;
top[v] = v; dfs2(v);
}
}
struct node;
typedef node* pos;
struct node { pos ls, rs; int l, r, lv, rv; node() {l = r = 0; lv = INT_MAX, rv = 0; ls = rs = this; }};
node buf[maxn << 1], *buf_pos = buf, *root = buf;
node operator & (const node &a, const node &b) { node res; res.lv = min(a.lv, b.lv); res.rv = max(a.rv, b.rv); return res; }
void push_up(pos p) { p -> lv = min(p -> ls -> lv, p -> rs -> lv); p -> rv = max(p -> ls -> rv, p -> rs -> rv); }
void update(pos p, int id) { (p -> l == p -> r) ? (p -> lv = INT_MAX, p -> rv = 0, void()) : (((id <= p -> ls -> r) ? update(p -> ls, id) : update(p -> rs, id)), push_up(p)); }
node ask(pos p, int l, int r) { return (p -> r < l || r < p -> l) ? *buf : ((l <= p -> l && p -> r <= r) ? *p : (ask(p -> ls, l, r) & ask(p -> rs, l, r))); }
pos new_node(int l, int r) { pos p = ++buf_pos; p -> ls = p -> rs = buf, p -> lv = p -> l = l, p -> rv = p -> r = r; return p; }
void build(pos p) {
if (p -> l == p -> r) return;
int mid = (p -> l + p -> r) >> 1;
p -> ls = new_node(p -> l, mid), build(p -> ls);
p -> rs = new_node(mid + 1, p -> r), build(p -> rs);
push_up(p);
}
int ask_tree(int u, int v) {
node ru, rv; int tv = v;
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) ru = (ru & ask(root, dfn[top[u]], dfn[u])), u = fa[top[u]];
else rv = (rv & ask(root, dfn[top[v]], dfn[v])), v = fa[top[v]];
}
if (dep[u] > dep[v]) ru = (ru & ask(root, dfn[v] + 1, dfn[u]));
else if (dep[u] < dep[v]) rv = (rv & ask(root, dfn[u] + 1, dfn[v]));
if (!ru.rv) {
if (!rv.rv) return tv;
else return fa[in_dfn[rv.lv]];
} else return in_dfn[ru.rv];
}
int n, m;
int ans[maxn];
int main() {
//freopen("peace.in", "r", stdin), freopen("peace.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i < n; i++) {
int u, v, w; scanf("%d %d %d", &u, &v, &w);
e.emplace_back(u, v, w, 0);
tree[u].emplace_back(v), tree[v].emplace_back(u);
}
fa[1] = 1, dep[1] = 1, dfs1(1), top[1] = 1, dfs2(1);
root = new_node(1, n); build(root);
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d %d %d", &u, &v, &w);
e.emplace_back(u, v, w, i);
}
sort(e.begin(), e.end(), [&](edge &a, edge &b) -> bool { return a.w != b.w ? a.w > b.w : a.id < b.id; });
for (auto x : e) {
if (!x.id) update(root, dfn[dep[x.u] > dep[x.v] ? x.u : x.v]);
else ans[x.id] = ask_tree(x.u, x.v);
}
for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
return 0;
}
T4 fantasy
\(n\) 个城市最终会被分成大小不一的环,既然在任意一个环里都能够回到开始,每个环的大小一定是 \(k\) 的因数。显然,选取 \(k\) 的质因数一定不会更劣,所以就是问能不能将 \(n\) 拆分成几个 \(k\) 的质因数之和。
既然不同的 \(k\) 至多有 50 个,考虑在 \(k\) 一定时处理多个 \(n\)。假设 \(k\) 一共有 \(c\) 个本质不同的质因子,从小到大记为 \(p_0,p_1,p_2,...,p_{c-1}\)。考虑分讨 \(c\) 的大小:
\(c=1\):此时直接特判即可,答案为 \([c \mid n]\)
\(c=2\):此时问题为 \(p_0x+p_1y=n\) 有无非负整数解,使用扩展欧几里得算法求解即可,注意中间过程可能会爆
__int128
,要记得在乘 \(n\) 之前先变成最小非负整数解。\(c \ge 3\):此时最小的 \(p_0 \le 10^5\)。如果 \(x\) 可以被拆成几个数的和,则 \(x+kp_0\) 一定也可以。所以,我们考虑对于 \(\forall a \in [0,p_0-1]\cap\mathbb{N}\),求出最小的 \(x, \text{ s.t. } x \equiv a \pmod{p_0}\)。接下来只要判断 \(n\) 是否大于 \(x\) 即可。
怎么求这个最小值呢?将 \([0,p_0-1]\cap\mathbb{N}\) 中的每一个数建一个点,然后在 \(u,(u+p_i)\bmod p_0\) 之间连一条边权是 \(p_i\) 的边。这样,\(a=u\) 时的最小值,就是从 0 到 \(u\) 的最短路长度。
时间复杂度 \(O(n_k(\sqrt{k}+p_0 \log^2k)+T\log k)\)。(\(n_k\) 是不同的 \(k\) 的个数)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
using namespace std;
const int maxt = 1e4 + 5, maxv = 3.3e7 + 5, maxp = 1e5 + 5;
const long long inf = 0x3f3f3f3f3f3f3f3f;
long long ex_gcd(long long a, long long b, __int128 &x, __int128 &y) {
if (b == 0) { x = 1, y = 0; return a; }
long long d = ex_gcd(b,a % b,y,x); y -= a / b * x;
return d;
}
namespace io {...};
using namespace io;
int t, tid;
map<long long, int> mp;
vector<int> ask[55];
int kcnt;
long long kk[55], n[maxt];
bitset<maxt> ans;
bitset<maxv> np;
vector<int> primes;
vector<long long> factor;
typedef pair<long long, int> plli;
priority_queue<plli, vector<plli>, greater<plli> > pq;
long long dis[maxp];
long long quick_pow(long long x, long long p, long long mod) {
long long res = 1; while(p) {
if (p & 1LL) (res *= x) %= mod;
(x *= x) %= mod, p >>= 1;
} return res;
}
void yes() { putchar('Y'); putchar('E'); putchar('S'); putchar('\n'); }
void no() { putchar('N'); putchar('O'); putchar('\n'); }
int main() {
// freopen("fantasy.in", "r", stdin), freopen("fantasy.out", "w", stdout);
np[0] = np[1] = true;
for (int i = 2; i < 3.3e7; i++) {
if (!np[i]) primes.emplace_back(i);
for (int j : primes) {
if (i * j > 3.3e7) break;
np[i * j] = true;
if (i % j == 0) break;
}
}
read(tid), read(t);
for (int i = 1; i <= t; i++) {
long long k;
read(n[i]); read(k);
if (!mp.count(k)) {
mp[k] = ++kcnt;
kk[kcnt] = k;
ask[kcnt].emplace_back(i);
}
else ask[mp[k]].emplace_back(i);
}
for (int j = 1; j <= kcnt; j++) {
long long tk = kk[j]; factor.clear();
if (tk == 1) continue;
for (int p : primes) {
if (tk < p) break;
if (tk % p == 0) {
factor.emplace_back(p);
while (tk % p == 0) tk /= p;
}
}
if (tk > 1) factor.emplace_back(tk);
if (factor.size() < 2) {
for (int id : ask[j]) ans[id] = (n[id] % factor[0] == 0);
continue;
}
if (factor.size() == 2) {
for (int id : ask[j]) {
__int128 x, y, k;
ex_gcd(factor[0], factor[1], x, y);
if (x < 0) k = ceil(-1.0 * x / factor[1]), x += factor[1] * k, y -= factor[0] * k;
else k = x / factor[1], x -= factor[1] * k, y += factor[0] * k;
x *= n[id], y *= n[id];
if (x < 0) k = ceil(-1.0 * x / factor[1]), y -= factor[0] * k;
else k = x / factor[1], y += factor[0] * k;
ans[id] = (y >= 0);
}
continue;
}
memset(dis, 0x3f, sizeof dis);
int p0 = factor[0];
pq.emplace(0, 0);
while (!pq.empty()) {
auto now = pq.top(); pq.pop();
if (dis[now.second] ^ inf) continue;
dis[now.second] = now.first;
for (long long xx : factor) {
if (dis[(now.second + xx) % p0] == inf) {
pq.emplace(now.first + xx, int((now.second + xx) % p0));
}
}
}
for (int id : ask[j]) {
ans[id] = (dis[n[id] % p0] <= n[id]);
}
}
for (int i = 1; i <= t; i++) ans[i] ? yes() : no();
return 0;
}