难度排序（仅供参考）：

第一阶段： E、G、K、J

第二阶段： B、A、C、D、F

第三阶段： I、H

防AK（别拷打我）：L

A. anon 的博弈

知识点：博弈论

先说结论：拿到编号最大牌的最后一张的为胜者。

结合样例 "1 2 2 3 3 3 4 4 4 4" 来说，我们把它分层次列出，从高到低：

题目要求从最高层 '4' 开始着手，由于拿走这一层的卡牌后只能添加更低层的牌，因此这层的卡牌数量一定会是逐渐减少的。

我们可以发现，拿到最后一张 '4' 的人，可以将下一层 '3' 的数量控制为偶数，以此来让自己继续拿到最后一张 '3'。

具体操作为：不管之前经历了多少次添加，当你拿到最后一张 '4' 时，

若 '3' 的数量为偶数则你不进行添加，

若为奇数，则添加一张 '3' ，这样就可以确保你能拿到最后一张 '3' 。

然后你又可以继续控制下一层 ‘2’ 的数量以让自己拿到最后一张 ‘2’,

然后你又可以继续...... , 这样你就成功拿到了最后一张 ‘1’，获得胜利。

因此，先手胜利的条件是拿到最高层的最后一张卡牌，即拿到编号最大的牌的最后一张。

若编号最大牌的数量为奇数则先手获胜，反之后手获胜。

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        vector<int> arr(n);

        int maxx = -1;
        for (int i = 0; i < n; ++i)
        {
            cin >> arr[i];
            //获取最大的编号
            maxx = max(maxx, arr[i]);
        }

        int res = 0;
        for(int i = 0; i < n; ++i)
        {
            //统计最大编号的数量
            if(arr[i] == maxx)
                res++;
        }
        //若为奇数，先手必胜
        if(res & 1)
            cout << "YES\n";
        else cout << "NO\n";
    }
}

B. rana 吃巴菲

知识点：动态规划 / 记忆化搜索

方法一: 动态规划

每个点的选择都会影响后续，而不会被后续的选择影响，因此我们仅需记录到达每个位置的最短时间，以决定之后位置的选择。

对于这道题，无论是dp数组的含义、初始化还是状态转移都很容易看出来：

对位置dp，含义是到当前位置花费的最小时间；
初始化是最一开始的0点，花费0秒；
状态转移有三种可能，取最小的那个：
1. 每一个位置都可以由上一步移动而来
2. 若当前位置是3的整数倍，则可以从 i / 3 的位置跳跃而来
3. 若当前位置有传送门的出口，则可以从对应入口传送而来

用 map 记录传送门的出口和入口，接下来从 1 遍历到 n，记录下到达这些位置花费的最短时间。思考到这里，本题已经解决了。

时间复杂度为 $\rm O (n)$ 。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> dp(n + 1);
    unordered_map<int, int> portal;
    int p, q;
    while (m--)
    {
        cin >> p >> q;
        //记录传送门的出口和入口
        portal[q] = p;
    }
    for (int i = 1; i <= n; ++i)
    {   
        //从前一点的位置移动
        dp[i] = dp[i - 1] + 1;

        //若为3的倍数，可以从 i/3 的位置跳跃
        if (i % 3 == 0)
            dp[i] = min(dp[i / 3] + 1, dp[i]);

        //若该点存在传送门的出口，可以从入口传送
        if(portal.find(i) != portal.end())
            dp[i] = min(dp[portal[i]] + 1, dp[i]);
    }

    //根据dp数组的含义，dp[n]即为“到达n点时花费的最短时间”
    cout << dp[n];

    return 0;
}

方法二：广度优先搜索（BFS）

将整个数轴想象成一个连通图，点 $x$ 与点 $x + 1$ 和 $3 * x$ 之间存在一条边，然后传送门又将 $p$ 和 $q$ 之间加了边，这样就变成了无向图的最短路问题，边的权值均为1，使用 $\rm bfs$ 可以轻松解决。

