笔试强训第 06 周：逐题精讲与完整题解

#include <iostream>
#include <queue>
using namespace std;
 
int n, k;
 
int main()
{
    cin >> n >> k;                                     // n 种原料，总预算 k
    priority_queue<int, vector<int>, greater<int>> heap; // 小根堆：每次取成本最低的方案
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;                                      // 每种原料当前做 1 个口罩的成本
        heap.push(x);
    }
 
    int sum = 0, count = 0;                            // 累计成本、已做口罩数
    while(true)
    {
        int t = heap.top();                            // 取当前成本最低的方案
        heap.pop();
        sum += t;                                      // 花掉这份成本，做出 1 个口罩
        heap.push(t * 2);                              // 该方案下次成本翻倍，重新入堆
        count++;                                       // 口罩计数 +1
        if(sum > k)                                    // 累计成本刚突破预算
        {
            cout << count - 1 << endl;                 // 突破的那一次没真正做成，故减 1
            break;
        }
    }
    return 0;
}

#include <iostream>
using namespace std;
typedef long long LL;
 
LL t;
LL n, a, b;
 
LL fun()
{
    // 边界情况：人特别少（<=2），一条船就能全坐，取两种船便宜的那个
    if(n <= 2) return min(a, b);
 
    LL ret = 0;
    if(a * 3 < b * 2)            // 双人船性价比更高 -> 优先双人船
    {
        ret += n / 2 * a;        // 装满的每对坐双人船
        n %= 2;                  // 看还剩 0 还是 1 人
        if(n)                    // 剩 1 人
        {
            // 两个选择取小：
            //   a           -> 单独再租一艘双人船（空 1 座）
            //   b - a       -> 把某人从"双人船"换成"三人船"（多 1 座），净多花 b - a
            ret += min(min(a, b), b - a);   // min(a,b) 包住 b-a 恰是因为 b 可能比 a 还贵/便宜
        }
    }
    else                         // 三人船性价比更高 -> 优先三人船
    {
        ret += n / 3 * b;        // 装满的每三个坐三人船
        n %= 3;                  // 剩 0 / 1 / 2 人
        if(n == 1)
        {
            // 剩 1 人：单独租船(取 a 或 b),或把一艘三人船换成两艘双人船（多 1 座净花 2a - b）
            ret += min(min(a, b), 2 * a - b);
        }
        if(n == 2)
        {
            // 剩 2 人：单独租双人船 a，或把一艘三人船换成三艘双人船（净花 3a - b）
            ret += min(min(a, b), 3 * a - b);
        }
    }
    return ret;
}
 
int main()
{
    cin >> t;
    while(t--)
    {
        cin >> n >> a >> b;
        cout << fun() << endl;
    }
    return 0;
}

#include <iostream>
using namespace std;
 
const int N = 20, M = N * 9;      // 最多 20 位，每位最大 9，故数字和上限 M
 
long long x;
int n, sum;                        // n = 位数，sum = 所有位数字之和
int arr[N];                        // 逐位存下来的数字
bool dp[M];                        // dp[j]: 能否用已选数字凑出和 j
 
bool fun()
{
    if(sum % 2 == 1) return false; // 奇数，必不可能均分，直接判 No
    sum /= 2;                      // 目标：凑出总和的一半
 
    dp[0] = true;                  // 空集：什么也不选，和恰为 0
    for(int i = 0; i < n; i++)     // 枚举每一位（一个物品）
    {
        for(int j = sum; j >= arr[i]; j--)   // 01背包：容量必须倒序遍历
        {
            dp[j] = dp[j] || dp[j - arr[i]]; // 不选 或 选这一位构成转移
        }
    }
    return dp[sum];                // 看目标值是否可达
}
 
