【非官方题解】2022牛客寒假算法基础集训营2

本文主要是介绍【非官方题解】2022牛客寒假算法基础集训营2，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

2022牛客寒假算法基础集训营2_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

A-小沙的炉石

B-小沙的魔法

C-小沙的杀球

D-小沙的涂色

E-小沙的长路

F-小沙的算数

G-小沙的身法

H-小沙的数数

I-小沙的构造

J-小沙的Dota

K-小沙的步伐

L、M-小沙的remake

A-小沙的炉石

原题链接：https://ac.nowcoder.com/acm/contest/23477/A

解题思路：数学题，结论题。首先有个非常重要的点是使用攻击牌是一个定值的话，我们的攻击范围是一个区间上的任意的伤害值。设攻击牌使用 a 次，回复牌使用 b 次（其中暗含了一个条件为 $a \leqslant b + 1$ ），那么最小伤害是先在使用回复牌的基础上将 a 次攻击牌使用完，最后再将回复牌全部用完，造成的伤害为 a^2 ；最大伤害是先将 b 次回复牌全部用完，再使用攻击牌，造成的伤害为 $ab + \frac{a(a + 1)}{2}$ 。对于使用不同攻击牌数量的不同区间，可以计算一下它们什么条件下能合并，也就是令上个区间的右端点大于等于当前区间的左端点减一，即 $(a - 1)b + \frac{a(a - 1)}{2} \geqslant a^2 - 1$ ，将 $a \leqslant b + 1$ 代入，可以解出 $a \geqslant 4,b \geqslant 3$ 时，区间可以合并，那么只需要特判 b = 1,b = 2 时的情况即可：b = 1时，区间分别为 [1, 2]，[4, 5]；b = 2时，区间分别为 [1, 3]，[4, 7]，[9, 12]，可以发现只有当 b = 1 且 x = 3 时和 b = 2 且 x = 8 时不能合并。其它情况下只要 x 小于等于伤害最大值即可斩杀，否则就不能斩杀。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;