代码（偷的赛场提交代码，点击跳转）：

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

int main() {  
    int n, m;  
    cin >> n >> m;  

    map<int, int> mp;
    for (int i = 0; i < m; ++i) {  
        int p, q;  
        cin >> p >> q; 
        
        mp[p] = q;
    }   
    
    queue<pair<int, int>> q; 
    q.push({0, 0}); 
    
    bool vis[n + 1];
    memset(vis, 0, sizeof vis);
    
    vis[0] = 1;  

    while (!q.empty()) {  
        auto [pos, t] = q.front();  
        q.pop();  
        if (pos == n) {  
            cout << t; 
            return 0;  
        }  

        if (pos + 1 <= n && !vis[pos + 1]) {  
            vis[pos + 1] = 1;  
            q.push({pos + 1, t + 1});  
        }  

        if (3 * pos <= n && !vis[3 * pos]) {  
            vis[3 * pos] = 1;  
            q.push({3 * pos, t + 1});  
        }  
 
        if (mp.count(pos) > 0) {  
            int ying = mp[pos];  
            if (!vis[ying]) {  
                vis[ying] = 1;  
                q.push({ying, t + 1});  
            }  
        }  
    }  
    return 0;  
}

C. soyo 下象棋

知识点：广/深度优先搜索

方法一：广度优先搜索（BFS）

本题与最简单的bfs的区别无非就是大多数题都是上下左右移动，而本题的马是 “八面威风” 的移动，改一下方向即可。写法有很多，按自己的习惯来就行，

