解题报告(ABCDE/10)

链接:https://ac.nowcoder.com/acm/contest/3005

A. 欧几里得

题目链接:https://ac.nowcoder.com/acm/contest/3005/A

分析:猜了一下斐波那契数列,(3,2),(5,3),(8,5)…这类是最小的,特判(1,0)。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL f[100];

void init() {
    f[0] = 0, f[1] = 1;
    for (int i = 2; i < 100; i++) f[i] = f[i - 1] + f[i - 2];
}

int main() {
    int T; cin >> T;
    init();
    while (T--) {
        int n; cin >> n;
        if (!n) cout << 1 << endl;
        else cout << (f[n + 1] + f[n + 2]) << endl;
    }
    return 0;
}

B. 括号序列

题目链接:https://ac.nowcoder.com/acm/contest/3005/B

分析:堆栈搞一下,从前往后扫描,遇到左括号,就把对应右括号入栈,遇到右括号,就把栈顶弹出,如果不一致就不合法。最后栈空表示有解。

#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

char str[N];
char stk[N];
int tt;

int main() {
    scanf("%s", str);
    bool valid = true;
    for (int i = 0; str[i]; i++) {
        if (str[i] == '[') stk[++tt] = ']';
        else if (str[i] == '(') stk[++tt] = ')';
        else if (str[i] == '{') stk[++tt] = '}';
        else {
            char t = stk[tt--];
            if (t != str[i]) {
                valid = false;
                break;
            }
        }
    }
    if (valid && !tt) puts("Yes");
    else puts("No");
    return 0;
}

C. 子段乘积

题目链接:https://ac.nowcoder.com/acm/contest/3005/C

分析:有零的话,比较难以使用线性做法,所以我干脆线段树维护区间乘积,然后它过了= =。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 200010, mod = 998244353;

int n, k;
LL a[N];
struct Tree {
    int l, r;
    LL mul;
} tr[N << 2];

void pushup(int u) {
    tr[u].mul = (tr[u << 1].mul * tr[u << 1 | 1].mul) % mod;
}

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = {l, r, a[r]};
    } else {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

LL query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
        return tr[u].mul;
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        LL res = 1;
        if (l <= mid) (res *= query(u << 1, l, r)) %= mod;
        if (r > mid) (res *= query(u << 1 | 1, l, r)) %= mod;
        return res;
    }
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    build(1, 1, n);
    LL ans = 0;
    for (int i = 1; i + k - 1 <= n; i++) {
        ans = max(ans, query(1, i, i + k - 1));
    }
    printf("%lld\n", ans);
    return 0;
}

D. 子段异或

题目链接:https://ac.nowcoder.com/acm/contest/3005/D

分析:$s[i]$ 维护异或前缀和,那么 $[l,r]$ 区间异或值即 $s[r] \text{^} s[l-1]$,本题需要求 $s[r]==s[l-1]$ 的方案数。哈希表统计一下每一个 $s[i]$ 的个数,然后运用一下乘法原理和加法原理即可。不要漏了初始的 $s[0]=0$ 的一个。

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;

int n;
int s[N];
unordered_map<int, int> mp;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
        s[i] ^= s[i - 1];
        mp[s[i]]++;
    }
    mp[0]++;
    long long res = 0;
    for (auto item : mp) {
        int cnt = item.second;
        res += 1ll * (cnt - 1) * cnt / 2;
    }
    cout << res << endl;
    return 0;
}

E. 最小表达式

题目链接:https://ac.nowcoder.com/acm/contest/3005/E

分析:贪心,高精度。如果有 $k$ 个加号,就有 $k+1$ 个数,我们将所有可以使用的数字排序,从大到小的枚举,依次往这 $k + 1$ 个数的个位分配,然后分配十位,……。具体做的时候,只要直接全部加到某一位上,最后再调整进位问题即可,套板子的话,那就把这个未调整好的数和 $0$ 相加即可。

#include <bits/stdc++.h>

#define vint vector<int>
#define pb push_back

using namespace std;

const int N = 500010;

char str[N];
int x[N];
unordered_map<int, int> mp;

vint add(vint &a, vint &b) {
    vint c;
    for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i++) {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.pb(t % 10);
        t /= 10;
    }
    return c;
}

int main() {
    scanf("%s", str);
    for (int i = 0; str[i]; i++) mp[str[i] - '0']++;
    int num = mp['+' - '0'] + 1;
    int cnt = 0;
    for (int i = 9; i >= 1; i--) {
        for (int j = 0; j < mp[i]; j++) {
            x[cnt++] = i;
        }
    }
    vint res;
    for (int i = 0; i < cnt; i += num) {
        int temp = 0;
        for (int j = i; j <= i + num - 1; j++) {
            temp += x[j];
        }
        res.push_back(temp);
    }
    vint t(1, 0);
    vint ans = add(res, t);
    for (int i = ans.size() - 1; i >= 0; i--) printf("%d", ans[i]);
    return 0;
}

F. 树上博弈(待补)

题目链接:https://ac.nowcoder.com/acm/contest/3005/F

分析:没时间想了,大概和LCA有关吧。


G. 音乐鉴赏(待补)

题目链接:https://ac.nowcoder.com/acm/contest/3005/G

分析:期望咋推啊我ssfd。应该可以二分。


H. 坐火车(待补)

题目链接:https://ac.nowcoder.com/acm/contest/3005/H

分析:


I. 匹配星星(待补)

题目链接:https://ac.nowcoder.com/acm/contest/3005/I

分析:


J. 二维跑步(待补)

题目链接:https://ac.nowcoder.com/acm/contest/3005/J

分析:


总结

第四场官方说明考点:搜索,简单STL,前缀和,二分搜索,位运算,贪心,分治,树