牛客小白月赛30

比赛地址：https://ac.nowcoder.com/acm/contest/9667

出题人题解：https://ac.nowcoder.com/discuss/575975

A-黑白边

知识点：并查集

优先选择黑边然后再选白边，选择 $n-1$ 条边可使图连通。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;

int n, m;
int u[MAXN], v[MAXN], w[MAXN];
int fa[MAXN];
int get(int i) {
    if(fa[i] == i) return i;
    return fa[i] = get(fa[i]);
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i <= n; i++) fa[i] = i;

    int sum = 0;
    for(int i = 0; i < m; i++) {
        scanf("%d%d%d", &u[i], &v[i], &w[i]);
        if(w[i] == 0) {
            int x = get(u[i]);
            int y = get(v[i]);
            if(x != y) {
                fa[x] = y;
                sum++;
            }
        }
    }

    int cnt = 0;
    for(int i = 0; i < m; i++) {
        if(w[i] == 1) {
            int x = get(u[i]);
            int y = get(v[i]);
            if(x != y) {
                fa[x] = y;
                cnt++;
                sum++;
            }
        }
    }

    if(sum != n - 1) puts("-1");
    else printf("%d\n", cnt);
    return 0;
}

B-最好的宝石

知识点：线段树

线段树裸题，不会请看这篇文章线段树从零开始。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;

struct node {
    int x;
    int cnt;
} tree[MAXN * 4];
int n, m;
int a[MAXN];
void push_up(int i) {
    int l = i * 2, r = i * 2 + 1;
    if(tree[l].x > tree[r].x) {
        tree[i].x = tree[l].x;
        tree[i].cnt = tree[l].cnt;
    } else if(tree[l].x < tree[r].x) {
        tree[i].x = tree[r].x;
        tree[i].cnt = tree[r].cnt;
    } else {
        tree[i].x = tree[l].x;
        tree[i].cnt = tree[l].cnt + tree[r].cnt;
    }
}
void build(int i, int l, int r) {
    if(l == r) {
        tree[i].x = a[l];
        tree[i].cnt = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(i * 2, l, mid);
    build(i * 2 + 1, mid + 1, r);
    push_up(i);
}
void update(int i, int l, int r, int p, int x) {
    if(l == r) {
        tree[i].x = x;
        tree[i].cnt = 1;
        return;
    }
    int mid = (l + r) / 2;
    if(p <= mid) update(i * 2, l, mid, p, x);
    if(mid < p) update(i * 2 + 1, mid + 1, r, p, x);
    push_up(i);
}
node query(int i, int l, int r, int left, int right) {
    if(left <= l && r <= right) {
        return tree[i];
    }
    node ret;
    ret.x = -1;
    ret.cnt = 0;
    int mid = (l + r) / 2;
    if(left <= mid) {
        node ll = query(i * 2, l, mid, left, right);
        ret = ll;
    }
    if(mid < right) {
        node rr = query(i * 2 + 1, mid + 1, r, left, right);
        if(rr.x > ret.x) ret = rr;
        else if(rr.x == ret.x) ret.cnt += rr.cnt;
    }
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, 1, n);

    int l, r;
    char op[7];
    while(m--) {
        scanf("%s%d%d", op, &l, &r);
        if(op[0] == 'A') {
            node ans = query(1, 1, n, l, r);
            printf("%d %d\n", ans.x, ans.cnt);
        } else {
            update(1, 1, n, l, r);
        }
    }
    return 0;
}

C-滑板上楼梯

知识点：贪心

选择先3阶再1阶的跳法，剩下的再单独判断。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;

LL n;
int main() {
    scanf("%lld", &n);
    LL a = n / 4 * 2;//周期所需的次数
    LL b = n % 4; //剩下所需的次数
    if(b == 3) b = 1;
    cout << a + b << endl;
    return 0;
}

D-GCD

知识点：质数

极限情况下 $k$ 个数由1和质数构成，所以只要 $k>前n个数里质数的个数+1$ 则一定能满足条件。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;

