牛客春招刷题训练营-2025.03.26题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 截取字符串

按照题意模拟即可。

print(input()[0:int(input())])

中等题 矩阵乘法

按照题意计算即可。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int x, y, z;
    cin >> x >> y >> z;
    vector<vector<int>> a(x, vector<int>(y));
    vector<vector<int>> b(y, vector<int>(z));
    vector<vector<int>> c(x, vector<int>(z));
    for (int i = 0; i < x; i++)
        for (int j = 0; j < y; j++)
            cin >> a[i][j];
    for (int i = 0; i < y; i++)
        for (int j = 0; j < z; j++)
            cin >> b[i][j];
    for (int i = 0; i < x; i++)
        for (int j = 0; j < z; j++)
            for (int k = 0; k < y; k++)
                c[i][j] += a[i][k] * b[k][j];
    for (int i = 0; i < x; i++)
        for (int j = 0; j < z; j++)
            cout << c[i][j] << " \n"[j == z - 1];
    return 0;
}

困难题 小红的01子序列构造（easy）

原题链接

双指针。
设左右端点分别为 ， 内 的个数为 ， 的个数为 ， 子序列的个数为 。

• 如果 等于 ，直接输出答案并退出程序。
• 如果 小于 ，则 向右移动 。
  • 如果移动后的右端点为 ，则 。
  • 如果移动后的右端点为 ，则 。
• 如果 大于 ，则 向右移动 。
  • 如果移动后的右端点为 ，则 。
  • 如果移动前的左端点为 ，则 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ll n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    ll cnt0 = 0, cnt1 = 0;
    int l = 0, r = -1;
    ll ans = 0;
    while (r < n) {
        if (ans < k) {
            r++;
            if (s[r] == '0') {
                cnt0++;
            } else {
                ans += cnt0;
                cnt1++;
            }
        } else if (ans == k) {
            cout << l + 1 << " " << r + 1 << "\n";
            return 0;
        } else {
            if (s[l] == '0') {
                ans -= cnt1;
                cnt0--;
            } else {
                cnt1--;
            }
            l++;
        }
    }
    cout << -1;
    return 0;
}