int main()
{
    cin >> x;
    while(x)                       // 逐位拆解（倒着拆，因求和与顺序无关）
    {
        arr[n++] = x % 10;         // 取出最低位
        sum += x % 10;             // 累加数字和
        x /= 10;                   // 去掉最低位
    }
    if(fun()) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

#include <iostream>
#include <cmath>
#include <string>
using namespace std;
 
long long change(string s)
{
    // i 从倒数第二位开始，一直镜像到第一位，逐个往后贴
    for(int i = s.size() - 2; i >= 0; i--)
    {
        s += s[i];               // 把前面的字符接到末尾
    }
    return stol(s);              // 字符串转 long long
}
 
bool isprim(long long x)
{
    if(x <= 1) return false;     // 1 及以下不是素数
    for(long long i = 2; i <= sqrt(x); i++)  // 只需试到 sqrt(x)
    {
        if(x % i == 0) return false;
    }
    return true;
}
 
int main()
{
    string s;
    cin >> s;
    long long x = change(s);     // 先拼回文
    if(isprim(x)) cout << "prime" << endl;
    else cout << "noprime" << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> PII;      // first=开始，second=结束
const int N = 2e5 + 10;
int n;
PII arr[N];
 
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i].first >> arr[i].second;
 
    sort(arr, arr + n);          // 按开始时间升序排列
 
    int ret = 0, r = arr[0].second;      // 先默认第一场必选，r 为它的结束
    for(int i = 1; i < n; i++)
    {
        if(arr[i].first < r)
        // 与当前集合重叠 -> 不新增，缩紧右边界留机会
        {
            r = min(r, arr[i].second);
        }
        else
        // 不重叠 -> 多选一场，移动到新的结束边界
        {
            ret++;
            r = arr[i].second;
        }
    }
    cout << ret + 1 << endl;
    return 0;
}

#include <iostream>
using namespace std;
typedef long long LL;
 
const int N = 55, M = 15;
const LL INF = 0x3f3f3f3f3f3f3f3f;   // 一个非常大的 long long
 
int n, k, d;
LL arr[N];           // 能力值
LL f[N][M];          // f[i][j]: 以 i 结尾选 j 个的最大乘积
LL g[N][M];          // g[i][j]: 以 i 结尾选 j 个的最小乘积
 
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    cin >> k >> d;
 
    for(int i = 1; i <= n; i++)        // 枚举最后被选中的人 i
    {
        g[i][1] = f[i][1] = arr[i];    // 只选 1 个：最大=最小=它本身
        for(int j = 2; j <= min(i, k); j++)  // 一共选 j 个（不能超过 i 和 k）
        {
            f[i][j] = -INF;            // 求最大先初始化为极小
            g[i][j] = INF;             // 求最小先初始化为极大
            for(int prev = max(i - d, j - 1); prev <= i - 1; prev++)
            // 上一个选中的人 prev：距离不超过 d，且前面能凑出 j-1 个
            {
                // 前面的最大/最小，分别乘上当前能力值，取最大更新 f
                f[i][j] = max(max(f[prev][j - 1] * arr[i],
                                  g[prev][j - 1] * arr[i]), f[i][j]);
                // 同时用最大/最小乘当前值，取最小更新 g
                g[i][j] = min(min(f[prev][j - 1] * arr[i],
                                  g[prev][j - 1] * arr[i]), g[i][j]);
            }
        }
    }
 
    LL ret = -INF;
    for(int i = k; i <= n; i++) ret = max(ret, f[i][k]); // 最后选中的人可以是 k..n
    cout << ret << endl;
    return 0;
}

#include <iostream>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    cout << (1 << (n - 1)) << endl;   // 结论：2^(n-1)
    return 0;
}

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
    int left = 0, right = 0, n = s.size();
    int hash[26] = { 0 };              // 窗口内每种字母出现的次数
    int count = 0;                     // 窗口内一共有多少种不同的字母
    int ret = 0;
 
    while(right < n)
    {
        // 新字符若第一次进入窗口（0 -> 1），窗口内的种数 +1
        if(hash[s[right] - 'a']++ == 0) count++;
 
        // 种数超了 2，收缩窗口
        while(count > 2)
        {
            // 被移出的字符若从 1 -> 0，说明这种字母彻底离开，种数 -1
            if(hash[s[left++] - 'a']-- == 1) count--;
        }
 
        // 此时窗口合法，尝试更新答案
        ret = max(ret, right - left + 1);
        right++;
    }
 
    cout << ret << endl;
    return 0;
}

if(i > 0 && s[i] == s[i - 1] && !vis[i - 1]) continue;

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
class Solution {
public:
    vector<string> ret;                 // 收集所有排列（叶子节点）
    string path;                        // 记录当前递归路径
    bool vis[11] = { 0 };               // 标记某个位置的字符是否用过
    int n;
    string s;
 
    vector<string> Permutation(string str)
    {
        n = str.size();
        sort(str.begin(), str.end());   // 先排序，便于相邻去重 + 保证字典序
        s = str;
        dfs(0);
        return ret;
    }
 
