2021-08-06 11:22 Java

关注

2021牛客寒假算法基础集训营3

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

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

A-模数的世界

知识点：数学

先猜测最大值为 $p-1$ 再来求解，若求解成功则猜测正确QAQ。
当 $a=b=0$ 时，最大值为0。
当 $b=0$ 时，设 $x=(p-a)(p-1),y=p(p-1)$ 即可满足条件。
当 $b!=0$ 时，设 $x=(mp-a)(p-1),y=(p-b)(p-1)$ ，且 $gcd(mp-a,p-b)=1$ 即可满足条件。下面的代码是暴力求解的 $m$ ，出题人题解使用了 $exgcd$ 求解。

#include <bits/stdc++.h>
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;
LL a, b, p;
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%lld%lld%lld", &a, &b, &p);
        if(a == 0 && b == 0) printf("0 %lld %lld\n", p, p);
        else {
            LL x = (p - a) * (p - 1);
            LL y = (p - b) * (p - 1);
            while(__gcd(x, y) != p - 1) x += p * (p - 1);
            printf("%lld %lld %lld\n", p - 1, x, y);
        }
    }
    return 0;
}

B-内卷

知识点：模拟

参考神崎兰子的博客，考虑一开始全部人都是 $E$ 等级的成绩，这时最大值无法变得更小，我们可以选择当前分数最小的人提升到 $D$ 等级来增加最小值，依次迭代不断更新答案。

#include <bits/stdc++.h>
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, k;
int a[MAXN][5];
int maxx = 0;
struct node {
    int id, p, val;
    node(int _id, int _p, int _val) {
        id = _id, p = _p, val = _val;
    }
    bool operator <(const node &x)const {
        if(val != x.val) return val > x.val;
        if(p != x.p) return p < x.p;
        return id > x.id;
    }
};
priority_queue<node> que;
int main() {
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 5; j++) scanf("%d", &a[i][j]);
        que.push({i, 4, a[i][4]});
        maxx = max(maxx, a[i][4]);
    }
    int ans = maxx - que.top().val, cnt = 0;
    while(!que.empty()) {
        node now = que.top();
        que.pop();
        if(now.p == 0 || (now.p == 1 && cnt == k)) break;

        node ne(now.id, now.p - 1, a[now.id][now.p - 1]);
        que.push(ne);
        if(ne.p == 0) cnt++;
        maxx = max(maxx, ne.val);
        ans = min(ans, maxx - que.top().val);
    }
    printf("%d\n", ans);
    return 0;
}

C-重力坠击

知识点：穷举

题目要求攻击的点必须是整数点，可以枚举每次攻击的位置，选取能消灭最多敌人的方式即可。

#include <bits/stdc++.h>
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, k, R;
struct node {
    int x, y, r;
} a[11];

int ans;
bool f[11][4];
void boom(int i, int j, int cnt) {
    for(int k = 0; k < n; k++) {
        int dist = (i - a[k].x) * (i - a[k].x) + (j - a[k].y) * (j - a[k].y);
        if(dist <= R * R + 2 * R * a[k].r + a[k].r * a[k].r) {
            f[k][cnt] = true;
        }
    }
}
void dfs(int cnt) {
    if(cnt == k) {
        int sum = 0;
        for(int k = 0; k < n; k++)
            if(f[k][0] || f[k][1] || f[k][2]) sum++;
        ans = max(ans, sum);
        return;
    }

    for(int i = -7; i <= 7; i++) {
        for(int j = -7; j <= 7; j++) {
            boom(i, j, cnt);
            dfs(cnt + 1);
            for(int k = 0; k < n; k++) f[k][cnt] = false;
        }
    }
}
int main() {
    scanf("%d%d%d", &n, &k, &R);
    for(int i = 0; i < n; i++) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
    dfs(0);
    printf("%d\n", ans);
    return 0;
}

D-Happy New Year！

知识点：模拟

依题意模拟即可。

#include <bits/stdc++.h>
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 == 2030) puts("2102");
    else printf("%d\n", n + 9);
    return 0;
}

E-买礼物

知识点：线段树