int n;
int a[MAXN];
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) a[i] = 1;
    for(int i = 2; i <= n; i++) {
        if(a[i] == 1) {
            for(int j = i + i; j <= n; j += i) a[j] = 0;
        }
        a[i] += a[i - 1];
        //printf("%d = %d\n",i,a[i]);
    }
    if(a[n] == n) puts("-1");
    else printf("%d\n", a[n] + 1);
    return 0;
}

E-牛牛的加法

知识点：模拟

对于长度不同的数可以添加前导零使得运算更方便。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;

string a, b, c;
int main() {
    cin >> a >> b;
    int n = max(a.length(), b.length());
    while(a.length() < n) a = "0" + a;
    while(b.length() < n) b = "0" + b;

    for(int i = 0; i < n; i++) {
        int x = (a[i] - '0' + b[i] - '0') % 10;
        c += '0' + x;
    }

    for(int i = 0; i < n; i++) {
        if(c[i] != '0') {
            cout << c.substr(i) << endl;
            break;
        }
        if(i == n - 1) puts("0");
    }
    return 0;
}

F-石子合并

知识点：贪心

每次都选取最大的那堆与相邻的进行操作。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;

int n;
LL a[MAXN];
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
    sort(a, a + n);
    LL sum = 0;
    for(int i = 0; i < n - 1; i++) sum += a[i];
    printf("%lld\n", sum + a[n - 1] * (n - 1));
    return 0;
}

G-滑板比赛

知识点：双指针

对 $a$ 和 $b$ 排序之后，双指针扫一遍，对每个 $a[i]$ 选择最小的满足条件的 $b[i]$ 。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;

int n, m;
int a[MAXN], b[MAXN];
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < m; i++) scanf("%d", &b[i]);
    sort(a, a + n);
    sort(b, b + m);
    for(int i = 0, j = 0; i < m; i++, j++) {
        while(j < n && a[j] <= b[i]) j++;
        if(j == n) {
            printf("%d\n", i);
            break;
        }
        if(i == m - 1) {
            printf("%d\n", i + 1);
            break;
        }
    }
    return 0;
}

H-第K小

知识点：堆

维护一个大小为 $k$ 的大根堆，堆顶即为第 $k$ 小的数。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;

int n, m, k;
int op, x;
priority_queue<int> q;
int main() {
    scanf("%d%d%d", &n, &m, &k);
    while(n--) {
        scanf("%d", &x);
        q.push(x);
        while(q.size() > k) q.pop();
    }

    while(m--) {
        scanf("%d", &op);
        if(op == 1) {
            scanf("%d", &x);
            q.push(x);
            while(q.size() > k) q.pop();
        } else {
            if(q.size() < k) puts("-1");
            else printf("%d\n", q.top());
        }
    }
    return 0;
}

I-区间亦或

知识点：枚举

注意 $n$ 的范围不超过 $3000$ ，先枚举所有的区间并记录对应区间长度的最大值。
再对区间长度维护前缀最大值，对于每次询问二分查询答案。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 5e6 + 117;
const int MAXM = 1e6 + 117;

int n, m;
int a[MAXN];
int ans[MAXN];
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < n; i++) {
        int sum = 0;
        for(int j = i; j < n; j++) {
            sum ^= a[j];
            ans[j - i + 1] = max(ans[j - i + 1], sum);
        }
    }

    for(int i = 1; i <= n; i++) ans[i] = max(ans[i], ans[i - 1]);

    while(m--) {
        int x;
        scanf("%d", &x);
        int id = lower_bound(ans + 1, ans + n + 1, x) - ans;
        if(id > n) puts("-1");
        else printf("%d\n", id);
    }
    return 0;
}

J-小游戏

知识点： $dp$

注意 $a[i]$ 不超过 $2e5$ ，先统计每个数出现的次数，设 $dp[i][0/1]$ 表示前 $i$ 个数里第 $i$ 个数取和不取的最大分数，则有状态转移方程：

$dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])$
$dp[i][1] = dp[i - 1][0] + i * a[i]$

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;

int n;
int x;
LL a[MAXN];
LL dp[MAXN][2];
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &x);
        a[x]++;
    }
    for(int i = 1; i <= 200000; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = dp[i - 1][0] + i * a[i];
    }
    printf("%lld\n", max(dp[200000][0], dp[200000][1]));
    return 0;
}