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

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

简单题 挑7

从 到 遍历一遍计数即可。

n = int(input())
ans = 0
for i in range(1, n + 1):
    if i % 7 == 0 or str(i).count('7') > 0:
        ans += 1
print(ans)

中等题 仰望水面的歪

将 沿着平面 作对称点 ，则 ，输出 。
注意数据范围。

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, h;
    cin >> n >> h;
    for (int i = 0; i < n; i++) {
        long long x, y, z;
        cin >> x >> y >> z;
        z = 2 * h - z;
        long long g = gcd(gcd(x, y), z);
        x /= g;
        y /= g;
        z /= g;
        cout << x << ' ' << y << ' ' << z << '\n';
    }
    return 0;
}

困难题 1or0

额……写的很丑陋，见谅。

设 内有 个 ，这些 的位置分别为 。
枚举每个 ，计算所有以这个 作为第 个 的子串数量，这些子串向左可以延伸到没有 的位置，向右可以延伸到 ，这个 所贡献的计数为 。 则自审值 ，其中 为最后一个位置 的 的位置，不存在这个 则 ，这个求和式子可用前缀和或其他数据结构维护。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    string s;
    cin >> s;
    for (int i = 0; i < n; i++)a[i + 1] = s[i] - '0';
    vector<ll> pre1(n + 1), pre2(n + 1), pre3(n + 1);
    set<int> st;
    st.insert(0);
    int tmp = 0;
    for (int i = 1; i <= n; i++) {
        pre1[i] = pre1[i - 1] + (a[i] ? i : 0);
        pre2[i] = pre2[i - 1] + (a[i] ? 1ll * i * i : 0);
        pre3[i] = pre3[i - 1] + (a[i] ? 1ll * tmp * i : 0);
        if (a[i]) {
            st.insert(i);
            tmp = i;
        }
    }
    int q;
    cin >> q;
    for (int _ = 0; _ < q; _++) {
        ll l, r;
        cin >> l >> r;
        if (pre1[r] - pre1[l - 1]) {
            ll a1 = *st.lower_bound(l), an = *(--st.upper_bound(r)), a0 = *(--st.lower_bound(l));
            cout << (-1ll * (pre2[r] - pre2[l - 1]) + an * r - l * r + l * a1 + an - l + r - a1 + 1 + pre3[r] - pre3[l - 1] - a0 * a1) << '\n';
        }
        else cout << 0 << '\n';
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int t=1;cin>>t;while(t--)
    solve();
    return 0;
}