cf 579 div3
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 #include 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\n", 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 #include 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\n", ans); return 0;}