代码：

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    //方向数组
    int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};

    using tii = tuple<int, int, int>;
    int n = 10, m = 9;
    vector<string> arr(n);

    queue<tii> q;
    for (int i = 0; i < 10; ++i)
    {
        cin >> arr[i];
        for (int j = 0; j < 9; ++j)
        {   
            //找到起始点
            if (arr[i][j] == 'H')
                q.push({i, j, 0});
        }
    }
    while (!q.empty())
    {
        //取出队列中的首元素，分别为坐标x，坐标y，步数
        auto [x, y, z] = q.front();
        q.pop();
        for (int i = 0; i < 8; ++i)
        {   
            //进行八个方向的行走
            int xx = x + dx[i], yy = y + dy[i];
            if (xx >= 0 && xx < 10 && yy >= 0 && yy < 9)
            {
                if (arr[xx][yy] == '.')
                {
                    q.push({xx, yy, z + 1});

                    //标记，表示该点已经遍历过
                    arr[xx][yy] = ',';
                }
                if (arr[xx][yy] == 'O')
                {
                    //遇到‘O’，输出步数并终止该组输入
                    cout << z + 1 << endl;
                    return;
                }
            }
        }
    }
    //所有可到达的点全部遍历后，若未遇见‘O’，输出 -1
    cout << -1 << endl;
}
int main()
{
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

方法二：深度优先搜索（DFS）

话说在前，实际上，这样的最短路问题并不适合DFS，因为其本质上是穷举搜索，虽然能遍历所有可能的路径，但不保证第一次找到的解就是最短的，需要遍历所有可能路径才能确定最短步数，复杂度会非常高。

不过本题数据范围很小，因此可配合剪枝解决，即标记到达每个点时的步数，下次来到这个点时判断这一次步数是否低于上一次。

代码：

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

const int ROWS = 10, COLS = 9;
char board[ROWS][COLS];
int dist[ROWS][COLS];
int best; // 记录全局最少步数

// 定义马的 8 个移动方向（忽略蹩马腿规则）
int dx[8] = {1, 2, -1, -2, -1, -2, 1, 2};
int dy[8] = {2, 1, 2, 1, -2, -1, -2, -1};

void dfs(int x, int y, int steps) {
    // 如果当前位置是敌方棋子'O'，更新答案
    if(board[x][y] == 'O'){
        best = min(best, steps);
        return;
    }
    // 若当前步数已经不可能比当前最优解更优，则剪枝返回
    if(steps >= best) return;
    
    // 8 个方向
    for (int i = 0; i < 8; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        // 判断是否在棋盘内
        if (nx >= 0 && nx < ROWS && ny >= 0 && ny < COLS) {
            // 不能落在自己的棋子上
            if(board[nx][ny] == 'X') continue;
            // 如果此位置之前的步数更少，则没必要重复搜索
            if(steps + 1 < dist[nx][ny]) {
                dist[nx][ny] = steps + 1;
                dfs(nx, ny, steps + 1);
            }
        }
    }
}

int main(){
    int T;
    cin >> T;
    while(T--){
        for (int i = 0; i < ROWS; i++){
            for (int j = 0; j < COLS; j++){
                cin >> board[i][j];
            }
        }
        int sx = -1, sy = -1;
        for (int i = 0; i < ROWS; i++){
            for (int j = 0; j < COLS; j++){
                if(board[i][j] == 'H'){
                    sx = i;
                    sy = j;
                    break;
                }
            }
            if(sx != -1) break;
        }
        // 初始化距离数组，所有位置设为无穷大
        for (int i = 0; i < ROWS; i++){
            for (int j = 0; j < COLS; j++){
                dist[i][j] = INT_MAX;
            }
        }
        best = INT_MAX;
        dist[sx][sy] = 0;
        dfs(sx, sy, 0);
        // 如果 best 仍为 INT_MAX，表示无法吃到任何一个敌方棋子
        cout << (best == INT_MAX ? -1 : best) << "\n";
    }
    return 0;
}

D. taki 玩游戏

知识点：二分答案

注意到，消耗时间随生命值增多而减少，具有单调性，因此考虑二分答案，对生命值进行二分。

设定每天开始时生命值为 $\rm h$ ，当在一天连续挑战若干关卡后生命值不足以通过下一关时，需要休息一天（补满 $\rm h$ ），第二天继续挑战。

使用二分法在某个范围内寻找符合条件的最小 $\rm h$ ，不难发现这个范围的下界为数组中最大值+1，上界为数组和+1。

当然，也可以将下界设为 1，上界设为 $10^{14}+1$ 。

$\rm check$ 函数的思路：对于给定 $\rm h$ ，依次模拟挑战关卡：从第一关开始，每天生命值初始为 $\rm h$ ，遇到当前生命值 $\leq$ 本关卡消耗时，换一天，记录需要的天数；

若需要的天数 $\leq$ k，则说明当前的 $\rm h$ 符合要求，反之则不行

总的时间复杂度为 $\rm O(n * log_2 \space(\space \sum arr - max(arr)\space)\space)$ 。

代码：

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

signed main()
{
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    int sum = 0;
    for (auto &i : arr){
        cin >> i;
        sum += i;
    }
    auto check = [&](int hp) -> bool{
        //消耗天数
        int days = 0;
        //当前关卡
        int level = 0;
        //剩余生命
        int rem_hp;
        while (level < n)
        {   
            //新的一天补满生命
            rem_hp = hp;
            days++;

            //若使用的天数已经超过限制
            if (days > k)
                return false;

            for (; level < n; ++level)
            {
                //若剩余生命不足以通过本关，进入新一天
                if (rem_hp <= arr[level])
                    break;
                //否则剩余生命减去本关消耗
                rem_hp -= arr[level];
            }
        }
        //返回是否符合要求
        return days <= k;
    };

    //二分的上下界
    int l = *max_element(arr.begin(), arr.end()), r = sum + 2;
    while (l + 1 < r)
    {
        int mid = l + (r - l) / 2;
        //若符合要求，缩短上界
        if (check(mid))
            r = mid;
        //否则加大下界
        else
            l = mid;
    }
    cout << r;
    return 0;
}

E. tomori 捡石子

分类讨论 $n$ 和 $k$ 的奇偶性即可，每种情况的构造方法有很多，这里就各选择一个写出。

注意到，若 $n$ 为奇数同时 $k$ 为偶数，该题无解，输出-1。

对于其他情况，先开一个大小为 $k$ 的数组，由于每组都不能为0，所以先将其铺满 1。

接下来继续讨论，若 $n$ 和 $k$ 的奇偶性相同，则剩余的石子数量一定为偶数，把它们平均放在数组的两头即可。

若 $n$ 为偶数同时 $k$ 为奇数，将剩余的石子均放在数组的正中间即可。

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;
    //若n为奇数，k为偶数，无解
    if ((n % 2) && !(k % 2))
    {
        cout << -1;
        return 0;
    }
    vector<int> arr(k, 1);
    //剩余的石子数量
    int rem = n - k;
    //若n与k奇偶性相同，将剩余放在两头
    if(n % 2 == k % 2)
    {
        arr[0] += rem / 2;
        arr[k - 1] += rem / 2;
    }
    //否则全部放在中间
    else arr[k / 2] += rem;

    for (auto i : arr)
        cout << i << ' ';
    return 0;
}

