算法上机 - ldfd

Expt2(递归/分治)

王牌游戏

数据范围一给就知道是cf的原题，但是左半部分是什么傻逼翻译，请强调一下左面的一半。

彩球归位

Python 卡常+1

总体时间复杂度为 O(N + Q)，其中N是球的总数，Q是桶的数量。对于最坏情况，每个桶都有球，且所有球都能配对移除，我们需要处理每个球，因此是线性的。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;

    // 读取所有桶的数据
    vector<vector<int>> buckets(Q);
    for (int i = 0; i < Q; ++i) {
        int k;
        cin >> k;
        buckets[i].resize(k);
        for (int j = 0; j < k; ++j) {
            cin >> buckets[i][j];
        }
        // 从顶部取球，符合题意，需要反转
        reverse(buckets[i].begin(), buckets[i].end());
    }

    // 球 -> 桶的映射
    vector<vector<int>> color_to_buckets(N + 1);
    
    // BFS队列，存储可以配对的颜色
    queue<int> matching_colors;

    // 初始化：检查每个桶顶部的球，建立颜色到桶的映射
    for (int i = 0; i < Q; ++i) {
        if (!buckets[i].empty()) {
            int top_color = buckets[i].back();
            color_to_buckets[top_color].push_back(i);
            
            // 如果某种颜色刚好有两个球在不同桶的顶部，加入队列
            if (color_to_buckets[top_color].size() == 2) {
                matching_colors.push(top_color);
            }
        }
    }

    // BFS处理能够配对的球
    while (!matching_colors.empty()) {
        int current_color = matching_colors.front();
        matching_colors.pop();

        // 如果当前颜色的球少于2个（可能在之前的操作中已被处理），跳过
        if (color_to_buckets[current_color].size() < 2) {
            continue;
        }

        // 获取两个包含当前颜色球的桶
        int bucket1 = color_to_buckets[current_color].back();
        color_to_buckets[current_color].pop_back();
        int bucket2 = color_to_buckets[current_color].back();
        color_to_buckets[current_color].pop_back();

        // 从两个桶中移除顶部的球
        buckets[bucket1].pop_back();
        buckets[bucket2].pop_back();

        // 检查移除球后，两个桶的新顶部球
        for (int bucket_idx : {bucket1, bucket2}) {
            if (!buckets[bucket_idx].empty()) {
                int new_top_color = buckets[bucket_idx].back();
                color_to_buckets[new_top_color].push_back(bucket_idx);
                
                // 如果新顶部颜色刚好有两个，加入队列
                if (color_to_buckets[new_top_color].size() == 2) {
                    matching_colors.push(new_top_color);
                }
            }
        }
    }

    // 检查是否所有桶都为空
    bool all_empty = true;
    for (const auto& bucket : buckets) {
        if (!bucket.empty()) {
            all_empty = false;
            break;
        }
    }

    cout << (all_empty ? "Yes" : "No") << endl;

    return 0;
}

异或游戏

Python被卡常了，差评。

#include <bits/stdc++.h>

using namespace std;

/**
 * @brief 通过对位的二进制搜索计算最小可能的异或(XOR)值
 * 
 * 这个函数实现了一种分治方法来寻找最小异或值:
 * 1. 对于每个位置(从最高有效位到最低有效位)，将数字分成两组
 * 2. 一组在当前位置有1，另一组在当前位置有0
 * 3. 递归处理导致最小异或值的那个组
 * 
 * @param bit 当前处理的位位置(从最高有效位开始)
 * @param candidates 当前递归级别要处理的整数数组
 * @return 给定位置和候选数字可能的最小异或值
 * 
 * 时间复杂度: O(N * log(max(candidates)))
 * 空间复杂度: O(N) 用于存储分离的组
 * 
 * 注意: 假设输入向量非空且包含非负整数
 */

