https://ac.nowcoder.com/acm/contest/11169

D - 回文字D

 

题意：定义D型回文串：若长度小于D，则必是；否则，对于任意长度为D的连续子串，必须是回文串。给定D，串 S，要分割成 kk 个连续子串，满足每个子串都是D型回文串，问最小的 kk。

贪心+字符串哈希

假设用dp，则 dp[i]=min⁡j<i且S[j+1⋯i]为D型回文串(dp[j])+1dp[i]=\min\limits_{j<i且S[j+1\cdots i]为D型回文串}(dp[j])+1。

又容易发现 dp[i]dp[i] 必是递增的，所以上面这个dp实际上就是贪心选最长的D型回文串 S[j⋯i]S[j\cdots i]。

所以直接从头开始匹配最长的D型回文串即可。

匹配固定长度D的回文串可以用字符串哈希，正着哈希值等于反着哈希值，说明是回文串。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 1e7 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
const int maxm = 1e6 + 10;
int n, d;
char s[N];
ull h[N], rh[N], p[N], P = 131;
ull hsh(int l, int r, ull* h) {
	return h[r] - h[l - 1] * p[r - l + 1];
}
ull rhsh(int l, int r, ull* h) {
	return h[l] - h[r + 1] * p[r - l + 1];
}
int main() {
	scanf("%d%d", &n, &d);
	scanf("%s", s + 1);
	p[0] = 1;
	for (int i = 1; i <= n; i++) {
		h[i] = h[i - 1] * P + s[i] - 'a';
		p[i] = p[i - 1] * P;
	}
	for (int i = n; i >= 1; i--) {
		rh[i] = rh[i + 1] * P + s[i] - 'a';
	}
	int ans = 0, L = 1, R = 1;
	while (L <= n) {
		while (R <= n && (R - L + 1 < d || hsh(R - d + 1, R, h) == rhsh(R - d + 1, R, rh)))R++;
		ans++;
		L = R;
	}
	printf("%d\n", ans);
	return 0;
}

 

E - 小G的数学难题

 

题意：给定长度为 1≤n≤10001\le n\le 1000 的数列 a,b,ca,b,c，正整数 1≤P≤100001\le P\le 10000，且有 ai≤bia_i\le b_i，选出一个下标集合 SS，满足 ∑i∈Sai≤P\sum\limits_{i\in S}a_i\le P 且 ∑i∈Sbi≥P\sum\limits_{i\in S}b_i\ge P，且最小化 ∑i∈Sci\sum\limits_{i\in S}c_i.

dp+单调队列

dp[i][j]dp[i][j] 表示前 ii 个数，∑a≤j\sum a\le j 且 ∑b≥j\sum b\ge j，最小的 ∑c\sum c.

上面就是最关键最妙的一步了，假设现在是 dp[i][j]dp[i][j]，那么加上 a[i+1]a[i+1] 后，有 (∑a)′≤j+a[i+1],(∑b)′≥j+a[i+1](\sum a)'\le j+a[i+1],(\sum b)'\ge j+a[i+1]，且 (∑a)′≤j+b[i+1],(∑b)′≥j+b[i+1](\sum a)'\le j+b[i+1],(\sum b)'\ge j+b[i+1]，并且在 [j+a[i+1],j+b[i+1]][j+a[i+1],j+b[i+1]] 也都是如此。也就是说可以从 dp[i][j]dp[i][j] 更新到 dp[i+1][k],k∈[j+ai+1,j+bi+1]dp[i+1][k],k\in[j+a_{i+1},j+b_{i+1}]，换一下就是 dp[i][j]dp[i][j] 由 dp[i−1][k],k∈[j−bi,j−ai]dp[i-1][k],k\in[j-b_i,j-a_i] 转移得到。

枚举 ii，可以发现 [j−bi,j−ai][j-b_i,j-a_i] 这个区间是随着 jj 增加而向右移动的，所以通过单调队列维护这个范围内的 dp[i][k]dp[i][k] 的最小值。当然要是用个multiset也可以，但是复杂度多了个 log⁡\log。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
const int maxm = 1e6 + 10;
int T;
int n, P;
int a[N], b[N], c[N];
int dp[1010][10010];
int st, ed;
int que[N];
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &P);
		for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
		for (int i = 1; i <= n; i++)scanf("%d", &b[i]);
		for (int i = 1; i <= n; i++)scanf("%d", &c[i]);
		memset(dp, 0x3f, sizeof(dp));
		dp[0][0] = 0;
		for (int i = 1; i <= n; i++) {
			st = ed = 0;
			for (int j = 0; j <= P; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j < a[i])continue;
				while (ed > st&&dp[i - 1][que[ed - 1]] >= dp[i - 1][j - a[i]])ed--;
				que[ed++] = j - a[i];
				while (ed > st && que[st] < j - b[i])st++;
				dp[i][j] = min(dp[i][j], dp[i - 1][que[st]] + c[i]);
			}
		}
		if (dp[n][P] == INF)puts("IMPOSSIBLE!!!");
		else printf("%d\n", dp[n][P]);
	}
	return 0;
}