钟柯哲哲的博客
钟柯哲哲7.12总结
钟柯哲哲 LV2 金丹期 LV 6 @ 2024-7-17 19:59:09

Day05 7.12总结

第一类：暴力(T1)

T1.小田的最大价值

本题十分的简单，可以第一个想到的是先将这个数组排好序，这样就可以方便的取到最大和最小值。

显而易见的是，对于 $|a_i - a_j| > k$ 的条件，应该让 $a_i$ 和 $a_j$ 的差尽可能大，那么在我们排好序的数组里，差最大的 $(a_i, a_j)$ 明显就是 $(a_1, a_n)$ ，一个最大值，一个最小值。但是，这是 $a_n - a_1 > k$ 的情况，只有这样才能取到 $\max (a_n, a_1)$ ，也就是最大值 $a_n$ 。但是如果在 $a_n - a_1 \le k$ 的情况下，就不能这样了。因为在这样的情况下，取的值会是 $\min (a_1, a_n)$ ，答案将是 $a_1$ 也就是最小值，显然是不行的。

那么，怎么样才能使 $\min (\{a_1, a_2, a_3...a_n\})$ 的值尽可能大呢？思考一下取什么值呢？ $a_n$ 肯定是不行的，因为没有比它还小的值；那么除 $a_n$ 外，什么值最大呢？容易看出，是 $a_{n - 1}$ ，也就是次大值，取 $\min (a_{n - 1}, a_n)$ 得到。

$Code:$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n, k, a[N];