int dfs(int bit, vector<int>& candidates) {
    if (bit < 0) {
        return 0;
    }
    int mask = 1 << bit;
    vector<int> zeros, ones;
    for (int num : candidates) {
        if (num & mask) {
            ones.push_back(num);
        } else {
            zeros.push_back(num);
        }
    }
    if (zeros.empty()) {
        return dfs(bit - 1, ones);
    } else if (ones.empty()) {
        return dfs(bit - 1, zeros);
    } else {
        int val1 = dfs(bit - 1, ones);
        int val2 = dfs(bit - 1, zeros);
        return (1 << bit) + min(val1, val2);
    }
}

int find_min_max_xor(vector<int>& arr) {
    // 找到最大的数，然后调用抽象函数实现O(1)计算最高位是哪一位，不过只算一次其实复杂点也无所谓（
    if (arr.empty()) {
        return 0;
    }
    int max_val = *max_element(arr.begin(), arr.end());
    int max_bit = max_val ? __builtin_clz(1) - __builtin_clz(max_val) : 0;
    return dfs(max_bit, arr);
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    cout << find_min_max_xor(arr) << endl;
    return 0;
}

魔法符文分形

原题 USACO17JAN

def solve(a, n, i):
    """
    递归函数，用于查找序列中数字的位置。
    此函数通过递归二分法计算序列中数字的位置，
    在每个递归层级将序列分成两半。
    参数：
        a (int): 当前考虑的序列长度
        n (int): 要在当前序列中查找的位置（基于1的索引）
        i (int): 变换的次数
    返回：
        int: 原始序列s中目标位置的值
    注意：
        - 函数假设存在包含原始序列的全局列表/数组's'
        - 当i=1时达到基本情况，返回原始序列s的第(n-1)个元素
        - 对于每个递归层级，长度为'a'的序列被分成两半
        - 根据目标位置在哪一半中重新计算位置n
    """

    if i == 1:
        return s[n-1]

    x = a // 2
    # 下面所有的目的都是把n映射到左侧的位置
    if n <= x:
        # 在左面
        return solve(x, n, i-1)
    else:
        # 恰好在右面的第一个 等价于 找左面的最后一个
        if n == (x + 1):
            return solve(x, n-1, i-1)
        # 其他右面情况 仅考虑最简情况理解 举例理解
        """
        ABCD
        ABCD DABC
        """
        # 此时n-x为右侧的第几个，是由左侧尾巴移动到头构造得到的，所以比在左侧的对应的位置大1。
        else:
            return solve(x, n-x-1, i-1)


s, n = input().split()
n = int(n)
a = len(s)
i = 1
# a变换i次后，满足第n个字符在这个变形后的串里面
while a < n:
    i += 1
    a *= 2

print(solve(a, n, i))

为运算表达式设计优先级

和表达式递归求值想法相同。一个表达式可以分成：运算符、数字、更小的表达式。

当遇到运算符时进行左右切片，左右是表达式进而递归调用函数。当表达式不再存在运算符时等价于它就是数字，所以返回整数。

注意对于一个表达式返回的是一个列表，这样代码中的两种循环就可以理解了。

def f(input):
    res = []
    for i in range(len(input)):
        if input[i] in {'+', '-', '*'}:
            left = f(input[:i])
            right = f(input[i+1:])
            for l in left:
                for r in right:
                    if input[i] == '+':
                        res.append(l + r)
                    elif input[i] == '-':
                        res.append(l - r)
                    elif input[i] == '*':
                        res.append(l * r)
    if not res:
        res.append(int(input))
    return res
print('\n'.join(map(str,sorted(f(input())))))

石子游戏

记忆化搜索

Expt3(DP)

调制四果汤

原题 CF1042B Vitamins 现在加强完不能暴力了（

由题目可知，四果汤的特征n = 15为一个较小的值，又没那么小的值，所以可以采用状压dp来做。

