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

C. 操作集锦

 

题意：问给定字符串有几个长度为 kk 的不同的子序列。

dp

dp[i][j]dp[i][j] 表示到第 ii 位，长度为 jj 的不同子序列个数。

如果第 ii 位的字母没有出现过，则可以直接再前面的所有序列末尾再加上，得到新的序列。

而如果出现过，那么就可能和最近一次相同的字母位置的dp重复，重复的数量就是前一次dp的值，因为前一次得到的序列，这一次一定都能得到。而每次都只减去最近一次的重复值，就可以保证不会多减。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n, k;
char s[N];
ll dp[1010][1010];int b[30];
int main() {
	scanf("%d%d", &n, &k);
	scanf("%s", s + 1);
	if (k == 0) { puts("1"); return 0; }
	for (int i = 0; i <= n; i++)dp[i][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] - dp[b[s[i] - 'a'] - 1][j - 1] + mod) % mod;
		}
		b[s[i] - 'a'] = i;
	}
	printf("%lld\n", dp[n][k]);
	return 0;
}

 

D. 斩杀线计算大师

 

题意：求三元一次不定方程 ax+by+cz=kax+by+cz=k 的一组非负整数解。1≤a,b,c≤1e51\leq a,b,c\leq 1e5，0≤k≤1e120\leq k\leq 1e12

要求的是非负整数解，所以如果直接枚举 xx 转成二元的话，复杂度得不到保证。而如果换元再解二元方程组的话，又不能保证找到解。

同余最短路

P3403 跳楼机

这里面的题解写的很清楚了，同余最短路就是求解给定 a,b,ca,b,c ，问用 a,b,ca,b,c 能凑出的数的个数或者最小的数。

大致思路就是dp，发现转移方程类似最短路，就用spfa求解dp。

dp[i]dp[i] 表示只用 a,ba,b 凑出的，且mod  c=i\mod c=i 的最小的数。

那么 ii 的范围只会是 [0,c)[0,c)

dp[(i+a)%c]=min(dp[(i+a)%c],dp[i]+a)dp[(i+b)%c]=min(dp[(i+b)%c],dp[i]+b)dp[(i+a)\%c]=min(dp[(i+a)\%c],dp[i]+a)\\ dp[(i+b)\%c]=min(dp[(i+b)\%c],dp[i]+b)\\

第一种表示 ii 的等价类中最小的数 +a+a，得到 (i+a)%c(i+a)\%c 的等价类中的一个数，再看如果这个数是最小的，就更新答案。第二种类似。

可以发现这个转移方程和最短路类似，所以可以最短路做，保证了复杂度不超过 clog⁡cc\log c。

还要记录一下是从+a+a 还是 +b+b 转移来的。因为 cz%c=0cz\%c=0，所以最后的终点就是 k%ck\%c。注意这样转移会使得 zz 最大，所以 zz 要用 long long。

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>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
typedef pair<int, int> pii;
int a, b, c, x, y; ll k, z;
int fa[N], op[N], d[N];
void spfa() {
	memset(d, 0x3f, sizeof(d));
	d[0] = 0;
	priority_queue<pii, vector<pii>, greater<pii> >q;
	q.push(pii(0, 0));
	while (!q.empty()) {
		int u = q.top().second, di = q.top().second; q.pop();
		if (di > d[u])continue;
		int v1 = (u + a) % c, v2 = (u + b) % c;
		if (d[v1] > d[u] + a) {
			d[v1] = d[u] + a;
			fa[v1] = u, op[v1] = 1;
			q.push(pii(d[v1], v1));
		}
		if (d[v2] > d[u] + b) {
			d[v2] = d[u] + b;
			fa[v2] = u, op[v2] = 2;
			q.push(pii(d[v2], v2));
		}
	}
}
int main() {
	scanf("%d%d%d%lld", &a, &b, &c, &k);
	spfa();
	int u = k % c;
	while (u) {
		if (op[u] == 1)x++;
		else y++;
		u = fa[u];
	}
	z = (k - d[k%c]) / c;
	printf("%d %d %lld\n", x, y, z);
	return 0;
}

 

E. 旗鼓相当的对手

 

题意：给定一棵树，有点权，每一对节点 (u,v)(u,v)，如果距离为 kk，且 LCA(u,v)≠u≠vLCA(u,v)\neq u\neq v，则 LCA(u,v)LCA(u,v) 的答案加上 uu 和 vv 的权值。

树上dsu

考虑 uu 的答案，就是在不同子树中，且距离为 kk 的点对的权值和。

首先把 uu 的重儿子的结果记录下来，以后再枚举轻儿子的子树，依次更新答案。如果当前节点是轻儿子，则删除自己的记录，保证记录下的始终是需要的重儿子。记录重儿子子树中每个深度下的节点权值和以及结点数，则对于节点 nwnw，与它对应的深度就是 2dep[lca]+k−dep[nw]2dep[lca]+k-dep[nw]，把这个深度下的权值都加上，再加上深度下的点数乘以 nwnw 的权值，就是 nwnw 的贡献。注意一边查询一边加，防止重复。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, k;
int a[N];
vector<int>G[N];
int son[N], siz[N], dep[N];
ll sum[N], cnt[N], ans[N];
void dfs1(int u, int _fa) {
	dep[u] = dep[_fa] + 1;
	siz[u] = 1;
	for (int v : G[u]) {
		if (v == _fa)continue;
		dfs1(v, u);
		siz[u] += siz[v];
		if (siz[v] > siz[son[u]])son[u] = v;
	}
}
void add(int u, int _fa, int op) {
	sum[dep[u]] += op * a[u];
	cnt[dep[u]] += op;
	for (int v : G[u])
		if (v != _fa)add(v, u, op);
}
void query(int u, int _fa, int lca) {
	int d = 2 * dep[lca] + k - dep[u];
	if (d <= 0)return;
	ans[lca] += sum[d] + a[u] * cnt[d];
	for (int v : G[u])
		if (v != _fa)query(v, u, lca);
}
void dsu(int u, int _fa, int op) {
	for (int v : G[u]) {
		if (v == _fa || v == son[u])continue;
		dsu(v, u, 0);
	}
	if(son[u])dsu(son[u], u, 1);
	for (int v : G[u]) {
		if (v == _fa || v == son[u])continue;
		query(v, u, u); add(v, u, 1);
	}
	cnt[dep[u]]++, sum[dep[u]] += a[u];
	if (!op)add(u, _fa, -1);
}
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1, 0);
	dsu(1, 0, 1);
	for (int i = 1; i <= n; i++)printf("%lld%c", ans[i], " \n"[i == n]);
	return 0;
}