F. ----✄---剪切线-------------

知识点: 滑动窗口 / 二分答案

方法一：双指针不定长滑动窗口，寻找最短子数组

这道题的本质是求符合要求的最短子数组，且数组中所有元素均为正数，滑动窗口十分适配。

窗口长度从 $\rm 0$ 开始，只要窗口内元素总和小于 $\rm k$ 就持续向右扩大窗口；当窗口内元素和大于等于 $\rm k$ 时，开始移动窗口左边界，缩小窗口，当再次小于 $\rm k$ 时，继续移动右边界，扩大窗口，重复以上操作，直到遍历完整个数组。

无法达成要求的条件则是 $\rm\sum arr < k$ ，即选择数组中所有数之后依然小于 $\rm k$ 。

时间复杂度为 $\rm O (n)$ 。

(特别注意：数组中的数加到一起会很大，需要开 $\rm long\space long$ )

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    int s = 0;
    for (auto &i : arr)
    {
        cin >> i;
        s += i;
    }
    //若数组和小于k
    if (s < k)
    {
        cout << -1 << '\n';
        return;
    }
    //特判等于1，因为n等于1不会进入下面的while循环
    if (n == 1)
    {
        cout << 1 << '\n';
        return;
    }
    //i是左指针，j是右指针
    int i = 0, j = 1;
    int res = INT_MAX;
    //当前的窗口内元素总和
    int sum = arr[i];
    while (j < n)
    {
        sum += arr[j];
        j++;
        while (sum >= k)
        {
            //更新结果，移动左指针
            res = min(res, j - i);
            sum -= arr[i];
            i++;
        }
    }
    cout << res << '\n';
}

signed main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

方法二：定长滑动窗口，对滑窗的长度进行二分

设选择的长度为 $\rm len$ ，设数组中所有长度为 $\rm len$ 的连续子数组和最大为 $\rm sum$ ，由于数组中所有元素均为正数，所以 $\rm len$ 越大， $\rm sum$ 越大，具有单调性，因此可以考虑二分答案，对长度 $\rm len$ 进行二分。

不难发现二分的下界为 1，上界为 $\rm n$ 。

对于给定的长度 $\rm len$ ，在数组中遍历所有该长度的连续子数组，比较他们的和与 $\rm k$ 的大小，若某个连续子数组的和大于等于 $\rm k$ ，说明当前这个 $\rm len$ 符合要求，需要缩短上界；相对地，如果遍历的一遍连续的子数组发现没有任何一个子数组的和大于等于 $\rm k$ ，则需要加大下界。

无法达成要求的条件则是 $\rm\sum arr < k$ ，即选择数组所有数之后依然小于 $\rm k$ 。

遍历子数组的时间复杂度为 $\rm O(n)$ ，再乘上对长度进行二分，所以总的时间复杂度为 $\rm O(n * log_2 \space n)$ ，对于 $10^5$ 也是可以接受的。

(特别注意：数组中的数加到一起会很大，需要开 $\rm long\space long$ )

代码：

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

