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
#include <bits/stdc++.h>
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
#include <bits/stdc++.h>
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;
}

#define FILE_IO
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;
}