https://acm.ecnu.edu.cn/contest/448/

E. Effective Gradient

 

题意：给定 p,qp, q，以及平面上 nn 个点，求一条至少过两个点的直线，斜率与 p/qp / q 的差的绝对值最小。

几何

把所有点按照与直线 y=pqxy=\frac{p}{q}x 的有向距离的大小排序。即按照 pqxi−yi\frac{p}{q}x_i-y_i 排序。

最终答案的两个点一定相邻。否则选择它们中间的一个点，一定与这两点之一能够组成更优的直线。

之所以是有向距离是因为在直线两侧的点不同。

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

using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 998244353;

int n, p, q;

struct X {
    int x, y;

    bool operator<(const X &b) const {
        return y - 1.0 * p / q * x < b.y - 1.0 * p / q * b.x;
    }
} a[N];

int main() {
    scanf("%d%d%d", &n, &p, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
    }
    int flg = 1;
    for (int i = 2; i <= n; i++)if (a[i].x != a[i - 1].x)flg = 0;
    if (flg) {
        puts("1/0");
        return 0;
    }
    sort(a + 1, a + n + 1);
    double mn = 1e18;
    int aid;
    for (int i = 2; i <= n; i++) {
        if (a[i].x == a[i - 1].x)continue;
        double tmp = fabs(1.0 * (a[i].y - a[i - 1].y) / (a[i].x - a[i - 1].x) - 1.0 * p / q);
        if (tmp < mn) {
            mn = tmp;
            aid = i;
        }
    }
    int x = a[aid].x - a[aid - 1].x, y = a[aid].y - a[aid - 1].y;
    int g = __gcd(x, y);
    printf("%d/%d\n", y / g, x / g);
    return 0;
}

 

F. Frog

 

题意：给定一棵树 1≤n≤2×1051\le n\le 2\times 10^5 个节点，每个节点有权值，1≤q≤1061\le q\le 10^6次询问，每次给定两个节点 s，t，问有几种选择节点的方案满足：选出的节点都在 s，t 的最短路径上，且权值之和为 kk 的倍数。

树上点分治

点分治，每次分割之后dfs处理整个分配到的区域。

一次询问一定只能在一次dfs中被处理，那么就要保证 s，t 都在分配到的区域中。

按照点分治的方式找根get_root。假设当前的根为 u，要在 u 所管理的区域中 get_root，找到的一个根为 v，那么就将 u 作为 v 的父亲。这样最终得到一棵高为 O(]log)O(]log) 的新树，一次询问 (s, t) 仅在当前根为 LCA(s,t)LCA(s,t) 时被处理。容易证明，在新树中的 LCA(s, t) 一定在原树中是 s, t 最短路径上的一个点。

对每个节点维护 f[u][i]f[u][i] 表示在当前正在处理的区域中，从根到 uu 的路径上选中的节点的权值之和为 ii 的方案数。则 f[v][i]f[v][i] 可以由其父亲的值得到，分类讨论是否取节点 vv 即可。

由于当前的根一定在当前需要处理的询问 (s, t) 的最短路径上，所以可以由 f[s][i],f[t][k−i]f[s][i],f[t][k-i] 的乘积得到该询问的答案。

需要注意的是 f[u][i]f[u][i] 中不能包含根 rtrt，即在维护 ff 时 rtrt 必须不取，而在计算答案时才分类讨论 rtrt 取或不取。否则计算答案时就无法区分作乘积的两个 ff 中是否取到了 rtrt 而导致 rtrt 被重复取到。

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<bits/stdc++.h>

using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
const ll mod = 998244353;

int n, k, q;
vector<int> G[N];
int a[N];
ll ans[2000000];

bool vis[N];
int siz[N];

int get_sz(int u, int _fa) {
    siz[u] = 1;
    for (int v:G[u]) {
        if (v == _fa || vis[v])continue;
        siz[u] += get_sz(v, u);
    }
    return siz[u];
}

typedef pair<int, int> pii;

pii get_rt(int u, int _fa, int tot) {
    pii res = pii(INF, -1);
    int s = 1, m = 0;
    for (int v:G[u]) {
        if (v == _fa || vis[v])continue;
        res = min(res, get_rt(v, u, tot));
        m = max(m, siz[v]);
        s += siz[v];
    }
    m = max(m, tot - s);
    res = min(res, pii(m, u));
    return res;
}

struct Q {
    int s, t, id;
};
vector<Q> qrys[N];

vector<int> T[N];
int fa[N], dep[N];

int build(int u, int _fa, int d) {
    get_sz(u, 0);
    int rt = get_rt(u, 0, siz[u]).second;
    vis[rt] = 1;
    dep[rt] = d;
    for (int v:G[rt]) {
        if (vis[v] || v == _fa)continue;
        int vrt = build(v, rt, d + 1);
        T[rt].push_back(vrt);
        fa[vrt] = rt;
    }
    return rt;
}

int LCA(int u, int v) {
    if (dep[u] < dep[v])swap(u, v);
    while (dep[u] > dep[v])u = fa[u];
    while (u != v)u = fa[u], v = fa[v];
    return u;
}

ll f[N][55];

void getf(int u, int _fa) {
    for (int v:G[u]) {
        if (v == _fa || vis[v])continue;
        fill(f[v], f[v] + k, 0);
        for (int i = 0; i < k; i++) {
            f[v][i] = (f[v][i] + f[u][i]) % mod;
            f[v][(i + a[v]) % k] = (f[v][(i + a[v]) % k] + f[u][i]) % mod;
        }
        getf(v, u);
    }
}

void solve(int rt) {
    vis[rt] = 1;
    fill(f[rt], f[rt] + k, 0);
    f[rt][0] = 1;
    getf(rt, 0);
    for (Q o:qrys[rt]) {
        int s = o.s, t = o.t, id = o.id;
        if (s == rt) {
            ans[id] = (f[t][0] + f[t][(k - a[rt]) % k]) % mod;
        } else {
            for (int i = 0; i < k; i++) {
                ans[id] = (ans[id] + f[s][i] * f[t][(k - i) % k] % mod) % mod;
                ans[id] = (ans[id] + f[s][i] * f[t][(k - i - a[rt] + k) % k] % mod) % mod;
            }
        }
    }
    for (int v:T[rt]) {
        if (vis[v])continue;
        solve(v);
    }
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
    build(1, 0, 1);
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        int s, t;
        scanf("%d%d", &s, &t);
        qrys[LCA(s, t)].push_back(Q{s, t, i});
    }
    memset(vis, 0, sizeof(vis));
    get_sz(1, 0);
    int root = get_rt(1, 0, siz[1]).second;
    memset(vis, 0, sizeof(vis));
    solve(root);
    for (int i = 1; i <= q; i++)printf("%lld\n", ans[i]);
    return 0;
}