Codeforces Round 430 (Div. 2) 题解

2017/11/02

A. Kirill And The Game

签到题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int l, r, x, y, k;

int main() {
    scanf("%d %d %d %d %d", &l, &r, &x, &y, &k);

    for(int i=x;i<=y;i++) {
        if(1LL * k * i >= l && 1LL * k * i <= r) {
            puts("YES");
            return 0;
        }
    }

    puts("NO");
}

B. Gleb And Pizza

继续签到

 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
#include <bits/stdc++.h>
using namespace std;
typedef double db;

db R, D;
int N;

db dist(db x, db y) {
    return sqrt(x * x + y * y);
}

int main() {
    scanf("%lf %lf", &R, &D);
    int N; scanf("%d", &N);

    db x, y, r;
    int ans = 0;
    while(N--) {
        scanf("%lf %lf %lf", &x, &y, &r);
        db dis = dist(x, y);
        db mn = dis - r;
        db mx = dis + r;

        if(mn >= R - D && mx <= R)
            ans++;
    }

    printf("%d\n", ans);
}

C. Ilya And The Tree

dfs 过程中栈里的元素恰好就是跟求解相关的序列,需要求出在上面最多删掉一个元素的 gcd

枚举第一个元素是否删掉:

  1. 如果删掉,某个位置的删掉一个元素的 gcd 就是从第二个起的前缀 gcd
  2. 如果不删,那么答案值一定是第一个元素的某个约数,统计这个约数在序列中作为约数出现的次数,出现大于 等于 N-1 次的最大的约数即是答案。

复杂度

 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
#include <bits/stdc++.h>
using namespace std;
const int SIZ = 2e5 + 2007;

int N;
int S[SIZ];

struct tgno {
    int v; tgno *n;
} POOL[SIZ<<1], *Head[SIZ]; int ppos;

void _add(int u, int v) {
    POOL[ppos].v = v;
    POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
}

void addEdge(int u, int v) {
    _add(u, v), _add(v, u);
}

int gcd(int x, int y) {
    return y ? gcd(y, x % y) : x;
}

vector<int> factorize(int x) {
    vector<int> ret;

    for(int i=1;i*i<=x;i++) {
        if(x % i == 0) {
            ret.push_back(i);
            if(x != i * i)
                ret.push_back(x / i);
        }
    }

    sort(ret.begin(), ret.end());
    return ret;
}

vector<int> fac;
int ans[SIZ];
void dfs1(int u = 1, int pre = 0) {
    typedef tgno* It;
    ans[u] = gcd(ans[pre], S[u]);

    for(It i=Head[u];i;i=i->n) {
        if(i->v != pre)
            dfs1(i->v, u);
    }
}

int cnt[SIZ];
void dfs2(int u = 1, int pre = 0, int dd = 1) {
    int _ = fac.size();
    for(int i=0;i<_;i++) {
        cnt[i] += (S[u] % fac[i] == 0);
        if(cnt[i] >= dd-1)
            ans[u] = max(ans[u], fac[i]);
    }

    typedef tgno* It;
    for(It i=Head[u];i;i=i->n) {
        if(i->v != pre)
            dfs2(i->v, u, dd + 1);
    }

    for(int i=0;i<_;i++)
        cnt[i] -= (S[u] % fac[i] == 0);
}

int main() {
    scanf("%d", &N);

    for(int i=1;i<=N;i++)
        scanf("%d", &S[i]);

    for(int i=1,u,v;i<N;i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }

    int p = S[1];
    S[1] = ans[1] = 0;
    dfs1();
    S[1] = p;
    fac = factorize(p);
    dfs2();

    for(int i=1;i<=N;i++)
        printf("%d ", ans[i]);
    puts("");
}

D. Vitya and Strange Lesson

因为 , 所以说我们可以把修改操作换掉,每次询问序列各项被某个数异或后的 mex

方法类似 BZOJ4571 - [Scoi2016]美味 , 在 trie 树上瞎走即可。

 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
#include <bits/stdc++.h>
using namespace std;
const int SIZ = 4e5 + 2007;

int N, M;
int S[SIZ<<2];

int psm[SIZ<<2], W, lw;
void sinit(int C) {
    for(W=1, lw=0;W<=C;W<<=1, lw++);
    for(int i=1;i<=W;i++)
        psm[i] = psm[i-1] + S[i-1];
}

int sum(int l, int r) { 
    return psm[r+1] - psm[l];
}

int query(int q, int l = 0, int r = W-1, int d=lw-1) {
    if(l == r || sum(l, r) == 0) {
        return l;
    }

    int mid = (l + r) >> 1;
    int qd = (q >> d) & 1;

    if(!qd) {
        if(sum(l, mid) < (mid - l + 1)) {
            return query(q, l, mid, d-1);
        } else {
            return query(q, mid+1, r, d-1);
        }
    } else {
        if(sum(mid+1, r) < (r - mid)) {
            return query(q, mid+1, r, d-1) - (mid - l + 1);
        } else {
            return query(q, l, mid, d-1) + (mid - l + 1);
        }
    }
}

int main() {
    scanf("%d %d", &N, &M);

    int mx = 0;
    for(int i=1, x;i<=N;i++) {
        scanf("%d", &x); S[x] = 1;
        mx = max(mx, x);
    }

    sinit(mx + 10);

    int q = 0, qc;
    while(M--) {
        scanf("%d", &qc);
        q ^= qc;
        printf("%d\n", query(q));
    }
}

E. Nikita and game

动态维护树上直径的端点。

 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
#include <bits/stdc++.h>
using namespace std;
const int SIZ = 3e5 + 2007;
int fa[SIZ][20];
int dep[SIZ];

int dist(int u, int v) {
    int ret = 0;
    if(dep[u] < dep[v])
        swap(u, v);

    for(int i=19;i>=0;i--)
        if(dep[fa[u][i]] >= dep[v])
            u = fa[u][i], ret += (1<<i);

    if(u == v)
        return ret;

    for(int i=19;i>=0;i--)
        if(fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i], ret += (1<<i)<<1;

    return ret + 2;
}

int N;
set<int> s1, s2;

int main() {
    scanf("%d", &N);
    dep[1] = 1; s1.insert(1);
    int mx = 1;
    
    for(int v=2, u;v<=N+1;v++) {
        scanf("%d", &u);
        fa[v][0] = u;
        dep[v] = dep[u] + 1;
        for(int i=1;i<20;i++)
            fa[v][i] = fa[fa[v][i-1]][i-1];
        
        int dist1 = s1.empty() ? 0 : dist(v, *s1.begin());
        int dist2 = s2.empty() ? 0 : dist(v, *s2.begin());
    
        if(max(dist1, dist2) > mx) {
            mx = max(dist1, dist2);
            if(dist1 == mx) {
                for(int u : s2)
                    if(dist(u, v) == mx)
                        s1.insert(u);
                s2.clear();
                s2.insert(v);
            } else {
                for(int u : s1)
                    if(dist(u, v) == mx)
                        s2.insert(u);
                s1.clear();
                s1.insert(v);
            }
        } else if(max(dist1, dist2) == mx) {
            if(dist1 >= dist2)
                s2.insert(v);
            else
                s1.insert(v);
        }

        printf("%d\n", int(s1.size() + s2.size()));
    }
}