    void dfs(int pos)
    {
        if(pos == n)                    // 所有位置填满，收集一个排列
        {
            ret.push_back(path);
            return;
        }
 
        for(int i = 0; i < n; i++)      // 枚举填 pos 位置用哪个字符
        {
            if(!vis[i])
            {
                // 去重剪枝：与前一位字符相同、而前一个还没用，说明是同一字符的首枝，跳过
                if(i > 0 && s[i] == s[i - 1] && !vis[i - 1]) continue;
 
                path.push_back(s[i]);   // 选择
                vis[i] = true;
                dfs(pos + 1);           // 填下一个位置
 
                vis[i] = false;         // 恢复现场（回溯）
                path.pop_back();
            }
        }
    }
};
 
int main()   // 本地演示用 main，OJ 上交时只需提交 Solution 类
{
    string str;
    cin >> str;
    Solution sol;
    for(auto &e : sol.Permutation(str)) cout << e << endl;
    return 0;
}

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
    int sum = 0, count = 1, n = s.size();   // count 是权重，从 1 到 9
 
    for(int i = 0; i < n - 1; i++)          // 前 n-1 位参与计算（最后一位是识别码）
    {
        if(s[i] >= '0' && s[i] <= '9')      // 只对数字位加权
        {
            sum += (s[i] - '0') * count;
            count++;                        // 每遇到一个数字位，权重 +1
        }
        // 分隔符 '-' 跳过，不计权
    }
 
    sum %= 11;                              // 对 11 取模得校验值
 
    // 识别码正确的情况：是数字且相等；或是 X（代表 10）且 sum 也为 10
    if(sum == s[n - 1] - '0' || (sum == 10 && s[n - 1] == 'X'))
    {
        cout << "Right" << endl;
    }
    else
    {
        // 修正最后一位：sum==10 要写回 'X'，否则写回数字字符
        s[n - 1] = sum == 10 ? 'X' : sum + '0';
        cout << s << endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
const int N = 35;
int x1, y1;                 // 标记起点位置
int n, m;
char arr[N][N];             // 迷宫
int dist[N][N];             // 到每个格子的最短步数，-1 表示不可达
queue<pair<int, int>> q;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
 
void bfs()
{
    memset(dist, -1, sizeof dist);   // 先全部标为不可达
    dist[x1][y1] = 0;
    q.push({x1, y1});
 
    while(q.size())
    {
        auto [x2, y2] = q.front();   // C++17 结构化绑定取队首
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            int a = x2 + dx[i], b = y2 + dy[i];
            // 在界内、未访问过、且不是墙
            if(a >= 1 && a <= n && b >= 1 && b <= m && dist[a][b] == -1 && arr[a][b] != '*')
            {
                dist[a][b] = dist[x2][y2] + 1;
                if(arr[a][b] != 'e')   // 出口拿到步数即可，不再向外扩散
                {
                    q.push({a, b});
                }
            }
        }
    }
}
 
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> arr[i][j];
            if(arr[i][j] == 'k') x1 = i, y1 = j;   // 记录起点
        }
    }
 
    bfs();
 
    int count = 0, ret = 1e9;   // count: 可达出口数，ret: 最近出口步数
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(arr[i][j] == 'e' && dist[i][j] != -1)
            {
                count++;                        // 这个出口可达
                ret = min(ret, dist[i][j]);
            }
        }
    }
 
    if(count == 0) cout << -1 << endl;
    else cout << count << " " << ret << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
class Solution
{
    int m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int memo[1010][1010];        // memo[i][j]: 从 (i,j) 出发的最长递增路径
 
    int dfs(vector<vector<int> >& matrix, int i, int j)
    {
        if(memo[i][j] != -1) return memo[i][j];   // 算过就复用
 
        int len = 1;             // 至少包含自身一格
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            // 只走向值更大的相邻格子
            if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])
            {
                len = max(len, 1 + dfs(matrix, x, y));
            }
        }
        memo[i][j] = len;        // 记录，供后续状态复用
        return len;
    }
 
public:
    int solve(vector<vector<int> >& matrix)
    {
        m = matrix.size(), n = matrix[0].size();
        memset(memo, -1, sizeof memo);   // 全部置为"未计算"
 
        int ret = 1;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                ret = max(ret, dfs(matrix, i, j));   // 从每个格子出发都试一遍
        return ret;
    }
};
 