signed main ()
{
	freopen ("max.in", "r", stdin);
	freopen ("max.out", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    sort (a + 1, a + n + 1);
    if (a[n] - a[1] > k) cout << a[n];
    else cout << a[n - 1];
    return 0;
}

感受与学习：无 (~~太简单了~~)

错误原因：无

第二类：简单算法(T2, 高精度 / 模拟, T3, 双指针 / DP)

T2.小田的交换数字

题目传送门

本题的中心思想在于如何保证两个字符串的若干位交换后积最小。

首先，有数学基础的人都知道，两个数的积，差越大，积越小。如： $10 \times 10$ 就比 $1 \times 20$ 要小。所以我们可以遍历两个字符串，小数放第一个字符串，大数放第二个字符串，这样乘起来就是积最小的了。同时由于 $1 \le n \le 2 \times 10^3$ ，也就是说字符串的位数最多有 $2000$ 位，所以一开始可以想到用 高精度 来做：需要一个高精加、高精乘低精、高精乘高精和高精除低精。最后输出余数。

$Code:$

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
string sa, sb;

vector <signed> AddG (vector <signed> &aG, vector <signed> &bG)
{
    vector <signed> ans;
    int t = 0;
    for (int i = 0; i < aG.size () || i < bG.size (); i ++)
    {
        if (i < aG.size ()) t += aG[i];
        if (i < bG.size ()) t += bG[i];
        ans.push_back (t % 10);
        t /= 10;
    }
    if (t) ans.push_back (t);
    return ans;
}

vector <signed> LMulG (vector <signed> &aG, signed &bG)
{
	vector <signed> ans;
	int t = 0;
	for (int i = 0; i < aG.size () || t; i ++)
	{
		if (i < aG.size ()) t += aG[i] * bG;
		ans.push_back (t % 10);
		t /= 10;
	}
	while (ans.back () == 0 && ans.size () > 1) ans.pop_back ();
	return ans;
}

vector <signed> MulG (vector <signed> &aG, vector <signed> &bG)
{
	vector <signed> ans;
	ans.push_back (0);
	for (int i = bG.size () - 1; i >= 0; i --)
	{
		vector <signed> mul = LMulG (aG, bG[i]);
		signed xn = 10;
		ans = LMulG (ans, xn);
		ans = AddG (ans, mul);
	}
	return ans;
}

vector <signed> DivG (vector <signed> &aG, int bG, int &r)
{
	r = 0;
	vector <signed> ans;
	for (int i = aG.size () - 1; i >= 0; i --)
	{
		r = r * 10 + aG[i];
		ans.push_back (r / bG);
		r %= bG;
	}
	reverse (ans.begin (), ans.end ());
	while (ans.back () == 0 && ans.size () > 1) ans.pop_back ();
	return ans;
}

signed main ()
{
	freopen ("mul.in", "r", stdin);
	freopen ("mul.out", "w", stdout);
    cin >> n >> sa >> sb;
    if (sa > sb) swap (sa, sb);
    for (int i = 0; i < n; i ++)
        if (sa[i] > sb[i]) swap (sa[i], sb[i]);
    vector <signed> aG, bG;
    int r;
    for (int i = n - 1; i >= 0; i --) aG.push_back (sa[i] - '0');
    for (int i = n - 1; i >= 0; i --) bG.push_back (sb[i] - '0');
    vector <signed> res = MulG (aG, bG);
    res = DivG (res, 998244353, r);
    cout << r;
    return 0;
}

再进一步思考，由于本题要求取余，所以可以边处理边操作，码量简短，这里就不贴出来了。

感受与学习：本题我知道了平时要多积累数学常识，多思考，多观察。

错误原因：无

T3.小田的气球真好看

题目传送门

本题有些许难度，可以用两种方法来做： 双指针 和 DP 。

做法1：双指针

本题的第一种做法是使用双指针 - 快慢指针，使用一个数组 flag[i] 表示颜色为 $i$ 的气球上次出现的位置、变量 l 表示起点，变量 r 表示能与 l 组成符合条件的最后一个气球的位置。

只要 l 不为 $n$ ，我们就可以一直枚举。每次首先要更新 r ， r 的更新条件为：

r 的下一个不为 $n$ 。
(与 3 选其中之一) $r$ 所在下一个位置气球的颜色是第一次出现，这样把下一个加进来也不会影响 $(l, r)$ 之间气球元素的性质。 ( flag[a[r]] == 0 )
r 所在下一个位置气球 和 上一个这种颜色的气球 距离不超过 $k$ ，也不会影响。

只要满足条件 1 和条件 2，3中的任意一个，则更新 r 使其 ++，也就是将下一个加进来且不影响，同时更新 flag[r] 的值。更新完 r 以后，就要更新答案了。答案可能在 r ~ l 这个区间中产生，又因为只要以 l 为起点，从它往后 $0$ 个， $1$ 个， $2$ 个 ······ $r - 1$ 个的区间都是符合条件的，一共有 $r - l + 1$ 个区间，所以有 $r - l + 1$ 个答案会在这中间产生，所以 ans += r - l + 1 。

下一步，该更新 l 了。本来这时只要 l ++ 就好了(将起点移至下一个) ，但是， l 往右移，万一移着移着，移出了 r 的范围，怎么办呢？其实也没有什么要处理的情况，由于 l 不会影响 r ，该移的照样移，所以只要更新 flag[a[l]] ，也就是 l 这个位置气球颜色上次出现的位置就好了，更新到 $0$ (没有出现过) 即可，这样在判断时就不会被前面和 l 颜色相同的元素影响了。

$Code:$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], k, flag[N];
long long ans;

