T1

第一类斯特林数裸题

T2

一对相同的字符会产生一次重复的贡献，分计算26种字符的出现次数\(cnt_i\)，然后总和减去\(\frac{cnt_i*(cnt_i-1)}{2}\)

T4

不难得出一个人只会向左一直走然后右转，或向右一直走然后左转，且不会经过旁边的人的初始位置

于是可以dp，\(f_{i,j}\)表示第 i 个人终止在第 j 个点，前 i 个人的最短时间

转移就考虑枚举第 i-1 个人的终止位置，和第 i 个人的终止位置，计算第 i 个人移动的时间

考虑到整个dp实际只会有\(O(n)\)的合法状态，可以考虑将第二维在unordered_map上进行

空间复杂度\(O(n)\)，时间复杂度未知

代码

T1

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int N = 3e3 + 11;
int n, k;
int f[N][N];
inline void md(int& x) {
    if (x >= mod)
        x -= mod;
    return;
}
inline int read() {
    int s = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s;
}
signed main() {
    FILE* x = freopen("broken.in", "r", stdin);
    x = freopen("broken.out", "w", stdout);
    n = read();
    k = read();
    f[0][0] = 1;
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= k; ++j) md(f[i][j] += f[i - 1][j - 1] + f[i - 1][j] * (i - 1) % mod);
    for (int i = 1; i <= k; ++i) md(ans += f[n][i]);
    cout << ans << endl;
    return 0;
}

T2

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const ull p = 131;
const int N = 3e6 + 11;
char tx[N];
int n;
ull cnt[N];
ull mi[N];
int main() {
    FILE* h = freopen("turn.in", "r", stdin);
    h = freopen("turn.out", "w", stdout);
    cin >> (tx + 1);
    n = strlen(tx + 1);
    for (int i = 1; i <= n; ++i) ++cnt[tx[i] - 'a' + 1];
    ull sl = 0;
    for (int i = 1; i <= 26; ++i) sl += cnt[i] * (cnt[i] - 1) / 2;
    cout << 1ll * n * (n - 1) / 2 - sl + 1 << endl;
    return 0;
}

T4

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e6 + 11;
const int inf = 1e18;
int n, m;
int x[N], y[N];
int lsh[N], num;
unordered_map<int, int> f[N];
inline int max_(int a, int b) { return a > b ? a : b; }
inline int min_(int a, int b) { return a > b ? b : a; }
inline int calc(int l, int mid, int r) {
    return l = lsh[l], r = lsh[r], mid = lsh[mid], 2 * min_(mid - l, r - mid) + max_(mid - l, r - mid);
}
inline int read() {
    int s = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s;
}
void lsh_() {
    sort(lsh + 1, lsh + num + 1);
    int h = unique(lsh + 1, lsh + num + 1) - lsh;
    for (int i = 1; i <= n; ++i) x[i] = lower_bound(lsh + 1, lsh + h, x[i]) - lsh;
    for (int i = 1; i <= m; ++i) y[i] = lower_bound(lsh + 1, lsh + h, y[i]) - lsh;
    return;
}
signed main() {
    FILE* p = freopen("duplication.in", "r", stdin);
    p = freopen("duplication.out", "w", stdout);
    n = read(), m = read();
    for (int i = 1; i <= n; ++i) lsh[++num] = x[i] = read();
    for (int i = 1; i <= m; ++i) lsh[++num] = y[i] = read();
    sort(x + 1, x + n + 1);
    sort(y + 1, y + m + 1);
    lsh_();
    if (n == 1) {
        if (lsh[y[1]] > lsh[x[1]])
            cout << lsh[y[m]] - lsh[x[1]] << endl;
        else if (lsh[y[m]] < lsh[x[1]])
            cout << lsh[x[1]] - lsh[y[1]] << endl;
        else
            cout << calc(y[1], x[1], y[m]) << endl;
        return 0;
    }
    for (int i = x[1]; i < x[2]; ++i) {
        if (lsh[y[1]] < lsh[x[1]])
            f[1][i] = calc(y[1], x[1], i);
        else
            f[1][i] = lsh[i] - lsh[x[1]];
    }
    for (int i = 2; i < n; ++i) {
        for (int k = x[i]; k <= x[i + 1] - 1; ++k) f[i][k] = inf;
        for (int j = x[i - 1] + 1; j <= x[i]; ++j)
            for (int k = x[i]; k <= x[i + 1] - 1; ++k)
                f[i][k] = min_(f[i][k], max_(f[i - 1][j - 1], calc(j, x[i], k)));
    }
    if (lsh[y[m]] > lsh[x[n]])
        f[n][y[m]] = inf;
    else
        f[n][x[n]] = inf;
    for (int i = x[n - 1] + 1; i <= x[n]; ++i) {
        if (lsh[y[m]] > lsh[x[n]])
            f[n][y[m]] = min_(f[n][y[m]], max_(f[n - 1][i - 1], calc(i, x[n], y[m])));
        else
            f[n][x[n]] = min_(f[n][x[n]], max_(f[n - 1][i - 1], calc(i, x[n], x[n])));
    }
    if (lsh[y[m]] > lsh[x[n]])
        cout << f[n][y[m]] << endl;
    else
        cout << f[n][x[n]] << endl;
    return 0;
}