A. AcWing 4428. 字符串

题意：
给定一个字符串 $s$ ，判断26个字母是否都出现过，字母不区分大小写。

数据范围：
$1\leq len(s)\leq 100$

题解：
直接遍历统计即可。

代码：

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

typedef long long ll;

int cnt[26];

void solve() {
    string s;
    int n;
    cin >> n;
    cin >> s;
    for (auto u : s) {
        if (u >= 'A' && u <= 'Z') cnt[u - 'A'] += 1;
        else cnt[u - 'a'] += 1;
    }
    for (int i = 0; i < 26; ++i)
        if (cnt[i] <= 0) {
            puts("NO");
            return ;
        }

    puts("YES");
}

int main()
{
    int T = 1;
    //scanf("%d", &T);
    for (int i = 1; i <= T; ++i) {
        solve();
    }

    return 0;
}

B. AcWing 4429. 无线网络

题意：
给定 两个无线网络基站 $n_1$ 和基站 $n_2$的坐标， 以及 $n$ 头奶牛的坐标( $x_i, y_i$ )。
请你指定 $r_1$ 和 $r_2$ 的值，使得 $n$ 投奶牛都被无线网络覆盖。
其中 $r_1$ 是基站 $n_1$的辐射半径，$r_2$ 是基站 $n_2$的辐射半径。
奶牛被无线网络覆盖的条件是被 $n_1$ 和 $n_2$ 中至少一个辐射到。

问在覆盖所有奶牛的条件下，${r_1}^2 + {r_2}^2$尽可能小。

数据范围：
$1\leq n\leq 2000$
$-10^7\leq x_i, y_i\leq 10^7$

题解：
考虑从小到大枚举 $r1$ ，那么所有未被 $n_1$ 覆盖的奶牛就必须被 $n_2$覆盖。
预处理出所有奶牛到 $n_1$ 的距离 $v_1$ 以及到 $n_2$ 的距离 $v_2$。
按照 $v_1$ 排序，由小到大枚举 $r_1$，则后续部分中的最大值就是 $r_2$ 的值。

代码：

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

typedef long long ll;

const int N = 2010;

struct Node {
    ll x, y, v;
} a[N];
Node n1, n2;

ll get(ll x, ll y) {
    return x * x + y * y;
}

struct Dist {
    ll v1, v2, id;
} d[N];
ll suf[N];

void solve() {
    int n;
    scanf("%d%lld%lld%lld%lld", &n, &n1.x, &n1.y, &n2.x, &n2.y);

    for (int i = 1; i <= n; ++i) scanf("%lld%lld", &a[i].x, &a[i].y);

    ll r1 = 0, r2 = 0;
    for (int i = 1; i <= n; ++i) {
        d[i].v1 = get(a[i].x - n1.x, a[i].y - n1.y);
        d[i].v2 = get(a[i].x - n2.x, a[i].y - n2.y);
        d[i].id = i;
    }

    sort(d + 1, d + n + 1, [](const Dist& A, const Dist& B) {
        return A.v1 < B.v1;
    });

    ll res = 1e18;
    suf[n] = d[n].v2;
    suf[n + 1] = 0;
    for (int i = n - 1; i >= 1; --i) {
        suf[i] = max(suf[i + 1], d[i].v2);
    }

    for (int i = 0; i <= n; ++i) {
        res = min(res, d[i].v1 + suf[i + 1]);
    }

    printf("%lld\n", res);
}

int main()
{
    int T = 1;
    //scanf("%d", &T);
    for (int i = 1; i <= T; ++i) {
        solve();
    }

    return 0;
}

C. AcWing 4430. 括号序列

题意：
给定一个括号序列 $s$ ，每次翻转一个括号，问有多少个括号满足翻转后的括号序列是合法的。

数据范围：
$1\leq len(s)\leq 10^6$

题解：
首先， $len(s)$ 必然得是偶数，
其次， $pre[len(s)]$ 必须是 $2$ 或者 $-2$，这是因为翻转一个括号相当于对后缀都 $+2$ 或 $-2$

• $pre[len(s)] = 2$
  翻转一个左括号 $s_i$ ，翻转后 $s_i$ 为右括号，同时保证在翻转后，$pre[j]\geq 0(1\leq j\leq len(s))$

• $pre[len(s)] = -2$
  翻转一个右括号，$s_i$ ，翻转后 $s_i$ 为左括号，同时保证在翻转后，$pre[j]\geq 0(1\leq j\leq len(s))$

代码：

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

typedef long long ll;

const int N = 1000010;
char s[N];
int pre[N];
int temp[N]; 
int n;

void solve() {
    scanf("%d", &n);
    scanf("%s", s + 1);

    if (n & 1) {
        puts("0");
        return ;
    }

    for (int i = 1; i <= n; ++i) {
        pre[i] = pre[i - 1];
        if (s[i] == '(') pre[i] += 1;
        else pre[i] -= 1;
    }

    if (pre[n] != 2 && pre[n] != -2) {
        puts("0");
        return ;
    } 

    int res = 0;
    if (pre[n] == 2) {

        for (int i = 1; i <= n; ++i)
            if (pre[i] < 0) {
                puts("0");
                return ;
            }

        temp[n] = pre[n];
        for (int i = n - 1; i >= 1; --i) temp[i] = min(temp[i + 1], pre[i]);

        for (int i = 1; i <= n; ++i)
            if (temp[i] >= 2 && s[i] == '(') res += 1;

    } else {

        for (int i = 1; i <= n; ++i)
            if (pre[i] < -2) {
                puts("0");
                return ;
            }

        temp[1] = pre[1];
        for (int i = 2; i <= n; ++i) {
            temp[i] = min(temp[i - 1], pre[i]);
        }

        for (int i = 1; i <= n; ++i) {
            if (temp[i - 1] < 0) break;
            else if (s[i] == ')') res += 1; 
        }
    }
    printf("%d\n", res);
}

int main()
{
    int T = 1;
    //scanf("%d", &T);
    for (int i = 1; i <= T; ++i) {
        solve();
    }

    return 0;
}