Summer 1400A

$D$ Absolute Sorting

$Idea$

这类题型，可以抽象出这样一种框架。

你需要解决一个问题，你不知道如何下手，但是你发现，这个问题的部分情况很容易想出来。

从而你去思考部分情况，然后发现部分情况可以组合起来，涵盖所有情况。

$D$ Priority queue

因为我对这个东西并不怎么了解，不知道什么时候该使用优先队列。

但据我做过的题目而言，它具有一些特点。

首先，会有多轮判断，每轮解的情况和当前最大值或最小值有关。

每次对当前轮次操作后，操作后的结果会重新进入。

最后，就是，这么操作的结果是最优的。

不过，不如说，就如数学归纳法一般，具有这种性质。

$G$ Inaccurate Subsequence Search

$Idea$

思路很直接，很明显是滑动窗口。但是代码有可取之处，为了下一次加速思考，记录如下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


    int tmp = 0;
    for(int i = 0; i < m; ++i) {
        if(cnt[a[i]] > 0) {
            tmp ++;
        }
        cnt[a[i]] --;
    }
    int ans = (tmp >= k);
    for(int i = m; i < n; ++i) {
        int t = i - m;
        cnt[a[t]] ++;
        if(cnt[a[t]] > 0) {
            tmp --;
        }
        if(cnt[a[i]] > 0) {
            tmp ++;
        }
        cnt[a[i]] --;
        if(tmp >= k) {
            ans ++;
        }
    }

代码目的是统计 $a$ 数组中元素在 $b$ 数组中的出现状况 (不重复)。

$H$ Suffix Structures

$Idea$

题本身很简单，记录一个应该会经常要用到的板子，判断 $s_{1}$ 是不是 $s_{2}$ 的子序列。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


bool check(const std::string& s1, const std::string& s2) {
    if (s1.size() > s2.size()) {
        return false;
    }
    
    int i = 0;
    int j = 0;

    while (i < s1.size() && j < s2.size()) {
        if (s1[i] == s2[j]) {
            i++;
        }
        j++;
    }

    return (i == s1.size());
}

$L$ Jumping Through Segments

$Statement$

你每次可以移动 $k$ 单位距离，现给定 $n$ 个区间，你每一次移动必须要落在这 $n$ 个区间内。求出最小的 $k$ ，满足题意。

$Idea$

二分答案。

首先，我认为二分只是工具，而不是目的。在考虑直接求出 $k$ 的情况十分困难下，应该逆向思维，先确定 $k$ ，然后去思考怎么来。

如果可以顺利想出，那么才应该考虑二分。

虽然逆向可能不是正解，但是这绝对可以打开思路。

还有一种我已经记牢的思路，在处理一个按照时间先后的序列时，如果当前状态依赖于未知状态。应该倒过来思考，使得未来状态已知，推导历史状态。

顺便吐槽一下，这个题应该评到 $1500$ 而不是 $1400$ 。

$Q$ Meximum Array

求$MEX$的方法，求 $MEX$ 本身并没有算法，也就是说，最优的思路，就是枚举 $MEX$ 。

枚举 $MEX$ 可以使用数组或者集合，在 $O(N)$ 或者 $O(N\log N)$ 内求出。

那么，求 $MEX$ 这个过程，就会与枚举过程有关。

最近做过的两个题，上面一个思路很暴力，但是解法的时间复杂度有点复杂。

但是，只要知道 $MEX$ 不会超过数组本身的长度，就可以计算出时间复杂度。

下面那个题很好，逆转思维，计算哪些区间会产生这样的 $MEX$。

由于数组不会给到 $1e7$，实际上，可以把大于 $n$ 的值全部改成 $n + 1$ 。

在全排列中，还有这样的特殊性质 :

$$ m=MEX_{i=1}^{j} a_{i} = min_{k=j+1}^{n} a_{k} $$

由于 $MEX$ 是序列的补集的最小值，所有比 $m$ 小的数都在 $lhs$ 中，$m$ 在 $rhs$ ，上式自然满足。

$S$ Vlad and a Pair of Numbers

在整数加法中，满足

$$ a+b= a \oplus b + (a \& b) \ll 1 $$

也就是说 $a+b$ 的值，等于不进位的和 $+$ 所有进位的值。

$T$ Hossam and Friends

好题。

我最开始的思路是直接计算总贡献，但是不太好算。

于是转换思路，考虑先计算最大贡献，然后再减掉消耗，但是也不好算。

但是在计算过程中发现，区间越小，消耗越大。而且前面的区间会影响后面的区间。

此时已经用时很长了，如果是赛时，我可能会接着往后面想，离出答案也不远了。

但是是练习，便干脆放弃看答案，答案利用了我发现的性质，进行区间压缩，再从后往前填表。最后直接计算贡献。

我很开心的一点是，我的整个思路过程是走在正轨上的，我的每一步分析都在往正解靠近。

这是我在高中不会有的体验，也是这些日子训练给我带来的最大的提升。

我并没有多学什么算法，期间就学了个数论分块，但是我的思维质量很明显有提升。

$Other$ Summary

大部分我没有写出来的题，是因为我没有观察到那个题目的 $trick$ ，这个东西，是随刷题数上升，经验上涨，会自然提升的。

就像什么看到 $gcd$ 就要想到 $lcm$ 。这两个东西之间自然有密不可分的练习，但是如果题目要结合这两个东西，更加本质的性质往往是质因数分解。

我现在虽然思维上来了，但是科技点严重不足，而且眼界不够宽广。也就是说，我刷的题，难度不够。我练的题，没有套路。

还有，我写一些题，我虽然能写出来，但是并不是那种我一眼看到，就出思路，得结果。往往是一开始一点思路没有，然后开始造样例，分析，慢慢的得到思路。

对于一些推公式的题目，我思路也不会很顺畅。总之就是，还有很大的提升空间。

仰天大笑出门去，我辈岂是蓬蒿人。