#define int long long
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    int s = 0;
    for (auto &i : arr)
    {
        cin >> i;
        s += i;
    }
    //若数组和小于k
    if (s < k)
    {
        cout << -1 << '\n';
        return;
    }

    auto check = [&](int len) -> bool
    {   
        //定长滑窗
        int i = 0, j = len;
        int sum = 0;
        //记录窗口总和
        for (int i = 0; i < len; ++i)
            sum += arr[i];
        while (j < n)
        {   
            //滑动，同时持续记录当前窗口总和
            sum += arr[j];
            sum -= arr[i];
            i++, j++;
            
            if (sum >= k)
                return true;
        }
        return sum >= k;
    };

    int l = 0, r = n + 1;
    while (l + 1 < r)
    {
        int mid = (l + r) / 2;
        if(check(mid))
            r = mid;
        else l = mid;
    }
    cout << r << '\n';
}

signed main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

G. sakiko 送报纸

知识点：并查集

并查集板子题，没什么好说的。注意路径压缩，本题特意卡了这点

代码：

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

int find(int x, vector<int> &p)
{   
    return x == p[x] ? x : p[x] = find(p[x], p);
}
void merge(int x, int y, vector<int> &p)
{
    p[find(x, p)] = find(y, p);
}
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n; ++i)
        p[i] = i;

    int a, b;
    while (k--)
    {
        cin >> a >> b;
        a--, b--;
        merge(a, b, p);
    }
    unordered_set<int> s;
    for (auto i : p)
        s.insert(find(i, p));
    cout << s.size();
}
signed main()
{
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

H. mutsumi 弹吉他

知识点：思维，构造，数论

题目要求将数组变为每相邻的两个数都互质，数组中最大的数也仅仅到 $10^9$ ，那么大于 $10^9$ 的质数一定与数组中的每个数都互质，而符合要求的数嘛，我们有一个熟人： $10^9 + 7$ （大于 $10^9$ 的最小质数，为便于观看，下面用 $a$ 代替）。

因此这道题只需要每隔一个数变一个 $10^9 +7$ 。

例如样例 $\rm 9\space 6 \space 3\space 11 \space 15$ ；

我们可以将其变为： $6 \space\space a \space\space 3\space\space a \space\space 15$ 。

具体操作为：选择 $i, i+1$ ，使 $a_i, a_{i+1}$ 分别变为 $\rm min(a_i,\space a_{i+1})$ 和 $10^9+7$ ， $i$ 从 $1$ 到 $n - 1$ ，步长为 $2$ 。

这样无论 $n$ 是奇数还是偶数都可以完成每相邻两个数互质，同时操作次数固定为 $n / 2$ 次（整除）。

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> arr(n);
        for (auto &i : arr)
            cin >> i;

        cout << n / 2 << '\n';

        for (int i = 0; i < n - 1; i += 2)
            cout << i + 1 << ' ' << i + 2 << ' '
                 << min(arr[i], arr[i + 1]) << ' ' << (int)1e9 + 7 << '\n';
    }
    return 0;
}

I. nyamu 发视频

知识点：贪心

观察操作特点可以注意到：每次操作会使其中一个数变为0；我们的目的是将序列变为非递减序列，因此要尽可能让左边的数变0，而非右面。

贪心策略：自左向右“清零”。首先可以注意到，如果 $a_1 > a_2$ ，那么是不可能让序列变为非递减序列的，因为即使进行“操作”也只能让序列变为 $(a_1 - a_2),\space 0,\space ......$ ，它将永远不会是非递减序列。

若 $a_1 <= a_2$ ，对 $a_1,\space a_2$ 进行“操作”，这样会让 $a_1$ 变成 0 的同时减小 $a_2$ ，一定会是最优的策略，令 $s = a_2 - a_1$ ，则序列变为 $0, \space s\space , a_3\space , ......$ ；

同样地，如果 $s > a_3$ ，序列将永远不会变成非递减序列。反之，进行“操作”，使序列变为 $0, \space 0\space , s\space , a_4\space , ......$ ；

