牛客小白月赛29

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

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

A-进攻

知识点：前缀最大值

战机按破坏力从小到大排序、基地按防御值从小到大排序并维护价值的前缀最大值。

#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 = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m;
int a[MAXN];
struct node {
    int d;
    int v;
} b[MAXN];
bool cmp(node x, node y) {
    if(x.d != y.d) return x.d < y.d;
    return x.v > y.v;
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= m; i++) scanf("%d", &b[i].d);
    for(int i = 1; i <= m; i++) scanf("%d", &b[i].v);
    sort(a, a + n);
    sort(b + 1, b + 1 + m, cmp);

    b[0].v = 0;
    for(int i = 1; i <= m; i++) b[i].v = max(b[i].v, b[i - 1].v);

    LL ans = 0;
    for(int i = 0, j = 0; i < n; i++) {
        while(j < m && b[j + 1].d < a[i]) j++;
        ans += b[j].v;
    }
    printf("%lld\n", ans);
    return 0;
}

B-二进制

知识点：二进制枚举

题意：求一个不超过5次的操作序列，满足对于任意的经过已知的操作序列后和经过ans操作序列后所得的结果相同。

枚举每一位经过次操作后的结果，再运用位运算的性质选择合适的操作。

#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 = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
int op[MAXN], a[MAXN];
int one, two, three;
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d%d", &op[i], &a[i]);
    for(int i = 0; i < 20; i++) {
        int x = 0, y = 1 << i;
        for(int j = 0; j < n; j++) {
            if(op[j] == 1) x &= a[j], y &= a[j];
            if(op[j] == 2) x |= a[j], y |= a[j];
            if(op[j] == 3) x ^= a[j], y ^= a[j];
        }

        x = (x >> i) & 1, y = (y >> i) & 1;
        if(x == 1 || y == 1) one += 1 << i;
        if(x == 1 && y == 1) two += 1 << i;
        if(x == 1 && y == 0) three += 1 << i;
    }
    printf("3\n1 %d\n2 %d\n3 %d\n", one, two, three);
    return 0;
}

C-积木

知识点：构造

易证当为奇数时无解，当为偶数时分解成若干个2阶立方体即可。

#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 = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
int main() {
    scanf("%d", &n);
    if(n & 1) puts("-1");
    else {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                for(int k = 0; k < n; k++) {
                    int num = (j / 2 + k / 2) & 1;
                    printf("%d ", num ^ (i & 1));
                }
                putchar(10);
            }
        }
    }
    return 0;
}

D-种树

知识点：dfs

只能取到深度小于等于操作次数的点的子树的最小值。

注：出题人题解给出了二分的做法。

#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 = 5e5 + 117;
const int MAXM = 1e6 + 117;

int n;
int a[MAXN], ans;
int l[MAXN], r[MAXN];
void dfs(int i, int high) {
    if(l[i]) {
        dfs(l[i], high + 1);
        dfs(r[i], high + 1);
        a[i] = min(a[l[i]], a[r[i]]);
    }
    if(high <= n / 2 / 2) ans = max(ans, a[i]);
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d%d", &l[i], &r[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    ans = -INF;
    dfs(1, 0);
    printf("%d\n", ans);
    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 = 998244353 ;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, k;
int a[MAXN], b[MAXN];
int yes, no;
int main() {
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
        if(a[i] == b[i]) yes++;
        else no++;
    }
    if(k <= no) printf("%d\n", n - (no - k));
    else printf("%d\n", n - (k - no));
    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 = 5e5 + 117;
const int MAXM = 1e6 + 117;

int n, m;
int f;
int l[MAXN], r[MAXN];
void pr() {
    int x = 1;
    if(f) {
        do {
            printf("%d ", x);
            x = l[x];
        } while(x != 1);
    } else {
        do {
            printf("%d ", x);
            x = r[x];
        } while(x != 1);
    }
    putchar(10);
}
void del(int i) {
    int ll = l[i], rr = r[i];
    r[ll] = rr;
    l[rr] = ll;
}
void add(int x, int i) {
    int rr = r[i];
    r[i] = x;
    l[x] = i;
    r[x] = rr;
    l[rr] = x;
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        if(i == 1) l[i] = n;
        else l[i] = i - 1;
        if(i == n) r[i] = 1;
        else r[i] = i + 1;
    }

    int op, x, y;
    while(m--) {
        scanf("%d", &op);
        if(op == 1) {
            scanf("%d%d", &x, &y);
            del(x);
            if(f) add(x, l[y]);
            else add(x, y);
        } else if(op == 2) {
            scanf("%d%d", &x, &y);
            del(x);
            if(f) add(x, y);
            else add(x, l[y]);
        } else if(op == 3) {
            f ^= 1;
        } else pr();
    }
    return 0;
}

