首先膜拜扶苏巨佬%%%(不会有人不知道扶苏是个小黑子吧this)

题外话:这次T4竟然要用线段树,差评

T1:

题意:

给一个字符串，让你求其数字，大小写字母的数量。

题解

没啥好说的，直接模拟。

Code(考场代码)

#include <bits/stdc++.h>

using namespace std;

int cnt[3];
string s;

int main()
{
    cin >> s;
    for (int i = 0; i < s.size(); i ++ )
        if (isdigit(s[i])) cnt[0] ++ ;
        else if (s[i] >= 'a' && s[i] <= 'z') cnt[1] ++ ;
        else if (s[i] >= 'A' && s[i] <= 'Z') cnt[2] ++ ;
    for (int i = 0; i < 3; i ++ ) printf("%d ", cnt[i]);
    return 0;
}

T2:

题意:

具体地，有 $n$ 个编号从 $1$ 到 $n$ 的数列 $a_1, a_2, \dots a_n$，每个数列的长度均为 $m + 1$。第 $i$ 个数列 $a_i$ 满足递推式 $a_{i,j} = a_{i,j - 1} \times i$，其中 $1 \leq j \leq m$。而扶苏会告诉你每个序列的首项 $a_{i,0}$，你需要帮助她把这些数列按字典序排序。

数据规模与约定

对全部的测试点，保证 $1 \leq n \leq 10^5$，$1 \leq m \leq 10^9$，$1 \leq |a_{i,0}| \leq 10^9$。

提示

对两个数列 $a_i, a_j$，按如下方式比较其字典序：

找到最小的满足 $a_{i,p} \neq a_{j, p}$ 的下标 $p$，比较 $a_{i, p}$ 和 $a_{j, p}$ 的大小：

• 如果 $a_{i,p} < a_{j, p}$，则称 $a_i$ 的字典序比 $a_j$ 的小。
• 如果 $a_{i,p} > a_{j, p}$，则称 $a_i$ 的字典序比 $a_j$ 的大。

可以证明，在本题的限制下，这样的 $p$ 一定存在。

题解:

当第一项不同时，按第一项排序。
否则由于$i$不同，所以可以按第二项排序，注意要开$long long$

Code(考场代码)

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

typedef long long LL;

struct Node
{
    int v, id;
    bool operator < (const Node& t)
    {
        if (v != t.v) return v < t.v;
        return (LL)v * id < (LL)t.v * t.id;
    }
}a[N];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i].v), a[i].id = i;
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i ++ ) printf("%d ", a[i].id);
    return 0;
}

T3:

题意:

题目描述

给定 $n$ 个正整数 $a_1, a_2, a_3, \dots a_n$，记 $g$ 是这些数的最大公约数，$l$ 是这些数的最小公倍数。请你判断 $l \times g$ 是否等于 $a_1 \times a_2 \times \dots \times a_n$。

数据规模与约定

• 对 $100\%$ 的数据，保证 $2 \leq n,N \leq 5 \times 10^5$，$2 \leq a_i \leq 10^8$，$1 \leq T \leq 20$。

形式化题意:

判断$l \times g$是否等于$\prod \limits _ {i = 1} ^ n a_i$，其中$l = \gcd(a_1, a_2, \dots a_n),g=\operatorname {lcm}(a_1, a_2, \dots, a_n)$

题解:

$44pts$：开long long爆算gcd,lcm
$76pts$:
移项，得
$g = \frac{\prod \limits _ {i = 1} ^ n a_i}{l}$
但根据短除法得 $g \le \frac{\prod \limits _ {i = 1} ^ n a_i}{l ^ {n - 1}}$
所以$l$一定要等于1，且$\frac{a_1}{l} \dots \frac{a_n}{l}$两两互质
即$a_1,a_2,\dots,a_n$两两互质，输出YES,否则NO
暴力分解质因数，$O(n \sqrt n)$

Code(考场代码):

#include <bits/stdc++.h>

using namespace std;

const int N = 500010;

inline int read()
{
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 3) + (s << 1) + (c ^ 48);
    return s * w;
}