Solution sol;   // memo 数组较大（约4MB），置于全局避免栈溢出
 
int main()      // 本地演示用 main，OJ 上交时只需 Solution 类
{
    int r, c;
    cin >> r >> c;
    vector<vector<int> > mat(r, vector<int>(c));
    for(int i = 0; i < r; i++)
        for(int j = 0; j < c; j++)
            cin >> mat[i][j];
    cout << sol.solve(mat) << endl;
    return 0;
}

#include <iostream>
using namespace std;
 
int main()
{
    int n;
    while(cin >> n)                  // 多组输入，读到文件结束符为止
    {
        int ret = 1;
        // 让 ret 翻倍，直到 ret-1 > n，即 ret/2-1 是不超过 n 的最大(2^k-1)
        while(ret - 1 <= n) ret *= 2;
        cout << ret / 2 - 1 << endl;
    }
    return 0;
}

#include <iostream>
using namespace std;
 
int n, m;
bool choose[11];        // choose[i]：路径里是否选了数字 i
int sum;                // 当前已选数字之和
 
void dfs(int x)
{
    if(sum == m)                     // 凑到了目标 m，输出当前方案
    {
        for(int i = 1; i <= n; i++)
            if(choose[i]) cout << i << " ";
        cout << endl;
        return;
    }
    if(sum > m || x > n) return;     // 剪枝：已超越目标，或无号可选
 
    // 分支一：选 x
    sum += x;
    choose[x] = true;
    dfs(x + 1);
    sum -= x;                        // 恢复现场
    choose[x] = false;
 
    // 分支二：不选 x
    dfs(x + 1);
}
 
int main()
{
    cin >> n >> m;
    dfs(1);
    return 0;
}

#include <iostream>
#include <string>
using namespace std;
 
const int N = 1010;
string a, b;
int dp[N][N];
 
int main()
{
    cin >> a >> b;
    int n = a.size(), m = b.size();
 
    // 边界：一个串变成空串
    for(int j = 0; j <= m; j++) dp[0][j] = j;    // a 空 -> 变 b 前 j 个：只需插入 j 次
    for(int i = 0; i <= n; i++) dp[i][0] = i;    // a 前 i 个 -> 空：只需删除 i 次
 
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1];                 // 末尾相同，不用操作
            else
                // 删除 / 插入 / 替换 三种取最小，再加一次操作
                dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
        }
    }
 
    cout << dp[n][m] << endl;
    return 0;
}

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
 
    bool hash[10] = { 0 };   // 标记 0~9 是否已经输出过
    for(int i = s.size() - 1; i >= 0; i--)   // 从个位往高位走
    {
        int x = s[i] - '0';                  // 数字字符转成整数
        if(!hash[x])                         // 第一次出现
        {
            cout << x;                       // 直接输出该数字（不换行）
            hash[x] = true;                  // 标记已输出
        }
    }
    return 0;
}

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
typedef long long LL;
 
int main()
{
    int n;
    cin >> n;
    priority_queue<LL, vector<LL>, greater<LL>> heap;  // 小根堆，存各个结点频次
 
    while(n--)                       // 读入全部频次
    {
        LL x;
        cin >> x;
        heap.push(x);
    }
 
    LL ret = 0;
    while(heap.size() > 1)           // 只剩一个结点时结束（那是根）
    {
        LL t1 = heap.top(); heap.pop();   // 最小
        LL t2 = heap.top(); heap.pop();   // 次小
        heap.push(t1 + t2);               // 合并为新结点放回
        ret += t1 + t2;                   // 累加即为带权路径长度增量
    }
 
    cout << ret << endl;
    return 0;
}

#include <iostream>
using namespace std;
 
typedef long long LL;
const int N = 1e5 + 10;
 
int n;
char s[N];
LL f[26];   // 已形成的 (不同前导字符, x) 对数
LL g[26];   // 字符 x 已出现的次数
 
int main()
{
    cin >> n >> s;
 
    LL ret = 0;
    for(int i = 0; i < n; i++)
    {
        int x = s[i] - 'a';
 
        ret += f[x];               // 当前字符作为第三个 b：前面所有 (a, x) 对均可成三元组
        f[x] = f[x] + i - g[x];    // 前面与 x 不同的字符个数为 i - g[x]，都与当前 x 配成新对
        g[x] = g[x] + 1;           // 当前这个 x 计入出现次数
    }
 
    cout << ret << endl;
    return 0;
}