牛客习题

小红的red计数

题目描述：
    小红拿到了一个字符串。她有若干次询问，每次询问：若翻转第 l 个字符到第 r 个字符对应的区间，该字符串有多少“red”子序列。子序列指按照原顺序取若干字符（可以不连续）形成的新字符串。每次询问后小红并不会真正翻转区间。

输入描述：
    第一行输入两个整数 n 和 q，代表字符串长度和询问次数。
    第二行输入一个长度为 n 的，仅由小写字母组成的字符串。
    接下来的 q 行，每行输入两个整数 l 和 r，代表一次询问。

输出描述：
    输出 q 行，每行输出一个整数，代表询问的答案。

输入格式：

  • 第1行：两个整数 n, q，表示字符串长度和询问次数。
  • 第2行：一个仅由小写字母组成的字符串，长度为 n。
  • 接下来的 q 行：每行两个整数 l, r，表示询问的区间。

输出格式：

  • 输出 q 行，每行一个整数，表示该区间中翻转后的“red”子序列的个数。

数据范围：

  • 1 ≤ n, q ≤ $10^5$
  • 1 ≤ l ≤ r ≤ n

示例:
    输入：

1
2
3
4
6 2
rreedd
1 2
1 6

    输出：

1
2
8
0

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
#define i64 long long
// 主要的解决函数
void solve()
{
    i64 n, q;           // n 表示字符串长度，q 表示询问次数
    std::cin >> n >> q; // 输入 n 和 q
    std::string s;
    std::cin >> s; // 输入字符串
    s = ' ' + s;   // 将字符串首位填充一个空格，方便使用1-based索引

    // 定义各类前缀和数组，用于存储不同子序列的计数
    std::vector<i64> prer(n + 1), pred(n + 1), pree(n + 1);                  // 分别存储 r, e, d 的前缀和
    std::vector<i64> prere(n + 1), preer(n + 1), preed(n + 1), prede(n + 1); // 分别存储 re, er, ed, de 的前缀和
    std::vector<i64> prered(n + 1), preder(n + 1);                           // 分别存储 red 和 der 的前缀和

    // 遍历字符串，计算所有前缀和
    for (i64 i = 1; i <= n; i++)
    {
        if (s[i] == 'r') // 当前字符是 'r'
        {
            prer[i] += 1;              // 记录 'r' 的前缀和
            preer[i] += pree[i - 1];   // 'er' 需要前面有 'e'
            preder[i] += prede[i - 1]; // 'der' 需要前面有 'de'
        }
        else if (s[i] == 'e') // 当前字符是 'e'
        {
            pree[i] += 1;            // 记录 'e' 的前缀和
            prere[i] += prer[i - 1]; // 're' 需要前面有 'r'
            prede[i] += pred[i - 1]; // 'de' 需要前面有 'd'
        }
        else if (s[i] == 'd') // 当前字符是 'd'
        {
            pred[i] += 1;              // 记录 'd' 的前缀和
            preed[i] += pree[i - 1];   // 'ed' 需要前面有 'e'
            prered[i] += prere[i - 1]; // 'red' 需要前面有 're'
        }

        // 将之前的前缀和累加到当前位置
        prer[i] += prer[i - 1];
        pree[i] += pree[i - 1];
        pred[i] += pred[i - 1];
        prere[i] += prere[i - 1];
        preer[i] += preer[i - 1];
        preed[i] += preed[i - 1];
        prede[i] += prede[i - 1];
        prered[i] += prered[i - 1];
        preder[i] += preder[i - 1];
    }

    // 以下几个 lambda 函数用于计算从 l 到 r 区间内的前缀和
    auto sumr = [&](i64 l, i64 r) -> i64
    {
        return prer[r] - prer[l - 1];
    };

    auto sume = [&](i64 l, i64 r) -> i64
    {
        return pree[r] - pree[l - 1];
    };

    auto sumd = [&](i64 l, i64 r) -> i64
    {
        return pred[r] - pred[l - 1];
    };

    auto sumre = [&](i64 l, i64 r) -> i64
    {
        return prere[r] - prere[l - 1];
    };

    auto sumer = [&](i64 l, i64 r) -> i64
    {
        return preer[r] - preer[l - 1];
    };

    auto sumed = [&](i64 l, i64 r) -> i64
    {
        return preed[r] - preed[l - 1];
    };

    auto sumde = [&](i64 l, i64 r) -> i64
    {
        return prede[r] - prede[l - 1];
    };

    auto sumred = [&](i64 l, i64 r) -> i64
    {
        return prered[r] - prered[l - 1];
    };

    auto sumder = [&](i64 l, i64 r) -> i64
    {
        return preder[r] - preder[l - 1];
    };

    // 处理每次询问
    while (q--)
    {
        i64 l, r;
        std::cin >> l >> r; // 输入询问的区间

        // 计算子区间中“red”和“der”子序列的数量
        i64 num = sumr(1, l - 1) * sumde(l, r) - sumr(1, l - 1) * sumed(l, r) - sumred(l, r) + sumder(l, r) - sumre(l, r) * sumd(r + 1, n) + sumer(l, r) * sumd(r + 1, n);

        // 输出结果
        std::cout << num + prered[n] << '\n';
    }
}