int main(){
    //freopen("input.txt", "r", stdin);
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n, m, k;
    cin >> n >> m >> k;
    ll a = min(n, m + 1);
    ll ans = a * m + a * (a + 1) / 2;
    while(k--){
        ll x;
        cin >> x;
        if(m == 1 && x == 3 || m == 2 && x == 8){
            cout << "NO" << endl;
            continue;
        }
        if(x <= ans) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

B-小沙的魔法

原题链接：https://ac.nowcoder.com/acm/contest/23477/B

解题思路：将需要上升较多的城市相关的通道优先加入图中形成极大连通子图（会形成多个极大连通子图），这样每个极大连通子图只需要操作最大上升高度的次数就可以将其中的城市都完成需要上升的高度，由于操作数不够而剩下的城市单独进行操作。具体操作时可以先把每座城市需要上升的高度累加，将有通道的两座城市需要上升的最小高度记录下来并排序。通过并查集的查找和合并来进行操作1，进行合并时将前面累加的数减去两座城市的最小上升高度（因为一个极大连通子图中只需要操作最大上升高度次数）。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 500005, M = 5000005;
int f[M];    // f[i]表示i结点的祖先(f[i] = i表示i为孤立结点)
ll h[N];    // h[i]表示第i座城市需要上升的高度

struct node{
    int x, y;
    int height;
    bool operator < (const node &u) const{
        return height > u.height;
    }
}e[M];

int find(int x){
    if(f[x] != x) f[x] = find(f[x]);
    return f[x];
}

int main(){
    //freopen("input.txt", "r", stdin);
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        cin >> h[i];
        ans += h[i];
        f[i] = i;
    }
    for(int i = 1; i <= m; i++){
        cin >> e[i].x >> e[i].y;
        e[i].height = min(h[e[i].x], h[e[i].y]);
    }
    sort(e + 1, e + m + 1);
    int x = min(5 * n, m);
    for(int i = 1; i <= m; i++){
        if(x == 0) break;
        int a = find(e[i].x), b = find(e[i].y);
        if(a != b){
            ans -= e[i].height;
            f[a] = b;
            x--;
        }
    }
    cout << ans << endl;
    return 0;
}

C-小沙的杀球

原题链接：https://ac.nowcoder.com/acm/contest/23477/C

解题思路：签到题，遇到1的时候判断体力是否够杀球，不够就选择不杀，恢复体力；遇到0的时候恢复体力。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;

int main(){
    //freopen("input.txt", "r", stdin);
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll x, a, b;
    cin >> x >> a >> b;
    string s;
    cin >> s;
    int len = s.size();
    int cnt = 0;
    for(int i = 0; i < len; i++){
        if(s[i] == '1' && x >= a){
            x -= a;
            cnt++;
        }
        else x += b;
    }
    cout << cnt << endl;
    return 0;
}

D-小沙的涂色

原题链接：https://ac.nowcoder.com/acm/contest/23477/D

解题思路：大模拟构造题。根据 n % 3 的值分别为 0，1，2 时进行构造（构造方法很多，下面代码用的其中一种）。注意 n % 3 = 0 时无法满足题意，除此之外还需特判 n == 1 时的情况。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1005;
int n, idx;
int a[N][N];

void draw1(int x, int y){                // 1 1
    for(int i = x; i <= n; i += 3){      // 1 2
        for(int j = y; j <= n; j += 2){  // 2 2
            a[i][j] = a[i][j + 1] = a[i + 1][j] = ++idx;
            a[i + 1][j + 1] = a[i + 2][j] = a[i + 2][j + 1] = ++idx;
        }
    }
}
                                         // 1
void draw2(int x){                       // 1 1 2
    for(int i = x; i <= n; i++){         //   2 2
        if(i & 1) a[i - 1][1] = a[i][1] = a[i][2] = ++idx;
        else a[i - 1][3] = a[i][2] = a[i][3] = ++idx;
    }
}

void draw3(int x, int y){                // 1 1 2
    for(int j = y; j <= n; j += 3){      // 1 2 2
        a[x][j] = a[x][j + 1] = a[x + 1][j] = ++idx;
        a[x][j + 2] = a[x + 1][j + 2] = a[x + 1][j + 1] = ++idx;
    }
}

void pf(){
    cout << "YES" << endl;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cout << a[i][j] << ' ';
        }
        cout << endl;
    }
}

int main(){
    //freopen("input.txt", "r", stdin);
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    if(n % 3 == 0) cout << "NO" << endl;
    else if(n == 1) cout << "YES" << endl << 0 << endl;
    else if(n % 3 == 1){
        idx = 5;
        a[1][1] = a[1][2] = a[2][1] = 1;
        a[4][3] = a[4][4] = a[3][4] = 2;
        a[3][1] = a[3][2] = a[4][2] = 3;
        a[2][2] = a[2][3] = a[3][3] = 4;
        a[1][3] = a[1][4] = a[2][4] = 5;
        draw3(1, 5);
        draw3(3, 5);
        if(n & 1) draw2(5), draw1(5, 4);
        else draw1(5, 1);
        pf();
    }
    else if(n % 3 == 2){
        a[1][1] = a[1][2] = a[2][2] = ++idx;
        draw3(1, 3);
        if(n & 1) draw2(3), draw1(3, 4);
        else draw1(3, 1);
        pf();
    }
    return 0;
}

E-小沙的长路

原题链接：https://ac.nowcoder.com/acm/contest/23477/E

解题思路：结论题，最小值是构造尽可能无环的有向图，这样最多经历每个点一次，路径长度为 n - 1 ；最大值是完全图中删去最短的边数构造欧拉迹（欧拉通路），即只要控制仅有两个结点度数为奇数，其它结点度数为偶数，对于奇数结点的完全图，每条边的度均为偶数，因此最大值即为完全图的边数 $\frac{n(n - 1)}{2}$ ；对于偶数结点的完全图，每条边的度数均为奇数，要控制成欧拉迹必须删去 $\frac{n}{2}$ 条边，变成欧拉迹后还能多走一步，因此最大值为 $\frac{n(n - 1)}{2} - \frac{n}{2} + 1$ 。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;

