第 38 场 蓝桥·算法挑战赛 - 蓝桥云课

0.双人成行

将2维图转换为俩个1维图，维护m，n队列

• 行和列独立：U/D 只改变行，L/R 只改变列。
• 两人最终同格 ⇔ 最终行号相同 且 最终列号相同。
• 分别计算一维行、列上“最终位置相同”的有序对数 Sr、Sc。
• 总有序对数 Sr × Sc 包含两人初始全同的情况（每个格子有 1 个这样的对），因此 答案 = Sr × Sc − N×M。

一维子问题：相当于模拟每个位置的起点，经过操作后双端队列存的就是有多少个点的终点是这个点。

• 长 L 的数轴，每个位置初始有 1 个起点。
• 按序列中对应方向移动，越界则停在边界。
• 最终每个位置有 cnt[i] 个起点，行（或列）的同位置有序对数 = Σ cnt[i]²。

双端队列优化：

1. 所有起点的相对顺序始终不变（只是平移、合并，不会穿插）。
2. 边界的起点会“粘住”，并不断吸收撞上来的新起点。

计算位置拆分为三部分：

• 左墙 L_wall：位置 1 的起点数量
• 右墙 R_wall：位置 L 的起点数量
• 内部队列 deque<ll> D：位置 2 ~ L-1 的起点数量，按从左到右的顺序存放

初始状态：
L_wall = 1，R_wall = 1，D 包含 L-2 个 1。

• 每一步操作 O(1)
• 总时间 O(|S| + N + M)
• 空间 O(N + M)（deque 大小）

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

/**
 * 一维模拟：计算所有起点经过操作序列后，最终位置相同的“有序对”数量
 * @param L     一维长度（行数 N 或列数 M）
 * @param s     操作序列
 * @param l     负方向字符（行：'U'，列：'L'）
 * @param r     正方向字符（行：'D'，列：'R'）
 * @return      最终同位置有序对数 = Σ cnt[pos]²
 */
ll solve_1d(int L, const string &s, char l, char r) {
    // 特判：只有一个位置，所有起点永远在一起
    if (L == 1) return 1;

    // 特判：只有两个位置，没有内部队列，直接维护左右墙模拟
    if (L == 2) {
        ll left = 1, right = 1;          // 位置1和位置2初始各1个起点
        for (char c : s) {
            if (c == l) {                // 左移：位置2并入位置1
                left += right;
                right = 0;
            } else if (c == r) {         // 右移：位置1并入位置2
                right += left;
                left = 0;
            }
        }
        return left * left + right * right;
    }

    // 一般情况：L >= 3
    deque<ll> D(L - 2, 1);   // 内部位置 2~L-1，初始各有1个起点
    ll L_wall = 1;            // 位置1（左墙）的起点数
    ll R_wall = 1;            // 位置L（右墙）的起点数

    for (char c : s) {
        if (c == l) {
            // ========= 左移操作,内部所有队伍整体左移一位=========
            L_wall += D.front();   // 左墙吸收从内部最左端撞来的队伍
            D.pop_front();         // 原来位置2的队伍已经合并到左墙，移除
            // 原本的右墙队伍（位置L）变为位置L-1，进入内部队列的最右端
            D.push_back(R_wall);   // 原右墙移入内部最右侧（变成位置 L-1）
            R_wall = 0;            // 右墙清空，位置L现在没有队伍
        } else if (c == r) {
            // ========= 右移操作,内部所有队伍整体右移一位=========
            R_wall += D.back();    // 右墙吸收从内部最右端撞来的队伍
            D.pop_back();          // 原来位置L-1的队伍已经合并到右墙，移除
            // 原本的左墙队伍（位置1）变为位置2，进入内部队列的最左端
            D.push_front(L_wall);  // 原左墙移入内部最左侧（变成位置 2）
            L_wall = 0;            // 左墙清空，位置1现在没有队伍
        }
        // 与当前维度无关的操作（如行模拟中的L/R）直接跳过
    }

    // 计算平方和：每个位置的起点数的平方之和
    // 这就是“同位置有序对数” Sr 或 Sc
    ll sum = L_wall * L_wall + R_wall * R_wall;
    for (ll x : D) sum += x * x;
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    string S;
    cin >> N >> M >> S;

    // 行方向：U 使行号减小（左移），D 使行号增大（右移）
    ll Sr = solve_1d(N, S, 'U', 'D');
    // 列方向：L 使列号减小（左移），R 使列号增大（右移）
    ll Sc = solve_1d(M, S, 'L', 'R');

    // 总有序对 = 行有序对 × 列有序对
    // 减去 N*M 是因为要排除两人初始位置完全相同的情况
    cout << Sr * Sc - (ll)N * M << "\n";

    return 0;
}