int main()
{
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; // 测试次数
    // std::cin >> t; // 如果有多组测试数据，可以解除这行注释
    while (t--)
    {
        solve(); // 运行解决方案
    }
}

小红的字符串重排

题目描述：

小红拿到了一个仅由小写字母组成的字符串，她希望你能重排这个字符串，使得每个对应位置的字符和重排前都不相同。你能帮帮她吗？

输入描述：

一个仅由小写字母组成的字符串。长度不超过$10^5$。

输出描述：

如果无解，请输出-1。否则输出任意合法字符串。

示例1:
    输入：

1
aba

输出：

1
-1

示例1:
    输入：

1
abbc

输出：

1
bcab

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// Problem: 小红的字符串重排
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/92662/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e5 + 5;

int n;
string s;
vector<int> h[N];

void solve()
{
    cin >> s;
    n = s.size();
    for (int i = n - 1; i >= 0; i--) {
        h[s[i]].push_back(i);
    }
    vector<array<int, 2>> all;
    for (int i = 'a'; i <= 'z'; i++) {
        if (h[i].size()) {
            if (h[i].size() * 2 > n) {
                cout << "-1\n";
                return;
            }
            all.push_back({ h[i].size(), i });
        }
    }
    vector<int> pre, can;
    sort(all.begin(), all.end());
    int t = 0;
    for (auto it : all) {
        int id = it[1];
        vector<int> tmp;
        while (h[id].size()) {
            if (pre.size()) {
                int x = pre.back();
                int y = h[id].back();
                swap(s[x], s[y]);
                pre.pop_back();
                h[id].pop_back();
                tmp.push_back(x);
                tmp.push_back(y);
            } else
                break;
        }
        while (h[id].size()) {
            if (can.size()) {
                int x = can.back();
                int y = h[id].back();
                swap(s[x], s[y]);
                can.pop_back();
                h[id].pop_back();
                tmp.push_back(x);
                tmp.push_back(y);
            } else
                break;
        }
        for (int i : tmp) {
            can.push_back(i);
        }
        for (int i : h[id]) {
            pre.push_back(i);
        }
    }
    cout << s;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

小红与小紫的博弈游戏

题目描述：

    小红和小紫拿到了一个2∗2的矩阵，她们准备在这个矩阵上玩一个博弈游戏。
    游戏的规则是：两人轮流操作，每次操作时选择两个相邻的正整数，使它们同时减1。谁先无法操作谁就输了。
    小红先手操作，她想知道，两人都使用最优策略的情况下，谁将获得最终胜利？

输入描述：

    第一行输入一个正整数t，代表询问次数。

    接下来的2∗t行，每两行分别输入两个整数$a_{ij}$​，代表一次询问的初始矩阵。
$1\leq t \leq 10^4$
$0 \leq a_{ij} \leq 10^9$

输出描述：

    如果小红获胜，则输出”kou”。否则输出”yukari”。

示例1:
    输入：

1
2
3
4
5
2
0 0
0 1
1 0
1 0

输出：

1
2
yukari
kou
a b
c d

由题目要求可知，需要将矩阵内的元素操作为0，对于任意一个点（设其大于相邻元素），只有当他相邻元素都为0后便不再进行操作，又此可知，最多的操作量即为$min(a+d,b+c)$，由此可推得当最小值为奇数则输出”kou”，反之输出”yukari”。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    long long t;
    cin >> t;
    while (t--)
    {
        long long a, b, c, d;
        cin >> a >> b >> c >> d;
        long long min_vul = min(a + d, b + c);
        if (min_vul % 2 == 0)
        {
            cout << "yukari" << endl;
        }
        else
        {
            cout << "kou" << endl;
        }
    }
}