int n, a[N];
bool st[N];

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        n = read();
        for (int i = 1; i <= n; i ++ ) a[i] = read();

        int l = 0;
        for (int i = 1; i <= n; i ++ ) l = gcd(l, a[i]);
        if (n == 2)
        {
            puts("Yes");
            continue ;
        }
        if (l != 1)
        {
            puts("No");
            continue ;
        }
        for (int i = 1; i <= n; i ++ ) a[i] /= l;

        memset(st, 0, sizeof st);
        bool success = true;
        for (int i = 1; i <= n; i ++ )
        {
            int t = a[i];
            for (int j = 2; j <= t / j; j ++ )
            {
                if (t % j == 0)
                {
                    if (st[j])
                    {
                        success = false;
                        break ;
                    }
                    st[j] = true;
                    while (t % j == 0)
                        t /= j;
                }
            }
            if (t > 1)
            {
                if (st[t])
                {
                    success = false;
                    break ;
                }
                st[t] = true;
            }
        }
        puts(success ? "Yes" : "No");
    }
    return 0;
}

$100pts$:
分解质因数时用欧拉筛优化，做到$O(n \frac{\sqrt n}{\ln n})$

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1000010, M = 100000010;

int n;
vector<int> primes;
bitset<M> st;
int v[M];
unordered_set<int> S;

void init(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes.push_back(i), v[i] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            v[primes[j] * i] = primes[j];
            if (i % primes[j] == 0) break ;
        }
    }
}

int main()
{
    init(M - 1);

    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        S.clear();

        bool success = true;
        for (int i = 1; i <= n; i ++ )
        {
            int x;
            scanf("%d", &x);

            int now = x;
            while (now != 1)
            {
                if (S.count(v[now]))
                {
                    success = false;
                    break ;
                }
                now /= v[now];
            }

            while (x != 1)
            {
                S.insert(v[x]);
                x /= v[x];
            }
        }

        if (n == 2) puts("Yes");
        else puts(success ? "Yes" : "No");
    }
    return 0;
}

T4:

题意:

共有 $n$ 个彩灯从左到右排成一排，从左到右用 $1$ 到 $n$ 编号，第 $i$ 个彩灯的亮度是 $a_i$。对 $1 \leq i < n$，我们说 $i$ 号彩灯和 $i + 1$ 号彩灯是相邻的。

我们保证这 $n$ 盏灯的亮度互不相同。

一组彩灯的和谐度定义为这组彩灯中亮度最大和最小的两盏彩灯的亮度之差。

扶苏想从这 $n$ 个彩灯中选出 $m$ 个互不相邻的彩灯作为一组，她希望这组彩灯的和谐度尽可能小。请你帮她求出这个最小值。

形式化地，你需要在元素互不相同的数列 $a$ 中选出一个长度为 $m$ 的元素互不相邻的子列，使得子列的极差最小。

数据规模与约定

• 对 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq m \leq \lceil\frac{n}{2}\rceil$，$1 \leq a_i \leq 10^9$，$a_i$ 互不相同。

题解:

$28pts$: 特殊点送分拿下
$36pts$: 枚举最大和最小值，贪心选数
$100pts$:
由于知道了最小值以后，最大值的位置一定递增，考虑使用双指针优化
其中选数的操作就是判断最大值和最小值之间的长度$len$,$\lceil \frac{len}{2} \rceil == m$
可以使用 $set$ 或者 线段树 来维护，复杂度 $O(n \log n)$

这里使用线段树。

Code:

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct Node
{
    int l, r;
    int lmax, rmax, val;
}tr[N * 4];

void pushup(int u)
{
    Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (left.lmax == left.r - left.l + 1) root.lmax = left.lmax + right.lmax;
    else root.lmax = left.lmax;
    if (right.rmax == right.r - right.l + 1) root.rmax = left.rmax + right.rmax;
    else root.rmax = right.rmax;
    root.val = left.val + right.val - (left.rmax + 1) / 2 - (right.lmax + 1) / 2 + (left.rmax + right.lmax + 1) / 2;
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, 0, 0, 0};
    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 modify(int u, int x, int v)
{
    if (tr[u].l == tr[u].r) tr[u].lmax = tr[u].rmax = tr[u].val = v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

struct node
{
    int x, id;
    bool operator < (const node& t) const { return x < t.x; }
}a[N];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i].x), a[i].id = i;
    sort(a + 1, a + 1 + n);
    build(1, 1, n);

    int res = 0x3f3f3f3f;
    int l = 1, r = 0;
    while (l <= n)
    {
        while (r <= n && tr[1].val < m) if ( ++ r <= n) modify(1, a[r].id, 1);
        if (r <= n) res = min(res, a[r].x - a[l].x);
        else break ; 
        modify(1, a[l ++ ].id, 0);
    }

    printf("%d\n", res);
    return 0;
}