2021-08-21一期17&二期15暑假集训

发表于

[2018国庆雅礼集训10-5T2]赛

难度 :

思维难度 : 2星

代码难度 : 3星

标签:

wqswqs 二分 + 贪心

题解 :

先考虑没有 mm 的限制，容易得到一种贪心策略，两个人得到的物品数是齐头并进的，即在某一次贪心中，要么两个人各拿一个自己喜欢的东西，要么拿一个两个人都喜欢的东西，容易证明这样是对的.$ $$

考虑加上 mm​​ 的限制，因为每次拿物品时，拿到的物品的价值一定大于等于上一次拿到的物品的价值. 所以价值和关于 mm​ 是一个凸函数，可以用 wqswqs​ 二分解决。

但是要注意 wqswqs​​​ 二分后物品的价值有可能是负数，因为负数是一定要被选的，所以贪心时要把它的价值视为 00.

Code:

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define int long long

using namespace std;

const int N = 3e5 + 10;
int n, m, k;
int v[N];
int cnta, cntb;
int isa[N], isb[N];
int a[N], b[N], ab[N], el[N]; 
int tota, totb, totab, totel;
int res;
int inf = 0x3f3f3f3f3f3f3f3f;
vector<int> w;

int check(int w) {
    int tmp = k;
    int ans = 0;
    int cho = 0;
    for (int i = 1; i <= totab; ++i) {
        ab[i] -= w;
    }
    for (int i = 1; i <= tota; ++i) {
        a[i] -= w;
    }
    for (int i = 1; i <= totb; ++i) {
        b[i] -= w;
    }
    for (int i = 1; i <= totel; ++i) {
        el[i] -= w;
    }
    int i = 1, j = 1;
    while (tmp--) {
        if (i == min(tota, totb) + 1 && j == totab + 1) {
            puts("-1");
            exit(0);
        }
        if ((i <= min(tota, totb) && (a[i] > 0 ? a[i] : 0) + (b[i] > 0 ? b[i] : 0) <= (ab[j] > 0 ? ab[j] : 0)) || j > totab) ans += a[i] + b[i], ++i, cho += 2;
        else ans += ab[j], ++j, cho += 1;
    }
    int x = i, y = j;
    for (int i = x; i <= tota; ++i) {
        if (a[i] <= 0) ans += a[i], cho += 1;
    }
    for (int i = x; i <= totb; ++i) {
        if (b[i] <= 0) ans += b[i], cho += 1;
    }
    for (int i = y; i <= totab; ++i) {
        if (ab[i] <= 0) ans += ab[i], cho += 1;
    }
    for (int i = 1; i <= totel; ++i) {
        if (el[i] <= 0) ans += el[i], cho += 1;
    }
    for (int i = 1; i <= totab; ++i) {
        ab[i] += w;
    }
    for (int i = 1; i <= tota; ++i) {
        a[i] += w;
    }
    for (int i = 1; i <= totb; ++i) {
        b[i] += w;
    }
    for (int i = 1; i <= totel; ++i) {
        el[i] += w;
    }
    res = ans;
    return cho;
}

signed main() {
    scanf("%lld%lld%lld", &n, &m, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &v[i]);
    }
    scanf("%lld", &cnta);
    for (int i = 1; i <= cnta; ++i) {
        int x;
        scanf("%lld", &x);
        isa[x] = 1;
    }
    scanf("%lld", &cntb);
    for (int i = 1; i <= cntb; ++i) {
        int x;
        scanf("%lld", &x);
        isb[x] = 1;
    }
    if (m < k) return puts("-1"), 0;
    for (int i = 1; i <= n; ++i) {
        if (isa[i] && isb[i]) ab[++totab] = v[i];
        else if (isa[i]) a[++tota] = v[i];
        else if (isb[i]) b[++totb] = v[i];
        else el[++totel] = v[i];
    }
    sort(ab + 1, ab + totab + 1);
    sort(a + 1, a + tota + 1);
    sort(b + 1, b + totb + 1);
    sort(el + 1, el + totel + 1);
    if (m < k) return puts("-1"), 0;
    if (m < 2 * k - totab) return puts("-1"), 0;
    if (tota + totab < k || totb + totab < k) return puts("-1"), 0;
    int l = -2000000000, r = 2000000000;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid) >= m) r = mid;
        else l = mid + 1;
    }
    int tmp = check(l);
    cout << res + l * m << endl;
    return 0;
}

总结

一道小贪心，但原题细节比较多，也是一道 wqswqs 的套路题.

[2018国庆雅礼集训10-6T1]Merchant

难度 :

思维难度 : 2星

代码难度 : 2星

标签:

二分 + STL

题解：

首先想到二分，然后发现二分不满足单调性。但是总价值关于 tt​​ 满足斜率单调递增，所以这是一个凸函数。先二分找到最低点，从最低点向右是一个递增函数，可以二分答案，最低点左边是一个递减函数，也可以二分答案.

其实没有这么麻烦，因为最低点左边最高点一定是 00, 先特判掉，然后如果 00 不满足条件，那么从 00​ 到最低点都不满足条件，从最低点向右有是一个递增函数，有单调性 , 所以特判零之后直接二分就行.

Code:

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long

using namespace std;

const int N = 2e6 + 10;
int n, m, s;
int ans = 0;