对于同一种商品编号的商品建立链表关系，这样可以 $O(1)$ 的维护每个商品的左右关系。
判断某一个商品在区间里是否有两个，只需要判断该商品右边的那个相同种类的商品是否在区间内即可。
判断一个区间内是否有两个相同的商品，只需要知道区间内每个商品右边那个相同种类的商品下标的最小值即可。

#include <bits/stdc++.h>
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, q;
int a[MAXN];
int pre[MAXN];
int tol[MAXN], tor[MAXN];
//线段树
int tree[MAXN * 4];
void push_up(int i) {
    tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
}
void build(int i, int l, int r) {
    if(l == r) {
        tree[i] = tor[l];
        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) {
    if(l == r) {
        tree[i] = tor[l];
        return;
    }
    int mid = (l + r) / 2;
    if(p <= mid) update(i * 2, l, mid, p);
    else update(i * 2 + 1, mid + 1, r, p);
    push_up(i);
}
int query(int i, int l, int r, int left, int right) {
    if(left <= l && r <= right) return tree[i];

    int ret = INF;
    int mid = (l + r) / 2;
    if(left <= mid) ret = min(ret, query(i * 2, l, mid, left, right));
    if(mid < right) ret = min(ret, query(i * 2 + 1, mid + 1, r, left, right));
    return ret;
}
int main() {
    scanf("%d%d", &n, &q);
    memset(tor, INF, sizeof(tor));
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        tol[i] = pre[a[i]];
        tor[pre[a[i]]] = i;
        pre[a[i]] = i;
    }
    //线段树初始化
    build(1, 1, n);
    //操作
    int op, index, l, r;
    while(q--) {
        scanf("%d", &op);
        if(op == 1) {
            scanf("%d", &index);
            int pre = tol[index], suf = tor[index];
            tol[index] = 0, tor[index] = INF;
            if(pre != 0) tor[pre] = suf;
            if(suf != INF) tol[suf] = pre;
            update(1, 1, n, index);
            update(1, 1, n, pre);
        } else {
            scanf("%d%d", &l, &r);
            int minnum = query(1, 1, n, l, r);
            if(minnum <= r) puts("1");
            else puts("0");
        }
    }
    return 0;
}

F-匹配串

知识点：思维

"#s#"和"#t#"两个串，无论 $s$ 和 $t$ 是什么一定有模式串存在且有无数个。
两个"#"之间的内容可以看成一个"#"，则所有的串可以看成"s#t"的形式，只要前缀和后缀有模式串即可。
如果所有串第一个"#"的前缀存在模式串和所有串最后一个"#"的后缀存在模式串，则存在无数个模式串，否则无解。

#include <bits/stdc++.h>
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;
string s;
string pre[MAXN], suf[MAXN];
string maxp, maxs;
bool check() {
    for(int i = 0; i < n; i++) {
        if(pre[i].length() != 0 && maxp.find(pre[i]) != 0) return false;
        if(suf[i].length() != 0 && maxs.find(suf[i]) != 0) return false;
    }
    return true;
}
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> s;
        int len = s.length();
        //处理前缀
        for(int j = 0; j < len; j++) {
            if(s[j] != '#') pre[i] += s[j];
            else break;
        }
        maxp = max(maxp, pre[i]);
        //处理后缀
        for(int j = len - 1; j >= 0; j--) {
            if(s[j] != '#') suf[i] += s[j];
            else break;
        }
        maxs = max(maxs, suf[i]);
    }
    if(check()) puts("-1");
    else puts("0");
    return 0;
}

G-糖果

知识点：并查集

注意题目并没有规定朋友的朋友是朋友，但是糖果的关系是有传递性的。一个人拥有的糖果数是他所在糖果关系中的最大值，对每个人并查集求值再求和即可。

#include <bits/stdc++.h>
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];
int fa[MAXN], cnt[MAXN];
int findfa(int x) {
    if(x == fa[x]) return x;
    return fa[x] = findfa(fa[x]);
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        fa[i] = i;
        cnt[i] = a[i];
    }
    while(m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        int rootu = findfa(u);
        int rootv = findfa(v);
        cnt[rootu] = max(cnt[rootu], cnt[rootv]);
        fa[rootv] = fa[rootu];
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++) ans += cnt[findfa(i)];
    printf("%lld\n", ans);
    return 0;
}

