A.Replacing Elements—签到

题意：一个数组你可以执行任意次操作，每次操作可以选择用两个元素的权值和代替另一个元素的权值，问可不可以将数组内每个元素的权值都不高于指定的数值

思路：将数组排一下序判断最小值和次小值权值和是否小于等于指定的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;

int n, d;
int a[maxn];

void solve() {
    cin >> n >> d;
    bool flag = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] > d) flag = 1;
    }
    if (!flag) {
        cout << "YES" << endl;
        return;
    }
    sort(a + 1, a + n + 1);
    if (a[1] + a[2] <= d)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    // system("pause");
    return 0;
}

B.String LCM—思维

题意：两个字符串，定义字符串的因子就是字符串中的循环节，如 abab 的因子就是 ab 或者 abab，现在要求出给定的两个字符串的最小公倍子串 lcm，也就是说两个字符串都是 lcm 的因子同时 lcm 是被两个字符串整除的最小字符串，不存在这样的 lcm 输出 -1

思路：先假设两个字符串存在 lcm，因为两个字符串都是 lcm 的循环节那么 lcm 的长度一定是两个字符串长度的 lcm，然后用两个字符串分别去凑 lcm，如果凑出来的结果一致就说明 lcm 存在且就是凑出来的结果，如果不相等说明 lcm 不存在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        string a, b;
        cin >> a >> b;
        int lena = a.size(), lenb = b.size();
        int cnt = (lena * lenb) / __gcd(lena, lenb);
        string ans1 = "", ans2 = "";
        for (int i = 1; i <= cnt / lena; ++i)
            ans1 += a;
        for (int i = 1; i <= cnt / lenb; ++i)
            ans2 += b;
        if (ans1 == ans2)   //延伸到一样长度比较
            cout << ans1 << endl;
        else
            cout << -1 << endl;
    }
    // system("pause");
    return 0;
}

C.No More Inversions—规律

题意：给定一个数组 a:1,2,3,...,k,k-1,k-2,k-(n-k)(k<=n<2k)，请找出一个自然数 1-k 的排序使得按照规则 b[i]=p[a[i]] 生成的数组 b 是所有可能中字典序最小的并且 b 中逆序对数量不高于 a 逆序对的数量

思路：乍一看觉的挺麻烦的，于是就尝试从样例中找找规律：

  • 对于第二组样例，数组 a:1,2,1，输出结果是 2,1，数组 b 的逆序对数量恰好等于数组 a 的逆序对的数量
  • 对于第三组样例，数组 a:1,2,3,2，输出结果是 1,3,2，数组 b 的逆序对数量也恰好等于数组 a 的逆序对的数量

到这里可以发现数组 a 中最大值 k 后面的数和 k 前面的数重复了，并且答案恰好是对于重复的数不输出前面的数而输出后面的数，如果不确定这个规律可以再尝试几个反正归纳推理可以确定就是这个规律

这个规律应该是有相应严谨的数学证明，以本人的数学基础是难以解释通不过不影响我 A 掉这道题 😑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 100;

bool vis[maxn];
void solve() {
    memset(vis, 0, sizeof vis);
    int n, k;
    cin >> n >> k;
    if (2 * k - n == n) {
        for (int i = 1; i <= n; ++i)
            cout << i << ' ';
        cout << endl;
        return;
    }
    for (int i = k - 1; i >= 2 * k - n; --i)  //标记这些在 k 前面重复的数
        vis[i] = 1;
    for (int i = 1; i <= k; ++i) {
        if (vis[i]) continue;  //不输出这些数
        cout << i << ' ';
    }
    for (int i = k - 1; i >= 2 * k - n; --i)
        cout << i << ' ';
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    // system("pause");
    return 0;
}

D.Program—前缀后缀和+思维

题意：起初 x 的值是 0，给出一个长度为 n 的操作串，其中 + 代表将当前的 x 加 1，- 代表将当前的 x 减 -1。然后有 m 次询问，每次询问会产出操作串 [l,r] 区间的操作，请你计算出执行剩下的操作过程中 x 总共变成了多少个不同的值

思路：佩服自己训练的时候暴力模拟也敢往上写 😅。因为询问只考虑 x 的不同变化范围所以正确的方法是统计操作过程中出现的最大值和最小值，那么答案就是 maxx-minn+1，但是模拟遍历肯定是不行的会 TLE。考虑分别统计出前后缀区间 [1,i]和[i,n] 的最大值和最小值，如此删除区间 [l,r] 后最值一定是从剩余左右两个区间的最值中取出来，时间复杂度为O(1)，但是右区间由于缺少了删除区间的操作的 x 的变化范围整体发生改变，那么如何确定变化的数值用前缀和求出就可以了，同时借助前缀和也可以帮助我们计算出每个操作后当前 x 的值的同时顺便求出上述需要统计的前后缀区间的最大值和最小值

最后找答案的时候需要注意两个特殊情况：剩下区间全是左区间或者剩下区间全是右区间，另外还需要注意的细节是 x 起初还有个取值 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//用前缀后缀和分别维护区间[1,i][i,n]的最值O(1)查询答案
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 100;

int w[maxn];
char a[maxn];
int lmax[maxn], lmin[maxn], rmax[maxn], rmin[maxn];  //维护前缀和后缀区间的最值

signed main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        scanf("%s", a + 1);
        for (int i = 1; i <= n; ++i) {
            if (a[i] == '+')  //前缀和
                w[i] = w[i - 1] + 1;
            else
                w[i] = w[i - 1] - 1;
            //正向遍历一遍维护前缀区间的最值
            if (i == 1) {
                lmax[i] = w[i], lmin[i] = w[i];
                continue;
            }
            lmax[i] = max(w[i], lmax[i - 1]);
            lmin[i] = min(w[i], lmin[i - 1]);
        }
        for (int i = n; i >= 1; --i) {
            //再反向遍历一遍维护后缀区间的最值
            if (i == n) {
                rmax[i] = w[i], rmin[i] = w[i];
                continue;
            }
            rmax[i] = max(w[i], rmax[i + 1]);
            rmin[i] = min(w[i], rmin[i + 1]);
        }
        while (m--) {
            int l, r;
            cin >> l >> r;
            int k = w[r] - w[l - 1];
            int minn = 0, maxx = 0;  //起初x的取值也要算上
            if (l - 1 >= 1) {        //从剩余左区间更新最值
                minn = min(minn, lmin[l - 1]);
                maxx = max(maxx, lmax[l - 1]);
            }
            if (r + 1 <= n) {  //从剩余右区间更新最值
                minn = min(minn, rmin[r + 1] - k);
                maxx = max(maxx, rmax[r + 1] - k);
            }
            cout << maxx - minn + 1 << endl;
        }
    }
    // system("pause");
    return 0;
}