医生

题目描述：

    现在小红对于每个病人的症状用一个长度为m的01串表示，第i个字符代表第i个身体部位的症状，0代表健康，1代表不健康。
    一共有kkk种药，每种药也用一个长度为m的01串表示，第i个字符为’1’代表该药可以治愈第i个部位的症状。
    对于每个病人，请你帮小红求出治愈该病人需要开的最少的药数量。

输入描述：

    第一行输入两个正整数n，m,代表病人数量和症状种类数。
    接下来的n行，每行输入一个长度为m的01串，代表每个病人的症状情况。
    接下来一行输入一个正整数k，代表药物的数量。
    接下来的k行，每行输入一个长度为m的01串，代表每个药物可以治愈的症状情况。

$1\leq m\leq 20$

$1\leq n\leq 10^4$

$1\leq k\leq 10$

输出描述：

    输出n行，每行输出治愈该病人所需的最小药物数量。特殊的，如果该病人无法被治愈，请输出-1。

示例1:
    输入：

1
2
3
4
5
6
7
3 4
1000
0101
1011
2
1001
0011

输出：

1
2
3
1
-1
2

    遍历所有药物的组合情况$2^k$次，再判断是否能够治愈找到其中最少的药物数量。

如何判断能否治愈：

    对所有药物的组合进行|运算再将这个结果与病人的病情进行&运算，判断运算的结果是否等于病人的病情。|运算可以展示该组合所能治愈的位置，而对病人的病情进行&运算则是查看该组合是否包含病人的病情。

如何遍历所有的组合：

    可知所有药物的组合情况为$2^k$,可以设一个数mask从1遍历到$2^k$表示遍历所有的组合情况,mask=2表示10，即为只有第二种药的组合情况，在每一次的遍历里我们遍历从1~k分别查看该次遍历在这些位上有无1if (mask & (1 << j))

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> patients(n);

    for (int i = 0; i < n; ++i) {
        string symptoms;
        cin >> symptoms;
        int symptom_mask = 0;
        for (int j = 0; j < m; ++j) {
            if (symptoms[j] == '1') {
                symptom_mask |= (1 << j);
            }
        }
        patients[i] = symptom_mask;
    }

    int k;
    cin >> k;
    vector<int> medicines(k);

    for (int i = 0; i < k; ++i) {
        string cure;
        cin >> cure;
        int cure_mask = 0;
        for (int j = 0; j < m; ++j) {
            if (cure[j] == '1') {
                cure_mask |= (1 << j);
            }
        }
        medicines[i] = cure_mask;
    }

    for (int i = 0; i < n; ++i) {
        if (patients[i] == 0) {
            cout << 0 << endl;
            continue;
        }

        int min_meds = INT_MAX;
        bool can_cure = false


        int num_combinations = (1 << k);
        for (int mask = 1; mask < num_combinations; ++mask) {
            int combined_cure = 0;
            int meds_used = 0;
			//mask以二进制表示药物组合，mask=2，表示10，即只有第二种药物的情况
            for (int j = 0; j < k; ++j) {
                if (mask & (1 << j)) {  // 如果组合中包含第 j 种药物
                    combined_cure |= medicines[j];
                    meds_used++;
                }
            }

            if ((combined_cure & patients[i]) == patients[i]) {
                can_cure = true;
                min_meds = min(min_meds, meds_used);
            }
        }

        if (!can_cure) {
            cout << -1 << endl;
        } else {
            cout << min_meds << endl;
        }
    }

    return 0;
}

小苯的能量项链

题目描述：

链接：https://ac.nowcoder.com/acm/contest/97017/D
来源：牛客网

