2020-12-21 15:43 已编辑浙江大学计算机类

关注

2020蓝桥杯院内选拔赛题解

青竹的香蕉

https://ac.nowcoder.com/acm/contest/9429/J

赛后总结就是菜死了。

本场比赛个人难度分级：

A
CDGM
BFH
IJL
K

听说E有问题，我看了大概15min也没看懂，就不评价难度了

缩短博客长度，只发核心代码。

水题

A

牛客输出字符串的题目一律用PHP

/\*I like "algorithmic competitions" and I want to be stronger*/\

C

int main(){
    ll T=read();
    while(T--){
        ll a=read(),b=read(),c=read();
        ll aa=read(),bb=read(),cc=read();
        ll ans=min(c,aa)+min(b,cc)+min(a,bb);
        pr(ans);
    }
    return 0;
}

D

可以用函数封装来提高代码复用性能但是懒得改了。

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
inline ll read();
int main() {
    string who;
    while (cin >> who) {
        string op, s;
        int len;
        cin >> op >> len >> s;
        if (who == "sender") {
            int c0 = 0, c1 = 0;
            for (int i = 0; i < len; ++i) {
                if (s[i] == '0')
                    ++c0;
                else
                    ++c1;
            }
            cout << s;
            if (op == "even") {
                if (c1 % 2 == 0)
                    cout << 0 << endl;
                else
                    cout << 1 << endl;
            } else {
                if (c1 % 2 == 0)
                    cout << 1 << endl;
                else
                    cout << 0 << endl;
            }
        } else {
            int c0 = 0, c1 = 0;
            for (int i = 0; i < len - 1; ++i) {
                if (s[i] == '0')
                    ++c0;
                else
                    ++c1;
            }
            if (op == "even") {
                if (c1 % 2 == 0) {
                    puts(s[len - 1] == '0' ? "ACK" : "NAK");
                } else
                    puts(s[len - 1] == '1' ? "ACK" : "NAK");
            } else {
                if (c1 % 2 == 0) {
                    puts(s[len - 1] == '1' ? "ACK" : "NAK");
                } else
                    puts(s[len - 1] == '0' ? "ACK" : "NAK");
            }
        }
    }
    return 0;
}

G

int main() {
    ll n = read();
    if (n < 3) puts("No answer!");
    for (ll i = 1; i * 3 <= n; ++i) {
        pr(i * 3);
    }
    return 0;
}

M

题目本意并非暴力，但是数据比较弱。

string s, tp;
ll n,q,op;
inline bool chk(int a, int b, int L) {
    if(a + L >n||b+L>n)return 0;
    for (int l1 = a, l2 = b, r1 = a + L - 1, r2 = b + L - 1; l1 <= r1;
         ++l1, --r1, ++l2, --r2) {
        if (s[l1] != s[l2] || s[r1] != s[r2]) return 0;
    }
    return 1;
}
int main() {
    n = read(), q = read(), op;
    cin >> s;
    while (q--) {
        op = read();
        if (op == 1) {
            cin >> tp;
            ++n;
            s += tp;
        } else {
            ll x = read(), y = read(), L = read();
            if (x == y)
                puts("YES");
            else {
                bool f = chk(x - 1, y - 1, L);
                puts(f ? "YES" : "NO");
            }
        }
    }
    return 0;
}

简单题

B

其实是裸的dfs

int to[N << 1], nxt[N << 1], head[N], wt[N << 1], tot;
inline void init() { memset(head, -1, sizeof(head)), tot = 0; }
int a[N], dep[N], d;
inline void add(int u, int v) {
    to[++tot] = v;
    nxt[tot] = head[u];
    head[u] = tot;
}
void dfs(int x) {
    for (int i = head[x]; ~i; i = nxt[i]) {
        dep[to[i]] = dep[x] + 1;
        if (dep[to[i]] > d) d = dep[to[i]];
        dfs(to[i]);
    }
}
int main() {
    ll n = read();
    init();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        add(a[i], i);
    }
    dfs(0);
    pr(d);
    for (int i = 1; i <= n; ++i) {
        if (dep[i] == d) printf("%d ",i);
    }
    return 0;
}

F

dp[i][j]表示传i次到j的方案数量

ll dp[N][N];
int main() {
    ll n = read(), m = read();
    dp[0][1] = 1;
    for (int i = 1; i <= m; i++) {
        dp[i][1] = (dp[i - 1][n] % mod + dp[i - 1][1 + 1] % mod) % mod;
        for (int j = 2; j < n; j++)
            dp[i][j] = (dp[i - 1][j - 1] % mod + dp[i - 1][j + 1] % mod) % mod;
        dp[i][n] = (dp[i - 1][n - 1] + dp[i - 1][1]) % mod;
    }
    pr(dp[m][1] % mod);
}

H

思维题，核心要点在于数组初始为零。

ll ans, mx;
int main() {
    ll n = read();
    for (int i = 1; i <= n; ++i) {
        ll k = read(), now = 0;
        while (k) {
            if (k & 1) ++ans, --k;
            if (k) k >>= 1, ++now;
        }
        mx = max(mx, now);
    }
    ans += mx;
    pr(ans);
    return 0;
}

中档题

I

模式字符串记为P(下标从0开始) $next[q] = k$ 表示 $P[q]$ 之前的子串中，存在长度为 $k$ 的相同前缀和后缀，
即 $P[0]-P[k-1]$ 与 $P[q-k]-P[q-1]$ 依次相同。
所以只要判断 $Next[i]$ 是否在中间出现过即可，使用set容器记录。

考察了一个KMP的基础转换应用，听说HDU上面也是有很类似的题目的，好像就是2013ICPC区域赛的题目。