struct OB {
    int k, b, val;

    bool operator < (const OB A) const {
        if (val == A.val) {
            if (k == A.k) {
                return b < A.b;
            }
            return k < A.k;
        }
        return val > A.val;
    }
}a[N];

int check1(int t) {
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        a[i].val = a[i].k * t + a[i].b;
    }
    nth_element(a + 1, a + m,  a + n + 1);
    for (int i = 1; i <= m; ++i) {
        if (a[i].val > 0) res += a[i].k;
    }
    return res;
}

int check2(int t) {
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        a[i].val = a[i].k * t + a[i].b;
    }
    nth_element(a + 1, a + m, a + n + 1);
    for (int i = 1; i <= m; ++i) {
        if (a[i].val > 0) res += a[i].val;
        if (res >= s) return 1;
    }
    return 0;
}

signed main() {
    scanf("%lld%lld%lld", &n, &m, &s);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld%lld", &a[i].k, &a[i].b);
    }
    int l = 0, r = 1000000000;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check1(mid) >= 0) r = mid;
        else l = mid + 1;
    }
    if (check2(0)) {
        puts("0");
        return 0;
    }
    l = l, r = 1000000000;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check2(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%lld\n", l);
    return 0;
}

总结

nth_elementnth\_element 大法好。

[2018国庆雅礼集训10-6T2]Equation

难度

思维难度 : 3星

代码难度 : 3星

标签

dfsdfs 序 + 树状数组

题解 :

设询问时连的边是 (u,v)(u, v) ，那么从 uu 到根的方程可以看作 xu=v1−v2+v3−...±x1x_u = v_1 - v_2 + v3 - ...\pm x_1 , xv=v1−v2+v3−...±x1x_v = v_1 - v_2 + v3 - ...\pm x_1, 又有 xu+xv=sx_u + x_v = s, 可得 ±x1±x1+val=s\pm x_1 \pm x_1 + val = s, valval 为 v1−v2+v3−...v_1 - v_2 + v3 - ..., 如果两个 x1x_1 同号，那么解方程，否则如果 val=sval = s 有无穷解， 如果 val≠sval \neq s, 无解。

用树状数组维护一下就行

Code :

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
131
132
133
134
135
136
#include <iostream>
#include <cstdio>
#define int long long

using namespace std;

const int N = 2e6 + 10;

int head[N], nxt[N], to[N], w[N], e_tot;
int sign[N];

struct Node {
    int dfn, fa, dep, top, siz, son;
}tr[N];
int tot;

inline int read() {
    int res = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -f;
        c = getchar();
    }
    while ('0' <= c && c <= '9') {
        res = res * 10 + c - '0';
        c = getchar();
    }
    return res * f;
}

void add(int x, int y, int z) {
    nxt[++e_tot] = head[x], head[x] = e_tot, to[e_tot] = y, w[e_tot] = z;
}

void dfs1(int u, int _fa) {
    tr[u].fa = _fa;
    tr[u].dep = tr[_fa].dep + 1;
    tr[u].siz = 1;
    sign[u] = sign[_fa] * -1;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        dfs1(v, u);
        tr[u].siz += tr[v].siz;
        if (tr[v].siz > tr[tr[u].son].siz) tr[u].son = v;
    }
}

void dfs2(int u, int _top) {
    tr[u].dfn = ++tot;
    tr[u].top = _top;
    if (tr[u].son) dfs2(tr[u].son, _top);
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == tr[u].son) continue;
        dfs2(v, v);
    }
}

int n, q;
int o[N];
int val[N];

int lowbit(int x) {
    return x & (-x);
}

void change(int x, int y, int v) {
    for (int i = x; i <= n; i += lowbit(i)) {
        val[i] += v;
    }
    for (int i = y + 1; i <= n; i += lowbit(i)) {
        val[i] -= v;
    }
}

int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += val[i];
    return res;
}

void Change(int x, int v) {
    change(tr[x].dfn, tr[x].dfn + tr[x].siz - 1, v);
}

int Query(int x) {
    return query(tr[x].dfn);
}

int fa[N];

signed main() {
    n = read(), q = read();
    for (int i = 2; i <= n; ++i) {
        int f, w;
        f = read(), w = read();
        add(f, i, w);
        fa[i] = f;
        o[i] = w;
    }
    sign[0] = -1;
    dfs1(1, 0);
    dfs2(1, 1);
    for (int i = 2; i <= n; ++i) {
        Change(i, o[i] * sign[i]);
    }
    for (int i = 1; i <= q; ++i) {
        int op, u, v, s, w;
        op = read();
        if (op == 1) {
            u = read(), v = read(), s = read();
            int w1 = Query(u) * sign[u], w2 = Query(v) * sign[v];
            if (sign[v] != sign[u]) {
                if (w1 + w2 == s) {
                    puts("inf");
                    continue;
                }
                else {
                    puts("none");
                    continue;
                }
            }
            if (w1 + w2 - s & 1) {
                puts("none");
                continue;
            }
            printf("%lld\n", (s - w1 - w2) / (sign[u] + sign[v]));
        }
        else {
            u = read(), w = read();
            Change(u, (w - o[u]) * sign[u]);
            o[u] = w;
        }
    }
    return 0;
}