小苯有一个含有 n 颗珠子的“能量项链”，珠子排成一排，其中第i颗珠子的能量为 $a_i$。

但是这个项链并不稳定，如果项链的珠子个数不少于 3个，则它即将发生“崩坏”，即：除了第一颗珠子和最后一颗珠子以外的其余所有珠子都将销毁，最终只留下第一颗和最后一颗珠子。

小苯现在希望项链在“崩坏”后保留尽可能多的能量，为此他可以在崩坏前执行以下的操作：

  • 去掉项链的第一颗珠子（也就意味着项链原本的第二颗珠子将会变成第一颗）。

  • 去掉项链的最后一颗珠子（也就意味着项链原本的倒数第二颗珠子将会变成最后一颗）。

    两种操作各自均需要花费1 秒时间，而现在距离项链发生“崩坏”仅剩 k秒，小苯想知道，他最多可以保留住多少能量，请你帮他算一算吧。

输入描述：

每个测试文件内都包含多组测试数据。

第一行一个正整数 $ T (1≤T≤1000)$，表示测试数据的组数。

接下来对于每组测试数据，输入包含两行。

第一行两个整数 $n, k\ (1 \leq n \leq 5 \times 10^5, 0 \leq k \leq 10^9)$，表示项链的珠子个数和距离项链“崩坏”的时间。
第二行 n 个正整数 $a_i\ (1 \leq a_i \leq 10^9)$，表示每颗珠子的能量。

（保证所有测试数据中 n的总和不超过 $5 \times 10^5$。）

输出描述：

对于每一组测试数据，输出一行一个整数表示小苯能保留的最大能量。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500005;
int n,k,a[N],ansl[N],ansr[N];
int T,ans;
int mx[N];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>T;
    while(T--)
    {
        ans=0;
        cin>>n>>k;
        mx[n+1]=0;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=n;i>=1;i--)mx[i]=max(mx[i+1],a[i]);
        if(n==2)
        {
            cout<<a[1]+a[2]<<endl;
            continue;
        }
        else if(n==1)
        {
            cout<<a[1]<<endl;
            continue;
        }
        for(int i=1;i<=min(n-1,k+1);i++)
        {
            int m=k-(i-1);
            int r=n-k+(i-1);
            ans=max(ans,a[i]+mx[max(i+1,r)]);
        }
        cout<<ans<<endl;
    }
    
    return 0;
}

[小苯的最短路径](E-小苯的最短路_牛客周赛 Round 70)

链接：https://ac.nowcoder.com/acm/contest/97017/E
来源：牛客网

题目描述

​ 小苯有一个 n 个点的无向完全图，编号从 1 到 n，其中 i 号点和 j 号点之间的边权为$i \oplus j$。

​ 他想知道从 1号点出发到达所有点的最短路，请你帮他算一算吧。（其中 $\oplus$ 表示按位异或运算。）

​ （但为了避免输出数据量过大，你只需要输出到达所有点的最短路的异或和即可。）

输入描述:

本题含有多组测试数据。
第一行一个正整数 $T\ (1 \leq T \leq 10^5)T$，表示测试数据的组数。
接下来 TTT 行，每行一个正整数$n\ (1 \leq n \leq 10^9)$ 表示完全图的点数。

输出描述:

对于每组测试数据，输出包含一行一个正整数 s，表示到所有点的最短路的异或和，即：令$d_i$表示从 1 到 i 号点的最短路，则$S=d_1 \oplus d_2 \oplus d_3 \oplus \cdots \oplus d_n$。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll xor_1_to_n(ll n) {
    ll res = 0;
    if (n % 4 == 0)
        res = n;
    else if (n % 4 == 1)
        res = 1;
    else if (n % 4 == 2)
        res = n + 1;
    else
        res = 0;
    return res;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;
        ll a = (n - 1) % 2;
        ll xor_n = xor_1_to_n(n);
        ll xor_1 = xor_1_to_n(1);
        ll result = a ^ (xor_n ^ xor_1);
        cout << result << endl;
    }
}
exercise > acm
#算法练习
牛客习题
http://2819461143wp.github.io/牛客习题/
作者
cwdp.sky
发布于
2024年10月14日
许可协议