1. AcWing 3803. 数组去重

哈希表，记录最大的下标，O(n)

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

using namespace std;

const int N = 55;

int n;
int a[N];

int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        map<int,int> hash;
        cin >> n;
        for (int i = 0; i < n; i ++ ){
            cin >> a[i];
            hash[a[i]] = i;
        }
        int cnt = 0;
        for (int i = 0; i < n; i ++ ){
            if(hash[a[i]] == i) cnt ++ ; 
        }
        cout << cnt << endl;
        for (int i = 0; i < n; i ++ ){
            if(hash[a[i]] == i) cout << a[i] << ' '; 
        }
        cout << endl;
    }
    return 0;
}

2. AcWing 3804. 构造字符串

枚举，O(26n)

分类讨论：
1. 如果n < k , 后面补最小的字母即可
2. n >= k, 考虑前k个字符，从后往前考虑 能替换即可

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

using namespace std;

bool st[26];

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int n, k;
        cin >> n >> k;

        memset(st,0,sizeof st);

        string s;
        cin >> s;
        int minidx = 1e9;
        for(auto c : s) st[c - 'a'] = true, minidx = min(minidx, c - 'a');


        if(n < k){
            for(int i = 0;i < 26;i ++ )
                if(st[i]){
                    cout << s << char(i + 'a') << endl;
                    break;
                }
        }else{
            int idx;
            int temp;

            for(int j = s.size() -1;j >= 0;j -- )
            {
                bool f = false;
                int num = s[j] - 'a';
                for(int i = num + 1;i < 26;i ++ ){
                    if(st[i])
                    {
                        temp = i;
                        idx = j;
                        f = true;
                        break;
                    }
                }
                if(f) break;

            }
            // printf("idx = %d, temp = %d\n", idx, temp);
            s[idx] = temp + 'a';
            for(int i = 0;i <= idx;i ++ ) cout << s[i];
            for(int j = k - idx;j >= 2;j -- ) cout << char(minidx + 'a');
            cout << endl;

        }

    }

    return 0;
}

3. AcWing 3805. 环形数组

线段树模板题，暂时还不会，支持区间修改和区间查询

y总代码

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

using namespace std;

typedef long long LL;
const int N = 200010;
const LL INF = 1e18;

int n, m;
int w[N];

struct Node
{
    int l, r;
    LL dt, mn;
}tr[N * 4];

void pushup(int u)
{
    tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn);
}

void pushdown(int u)
{
    auto &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
    l.dt += root.dt, l.mn += root.dt;
    r.dt += root.dt, r.mn += root.dt;
    root.dt = 0;
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, 0, w[l]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void update(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].dt += d, tr[u].mn += d;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, d);
        if (r > mid) update(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

LL query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].mn;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        LL res = INF;
        if (l <= mid ) res = query(u << 1, l, r);
        if (r > mid) res = min(res, query(u << 1 | 1, l, r));
        return res;
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);
    build(1, 0, n - 1);
    scanf("%d", &m);
    while (m -- )
    {
        int l, r, d;
        char c;
        scanf("%d %d%c", &l, &r, &c);
        if (c == '\n')
        {
            if (l <= r) printf("%lld\n", query(1, l, r));
            else printf("%lld\n", min(query(1, l, n - 1), query(1, 0, r)));
        }
        else
        {
            scanf("%d", &d);
            if (l <= r) update(1, l, r, d);
            else update(1, l, n - 1, d), update(1, 0, r, d);
        }
    }

    return 0;
}