前言

T1

原题CF2117C。这题维护两个set就行。首先考虑到一点，如果当前段已经符合抽象分割了，那么就应该分割，使得后面有尽可能多的元素用来分割。然后我们注意到，抽象分割具有传递性，也就是如果$b_{j+2}$是$b_{j+1}$的抽象分割，那么$b_{j+2}$也是$b_j$的抽象分割。这一点非常好说明，利用性质就行。接下来我们能得到一个进一步的结论，也就是如果$b_j$是一个抽象分割，那么它一定出现了前面的所有元素，好像击鼓传花一样。

既然这样，我们只要维护两个set，第一个set $global$表示到目前为止出现的所有元素，第二个set $cur$表示当前段的元素。根据刚刚第二个结论，如果两个set相等，则这里就可以分段。

std:

// CF2117C
#include <bits/stdc++.h>

using namespace std;
set<int> cur, global;

int main()
{
    int T;
    cin >> T;
    while (T--) {
        int n, ans = 0;
        cur.clear();
        global.clear();
        cin >> n;
        int a[n + 1];
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i <= n; i++) {
            global.insert(a[i]);
            cur.insert(a[i]);
            if (global.size() == cur.size()) {
                ans++;
                cur.clear();
            }
        }
        if (ans == 0)
            cout << 1 << endl;
        else
            cout << ans << endl;
    }
    return 0;
}

T2

原题CF2094D。这题把两个序列都按照连续的L和R分段。然后，如果第一段所代表的元素就不一样，那么它结果一定是NO。对于剩下的一个一定是L和R交错的序列，我们统计个数，如果$s$中对应元素在$p$中对应元素一倍到两倍之间，则有可能正确，反之，输出NO。

// CF2094D
#include <bits/stdc++.h>
#include <cstring>

using namespace std;

constexpr int MAX_N = 2e5 + 1;
int ps[MAX_N], pp[MAX_N];
int pspt = 1, pppt = 1;

int main()
{
    int T;
    cin >> T;
    while (T--) {
        // Reset
        memset(ps, 0, sizeof(ps));
        memset(pp, 0, sizeof(pp));
        pspt = 1;
        pppt = 1;
        // Input
        string p, s;
        cin >> p >> s;
        if (p[0] != s[0]) {
            cout << "NO" << endl;
            continue;
        }
        // Execute
        pp[pppt] = 1;
        for (int i = 1; i < p.size(); i++) {
            if (p[i] != p[i - 1]) {
                pppt++;
                pp[pppt] = 1;
            } else {
                pp[pppt]++;
            }
        }
        ps[pspt] = 1;
        for (int i = 1; i < s.size(); i++) {
            if (s[i] != s[i - 1]) {
                pspt++;
                ps[pspt] = 1;
            } else {
                ps[pspt]++;
            }
        }
        // for (int i = 1; i <= pppt; i++) {
        //     cerr << pp[i] << ',';
        // }
        // cerr << endl;
        // for (int i = 1; i <= pspt; i++) {
        //     cerr << ps[i] << ',';
        // }
        // cerr << endl;
        if (pppt != pspt) {
            cout << "NO" << endl;
            continue;
        }
        for (int i = 1; i <= pppt; i++) {
            if (ps[i] >= pp[i] && ps[i] <= 2 * pp[i]) {
                continue;
            } else {
                cout << "NO" << endl;
                goto nxt_loop;
            }
        }
        cout << "YES" << endl;
    nxt_loop:;
    }
    return 0;
}

T3

这是我三年前打的一个模拟赛的题目，原题P8474，是一个数列题。我懒得打公式了，直接抄题解吧。

std:

// P8474
#include <stdio.h>
int MOD = 1e9 + 7;
int main() {
  int n;
  scanf("%d", &n);
  long long ans = 1;
  int bi = 1;
  for (int i = 1; i <= n; i++) {
    bi = (bi << 1) % MOD;
    ans = ans * (bi - 1) % MOD;
  }
  printf("%lld\n", ans % MOD);
  return 0;
}

T4

原题OSU!。这题考虑第$i$位取0和取1的情况。如果取1，那么它和前面的形成连续段，新的答案是$x^3+3x^2+3x+1$，增加了$3x^2+3x+1$；如果取0，则不变仍然为$x^3$。然后我们分别维护$x,x^2,x^3$的值，然后将最终的答案加上增加的值，就能得到答案。

std:

// U139602
#include <bits/stdc++.h>

using namespace std;

double x1[114520], x2[114520], x3[114520], ans[114520];

int main()
{
    int n;
    cin >> n;
    double p;
    for (int i = 1; i <= n; i++) {
        cin >> p;
        x1[i] = (x1[i - 1] + 1) * p;
        x2[i] = (x2[i - 1] + 2 * x1[i - 1] + 1) * p;
        x3[i] = (x3[i - 1] + 3 * x2[i - 1] + 3 * x1[i - 1] + 1) * p;
        ans[i] = (ans[i - 1] + 4 * x3[i - 1] + 6 * x2[i - 1] + 4 * x1[i - 1] + 1) * p + ans[i - 1] * (1 - p);
    }
    cout << fixed << setprecision(1) << ans[n] << endl;
    return 0;
}