$......$

那么接下来的判断就一目了然了，循环以上操作，若出现某个余量 $s > a_i$ 则答案为 “NO” ；若经过这一系列操作成功将序列全部清零或仅剩最后一个元素则答案为“YES”

代码：

#include<bits/stdc++.h>
using namespace std;
void Akira()
{
    int n;
    cin >> n;
    vector<int> arr(n);
    for(auto &i : arr)
        cin >> i;
    if (arr[1] < arr[0])
    {
        cout << "NO\n";
        return;
    }
    int s = arr[1] - arr[0];
    for (int i = 2; i < n; ++i)
    {
        if (s > arr[i])
        {
            cout << "NO\n";
            return;
        }
        s = arr[i] - s;
    }
    cout << "YES\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_--)
        Akira();

    return 0;
}

J. umiri 抄笔记

知识点：质数筛

（本题数据给弱了，暴力不应该能过的QAQ，下面是标准解法）

先预处理，使用质数筛筛出质数，然后判断每个小于 $n$ 的数 $i$ 是否符合

是质数
$n - i$ 是质数

若符合则说明找到了一组符合条件的数并终止本组，若遍历到了 $n$ 还没找到这样的一组数则输出 -1。（但其实永远都不会出现 -1 的）

时间复杂度最差也仅仅为 $\rm O(n)$ 。

代码：

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

const int N = 1e5 + 5;
vector<int> isPri(N, 1);
//预处理，质数筛
void pre()
{
    isPri[0] = isPri[1] = 0;
    for (int i = 2; i <= sqrt(N); ++i)
        if (isPri[i])
            for (int j = i * i; j <= N; j += i)
                isPri[j] = 0;
}
void solve()
{
    int n;
    cin >> n;
    for (int i = 2; i < n; ++i)
    {
        if (isPri[i] && isPri[n - i])
        {
            cout << i << ' ' << n - i << '\n';
            return;
        }
    }
    cout << -1 << '\n';
}
int main()
{
    pre();
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

K. uika 去超市

知识点：哈希表，集合

方法一: 使用STL

使用 $\rm set、map$ 都可以，更推荐 $\rm unordered\_set$ 或 $\rm unordered\_map$ ，前两个各种操作的时间复杂度均为 $\rm O(log\space n)$ ，而后两个均为 $\rm O(1)$ ，当然对于这道题无所谓，并没有卡那么紧。

回到问题，实际上就是给出两个数组，需要去除第一个数组中所有的第二个数组中出现的元素，进一步地说，我们需要做的就是对于第一个数组中的每个元素，确认它是否再第二个数组中存在即可。而上面提到的四个 $\rm STL$ 容器都有一个 $\rm find$ 方法，可以快速查询容器中是否含有某个元素。

若用 $\rm set$ 或 $\rm map$ ，时间复杂度为 $\rm O(n*log\space m)$ ；若用 $\rm unordered\_map$ 或 $\rm unordered\_set$ ，时间复杂度为 $\rm O(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> uik(n);
    unordered_set<int> skk;
    //unordered_map<int,int> skk;
    for(auto &i : uik)
        cin >> i;
    int tmp;
    while (m--)
    {
        cin >> tmp;
        // skk[tmp] = 1;
        skk.insert(tmp);
    }

    for (auto i : uik)
    {
        //若没有找到元素i
        if (skk.find(i) == skk.end())
            cout << i << ' ';
    }

    return 0;
}

方法二：二分查找

可以将第二个数组排序，接下来对于第一个数组的所有元素，查找是否存在于第二个数组，若不存在直接输出，当然查找是用二分查找。

时间复杂度为 $\rm O(n * log\space m)$ 。代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> uk(n), skk(m);
    for (auto &i : uk)
        cin >> i;
    for (auto &i : skk)
        cin >> i;

    sort(skk.begin(), skk.end());
    for (auto i : uk)
    {
        int l = -1, r = m;
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;
            if (skk[mid] >= i)
                r = mid;
            else
                l = mid;
        }
        if (skk[r] != i)
            cout << i << ' ';
    }
    return 0;
}

