情况

时间：2024年6月30日星期日 23:28
备注：暑假第一场VP，蓝桥杯之后基本没有做过题，cf的板子也没有准备，因此开了一次div3试试水。结果也是出奇的烂啊，只开了前4题，第四题还因为越做越乱而没有做完。
完成情况：

8684

题解

A：

三点求绝对值，没啥难度；

B：Matrix Stabilization

一个简单的贪婪题，按照序号每次找周围元素的最小值然后赋值即可。

感觉有更简便的形式，之后记得看竞速大佬的代码。

C：Update Queries

又是一道贪心。

题意

给出一组索引（指向原字符串位置），和一组备选字母，调整顺序，修改原来的字符串，从而使原来的字符串可以达到字典序最小值。

思路

给备选字母排序，每个需要修改的位置，从高到低给予能给的最小字典序字母即可。

代码

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        char target[N];
        for (int i = 1; i <= n; i++)
        {
            cin >> target[i];
        }
        int s[N];
        bool exist[N] = {false};
        for (int i = 1; i <= m; i++)
        {
            cin >> s[i]; // 索引
            exist[s[i]] = true;
        }
        char p[N];

        for (int i = 1; i <= m; i++)
        {
            cin >> p[i]; // 备选
        }
        sort(s + 1, s + m + 1);
        sort(p + 1, p + m + 1);
        // process
        int in = 1; // 备选
        for (int i = 1; i <= n; i++)
        {
            if (exist[i])
            {
                target[i] = p[in];
                in++;
            }
        }
        // cout
        for (int i = 1; i <= n; i++)
        {
            cout << target[i];
        }
        cout << endl;
    }
    return 0;
}

问题

33行中的if条件刚开始还限制非常多，想着什么必须要在索引排序后交接处啥的···，其实完全没有用。不谈了

D：Mathematical Problem

题意

提供数字字符串，及其长度n。要求添加n-2个加号或者乘号，使其结果式子的结果最小。

思路

比赛时有的思路：
讨论长度2和3.
有0的，结果为0；
有1的，要讨论（乱了），如果前n-1个数中没有1，要找连续两位数里最小的，然后写不完了。
复盘：无需讨论，直接遍历i，看i和i+1上数字情况。

官方题解：
首先，让我们遍历位置 i，这样我们就不用在第 i-th 和 (i+1)-th 元素之间放置一个数学符号。

接下来，我们有以下任务——我们有 n−1数字，我们需要在每对相邻数字之间放置一个 + or × 符号以最小化结果。有三种可能的情况：

如果至少有一个 0，答案是 0。我们可以简单地将所有符号放置为 ×.
如果所有数字都是 1，答案是 1。我们可以简单地将所有符号放置为 ×.
否则，答案是不等于 1 的数字之和。将大于 1 的数字相乘是没有好处的，所有 1 都可以简单地乘以任何邻居。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
int a[20], b[20], c;

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int tc;
    cin >> tc;
    while (tc--)
    {
        int n;
        string s;
        cin >> n >> s;
        // a[n]是数字数组
        for (int i = 0; i < n; i++)
            a[i] = s[i] - '0';
        int ans = 1e9;
        for (int i = 0; i + 1 < n; i++)
        {
            c = 0; // b数组用来算结果。
            for (int j = 0; j < n; j++)
            {
                if (i == j) // 讨论第i个数字，是否将它和下一个数字组成一个两位数
                    b[c++] = a[j] * 10 + a[j + 1];
                else if (i + 1 != j) // 没到第i个数字，就直接放
                    b[c++] = a[j];
            }
            bool f = 0; // 有0，直接break
            for (int j = 0; j < n - 1; j++)
                f |= b[j] == 0; // 检查 b[j] 是否为0，并根据结果设置 f 的最低位。如果 b[j] 为0，f 的最低位将被设置为1；否则，f 的值保持不变（如果它的最低位已经是1的话）
            if (f)              // 有0直接break
            {
                ans = 0;
                break;
            }
            int cur = 0; // 暂时答案
            for (int j = 0; j < n - 1; j++)
                if (b[j] != 1) // 不为1就加
                    cur += b[j];
            if (!cur)
                cur++;
            ans = min(ans, cur); // 比较哪种最小
        }
        cout << ans << '\n';
    }
    return 0;
}