int main(){
    //freopen("input.txt", "r", stdin);
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin >> n;
    cout << n - 1 << ' ';
    if(n & 1) cout << n * (n - 1) / 2 << endl;
    else cout << n * (n - 1) / 2 - n / 2 + 1 << endl;
    return 0;
}

F-小沙的算数

原题链接：https://ac.nowcoder.com/acm/contest/23477/F

解题思路：由于乘号优先级高，可以将每个加号当作分隔符，分隔成若干个区间，每个区间的值单独预处理出来，再在每次询问中对相应区间的值进行修改，并计算出式子结果输出。（由于数值较大需要取模，除法需要变成乘以它的逆元，减法需要加上模数再进行取模）

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f;
const int mod = 1000000007;
const int N = 1000005;
char s[N];
ll a[N], pa[N], b[N];

ll qmi(ll a, ll b){
    ll res = 1;
    a %= mod;
    while(b){
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x){
    return qmi(x, mod - 2) % mod;
}

int main(){
    int n, q;
    cin >> n >> q;
	cin >> s + 1;
    s[n] = '+';
    for(int i = 1; i <= n; i++) cin >> a[i];
    ll pos = 0, now = 1;
    memset(pa, -1, sizeof pa);
    for(int i = 1; i <= n; i++){
        now = now * a[i] % mod;
        if(s[i] == '+'){
            pa[i] = pos;
            b[pos++] = now;
            now = 1;
        }
        else pa[i] = pos;
    }
    
    ll x, y, ans = 0;
    for(int i = 0; i < pos; i++) ans = (ans + b[i]) % mod;
    
    while(q--){
        cin >> x >> y;
        int pos = pa[x];
        ll tmp = b[pos] * y % mod * inv(a[x]) % mod;
        if(tmp >= b[pos]) ans = (ans + (tmp - b[pos] + mod) % mod) % mod;
        else ans = (ans - (b[pos] - tmp + mod) % mod + mod) % mod;
        a[x] = y;
        b[pos] = tmp;
        cout << ans << endl;
    }
    return 0;
}

G-小沙的身法

原题链接：https://ac.nowcoder.com/acm/contest/23477/G

解题思路：LCA算法，树上差分思想。将树用邻接表存储（双向），通过dfs将每个结点由上到下的前缀和、由下到上的前缀和都存储起来（设由下到上用 $sum[\cdot][0]$ 存储，由上到下用 $sum[\cdot][1]$ 存储）。那么总体力消耗为从地面跳到起始点 u 的消耗加上 u 从下到 u 和 v 的最小公共祖先结点的消耗再加上从 u 和 v 的最小公共祖先结点到 v 结点的消耗，即 ans = a[u] + (sum[u][0] - sum[lca(u, v)][0]) + (sum[v][1] - sum[lca(u, v)][1]) 。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1000005, M = 2000005;
int a[N], h[N], e[M], ne[M], idx;
int fa[N][20], deep[N];    // fa[i][j]表示i结点的第2^j级祖先
ll sum[N][2];    // sum[i][0]表示i结点向祖先结点跳（由下到上）的前缀和
                 // sum[i][1]表示i结点的父结点向i结点跳（由上到下）的前缀和

void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u, int f){
    fa[u][0] = f;
    deep[u] = deep[f] + 1;
    sum[u][0] = sum[f][0] + max(0, a[f] - a[u]);
    sum[u][1] = sum[f][1] + max(0, a[u] - a[f]);
    for(int i = 1; i < 20; i++){
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for(int i = h[u]; i != -1; i = ne[i]){
        int v = e[i];
        if(v != f) dfs(v, u);
    }
}

int lca(int x, int y){
    if(deep[x] < deep[y]) swap(x, y);
    for(int i = 19; i >= 0; i--){
        if(deep[fa[x][i]] >= deep[y]){
            x = fa[x][i];
        }
    }
    if(x == y) return y;
    for(int i = 19; i >= 0; i--){
        if(fa[x][i] != fa[y][i]){
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

int main(){
    //freopen("input.txt", "r", stdin);
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    dfs(1, 0);
    while(m--){
        int u, v;
        cin >> u >> v;
        cout << a[u] + sum[u][0] + sum[v][1] - sum[lca(u, v)][0] - sum[lca(u, v)][1] << endl;
    }
    return 0;
}

H-小沙的数数

原题链接：https://ac.nowcoder.com/acm/contest/23477/H

解题思路：根据二进制拆分，将拆分成每一位只有 0 或 1，要想 a[+] = m 且 $a[\oplus]$ 最大，就要保证每个数在同一个二进制位只能有一个 1，即保证 $a[\oplus] = a[+] = m$ 。然后由于每一位都不互相干扰，所以可能产生的情况为种，设二进制下有 cnt 个 1，则总方案数为 $n^{cnt}$ 种。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;

ll quick_pow(ll a, ll b){
    ll res = 1;
    a %= mod;
    while(b){
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main(){
    //freopen("input.txt", "r", stdin);
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n, m;
    cin >> n >> m;
    ll cnt = 0;
    while(m){
        if(m & 1) cnt++;
        m >>= 1;
    }
    cout << quick_pow(n, cnt) << endl;
    return 0;
}

I-小沙的构造

原题链接：https://ac.nowcoder.com/acm/contest/23477/I

解题思路：细节较多的模拟题。由于前25个字符是单独对称的，使用两个相同字符时只用了一种，而后10个字符是配套对称的，使用一对字符时用了两种。还需注意为奇数和偶数时的写法不同，并且注意不成立时的条件特判。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
string s = "\"!'*+-.08:=^_WTYUIOAHXVM|", l = "<\\[{(", r = ">/]})", ans;

int main(){
    //freopen("input.txt", "r", stdin);
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    if(n == m && n == 1) cout << s[24];
    for(int i = 0; i < 5; m -= 2, i++){
        if(m <= 2 && (n & 1 || m <= 1)) break;
        ans = l[i] + ans + r[i];
    }
    for(int i = 0; i < 24; m--, i++){
        if(m <= 1) break;
        ans = s[i] + ans + s[i];
    }
    if(ans.size() >= n || m > 1) cout << -1;
    else{
        while(ans.size() + 2 <= n)
            if(m == 1) ans = s[24] + ans + s[24];
            else ans = l[0] + ans + r[0];
        if(n & 1){
            for(int i = 0; i < n - 1; i++){
                if(i == n / 2) cout << s[24];
                cout << ans[i];
            }
        }
        else cout << ans;
    }
    return 0;
}

J-小沙的Dota

原题链接：https://ac.nowcoder.com/acm/contest/23477/J

解题思路：对于不同的技能施放所需要的三颗法球不同，可以列表存储。由于需要进行的两种操作分别为放技能（区间查询）和改手法（定点修改），且数据量不小，可以通过线段树维护DDP来实现。由于施放技能只与法球属性有关，与顺序无关，因此每个技能三颗法球就有最多 6 种排列方式，可以使用 next_permutation() 进行全排列。在操作前预处理好每个技能之间的关系存入 M[i][j].c[x][y] （表示第i个技能的第x种排列和第j个技能的第y种排列的关系）中，取值0，1，2，3的含义参考下面代码。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 100005;
int a[N];

int skill[10][3] = {    // 1代表火球，2代表雷球，3代表冰球
    {1, 1, 1}, {1, 1, 2}, {1, 1, 3},
    {3, 3, 3}, {3, 3, 1}, {3, 3, 2},
    {2, 2, 2}, {2, 2, 1}, {2, 2, 3}, {1, 2, 3}
};

struct Matrix{    // 矩阵
    int c[6][6];
    Matrix(){
        for(int i = 0; i < 6; i++)
            for(int j = 0; j < 6; j++)
                c[i][j] = ((i == j) ? 0 : INF);
    }
}M[10][10];

Matrix operator * (Matrix A, Matrix B){    // 矩阵乘法重载
    Matrix C;
    for(int i = 0; i < 6; i++){
        for(int j = 0; j < 6; j++){
            C.c[i][j] = INF;
            for(int k = 0; k < 6; k++){
                C.c[i][j] = min(C.c[i][j], A.c[i][k] + B.c[k][j]);
            }
        }
    }
    return C;
}

struct sgt_tree{    // 线段树结点
    int lchild, rchild;
    Matrix v;
}sgt[4 * N];

int root, topt;
void sgt_build(int &now, int l, int r){    // 线段树建立
    if(!now) now = ++topt;
    if(l == r){
        sgt[now].v = M[a[l]][a[l + 1]];
        return;
    }
    int mid = l + r >> 1;
    sgt_build(sgt[now].lchild, l, mid);
    sgt_build(sgt[now].rchild, mid + 1, r);
    sgt[now].v = sgt[sgt[now].lchild].v * sgt[sgt[now].rchild].v;
}

void sgt_modify(int &now, int l, int r, int k){    // 线段树修改
    if(!now) now = ++topt;
    int mid = l + r >> 1;
    if(l == r){
        sgt[now].v = M[a[l]][a[l + 1]];
        return;
    }
    if(k <= mid) sgt_modify(sgt[now].lchild, l, mid, k);
    else sgt_modify(sgt[now].rchild, mid + 1, r, k);
    sgt[now].v = sgt[sgt[now].lchild].v * sgt[sgt[now].rchild].v;
}

Matrix res;
void sgt_query(int &now, int l, int r, int x, int y){    // 线段树查询
    if(!now) now = ++topt;
    int mid = l + r >> 1;
    if(l >= x && r <= y){
        res = res * sgt[now].v;
        return;
    }
    if(x <= mid) sgt_query(sgt[now].lchild, l, mid, x, y);
    if(y > mid) sgt_query(sgt[now].rchild, mid + 1, r, x, y);
}

int main(){
    //freopen("input.txt", "r", stdin);
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i]--;
    }
    
    // 预处理不同技能之间的关系
    int s1[3], s2[3];
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            for(int k = 0; k < 3; k++){
                s1[k] = skill[i][k];
                s2[k] = skill[j][k];
            }
            for(int x = 0; x < 6; x++){
                for(int y = 0; y < 6; y++){
                    if(s1[0] == s2[0] && s1[1] == s2[1] && s1[2] == s2[2]) M[i][j].c[x][y] = 0;
                    else if(s1[1] == s2[0] && s1[2] == s2[1]) M[i][j].c[x][y] = 1;
                    else if(s1[2] == s2[0]) M[i][j].c[x][y] = 2;
                    else M[i][j].c[x][y] = 3;
                    next_permutation(s2, s2 + 3);
                }
                next_permutation(s1, s1 + 3);
            }
        }
    }
    sgt_build(root, 1, n - 1);
    
    int op, l, r;
    while(m--){
        cin >> op >> l >> r;
        if(op == 1){
            if(l == r){
                cout << 3 << endl;
                continue;
            }
            Matrix zero;
            res = zero;    // 初始化res矩阵
            sgt_query(root, 1, n - 1, l, r - 1);
            int ans = INF;
            for(int i = 0; i < 6; i++){
                for(int j = 0; j < 6; j++){
                    ans = min(ans, res.c[i][j]);
                }
            }
            cout << ans + 3 << endl;
        }
        if(op == 2){
            a[l] = r - 1;
            if(l != 1) sgt_modify(root, 1, n - 1, l - 1);
            if(l != n) sgt_modify(root, 1, n - 1, l);
        }
    }
    return 0;
}

K-小沙的步伐

原题链接：https://ac.nowcoder.com/acm/contest/23477/K

解题思路：签到题，每走一步都会使那个点和5这个点都经过一次（既要过去又要回来），注意特判当出现的是5时，不需要任何移动。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int cnt[10];

int main(){
    //freopen("input.txt", "r", stdin);
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s;
    cin >> s;
    int n = s.size();
    for(int i = 0; i < n; i++){
        if(s[i] != '5'){
            cnt[s[i] - '0']++;
            cnt[5]++;
        }
    }
    for(int i = 1; i < 9; i++)
        cout << cnt[i] << ' ';
    cout << cnt[9] << endl;
    return 0;
}

L、M-小沙的remake

普通版原题链接：https://ac.nowcoder.com/acm/contest/23477/L

竞速版原题链接：https://ac.nowcoder.com/acm/contest/23477/M

解题思路：树状数组维护动态前缀和。先按照气运值排序，然后遍历一遍气运，每次求当前点和当前点前 b_i 位的区间和，并将该值加入到当前位下标的树状数组中进行更新。最后对 n 进行查询查询结果即为要求的方案数。

AC代码：

#include<bits/stdc++.h>
namespace GenHelper
{
    int z1,z2,z3,z4,z5,u,res;
    int get()
    {
        z5=((z1<<6)^z1)>>13;
        z1=((int)(z1&4294967)<<18)^z5;
        z5=((z2<<2)^z2)>>27;
        z2=((z2&4294968)<<2)^z5;
        z5=((z3<<13)^z3)>>21;
        z3=((z3&4294967)<<7)^z5;
        z5=((z4<<3)^z4)>>12;
        z4=((z4&4294967)<<13)^z5;
        return (z1^z2^z3^z4);
    }
    int read(int m) {
        u=get();
        u>>=1;
        if(m==0)res=u;
        else res=(u/2345+1000054321)%m;
        return res;
    }
     void srand(int x)
    {
        z1=x;
        z2=(~x)^(0x23333333);
        z3=x^(0x12345798);
        z4=(~x)+51;
      	u = 0;
    }
}
using namespace GenHelper;
using namespace std;
typedef long long ll;
const int N=2e6+7,mod=1e9+7;
int a[N],b[N];

ll tree[N];
struct node{
    int id, x;
    bool operator < (const node &u) const{
        return x == u.x ? id < u.id : x < u.x;
    }
}s[N];

inline int lowbit(int x){
    return x & -x;
}

void add(int x, ll c){
    while(x < N){
        tree[x] = (tree[x] + c) % mod;
        x += lowbit(x);
    }
}

ll ask(ll x){
    ll res = 0;
    while(x){
        res = (res + tree[x]) % mod;
        x -= lowbit(x);
    }
    return res;
}

int main(){
    int n,seed;
    scanf("%d %d",&n,&seed);
    srand(seed);
    for(int i=1;i<=n;i++){
        a[i]=read(0),b[i]=read(i);
        s[i].id = i, s[i].x = a[i];
    }
    sort(s + 1, s + n + 1);
    for(int i = 1; i <= n; i++){
        int id = s[i].id;
        ll x = (ask(id - 1) - ask(id - b[id] - 1) + 1 + mod) % mod;
        add(id, x);
    }
    printf("%lld\n", ask(n));
    return 0;
}

这篇关于【非官方题解】2022牛客寒假算法基础集训营2的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

【非官方题解】2022牛客寒假算法基础集训营2

A-小沙的炉石

B-小沙的魔法

C-小沙的杀球

D-小沙的涂色

E-小沙的长路

F-小沙的算数

G-小沙的身法

H-小沙的数数

I-小沙的构造

J-小沙的Dota

K-小沙的步伐

L、M-小沙的remake

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