int main ()
{
    freopen ("balloon.in", "r", stdin);
    freopen ("balloon.out", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    int l = 1, r = 0;
    while (l <= n)
    {
        while ((flag[a[r + 1]] == 0 || r + 1 - flag[a[r + 1]] <= k) && r < n)
            r ++, flag[a[r]] = r;
        ans += r - l + 1;
        if (flag[a[l]] == l) flag[a[l]] = 0;
        l ++;
    }
    cout << ans;
    return 0;
}

做法2：DP

DP 的做法思考量稍微简单(但也简单不到哪去)

用一个 f[i] 数组表示以 a[i] 为结尾的合法区间的数量， flag[i] 和上面定义一样，不多赘述 (下文以 last 表示 flag[a[i]])。

开始分类讨论：

初始化：以第一个元素结尾的可行区间只有它自己一个，所以 f[1] = 1 ，而 a[1] 这个气球颜色上一次出现的位置就是自己，所以 flag[a[1]] = 1 。

首先思考：每个气球都有选与不选两个决定， $f[i]$ 会从中赋值为较小值。

如果当前气球不选，那么 $f[i] = f[i - 1] + 1$ ，将所有以 $i - 1$ 结尾的区间都加上一个 $i$ ，再算上 $i$ 自己，共有 $f[i - 1] + 1$ 种可能。

如果当前气球选，会有多少种可能呢？这就要据情况而定了，详见下方。

$last = 0$ ：也就是说 a[i] 在这之前从来没有出现过，那么选的情况就是 $i$ ，因为选它不会有任何影响，则有 $i$ 个以 $a[i]$ 结尾的合法区间。
$i - last \le k$ ：这种情况下， $i$ 距离上次出现间隔不超过 $k$ ，可以选第 $i$ 个。那么选的可能就有 上次颜色 i 出现的位置合法区间数(f[last]) + i - last ，上次颜色 $i$ 出现的位置合法区间数加上 $i$ ，是将上次出现的合法区间接上现在的 $i$ 个区间；再减去 $last$ ，是因为这中间算了 $1, 2, 3... last$ 的区间数，由于 $last$ 之前会与 $flag[last]$ 冲突，而这里一共有 $last$ 个区间，所以减去 $last$ 。
$i - last > k$ ：这样的话，就不能将 $i$ 加到上个可能性后面了。和 $i$ 不冲突的区间数只有从 $last$ 到 $i$ 这一段区间，共有 $i - last$ 种可能，所以加上 i - last 。

注意：本文中 $last = 0$ 的情况是可以合并到第二种情况中去的，因为如果 $last = 0$ ，那么 $f[last] + i - last = 0 + i - 0 = i$ ，不影响。

最后，更新 flag[a[i]] 为 i 。

$Code:$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n, f[N], a[N], flag[N], sum, k;

signed main ()
{
	freopen ("balloon.in", "r", stdin);
	freopen ("balloon.out", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    f[1] = 1, flag[a[1]] = 1;
    for (int i = 2; i <= n; i ++)
    {
        int j = flag[a[i]];
        flag[a[i]] = i;
        if (i - j <= k) f[i] = min (f[j] + i - j, f[i - 1] + 1);
        else f[i] = min (i - j, f[i - 1] + 1);
    }
    for (int i = 1; i <= n; i ++) sum += f[i];
    cout << sum;
    return 0;
}

感受与学习：本题我知道了双指针 (或DP) 的运用要讲究。只有例如区间中符合某种条件、一次贡献多种可能性的问题就可用双指针，一般可将 $O(n^2)$ 优化为 $O(n)$ (或一般对已知问题可划分为小子问题的问题可用 DP)。

错误原因：对本题涉及的两种算法不熟练，特别是双指针，应该搞清楚如何用两个变量使双重 for 循环中的第二个变量"不回头"，优化掉 $O(n^2)$ 。

第三类：数据结构(T4, 栈)

T4.表达式求值

题目传送门

本题就是一道普通表达式求值的弱化版，运算不多。我们需要一个数字栈(但是元素类型为 char ) 和一个符号栈。

当遇到运算符 & , | 和 ! 时，就压入符号栈。
遇到 'f' , t 和左括号 ( 时将其入数字栈。
当遇到右括号时，就要对前边所记录的表达式进行求值了，这里求值又分为几步。
1. 想到可以构造一个函数 bool Calc (string, char, bool) ，三个参数分别是一个字符串，一个字符和一个要进行运算的初始值。字符串中只有 'f' 和 't' ，代表初始值将要与它们进行运算，其中 'f' 表示 false ， 't' 表示 true 。第二个参数字符一定为 & , | 或 ! 其中一个，代表要进行的运算(与，或和非) ，布尔型参数则为要运算的初始值。整个函数的大意就是给定运算数和符号，让你算出结果 ( 注意非号要先处理 )。
2. 现在我们要在主函数里得到刚才函数里说的要进行运算的初始值 ans 。但是 ans 既不能直接赋值为 true ，也不能赋值为 false ，而是应该赋值为本次要运算的表达式的第一个数，也就是拿出第一个数给 ans ，具体实现为：
```
ans = opt.top (); opt.pop ();
```
3. 接下来我们就要得到第一个参数—字符串。字符串的获取十分简单，只需要一直取出数字栈顶元素，直到栈顶元素为左括号停止 (当运算符为非时不会有这一步操作，因为仅有的元素也被 ans 拿出去了) 。
4. 记得用 pop 将 左括号也从数字栈里拿出来 ，否则会 造成死循环 。
5. 再从符号栈里取出一个运算符。
6. 随后将取出来的 ans 赋值为 Calc (取出来的字符串, 取出来的运算符, ans); 。
7. 最后将 ans 重新压入数字栈，是 true 则压入 't' ，否则压入 'f' 。
当以上操作结束后，判断栈顶元素是 true 还是 false 并输出即可。

$Code:$

#include <bits/stdc++.h>
using namespace std;
int t;

bool Calc (string s, char c, bool ans)
{
    if (c == '!') return ! ans;
    for (int i = 0; i < s.size (); i ++)
    {
        bool now;
        if (s[i] == 'f') now = false;
        else now = true;
        if (c == '&') ans &= now;
        else ans |= now;
    }
    return ans;
}

int main ()
{
    freopen ("expr.in", "r", stdin);
    freopen ("expr.out", "w", stdout);
    cin >> t;
    while (t --)
    {
        string s;
        stack <char> opt, num;
        cin >> s;
        for (int i = 0; i < s.size (); i ++)
        {
            char nw = s[i];
            if (nw == '&' || nw == '|' || nw == '!') opt.push (nw);
            else if (nw == 'f' || nw == 't' || nw == '(') num.push (nw);
            else if (nw == ')')
            {
                string ns = "";
                bool ans;
                if (num.top () == 't') ans = true;
                else ans = false;
                num.pop ();
                while (num.top () != '(')
                {
                    ns = ns + num.top ();
                    num.pop ();
                }
                num.pop ();
                ans = Calc (ns, opt.top (), ans);
                if (ans) num.push ('t');
                else num.push ('f');
                opt.pop ();
            }
        }
        if (num.top () == 't') cout << "true\n";
        else cout << "false\n";
    }
    return 0;
}

感受与学习：本题就是一道对栈和表达式求值的基本运用 (~~但我没写出来~~) ，在做这种题时，应该一个字符一个字符的用人脑去模拟算的过程，这个过程也就是计算机算的过程。

错误原因：对这种题缺乏信心，不愿意主动去做，下次不应该对这种题放弃希望，应该细致全面的去考虑栈中各种字符数字的情况与对其的分类。

第四类：搜索(T5, 深搜)

T5.小W去冒险

题目传送门

本题依然是一道很简单而普通的深搜题 ~~我依然不出所料的没做出来~~ 。

大致思路如下：每次只要找到一个值不为 $0$ 的格子，就深搜一次。

深搜的主要思想就是一个标记数组判断当前点有没有走过，如果没有走过就将当前点 $(x, y)$ 标记为已走过，并将原数组的这个位置赋值为 $0$ (这一步是为了在主函数里判断一个格子走没走过而使其不会重复判断) ，接下来使用方向数组去往四个方向搜，越界了跳过，要去的位置是 $0$ 也跳过(注意：标记过的地方不用判，因为一定没有标记过) ，再往后面搜。而最后的答案，由于在深搜时已经将走过的格子标记为了 $0$ ，所以深搜的次数就是答案，用一个 cnt 统计即可。

$Code:$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n, m, cnt, mp[N][N];
bool vis[N][N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void DFSmp (int x, int y)
{
    if (vis[x][y]) return;
    vis[x][y] = true, mp[x][y] = 0;
    for (int i = 0; i < 4; i ++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (! mp[nx][ny]) continue;
        DFSmp (nx, ny);
    }
}

int main ()
{
    freopen ("ymx.in", "r", stdin);
    freopen ("ymx.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            char c;
            cin >> c;
            if (c != '0') mp[i][j] = 1;
            else mp[i][j] = 0;
        }
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            if (mp[i][j])
            {
                cnt ++;
                DFSmp (i, j);
            }
        }
    }
    cout << cnt;
    return 0;
}

感受与学习：本题又双叒叕是一题搜索题，然后我又错了(我在这方面是真的薄弱) ，对搜索题一定要多加练习。

错误原因：依然是对搜索这方面锻炼不够，具体练习可以看我的 Day02博客 。

第五类：DP (T6, 线性DP)

T6.检查总结

题目传送门

本题就是一道看似复杂但是是 01背包 的题，因为每个评分都有选和不选两种抉择。

状态表示 ：用一个 $f[]$ 数组， $f[i]$ 表示从第 $i$ 项到第 $n$ 项需要删除多少项使序列合法(的集合) ，属性为最小 $\min$ ，并且由于是用后面的更新 $i$ ，所以要从后往前遍历。

初始化就很明显了： $f[n]$ ，从 $n$ 到 $n$ 只有一个数，而一个数是肯定不合法的，所以 $f[n] = 1$ 。

状态计算 ：每个评分都可以选择删或不删。

删的情况。如果当前评分删掉了，那么它对从后面接上来的合法序列就没有影响了，也就是可以将 $i - 1$ 这个位置的所有合法序列接到它后面，反正它已经被删掉了，但记住 $f[i]$ 自己也算删掉的一个。所以 $f[i] = f[i - 1] + 1$ 。
不删的情况。不删的话，说明它要用掉它后面的 $a[i]$ 个数字，这 $a[i]$ 个数字就用不了了，那么从 $i$ 到 $a[i] + i$ 的数字都不能删，能删的只有从 $a[i] + i + 1$ 开始到 $n$ 的数，所以从 $i$ 开始要删的数字个数就是从 $a[i] + i + 1$ 开始的删除数字个数， $f[i] = f[i + a[i] + 1]$ 。

注意：由于在一些题目中可能有特殊要求或情况(本题没有) ，类似 $f[i + a[i] + 1]$ 这种可能越界的下标要特判一下，在本题中就是 if (i + a[i] <= n) ，为什么不是 i + a[i] + 1 <= n 呢？因为如果从 $i$ 开始，刚好有 $a[i]$ 个数一直到 $n$ ，那么这个序列肯定不用删数字，如果加上了 $1$ ，就会让这种答案漏掉。但为了养成良好习惯，在这里用到了 $f[n + 1]$ ，由于 $n + 1$ 超出了 $n$ ，当然就不用删除数字(前面也能看出来，是删 $0$ 个数字) ，所以赋 $f[n + 1] = 0$ 。

最后的答案就是 $f[1]$ ，从 $1$ 到 $n$ 的最少删除数字数。

$Code:$

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, f[N], a[N];

int main ()
{
    freopen ("summary.in", "r", stdin);
    freopen ("summary.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    f[n] = 1, f[n + 1] = 0;
    for (int i = n; i >= 1; i --)
    {
        if (i + a[i] <= n) f[i] = min (f[i + 1] + 1, f[i + a[i] + 1]);
        else f[i] = f[i + 1] + 1;
    }
    cout << f[1];
    return 0;
}

感受与学习：本题其实就是一道 01背包 的小变形，但是我没有看出来，所以以后要对题目的性质与答案进行深入分析，思考是不是经过 伪装变形 的模版题。

错误原因：知道是 DP ，但没看出来是 01 ，更没看出来怎么做，认为是一道比较难的线性，所以先去做前几题去了。

钟柯哲哲7.12总结

Day05 7.12总结

第一类：暴力(T1)

T1.小田的最大价值

第二类：简单算法(T2, 高精度 / 模拟, T3, 双指针 / DP)

T2.小田的交换数字

T3.小田的气球真好看

做法1：双指针

做法2：DP

第三类：数据结构(T4, 栈)

T4.表达式求值

第四类：搜索(T5, 深搜)

T5.小W去冒险

第五类：DP (T6, 线性DP)

T6.检查总结

状态

开发

支持

关于

钟柯哲哲7.12总结

Day05 7.12总结

第一类：暴力(T1)

T1.小田的最大价值

第二类：简单算法(T2, 高精度 / 模拟, T3, 双指针 / DP)

T2.小田的交换数字

T3.小田的气球真好看

做法1：双指针

做法2：DP

第三类：数据结构(T4, 栈)

T4.表达式求值

第四类：搜索(T5, 深搜)

T5.小W去冒险

第五类：DP (T6, 线性DP)

T6.检查总结

状态

开发

支持

关于

登录