1.耐力挑战

知识点：贪心 + 优先队列（建筑抢修模型）

问题转化
每个关卡需要消耗 $a_i$ 体力，开始前累计体力不能超过 $b_i$​。若完成该关卡，完成时累计体力最多为 $b_i+a_i$。
反过来看，这相当于：每个任务需要耗时 $a_i$​，必须在“截止时间” $d_i=a_i+b_i$ 之前完成。题目变成从 n 个任务中选出尽可能多的任务，使其能在各自截止时间内完成，即经典的“建筑抢修”问题。

贪心策略

1. 将所有关卡按截止时间 $d_i=a_i+b_i$升序排序（越紧迫的越先处理）。

2. 依次考虑每个关卡，维护当前已选关卡的总耗时 sum 和一个大根堆（存放已选关卡的 aiai）。

   • 若当前总耗时 sum ≤ bibi（满足开始门槛），则直接选择该关卡：sum += a_i，将 aiai 入堆。
   • 否则，如果当前关卡的 aiai 小于堆顶的最大耗时，说明我们可以用当前关卡替换掉已选中最耗时的那个，从而减小总耗时，为后续关卡留出空间：sum = sum - top + a_i，弹出堆顶并压入当前 aiai。
3. 最后堆的大小就是能够完成的最多关卡数。

时间复杂度 O(nlog⁡n)O(nlogn)，可以通过 n≤105n≤105 的数据。

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

struct Level {
    int a, b;
    ll d; // 最晚完成时刻 = a + b
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<Level> lvs(n);
    for (int i = 0; i < n; ++i) {
        cin >> lvs[i].a >> lvs[i].b;
        lvs[i].d = (ll)lvs[i].a + lvs[i].b;
    }
    
    // 按最晚完成时刻 d 升序排序
    sort(lvs.begin(), lvs.end(),
         [](const Level& x, const Level& y) { return x.d < y.d; });
    
    priority_queue<int> pq; // 大根堆，存已选关卡的 a
    ll sum = 0;             // 当前已选关卡的总耗时
    
    for (auto& lv : lvs) {
        if (sum <= lv.b) {          // 满足开始门槛，直接选
            sum += lv.a;
            pq.push(lv.a);
        } else if (!pq.empty() && lv.a < pq.top()) {
            // 替换堆顶更耗时的关卡，减小总耗时
            sum = sum - pq.top() + lv.a;
            pq.pop();
            pq.push(lv.a);
        }
    }
    
    cout << pq.size() << "\n";
    return 0;
}

struct node{
    ll a,d;//d=a+b
};

void solve() {
    int n;cin>>n;
    
    vector<node>lvs(n,{0,0});
    for(int i=0;i<n;i++){
        cin>>lvs[i].a>>lvs[i].d;
        lvs[i].d+=lvs[i].a;
    }
    sort(lvs.begin(),lvs.end(),[](node&a,node&b){return a.d<b.d;});
    ll sum=0;/已花费的体力
    priority_queue<ll>q;
    //默认直接选，如果超时就弹出
    //sum+a>d=a+b即sum>b,如果这个a最大且超时了，相当于不选，a不是最大超时了，替换最大的a
    //因为按a+b排序，所以a大的b一定比后面的b小，安全替换
    for(auto [a,d]:lvs){
        sum+=a;
        q.push(a);
        if(sum>d){
            sum-=q.top();
            q.pop();
        }
    }
    cout<<q.size()<<endl;
}

2.配方校验

知识点：异或运算性质 + 序列周期性

问题要求统计前 N 份配方中通过校验的数量。配方序列由递推式$A_i = A_{i-1} ⊕ A_{i-2} ⊕ A_{i-3} ⊕ B$生成，每个 $A_i$ 是长度为 m 的 01 串，全为 0 才算通过校验。

推导前几项发现配方序列周期为 4：