状态定义 : dp[mask] 表示获得当前集合所需的最小成本
mask : 第(i-1)为表示第i种元素, ABCD... -> 第0123二进制位
初始状态 : dp[0] = 0 无集合成本视作空
状态转移: dp[mask] 由 dp[mask | current] 转移而来， current表示当前配料的元素的mask

所以预处理出所有配料的mask, 然后进行dp即可。

vector<int> ingredient_bits(T, 0);
for (int i = 0; i < T; ++i) {
    const string& elem = elements[i];
    for (char c : elem) {
        if (c >= 'A' && c < 'A' + n) {
            int bit = c - 'A';
            ingredient_bits[i] |= (1 << bit);
        }
    }
}

vector<long long> dp(1 << n, LLONG_MAX);
dp[0] = 0;

for (int i = 0; i < T; ++i) {
    int current_mask = ingredient_bits[i];
    long long price = prices[i];

    for (int mask = (1 << n) - 1; mask >= 0; --mask) {
        if (dp[mask] != LLONG_MAX) {
            // 不等于LLONG_MAX说明当前mask是可达的，进而可以转移到mask | current
            int new_mask = mask | current_mask;
            if (dp[new_mask] > dp[mask] + price) {
                dp[new_mask] = dp[mask] + price;
            }
        }
    }
}

上课别摸鱼

原题统计打字方案数 - 力扣（LeetCode）

由leetcode可知常数非常宽松（

这道题的dp不是对于总方案而言的，而是对于每一个按键来说的。