我已经很久没有练习过很字符串的字符串题目了，更不要说KMP，所以比赛的时候确实写不出来。

~~强烈谴责某出题人说字符串考得少然后一场比赛出两道字符串~~

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int Next[maxn];
int n;
char s[maxn];
set<int> v;
void get_next() {
    Next[0] = Next[1] = 0;
    for (int i = 1; i < n; i++) {
        int j = Next[i];
        while (j && s[i] != s[j]) j = Next[j];
        Next[i + 1] = s[j] == s[i] ? j + 1 : 0;
    }
}
int main() {
    scanf("%s", s);
    n = strlen(s);
    get_next();
    for (int i = 0; i < n; i++) v.insert(Next[i]);
    int x = n;
    while (Next[x]) {
        if (v.count(Next[x])) {
            s[Next[x]] = 0;
            puts(s);
            return 0;
        }
        x = Next[x];
    }
    puts("Hello KMP!");
    return 0;
}

J

题意:

对于每一个 $i,i\in{[0,n)}$ ，求 $gcd(a+i,n)==gcd(a,n)$ 的个数

设 $gcd(a,n)=x$ ,则有 $a=px,n=qx$ ,且 $p\ q$ 互质，现在要求 $gcd(a+i,n)=x$ ，则要满足以下两个条件

$i$ 能被 $x$ 整除，即 $a+i=cx$
$gcd(c,n)=1$ ，否则会导致 $gcd(a+i,n)\ne x$

所以我们将找 $i$ 转化为了找 $c$ ，而 $c$ 必须与 $q$ 互质。

另外， $a+i=cx$ 而 $i\in{[0,n)},a\in(1,n]$ ，所以 $a+i\in(0,2n)$ ，但是实际上 $a$ 是定值，所以 $a+i$ 的可行范围大小只有 $n$ 。而因为辗转相除法或者辗转相减法，对于 $a+i\in(n,2n)$ 等效于 $(a+i)\%n$ ，也就是说，所有的 $a+i$ 都可以映射到 $(0,n]$ 上。

所以答案即为 $c$ 的数量，也就是 $n/gcd(a,n)$ 的欧拉函数。

欧拉函数 $phi(n)$ ：1-n中与n互质的数的个数。

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
using namespace std;
typedef long long ll;
// 要保持gcd，就不能乘n的因子，但可以乘与n互质的数
ll eular(ll n) {
    ll ret = 1, i;
    for (i = 2; i * i <= n; ++i)
        if (n % i == 0) {
            n /= i, ret *= i - 1;
            while (n % i == 0) n /= i, ret *= i;
        }
    if (n > 1) ret *= n - 1;
    return ret;
}
int main() {
    ll T, a, n;
    sc(T);
    while (T--) {
        sc(a), sc(n);
        pr(eular(n / (__gcd(a, n))));
    }
    return 0;
}

L

线段树维护区间min和sum是板子，没有想到用单调栈维护答案。

先贴个标程，~~明天发自己写的。~~

#include <bits/stdc++.h>
#define ls n<<1
#define rs n<<1|1
#define lson n<<1,l,mid
#define rson n<<1|1,mid+1,r
using namespace std;
const int maxn = 3e6 + 7, mod = 1e9 + 7;
typedef long long ll;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int n, k, a[maxn], b[maxn], st[maxn], top, l[maxn], r[maxn];
ll sum[maxn], c[maxn];
ll t1[maxn * 4], t2[maxn * 4];
void build(int n, int l, int r) {
    if(l == r) {
        t1[n] = t2[n] = c[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(lson); build(rson);
    t1[n] = max(t1[ls], t1[rs]);
    t2[n] = min(t2[ls], t2[rs]);
}
ll getMax(int n, int l, int r, int L, int R) {
    if(L <= l && R >= r) {
        return t1[n];
    }
    int mid = (l + r) >> 1;
    if(R <= mid) return getMax(lson, L, R);
    else if(L > mid) return getMax(rson, L, R);
    else return max(getMax(lson, L, R), getMax(rson, L, R));
}
ll getMin(int n, int l, int r, int L, int R) {
    if(L <= l && R >= r) {
        return t2[n];
    }
    int mid = (l + r) >> 1;
    if(R <= mid) return getMin(lson, L, R);
    else if(L > mid) return getMin(rson, L, R);
    else return min(getMin(lson, L, R), getMin(rson, L, R));
}
int main() {
//    freopen("8.in", "r", stdin);
//    freopen("8.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) b[i] = read(), sum[i] = sum[i - 1] + b[i];
    top = 0;
    for (int i = 1; i <= n; i++) {
        while (top && a[st[top]] >= a[i]) top--;
        l[i] = st[top];
        st[++top] = i;
    }
    top = 0;
    st[0] = n + 1;
    for (int i = n; i >= 1; i--) {
        while (top && a[st[top]] >= a[i]) top--;
        r[i] = st[top];
        st[++top] = i;
    }
    c[1] = 0;
    for (int i = 2; i <= n + 1; i++) c[i] = sum[i - 1];
    n++;
    build(1, 1, n);
    ll ans = -1e18;
    for (int i = 1; i <= n - 1; i++) {
        ll tmp;
        if(a[i] > 0) {
            tmp = getMax(1, 1, n, i + 1, r[i]) - getMin(1, 1, n, l[i] + 1, i);
        }
        else {
            tmp = getMin(1, 1, n, i + 1, r[i]) - getMax(1, 1, n, l[i] + 1, i);
        }
//        printf("i = %d, %lld\n", i, tmp);
        ans = max(ans, 1ll * a[i] * tmp);
    }
    printf("%lld\n", ans);
    return 0;
}