$$ A_4 = A_3 ⊕ A_2 ⊕ A_1 ⊕ B\\ A_5 = A_4 ⊕ A_3 ⊕ A_2 ⊕ B = (A_3 ⊕ A_2 ⊕ A_1 ⊕ B) ⊕ A_3 ⊕ A_2 ⊕ B = A_1\\ A_6 = A_2，A_7 = A_3，A_8 = A_4，循环往复。 $$

因此只需处理 A_1 到 A_4 这四种配方，检查每种是否全 0。每个完整周期（4 份）中通过的数量固定为 cnt，前 N 份包含 N/4 个完整周期和 N%4 个余数，分别累加即可。

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;

int main() {
    ll m, N;
    cin >> m >> N;
    string A1, A2, A3, B;
    cin >> A1 >> A2 >> A3 >> B;

    string A4(m, '0');
    for (int i = 0; i < m; i++)
        A4[i] = ((A1[i]-'0') ^ (A2[i]-'0') ^ (A3[i]-'0') ^ (B[i]-'0')) + '0';

    string seq[4] = {A1, A2, A3, A4};
    string zero(m, '0');
    int cnt = 0;
    for (int i = 0; i < 4; i++)
        if (seq[i] == zero) cnt++;

    ll full = N / 4, rem = N % 4;
    ll ans = (full % MOD) * cnt % MOD;
    for (int i = 0; i < rem; i++)
        if (seq[i] == zero) ans = (ans + 1) % MOD;

    cout << ans;
    return 0;
}

3.最大编号

知识点：状态压缩 + DFS回溯 + 记忆剪枝

题目要求从给定的若干张数字卡片（可重复）中选出若干张，排列成无前导零的正整数，使得能被 M 整除且最大。

• 卡片最多 14 张，全排列数达到 14! 会超时，必须剪枝。
• 数字可以不全部使用，因此需要尝试所有可能的长度。

1. 将卡片数字降序排序，保证先使用大数字。
2. 外层循环枚举最终数字的长度 len（从 n 到 1），一旦找到合法解即为最长且最大（因降序搜索），输出并结束。

3. DFS 搜索：传入当前已用卡片掩码 mask 和当前余数 r。

   • 若 ans 长度达到 len，判断 r == 0 则为合法解。
   • 使用记忆化数组 vis 避免重复搜索相同状态。

   • 枚举下一张卡片：

     • 首位不能是 0。
     • 已使用的卡片跳过。
     • 同数字卡片去重：若前一张相同数字卡片未使用，则当前卡片跳过（保证相同数字的排列只按一种顺序选取）。
   • 递归前将数字加入 ans，更新余数，递归后回溯。
4. 若所有长度均无解，输出 -1。

时间复杂度：最坏 O(2^n n m)，但实际状态远小于此，加上排序和去重剪枝，在 n ≤ 14, m ≤ 2026 范围内可快速通过。

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

int m;                  // 模数
string s;               // 存储卡片的数字字符串
bool vis[1<<14][2027];  // 记忆化数组：vis[mask][r] 表示状态(已选卡片mask,余数r)是否已经尝试过且无法达到目标

string ans="";          // 当前构造的数字
int len;                // 当前目标长度（从长到短尝试）

// mask: 已选卡片的位掩码，r: 当前已构造数字模m的余数
bool dfs(int mask, int r) {
    if(ans.length() == len) return r == 0; // 长度达到目标，检查整除
    if(vis[mask][r]) return 0;             // 状态已访问,返回
    vis[mask][r] = 1;

    for(int i = 0; i < s.length(); i++) {
        if(ans.length() == 0 && s[i] == '0') continue; // 前导零
        if(mask & (1 << i)) continue;                  // 卡片已用
        if(i > 0 && s[i] == s[i - 1] && !(mask & (1 << (i - 1)))) continue; // 同层去重
        ans.push_back(s[i]);
        int nr = (r * 10 + (s[i] - '0')) % m;         // 新余数
        if(dfs(mask | (1 << i), nr)) return 1;        // 找到解立即返回
        ans.pop_back();                               // 回溯
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> m >> s;
    sort(s.rbegin(), s.rend());          // 降序，优先大数字
    for(int i = s.length(); i >= 1; i--) { // 从长到短尝试
        len = i;
        memset(vis, 0, sizeof(vis));
        ans = "";
        if(dfs(0, 0)) {
            cout << ans;
            return 0;
        }
    }
    cout << -1;
}