H-数字串

知识点：模拟

考虑拆分和合并，有效范围是 $[11,19]和[21,26]$ 。

#include <bits/stdc++.h>
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;
char s[MAXN];
bool check(int x) {
    if(11 <= x && x <= 19) return true;
    if(21 <= x && x <= 26) return true;
    return false;
}
bool solve() {
    //可以拆分
    for(int i = 0; i < n; i++) {
        int x = s[i] - 'a' + 1;
        if(check(x)) {
            for(int j = 0; j < i; j++) putchar(s[j]);
            printf("%c%c", 'a' + x / 10 - 1, 'a' + x % 10 - 1);
            for(int j = i + 1; j < n; j++) putchar(s[j]);
            putchar(10);
            return true;
        }
    }
    //可以合并
    for(int i = 0; i < n - 1; i++) {
        int x = s[i] - 'a' + 1;
        if(x == 1) {
            int y = s[i + 1] - 'a' + 1;
            if(1 <= y && y <= 9) {
                for(int j = 0; j < i; j++) putchar(s[j]);
                putchar('a' + x * 10 + y - 1);
                for(int j = i + 2; j < n; j++) putchar(s[j]);
                return true;
            }
        }
        if(x == 2) {
            int y = s[i + 1] - 'a' + 1;
            if(1 <= y && y <= 6) {
                for(int j = 0; j < i; j++) putchar(s[j]);
                putchar('a' + x * 10 + y - 1);
                for(int j = i + 2; j < n; j++) putchar(s[j]);
                return true;
            }
        }
    }
    //无解
    return false;
}
int main() {
    scanf("%s", s);
    n = strlen(s);
    if(!solve()) puts("-1");
    return 0;
}

I-序列的美观度

知识点： $dp$

设 $dp[i]$ 表示前 $i$ 个数的最大美观度，则有以下转移方程。
$dp[i]=max(dp[j]),j<i且a[j]!=a[i]$ 。
$dp[i]=max(dp[j])+1,j<i且a[j]==a[i]$ 。
做一下前缀最大值并记录一下下标即可 $O(1)$ 转移。

#include <bits/stdc++.h>
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 a[MAXN];
int dp[MAXN];
int pre[MAXN];
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    dp[0] = -1;
    for(int i = 1; i <= n; i++) {
        dp[i] = max(dp[pre[a[i]]] + 1, dp[i - 1]);
        pre[a[i]] = i;
    }
    printf("%d\n", dp[n]);
    return 0;
}

J-加法和乘法

知识点：贪心、博弈论

贪心做法：

题目范围可以模拟，当牛牛操作时优先消除偶数，当牛妹操作时优先消除奇数。

#include <bits/stdc++.h>
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, x;
int ji, ou;
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &x);
        if(x & 1) ji++;
        else ou++;
    }

    for(int i = 0; i < n - 1; i++) {
        if(i & 1) {//牛妹操作
            if(ji > 0) {
                if(ji > 1) ji -= 2, ou++;
                else ji--;
            } else ou--;
        } else {//牛牛操作
            if(ou > 0) ou--;
            else ji--;
        }
    }
    if(ji) puts("NiuNiu");
    else puts("NiuMei");
    return 0;
}

博弈做法：

特判一个数的情况。
当操作次数是偶数时，牛妹必胜，任意两数都可以变成一个偶数。
当操作次数是奇数时，牛妹获胜的条件为初始数中至少有两个偶数。因为初始至少有两个偶数时，当经过牛牛一次操作后至少还有一个偶数，这样牛妹再操作恢复成至少两个偶数，直到最后一次操作时牛牛将面对两个偶数的情况。
当操作次数是奇数且初始数中偶数数目小于2，则牛牛获胜。

#include <bits/stdc++.h>
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, x;
int ji, ou;
bool solve() {
    if(n == 1) return ji ? true : false;
    if(n % 2 == 1) return false;
    if(ou > 1) return false;
    return true;
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &x);
        if(x & 1) ji++;
        else ou++;
    }
    if(solve()) puts("NiuNiu");
    else puts("NiuMei");
    return 0;
}