基础算法补题

Tepley · 2025-02-11 15:15:10 · 个人记录

四道题，总分四百，赛时一共拿了30 + 0 + 0 + 0 = 30分

第一题

第一题的话是一道签到题，就是一道纯递归的题，但是由于那恶心的范围，导致使用递归TLE了.赛后发现只需要加一个记忆化搜索就行了(其实赛时也想到了，但是不会写)

这是数据范围 1 \le N \le 10^6, 1 \le a_i, b_i, c_i \le 300(但凡是个人都知道递归过不了) 非常神奇，赛后提交居然过不了了只有 50pts

#define _CRT_SECURE_NO_WARNINGS 1 //这行是我用的VS2022不支持scanf加的
#include <bits/stdc++.h>
using namespace std;
long long N, mod = 1e9 + 7;
bool vis[309][309][309];
long long ans[309][309][309];

long long f(long long a, long long b, long long c) {
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    if (vis[a][b][c] == 1) //记录f(a, b, c)有没有被计算过
        return ans[a][b][c]; //记录过直接返回
    ans[a][b][c] = (f(a - 1, b, c) + f(a, b - 1, c) + f(a, b, c - 1)) % mod; //需要计算f(a, b, c)
    vis[a][b][c] = 1; //标记f(a, b, c)计算过
    return ans[a][b][c];
}

int main() {
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    while (N--) {
        long long a, b, c; cin >> a >> b >> c;
        cout << f(a, b, c) % mod << endl;
    }
    return 0;
}

第二题

这道题我赛时的话是暴力，枚举每一条路和每一个盔甲是否满足条件即可。

它的部分分(20pts)是 0 \le k_{i,j},也就是它只会对盔甲加生命值，这时候只需要枚举最小生命值的盔甲即可

正解：

使用二分法。

设res = 0, 模拟盔甲受到k_{i, j}的收益， 当积累到res时，最小的绝对值一定是res + 1就是盔甲的最小生命值。二分查找合法盔甲即可。

核心代码

void solve() {
    sort(h.begin(), h.end()); // 二分的条件:单调 -> 对盔甲进行升序排列
    long long i = 1;
    while (i <= t) {
        long long res = 0, ans = 0;
        while (m[i]--) {
            long long tmp; cin >> tmp;
            res += tmp; // res累加k_{i, j}
            ans = min(ans, res);
        }
        ans = abs(ans) + 1; // |ans| + 1 是盔甲最小的生命值
        long long pl = lower_bound(h.begin(), h.end(), ans) - h.begin();
        if (h[pl] != *h.end()) // 只要不是最后一个 -> 有解
            cout << h[pl] << endl;
        else 
            cout << "-1" << endl;
        ++i;
    }
}

第三题

赛时的时候是想用DFS做的，但是死活调不出来。它的正解我确实没想出来，主要是因为它的E不知道怎么求。

正解：

题目给了一个例子：111111的E值是123321，这个E值是怎么算出来的呢？

首先看第2个1，它的左边有一个1,距离为|2 - 1| + 1 = 2, 虽然右边有四个1，但是以第二个为中心，左边只扩展了一个，所以右边也只能扩展一个，所以距离也是2.

我们再来构造一个奇数的序列：00000的E值是12321，这是我们发现一个规律：当序列为偶数时，中间有2个最大数；奇数时只有一个。也就是说我们的E值是可以直接构造出来的。比如111000011111，它的E值可以分为三个部分构造。

所以这个序列的E值为121122112321。这样我们就可以在O(n)的复杂度里构造出来E值，而是O(n^2)的复杂度。

思路：根据不同连续子串的长度分类讨论构造出E值，最后加一个前缀和预处理即可。

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll n, m, pre[1000009];
vector<ll> sum;
string s;

void init() {
    cin >> n >> m >> s;
    s = "s" + s; // 下标从1开始
    return;
}

void ini() {
    ll i = 1, cnt0 = 0, cnt1 = 0; // cnt0 -> 连续0的子串, cnt1 -> 连续1的子串
    sum.push_back(0); // 下标从1开始
    while (i <= n) {
        if (s[i] == '0')
            cnt0++; // 连续0的数量
        else 
            cnt1++; // 连续1的数量
        // 连续的一段结束
        if (i != 1 && s[i] != s[i - 1]) {
            ll j = 1;
            // 构造
            if (s[i] == '0') {
                while (j < (cnt1 + 1) / 2) sum.push_back(j), ++j;
                if (cnt1 % 2 == 0 && cnt1 != 0) sum.push_back(j);
                while (j) sum.push_back(j), --j;
                cnt1 = 0;
            }
            else {
                while (j < (cnt0 + 1) / 2) sum.push_back(j), ++j;
                if (cnt0 % 2 == 0 && cnt0 != 0) sum.push_back(j);
                while (j) sum.push_back(j), --j;
                cnt0 = 0;
            }
        }
        // 到达末尾结束
        if (i == n) {
            ll j = 1;
            // 构造
            if (s[i] == '0') {
                while (j < (cnt0 + 1) / 2) sum.push_back(j), ++j;
                if (cnt0 % 2 == 0 && cnt0 != 0) sum.push_back(j);
                while (j) sum.push_back(j), --j;
                cnt0 = 0;
            }
            else {
                while (j < (cnt1 + 1) / 2) sum.push_back(j), ++j;
                if (cnt1 % 2 == 0 && cnt1 != 0) sum.push_back(j);
                while (j) sum.push_back(j), --j;
                cnt1 = 0;
            }
        }
        ++i;
    }
    i = 1;
    // 前缀和
    while (i <= n) {
        if (s[i] == '1') sum[i] = sum[i] * sum[i] * sum[i] % mod;
        else sum[i] = sum[i] * sum[i] % mod;
        pre[i] = (sum[i] + pre[i - 1]) % mod;
        ++i;
    }
    return;
}

void solve() {
    init();
    ini();
    while (m--) {
        ll l, r; cin >> l >> r;
        // 相减的时侯    取余先 + mod % mod
        cout << (pre[r] - pre[l - 1] + mod) % mod << endl;
    }
    return;
}

int main() {
    solve();
    return 0;
}

第四题

赛时的话我是想暴力枚举每个区间和再排序。但是由于时间不够了，没敲完。 结束之后，看了正解，它的思路的话是：直接寻找一个数值等于所有子区间的区间和，从小到大排序后的第k个数值。也就是说直接二分查找出这第k个数值，看能不能合法。

例如：枚举sum表示某一个区间的和，当它正好是第k个的时候 我们可以二分查找sum。然后再用双指针优化

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, ans, a[200009];

void init() {
    cin >> n >> k;
    ll i = 1;
    while (i <= n) cin >> a[i++];
    return;
}

bool check(ll mid) {
    ll i = 1, j = 1, tmp = 0, cnt = 0; // cnt -> mid大于等于的区间个数 <-> 区间和 <= mid的区间个数
    while (i <= n && j <= n) { // 双指针
        tmp += a[j];
        while (tmp > mid) tmp -= a[i++]; // tmp记录的区间和 <= mid
        cnt += (j - i + 1);
        ++j;
    }
    if (cnt >= k) return 1;
    else return 0;
}

void solve() {
    init();
    ll l = 0, r = 1e14; // A_min = 0, A_max*N = 1e14
    while (l <= r) {
        ll mid = l + r >> 1;
        if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans;
    return;
}

int main() {
    solve();
    return 0;
}