G-涂色

知识点：数学

可以，但易求答案为。

#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 = 998244353 ;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
int main() {
    cin >> n;
    cout << n + 1 << endl;
    return 0;
}

H-圆

知识点：几何

圆心距与两圆半径判交点。

#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 = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
int main() {
    double x1, y1, r1;
    double x2, y2, r2;
    cin >> T;
    while(T--) {
        cin >> x1 >> y1 >> r1;
        cin >> x2 >> y2 >> r2;
        double dist = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
        if(dist > r1 + r2 || dist < fabs(r1 - r2)) puts("NO");
        else puts("YES");
    }
    return 0;
}

I-修改

知识点：最小生成树

数列问题转化成图论问题的神奇操作：

• 数列值全为0-->差分数组值全为0。
• 选择区间进行修改-->差分数组和发生修改。
• 对点和点建边后，对任意数列满足的充要条件为：每个点都可以通过某些边到达点。
• 最小代价为最小生成树的大小。

总结的不好，建议看出题人的题解。

#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 = 1e5 + 117;
const int MAXM = 4e5 + 117;

int n, m;
int tot;
int F[MAXN];
struct Edge {
    int u, v, w;
} edge[MAXM];
void addedge(int u, int v, int w) {
    edge[tot].u = u;
    edge[tot].v = v;
    edge[tot++].w = w;
}
bool cmp(Edge a, Edge b) {
    return a.w < b.w;
}
int find(int x) {
    if(F[x] == x) return x;
    return F[x] = find(F[x]);
}
LL kruskal(int n) {
    for(int i = 0; i <= n; i++) F[i] = i;
    sort(edge, edge + tot, cmp);
    int cnt = 0;
    LL ans = 0;
    for(int i = 0; i < tot; i++) {
        int u = edge[i].u;
        int v = edge[i].v;
        int w = edge[i].w;
        int t1 = find(u);
        int t2 = find(v);
        if(t1 != t2) {
            ans += w;
            F[t1] = t2;
            cnt++;
        }
        if(cnt == n - 1) return ans;
    }
    return -1;
}
int main() {
    scanf("%d%d", &n, &m);
    int l, r, w;
    while(m--) {
        scanf("%d%d%d", &l, &r, &w);
        addedge(l, r + 1, w);
    }
    printf("%lld\n", kruskal(n + 1));
    return 0;
}

J-克隆

知识点：欧拉序

欧拉序：https://www.cnblogs.com/stxy-ferryman/p/7741970.html

个人能经过的点数总和不少于，欧拉序列长度为。

#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 = 1e5 + 117;
const int MAXM = 4e5 + 117;

int n, m, k;
int head[MAXN];
int edge[MAXM], ne[MAXM], tot;
bool vis[MAXN];
int ans[MAXM], cnt;
void addedge(int u, int v) {
    edge[tot] = v;
    ne[tot] = head[u];
    head[u] = tot++;
}
void dfs(int i) {
    ans[cnt++] = i;
    vis[i] = true;
    for(int j = head[i]; j != -1; j = ne[j]) {
        int v = edge[j];
        if(!vis[v]) {
            dfs(v);
            ans[cnt++] = i;
        }
    }
}
int main() {
    tot = cnt = 0;
    memset(head, -1, sizeof(head));

    scanf("%d%d%d", &n, &m, &k);
    int u, v;
    while(m--) {
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    dfs(1);

    puts("YES");
    int num = (2 * n + k - 1) / k;
    for(int i = 0; i < cnt; i += num) {
        if(i + num < cnt) printf("%d", num);
        else printf("%d", cnt - i);
        for(int j = 0; j < num && i + j < cnt; j++) printf(" %d", ans[i + j]);
        putchar(10);
    }
    return 0;
}