状态定义 : dp[i]表示i个相同数字可以产生的序列数量 1-index
初始状态 : dp[0] = 1 空串视作一种方案
状态转移 : 对于dp[i]，我们假设最后一个字母消耗了k个按键，但是这k个按键最终形成的是一个字母，所以说对于方案数不是乘法的关系，只是单纯的追加上去，和dp[i-k]的方案数是相同的，而k的取值是变化的,即[1, (1, min(i, mp[c])]，最终构成了dp[i]
mp[c] : 表示c按键有几个字母

然后进行下一步，我们只需要将不同连续的数字视作一个整体（不停地查相同数字个数即可），然后将它们的方案数相乘即可。当然预处理dp数组效率更高，一共就两个，但是下面的能过没被卡。

mp = {
        2: 3,
        3: 3,
        4: 3,
        5: 3,
        6: 3,
        7: 4,
        8: 3,
        9: 4
    }

def calc(n, c):
    dp = [0] * (n + 1)
    dp[0] = 1
    
    for i in range(1, n + 1):
        for j in range(1, min(i, mp[c]) + 1):
            dp[i] += dp[i - j]
    return dp[n]

ans = 1
cnt = 0
MOD = 10**9 + 7
pressedKeys = input()
n = len(pressedKeys)
for i in range(n):
    cnt += 1
    if i == n - 1 or pressedKeys[i] != pressedKeys[i+1]:
        ans = ans *  calc(cnt, ord(pressedKeys[i]) - ord('0'))% MOD
        cnt = 0
        
print(ans)

共享单车

原来这就是传说中的刷表法。由当前点的状态，更新后面点的状态。但是有反转填表法也行。所以两种代码都可以。

状态定义 : dp[i] 表示第i天的总花费的最小值
状态转移 : dp[i] 一共有两类, 一种是 dp[i-1] + 单价 * 当日次数 
         另一种是dp[i - k] +k 天套票的价格

dp = [float('inf')] * (len(d) + 1)
dp[0] = 0

for i in range(1, len(d) + 1):
    dp[i] = min(dp[i-1] + d[i-1] * m, dp[i])
    
    for j in range(k):
        valid_days = min(i + t[j] - 1, len(d))
        cost_before_pass = dp[i-1]
        dp[valid_days] = min(dp[valid_days], cost_before_pass + c[j])

dp = [float('inf')] * (len(d) + 1)
dp[0] = 0

for i in range(1, len(d) + 1):
    dp[i] = dp[i-1] + d[i-1] * m
    for j in range(k):
        if i - t[j] >= 0: 
            dp[i] = min(dp[i], dp[i - t[j]] + c[j])
        else:
            dp[i] = min(dp[i], dp[0] + c[j])

print(dp[len(d)])

小s的游戏

python又卡常了，乐。和上一道题一样，填表刷表均可，ai明显喜欢刷表，所以我决定填表。

状态定义 : dp[i][j] 表示走i次，到达第j个格子的最大欢乐值 注意数据是从第0个格子开始的 根据数据范围应该不会爆！
状态转移 : dp[i][j] 由 dp[i-1][j-k] 构成, k∈[1, 6]

dp[0][0] = 0;
for (int move = 1; move <= k; ++move) {
    for (int pos = 0; pos <= n; ++pos) {
        for (int step = 1; step <= 6; ++step) {
            // 来时路
            int npos = pos - step;
            // 越界
            if (npos < 0) break;
            // 前路未曾到过
            if (dp[move-1][npos] == MINF) continue;      
            ll new_val = dp[move-1][npos] + a[pos];           
            if (new_val > dp[move][pos]) {
                dp[move][pos] = new_val;
            }
        }
    }
}
int best_pos = max_element(dp[k].begin(), dp[k].end()) - dp[k].begin();
cout << dp[k][best_pos] << "\n";

以上是动态规划的代码，如果会的话还是不难的，甚至如果没有第二位还可以去掉一维数组。

为了知道我们的路线，还需要一个二维数组

par[i][j] : 表示第i步在j位置的时候并且是最优解的情况，是从哪一个格子走来的

这样更新一下上面的代码即可

 if (new_val > dp[move][pos] || 
    (new_val == dp[move][pos] && npos < par[move][pos])) {
     // 如果npos 即来自的那个格子比当前更靠近起点 则符合题意要求 也需要更新
    dp[move][pos] = new_val;
    par[move][pos] = npos;
}

然后逆序寻找路径即可

 vector<int> path;
for (int move = k, pos = best_pos; move > 0; --move) {
    path.push_back(pos);
    pos = par[move][pos];
}
reverse(path.begin(), path.end());

签到码生成

原题: ABC344_D 太好啦是abc我们的常数有救了原来是分组背包同样填表刷表均可

状态表示 : dp[i][j] 考虑前i组字符串构成S[0:j]签到码的最小资源 此处为python的左闭右开切片
状态转移 : dp[i][j] 由dp[i-1][j - k]构成, k∈[min(len(a[i])), max(len(a[i]))]

dp = [[INF] * (m + 1) for _ in range(n + 1)]
dp[0][0] = 0  # 空字符串不需要任何包

for i in range(1, n + 1):
    parts = input().split()
    count = int(parts[0])    # 当前包的字符串数量
    package = parts[1:]      # 当前包的字符串列表

    # 初始状态：不选当前包，继承前i-1个包的结果
    for j in range(m + 1):
        dp[i][j] = dp[i - 1][j]

    # 尝试用当前包的字符串更新状态 刷表
    for j in range(m + 1):
        if dp[i - 1][j] != INF:  # 如果前i-1个包能组成S[0:j]
            for s in package:
                ls = len(s)
                # 伟大的python切片 如此简洁
                if j + ls <= m and S[j:j + ls] == s:
                    # 更新dp[i][j + ls]，取最小值
                    if dp[i][j + ls] > dp[i - 1][j] + 1:
                        dp[i][j + ls] = dp[i - 1][j] + 1
	# 填表
    for j in range(m+1):
        for s in package:
            if j - len(s) >= 0 and S[j - len(s):j] == s:
                dp[i][j] = min(dp[i][j], dp[i - 1][j - len(s)] + 1)

下面考虑压缩一维，这道题虽然dp[i]仅有dp[i-1]层决定，但是由于每组字符串的长度没什么规律，所以至少需要两个dp数组，拷贝一份原来的才行。

for _ in range(n):
    parts = input().split()
    count = int(parts[0])    # 第一个数是当前包的字符串数量
    package = parts[1:]      # 剩下的部分是当前包的字符串列表

    new_dp = dp.copy()  # 初始化为不选当前包的情况

    for j in range(m + 1):
        if dp[j] != INF:
            for s in package:
                ls = len(s)
                if j + ls <= m and S[j:j+ls] == s:
                    if new_dp[j + ls] > dp[j] + 1:
                        new_dp[j + ls] = dp[j] + 1

    dp = new_dp  # 更新dp数组

print(dp[m] if dp[m] != INF else -1)

突击学习

首先你需要朴素地猜测一下忘得越快越后学

n天 m门课程

状态定义 : dp[i][j] 表示前i门课程, 从头开始学习了j天的最高分
状态转移 : dp[i][j] 假如我厌学了，那就不学！最起码能考dp[i-1][j]的分数
			我又悔改了，今天如果学了那么是另一类情况 dp[i-1][j-1] + 最终分数 j ∈ [1, n]

std::vector<int> xs(m);
std::vector<int> ds(m);

for (int i = 0; i < m; ++i) {
    std::cin >> xs[i];
}

for (int i = 0; i < m; ++i) {
    std::cin >> ds[i];
}

std::vector<std::pair<int, int>> courses(m);
for (int i = 0; i < m; ++i) {
    courses[i] = {xs[i], ds[i]};
}

std::sort(courses.begin(), courses.end(), 
         [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
             return a.second < b.second;
         });

std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

for (int i = 1; i <= m; ++i) {
    int x = courses[i-1].first;
    int d = courses[i-1].second;

    for (int j = 0; j <= n; ++j) {
        dp[i][j] = dp[i-1][j];

        if (j > 0) {
            int score = x - d * ((n+1) - j);
            // 罪不至此 考负分
            if (score < 0)  score = 0;
            dp[i][j] = std::max(candidate, dp[i-1][j-1] + score);

        }
    }
}


std::cout << dp[m][n] << std::endl;

电梯问题

这是贪心？

#include <bits/stdc++.h>
using namespace std;
 
struct Student {
    int from, to;
};
 
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, s;
    cin >> n >> s;
    vector<Student> stu(n);
    for (int i = 0; i < n; i++){
        cin >> stu[i].from>> stu[i].to;
    }
    // 按上电梯楼层升序排序
    sort(stu.begin(), stu.end(), [](const Student &a, const Student &b){
        return a.from < b.from;
    });
    // 优先队列按照目标楼层r降序排列（r大的优先）大根堆

    priority_queue<pair<int,int>> pq; // pair<r, l>
    long long totalCost = 0;
    int current = s; // 电梯当前楼层
    int idx = 0; 

    // 注意回忆一下，乘客上电梯的楼层是升序的
    // 并且电梯下来的时候一定空载的
    while(idx < n || !pq.empty()){
        // 把所有当前可以接的人加入优先队列
        while(idx < n && stu[idx].from <= current){
            pq.push({stu[idx].to, stu[idx].from});
            idx++;
        }
 
        if(!pq.empty()){
            auto top = pq.top();
            pq.pop();
            int pickup = top.second, drop = top.first;
            // 下来的时候没有人在电梯里
            // 乘客上电梯时，电梯可以先下行（免费）到达pickup
            // 再上行到达drop，消耗(drop - pickup)单位电量
            totalCost += (drop - pickup);
            current = drop;
        } else {
            // 当前没有可接的人，说明下一个乘客的 pickup 高于当前楼层，
            // 电梯必须上行（消耗电量）前往该楼层
            totalCost += (stu[idx].to - current);
            current = stu[idx].to;
        }
    }
    cout << totalCost << "\n";
    return 0;
}