1. AcWing 3778. 平衡数组

数学，模拟样例

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t -- )
    {
        int n;
        cin >> n;

        cout << n << endl;
        for(int i = 1;i <= n; i ++ ) cout << i << ' ';
        cout << endl;
    }
    return 0;
}

2. AcWing 3779. 相等的和

哈希表，O(n)

踩坑点：用数组当哈希表时，下标不能是负数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int k;
int a[N];
PII hash1[N];

int main()
{
    scanf("%d", &k);

    for(int i = 1;i <= k;i ++ )
    {
        int n;
        scanf("%d", &n);
        int s = 0;
        for (int j = 1; j <= n; j ++ )
        {
            scanf("%d",&a[j]);
            s += a[j];
        }

        for (int j = 1; j <= n; j ++ )
        {
            int x = s - a[j];
            if(hash1[x].first != 0 && hash1[x].first != i){
                printf("YES\n");
                printf("%d %d\n",i, j);
                printf("%d %d\n",hash1[x].first, hash1[x].second);
                return 0;
            }
            hash1[x] = {i, j};
        }
    }

    printf("NO\n");

    return 0;
}

3. AcWing 3780. 构造数组

递推+单调栈，O(n)

思路分析：

以为是构造题，结果听y总分析。题目答案要求是一个单峰图形，那么一定存在峰值。枚举每个点作为峰值，然后递推构造答案数组。

y总代码，不理解为什么从for (int i = k + 2; i <= n; i ++ ) k + 2开始？？？

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 500010;

int n;
int w[N];
LL l[N], r[N];
int stk[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    int tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        while (tt && w[stk[tt]] >= w[i]) tt -- ;
        l[i] = l[stk[tt]] + (LL)(i - stk[tt]) * w[i];
        stk[ ++ tt] = i;
    }

    tt = 0;
    stk[0] = n + 1;
    for (int i = n; i; i -- )
    {
        while (tt && w[stk[tt]] >= w[i]) tt -- ;
        r[i] = r[stk[tt]] + (LL)(stk[tt] - i) * w[i];
        stk[ ++ tt] = i;
    }

    LL res = 0, k = 0;
    for (int i = 1; i <= n; i ++ )
    {
        LL t = l[i] + r[i + 1];
        if (t > res) res = t, k = i;
    }

    for (int i = k - 1; i; i -- )
        w[i] = min(w[i], w[i + 1]);
    for (int i = k + 2; i <= n; i ++ )
        w[i] = min(w[i], w[i - 1]);

    for (int i = 1; i <= n; i ++ )
        printf("%d ", w[i]);
    return 0;
}