L. sumimi 才不会解散！

知识点：单调栈

单调栈推荐视频（点击跳转）

题目要求找出所有子数组中最小的值，我们可以反过来想，即依次判断每个元素在几个子数组中最小。例如样例 $3\space 1\space 2\space 4$ 中， $3$ 在 $1$ 个子数组中最小， $1$ 在 $6$ 个子数组中最小， $2$ 在 $2$ 个子数组中最小， $4$ 在 $1$ 个子数组中最小；则答案为 $3 × 1 + 1 × 6 + 2 × 2 + 4 × 1 = 17$ 。

这样，问题就变成了如何判断某个元素在几个子数组中最小。

若 $x$ 为我们要判断的元素，则符合条件的子数组一定不能包含比 $x$ 小的元素，因此我们可以去找 $x$ 左右两边第一个出现的比 $x$ 小的元素，到这里的距离就是子数组的 “边界”（若没有比 $x$ 小的元素则边界为数组之外）。方便起见，分别设 $l,\space r$ 为左右边界距离，根据乘法原理，符合条件的子数组数量为 $l * r$ 。例如样例中 $2$ 的 $l,\space r$ 分别为 $1$ 和 $2$ ，则以 $2$ 为最小值的子数组数量为 $l * r = 2$ 个。

至此，问题已经变成寻找每个元素的左右 “边界”。这里就和上面挂的视频高度相似了，只不过需要分别记录一下左右两边。以左边界举例，如果数组存在以下段：

$\{... , 5, 3, 7, ...\}$

当我们遍历到 $7$ 及后面时候， $5$ 一定不会成为左边界，因为在这之前有更小的 $3$ ；由此可得若 $x$ 后面出现了小于 $x$ 的数时， $x$ 就没用了，需要扔掉 $x$ ，选取栈正好合适。

转化为若当前元素 $x$ 小于栈顶元素，则 $\rm pop$ 掉栈顶元素，重复此操作，直到栈顶元素不小于 $x$ 或者栈为空；这样， $x$ 到栈顶元素的距离就是 $x$ 的边界了，因为现在的栈顶元素一定是第一个小于 $x$ 的元素；而若栈为空则说明在 $x$ 前面不存在小于 $x$ 的元素。

判断右边界则进行基本相同的操作，要特别注意有相同元素的情况，判断左右边界时不要重复计算。

只遍历了一边数组，时间复杂度为 $\rm O(n)$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;

    const int mod = 1e9 + 7;
    using pii = pair<int, int>;

    vector<int> arr(n + 2);
    for (int i = 1; i <= n; ++i)
        cin >> arr[i];

    //数组左右两端加个-1，方便处理
    arr[0] = -1;
    arr[n + 1] = -1;

    // 记录每个元素左右最近的比其小的元素距离
    // first为左边界，second为右边界
    vector<pii> record(n + 2);

    // 模拟栈，first为元素值，second为元素下标，方便计算距离
    vector<pii> stk;

    for (int i = 0; i <= n + 1; ++i)
    {
        while (!stk.empty() && arr[i] <= stk.back().first)
            stk.pop_back();
        // 记录左边距离
        if (!stk.empty())
            record[i].first = i - stk.back().second;
        stk.push_back({arr[i], i});
    }

    stk.clear();

    for (int i = n + 1; i >= 0; --i)
    {
        while (!stk.empty() && arr[i] < stk.back().first)
            stk.pop_back();
        // 记录右边距离
        if (!stk.empty())
            record[i].second = stk.back().second - i;
        stk.push_back({arr[i], i});
    }

    // 计算总和
    int res = 0;
    for (int i = 1; i <= n; ++i)
    {
        long long t = 1ll * arr[i] * record[i].first * record[i].second % mod;
        res = (res + t) % mod;
    }
    cout << res;
}

题解 | #大连民族大学ACM工作室训练赛题解#