cf 579 div3 d1 d2 e

cf 579 div3 d1 d2 e

D1 D2

题意

给你一个s串和t串，求删除一个最长的子串，使得s的子序列仍然有t，求删除的最长子串的长度

题解

用L和R数组来记录t每个元素最早和最晚出现的位置。初始化maxn为max(R[0], |s| - L[|t|-1] - 1)表示删除的是位于子序列两端的子串，用maxn = max(R[i] - L[i-1] - 1, maxn)表示删除子序列中间的子串嗯，大概可以这么说

#include <cstdio>
#include <cstring>

int main() {
    char s[200010], t[200010];
    int l[200010], r[200010];
    scanf("%s %s", s, t);
    int n = strlen(s), m = strlen(t);
    for(int i = 0, j = 0; i < n && j < m; i++) {
        if(s[i] == t[j]) {
            l[j] = i;
            j++;
        }
    }
    for(int i = n - 1, j = m - 1; j >= 0 && i >= 0; i--) {
        if(s[i] == t[j]) {
            r[j] = i;
            j--;
        }
    }
    int maxn;
    if(n - l[m-1] - 1 > r[0]) maxn = n - l[m-1] - 1;
    else maxn = r[0];
    for(int i = 1; i < m; i++) {
        if(r[i] - l[i-1] - 1> maxn) maxn = r[i] - l[i-1] - 1;
    }
    printf("%d
", maxn);
    return 0;
}

E

题意

给你一个序列，该序列的数可以变成他+1或者-1的数，但必须是大于0的，比如1只能变成2，而2可以变成1或者3，求该序列不同的数最多有多少个？

题解

如果a[i]是第一次出现(cnt[a[i]] == 0)，那么如果a[i]-1没有出现过了话，就把a[i]变成a[i]-1，a[i]-1已经出现过的话，就不变。

如果a[i]不是第一次出现了话(cnt[a[i]] > 0)，就把a[i]变成a[i]+1

cnt[a[i]]表示a[i]的数量

#include <cstdio>
#include <algorithm>
using std::sort;
 
int cnt[150010], a[150010];
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a + n);
    for(int i = 0; i < n; i++) {
        if(cnt[a[i]]) cnt[a[i]+1]++;
        else if(cnt[a[i] - 1] == 0 && a[i] > 1) cnt[a[i] - 1]++;
        else cnt[a[i]]++;
    }
    int ans = 0;
    for(int i = 1; i < 150002; i++) {
        if(cnt[i]) ans++;
    }
    printf("%d
", ans);
    return 0;
}