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

题解 https://ac.nowcoder.com/discuss/363450?type=101&order=0&pos=15&page=0

A. 托米的字符串

 

题意：给出一个字符串，求其所有子串中元音字母和’y’的期望占比。

前缀和套前缀和

主要是要得到计算公式。

期望=∑(1子串长度⋅子串含元音个数)子串个数期望=\frac{\sum(\frac{1}{子串长度}\cdot 子串含元音个数)}{子串个数}

首先对元音字母求一次前缀和，则 p[r]−p[l−1]p[r]-p[l-1] 表示 [l,r][l,r] 中含元音的个数。

考虑把相同长度的子串合在一起考虑，则对于长度 lenlen，起点从 11 到 n−len+1n-len+1 ，就是求 1len∑i=1n−len+1(p[i+len−1]−p[i−1])\frac{1}{len} \sum_{i=1}^{n-len+1}(p[i+len-1]-p[i-1])

把 ∑\sum 拆开放入后可以再得到关于 pp 的前缀和形式。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const ll maxn = 1e6 + 10;
ll n;
char a[maxn];
ll p[maxn], q[maxn];
double ans;
int main() {
	scanf("%s", a + 1);
	n = (ll)strlen(a + 1);
	for (ll i = 1; i <= n; i++) {
		if (a[i] == 'a' || a[i] == 'e' || a[i] == 'i' || a[i] == 'o' || a[i] == 'u' || a[i] == 'y')
			p[i] = p[i - 1] + 1;
		else p[i] = p[i - 1];
	}
	for (ll i = 1; i <= n; i++)q[i] = q[i - 1] + p[i];
	for (ll j = 1; j <= n; j++) {
		ans += 1.0 / j * (q[n] - q[j - 1] - q[n - j] + q[0]);
	}
	ans /= n * (n + 1)*0.5;
	printf("%.9lf\n", ans);
	return 0;
}

 

C. 纳新一百的石子游戏

 

题意：有 nn 堆石子，两个人，每人每轮可以从任意一堆中拿任意多石子。先拿不了的输。进行n次游戏，每次游戏只用前i堆石子，且每次游戏开始前复原所有石子堆。问每次游戏先手的人在第一轮有多少种方式使得自己获胜。

尼姆游戏,若面对石子异或和为0，必败。若有 n 堆石子，每堆石子数为 aia_i ，则先手要获胜就必须找到一堆石子，拿走这对石子中多于其它堆石子个数异或和的数量。即 ai−a1⨁a2⋯⨁ai−1⨁ai+1⋯⨁ana_i-a_1\bigoplus a_2\cdots\bigoplus a_{i-1}\bigoplus a_{i+1}\cdots \bigoplus a_n

则要找到满足 ai≥a1⨁a2⋯⨁ai−1⨁ai+1⋯⨁ana_i\geq a_1\bigoplus a_2\cdots\bigoplus a_{i-1}\bigoplus a_{i+1}\cdots \bigoplus a_n 的 i 的个数。

a1⨁a2⋯⨁ai−1⨁ai+1⋯⨁an=a1⨁a2⋯⨁an⨁ai=sum⨁aia_1\bigoplus a_2\cdots\bigoplus a_{i-1}\bigoplus a_{i+1}\cdots \bigoplus a_n=a_1\bigoplus a_2\cdots\bigoplus a_n\bigoplus a_i=sum\bigoplus a_i

所以每次 sum⨁=aisum\bigoplus =a_i，若sum=0，则先手必败，否则找到 ai≥sum⨁aia_i\geq sum\bigoplus a_i 的 i 的个数。

观察发现，ai≥sum⨁aia_i\geq sum\bigoplus a_i 等价于 aia_i 在sum的二进制最高位值为 1.

则再来个计数器，每次累加各个二进制位1的个数。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int n;
int a[100];
ll sum;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		ll x;
		scanf("%lld", &x);
		int flg = (sum <= x);
		sum ^= x;
		if (sum != 0) {
			int p = 61;
			for (; !(sum&(1ll << p)); p--);
			printf("%d\n", a[p] + flg);
		}
		else puts("0");
		for (int j = 0; j <= 60; j++) {
			if (x&(1ll << j))a[j]++;
		}
	}
	return 0;
}

 

E. 阔力梯的树

 

题意：有一棵树，求所有节点的子树的所有节点排序后相邻节点差的平方的和。

即假设子树的节点编号排序后的序列为a1,a2,a3,...,aka_1,a_2,a_3,...,a_k，这个节点的“结实程度”就是：
∑i=1k−1(ai+1−ai)2\sum_{i=1}^{k-1}\left(a_{i+1}-a_i\right)^2

树上启发式合并

所谓启发式合并就是把小的往大的里合并。这样可以降低暴力合并的复杂度。

而树上的启发式合并就是把轻儿子上的点往重儿子上合并。

详见 https://oi-wiki.org/graph/dsu-on-tree/

模板为：

  1. 先处理完轻儿子，但不保存合并结果，仅仅更新轻儿子自己的答案，用完就丢。
  2. 处理重儿子，这次保存处理结果以便处理自己。
  3. 再次处理轻儿子，这次在重儿子的结果上插入轻儿子，而不更新轻儿子自身答案，使其仅充当工具人的作用。

两次处理轻儿子可能并不是同一个函数。

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
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const ll maxn = 1e5 + 10;
ll n;
vector<ll>G[maxn];
ll siz[maxn], son[maxn];
void pre(ll u) {
	siz[u] = 1;
	for (ll v : G[u]) {
		pre(v);
		siz[u] += siz[v];
		if (siz[v] > siz[son[u]])son[u] = v;
	}
}
ll ans[maxn];
set<ll>st;
void ins(ll x, ll u) {
	auto iter = st.lower_bound(x);
	if (st.empty()) {
		st.insert(x);
		return;
	}
	if (iter == st.begin())ans[u] += ((*iter) - x)*((*iter) - x);
	else if (iter == st.end())ans[u] += (x - (*st.rbegin()))*(x - (*st.rbegin()));
	else {
		ll tmp = (*iter) - (*(--iter));
		ans[u] -= tmp * tmp;
		ans[u] += (x - (*iter))*(x - (*iter));
		tmp = (*(++iter)) - x;
		ans[u] += tmp * tmp;
	}
	st.insert(x);
}
void dfs2(ll u,ll p) {
	ins(u, p);
	for (ll v : G[u]) {
		dfs2(v, p);
	}
}
ll dfs(ll u, bool keep) {
	for (ll v : G[u]) {
		if (v == son[u])continue;
		dfs(v, 0);
	}
	if (son[u])ans[u] = dfs(son[u], 1);
	for (ll v : G[u]) {
		if (v == son[u])continue;
		dfs2(v, u);
	}
	ins(u, u);
	if (!keep)st.clear();
	return ans[u];
}
int main() {
	scanf("%lld", &n);
	for (ll i = 2; i <= n; i++) {
		ll u;
		scanf("%lld", &u);
		G[u].push_back(i);
	}
	pre(1);
	dfs(1, 0);
	for (ll i = 1; i <= n; i++)printf("%lld\n", ans[i]);
	return 0;
}

 

 

F. 采蘑菇的克拉莉丝

 

题意：给定一棵树，两种操作，第一种在结点v加入x个蘑菇，第二种把起点改为结点u。采蘑菇的代价是从起点到蘑菇的路径上最靠近起点的那条边的边权。问每次操作后，从起点采完所有蘑菇的代价，每次操作后要采所有蘑菇，蘑菇不会消失。

线段树+树链刨分

对于一个起点，所有蘑菇的代价就是把它的各个子结点子树中的蘑菇数乘以子节点边权再求和。

但是每次操作都统计，并且还会有变起点的操作，一定会超时。所以还是要固定根，最后直接输出每个点作为起点的答案。

对于么每个点，只统计它的重儿子，其他的在新增蘑菇时直接加进这个点的答案里。

新增蘑菇时，把它到根节点的路径上的所有重链上的点都加x，由于不断地向上跳的过程中断开只会是因为遇到了轻链，所以这时候把轻链上的点的答案直接加进去。

通过线段树达到区间加x的目的，可以发现，一个点的值就是这个点为根的子树中所有的蘑菇数。

统计答案时先把这个点外的所有蘑菇算出来（总的数量-这个点的子树中的数量），再加上重儿子的蘑菇，加上自己作为轻链的答案（即轻儿子的贡献）。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int n, Q;
struct E
{
	int v, w;
};
vector<E>G[maxn];
int vv[maxn];
int dfn[maxn], id[maxn], topf[maxn], fa[maxn], siz[maxn], son[maxn], cnt;
void dfs1(int u, int _fa) {
	fa[u] = _fa;
	siz[u] = 1;
	for (E e : G[u]) {
		if (e.v == _fa) {
			vv[u] = e.w;
			continue;
		}
		dfs1(e.v, u);
		siz[u] += siz[e.v];
		if (siz[e.v] > siz[son[u]])son[u] = e.v;
	}
}
void dfs2(int u, int topfa) {
	topf[u] = topfa;
	dfn[u] = ++cnt; id[cnt] = u;
	if (!son[u])return;
	dfs2(son[u], topfa);
	for (E e : G[u]) {
		if (!topf[e.v])dfs2(e.v, e.v);
	}
}
ll ans[maxn];
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
ll laz[maxn << 2];
void down(int rt) {
	ll& x = laz[rt];
	if (x) {
		laz[rt << 1] += x;
		laz[rt << 1 | 1] += x;
		x = 0;
	}
}
void update(int l, int r, int rt, int ql, int qr, int x) {
	if (ql <= l && qr >= r) {
		//tr[rt] += x;
		laz[rt] += x;
		return;
	}
	down(rt);
	if (ql <= mid)update(lson, ql, qr, x);
	if (qr > mid)update(rson, ql, qr, x);
	//pushup(rt);
}
void add(int u, int x) {
	while (u) {
		update(1, n, 1, dfn[topf[u]], dfn[u], x);
		ans[fa[topf[u]]] += 1ll * vv[topf[u]] * x;
		u = fa[topf[u]];
	}
}
ll query(int l, int r, int rt, int q) {
	if (l == r)return laz[rt];
	down(rt);
	if (q <= mid)return query(lson, q);
	else return query(rson, q);
}
ll sol(int u) {
	ll res = 1ll * (query(1, n, 1, dfn[1]) - query(1, n, 1, dfn[u]))*vv[u];
	//cout << query(1, n, 1, dfn[1]) << ' ' << query(1, n, 1, dfn[u]) << endl;
	if(son[u])
		res += 1ll * vv[son[u]] * query(1, n, 1, dfn[son[u]]);
	return res + ans[u];
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[u].push_back(E{ v,w });
		G[v].push_back(E{ u,w });
	}
	dfs1(1, 0);
	dfs2(1, 1);
	scanf("%d", &Q);
	int rt = 1;
	while (Q--) {
		int op;
		scanf("%d", &op);
		if (op == 1) {
			int u, x;
			scanf("%d%d", &u, &x);
			add(u, x);
		}
		else scanf("%d", &rt);
		printf("%lld\n", sol(rt));
	}
	return 0;
}

 

H. 叁佰爱抠的序列

 

题意：给定一个数 n，要求构造出一个长度为 n 的序列并给出 m，使得任意两个不同的 1 到 m 的数一定在这个序列中有相邻。要求 m 尽可能大。

欧拉路径

任意两个数相邻听起来是不是和任意两点相连很像？所以自然想到完全图。那么相邻就是有边相连，这个序列就是要包含完全图的所有的边。同时m最大，意味着相同m下，重复的边尽量少，这就是欧拉路径了。每条边只经过一次且经过所有边。

n 为奇数时根据定理得知一定有欧拉路径/回路。

n 为偶数时最少添加n−22\frac{n-2}{2} 条边，使得包含欧拉路径，间隔添加。

接下来就是二分找到最大的m，并输出欧拉路径。

由于边数比较多，所以直接递归会爆，且如果用邻接表的话擦除边时会超时，只有用前向星。

不能有行末空格！

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
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e7 + 10;
const int N = 2010;
ll n;
ll ans = 1;
int head[N], ver[maxn], nxt[maxn], tot;
int st[N*N], path[N*N], vis[maxn], top, t;
inline void add(int x, int y) {
	ver[++tot] = y; nxt[tot] = head[x]; head[x] = tot;
}
void euler() {
	st[++top] = 1;
	while (top) {
		int x = st[top], i = head[x];
		while (i && vis[i]) i = nxt[i];
		if (i) {
			st[++top] = ver[i];
			vis[i] = vis[i ^ 1] = true;
			head[x] = nxt[i];
		}
		else {
			top--;
			path[++t] = x;
		}
	}
}
int main() {
	scanf("%lld", &n);
	ll L = 0, R = 1e10;
	ll tmp = 0;
	while (L < R) {
		ll mid = L + (R - L + 1) / 2;
		tmp = 2 * mid - 1;
		if (tmp*(tmp - 1) / 2 + 1 > n)R = mid - 1;
		else L = mid;
	}
	ans = 2 * L - 1;
	L = 0, R = 1e10;
	while (L < R) {
		ll mid = L + (R - L + 1) / 2;
		tmp = 2 * mid;
		if (tmp*(tmp - 1) / 2 + (tmp - 2) / 2 + 1 > n)R = mid - 1;
		else L = mid;
	}
	ans = max(ans, 2 * L);
	cout << ans << endl;
	if (n > 2e6)return 0;
	tot = 1;
	for (int i = 1; i <= ans; i++) {
		for (int j = i + 1; j <= ans; j++) {
			add(i, j);
			add(j, i);
		}
	}
	if (ans % 2 == 0) {
		for (int i = 2; i < ans; i += 2) {
			add(i, i + 1);
			add(i + 1, i);
		}
	}
	euler();
	for (int i = t + 1; i <= n; i++)path[i] = 1;
	for (int i = 1; i <= n; i++)printf("%d%s", path[i], i == n ? "\n" : " ");
	return 0;
}

 

I. 堡堡的宝藏

 

题意：一张nm地图上相邻两格之间可能有连接，每个连接有边权，要求两端点的值之和大于等于边权。求所有点的值之和最小值。

KM最大权完备匹配

KM算法的思想就是相等子图上的匹配一定是最大权匹配。每次都是降低一边的顶标以向图中加入更多的边。虽然会有另一边的顶标增加，但是减小的那边一定会比增加的多出一个点，而由于两边单个点的改变量相等，所以这降低顶标的过程一定会导致所有点的顶标之和减小。

而一旦得到了完备匹配。就没办法再降低顶标了，这时就是本题的点值最小值。

所以本题就是要求KM完备匹配后所有点的顶标之和。

但是由于本题并不是直接给出了完备匹配。所以没法直接用KM。

若一个格子与两个相连，我们肯定是在这个格子上放大的那个w，放完之后相连的那两个格子都不能再放了。

所以就是费用流了。最大费用最大流，相同流量只走w大的那条边。

但是和匹配问题不同，这里两个点集都要和S相连。

否则就会如下图，为了保证最大流，而走了两条边权为1的边，实际上点2放2，点3放2，和为4，就能满足所有限制，但此时流量并不是最大。所以要免费提供多余的流量，就必须把3，4所在点集也连上S。

错误样例

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
int n, m, Q;
struct E
{
	int from, to, cp;
	ll v;
	int rev;
	E() {}
	E(int f, int t, int cp, ll v, int rev) :from(f), to(t), cp(cp), v(v), rev(rev) {}
};
struct MCMF
{
	int n, m, s, t;
	vector<E> edges;
	vector<int> G[maxn];
	bool inq[maxn];     //是否在队列
	ll d[maxn];        //Bellman_ford单源最短路径
	int p[maxn];        //p[i]表从s到i的最小费用路径上的最后一条弧编号
	int a[maxn];        //a[i]表示从s到i的最小残量
	void init(int _n, int _s, int _t) {
		n = _n; s = _s; t = _t;
		for (int i = 0; i < n; i++) G[i].clear();
		edges.clear(); m = 0;
	}

	void addedge(int from, int to, int cap, ll cost) {
		edges.push_back(E(from, to, cap, cost, 0));
		edges.push_back(E(to, from, 0, -cost, 1));
		G[from].push_back(m++);
		G[to].push_back(m++);
	}

	bool BellmanFord(int &flow, ll &cost) {
		for (int i = 0; i < n; i++) d[i] = inf;
		memset(inq, 0, sizeof inq);
		d[s] = 0, a[s] = INF, inq[s] = true;
		queue<int> Q; Q.push(s);
		while (!Q.empty()) {
			int u = Q.front(); Q.pop();
			inq[u] = false;
			for (int& idx : G[u]) {
				E &e = edges[idx];
				if (e.cp && d[e.to] > d[u] + e.v) {
					d[e.to] = d[u] + e.v;
					p[e.to] = idx;
					a[e.to] = min(a[u], e.cp);
					if (!inq[e.to]) {
						Q.push(e.to);
						inq[e.to] = true;
					}
				}
			}
		}
		if (d[t] == inf) return false;
		//if (flow + a[t] > K)a[t] = K - flow;//固定流量
		flow += a[t];
		cost += a[t] * d[t];
		int u = t;
		while (u != s) {
			edges[p[u]].cp -= a[t];
			edges[p[u] ^ 1].cp += a[t];
			u = edges[p[u]].from;
		}
		//if (flow == K)return false;//固定流量
		return true;
	}

	ll go() {
		int flow = 0;
		ll cost = 0;
		while (BellmanFord(flow, cost));
		return cost;
	}
} MM;
int id(int x, int y) {
	return x * m + y;
}
int main() {
	scanf("%d%d%d", &n, &m, &Q);
	int S = n * m, T = n * m + 1;
	MM.init(n*m + 2, S, T);
	while (Q--) {
		int x1, y1, x2, y2;
		ll w;
		scanf("%d%d%d%d%lld", &x1, &y1, &x2, &y2, &w);
		x1--; y1--; x2--; y2--;
		if ((x1 + y1) & 1)swap(x1, x2), swap(y1, y2);
		MM.addedge(id(x1, y1), id(x2, y2), 1, -w);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if ((i + j) & 1)MM.addedge(id(i, j), T, 1, 0);
			MM.addedge(S, id(i, j), 1, 0);
		}
	}
	printf("%lld\n", -MM.go());
	return 0;
}
/*
2 2 3
1 1 1 2 1
1 1 2 1 4
2 1 2 2 1
*/

 

J. 邦邦的2-SAT模板

 

题意：给出一个 O(nm)O(nm) 的2-SAT模板，找到一组达到复杂度 O(nm)O(nm) 的数据。

只有当 a‾\overline{a} 是必取的时候，dfs(a)dfs(a) 才是 falsefalse，所以要设置一个从 aa 不断深入，最终发现 cc 推出 c‾\overline{c} 。

刚开始我想了一个反过来的

这是不对的，因为它在 dfs(1‾)dfs(\overline{1}) 的时候就把 2‾,3‾\overline{2},\overline{3} 都visit了，而第一幅图由于没有出边，所以不会。

那么问题来了，这样的模板并不是没有用处，它可以控制输出一个字典序最小的答案，因为它每次都先尝试 dfs(a)dfs(a) 而不是 dfs(a‾)dfs(\overline{a})，所以要字典序最小，只要从位数小的向大的枚举，每次先试着 dfs(a)dfs(a) 即可。

而要真正的 O(n+m)O(n+m) 的方法还是要Tarjan缩强连通分量+拓扑序取答案，但是这样的答案是随机的，不能控制字典序大小。

并查集更不行，因为并查集连边没有方向。

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int n;
int main() {
    scanf("%d", &n);
    printf("%d\n", n);
    for (int i = 1; i < n; i++)printf("%d %d\n", -i, i + 1);
    printf("%d %d\n", -n, -n);
    return 0;
}

 

K. 破忒头的匿名信

 

题意：给出一些小串，和一个大串，每个小串有花费，要用尽可能少的花费用小串拼成大串。输出最小花费。

AC自动机+dp

遍历大串，每次找到树上的位置，再不断跳fail指针，更新dp值，注意要确保跳到的结点是某个小串的结尾。

所以这里AC自动机起到合法遍历字符串的作用。

把花费存在小串的结尾结点。

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
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
const int maxn = 1e6 + 10;
int n;
char s[maxn];
ll cost;
int tr[maxn][26], tot;
int e[maxn], fail[maxn], dep[maxn];
ll val[maxn];
void ins(char* s) {
	int u = 0;
	for (int i = 1; s[i]; i++) {
		if (!tr[u][s[i] - 'a']) {
			tr[u][s[i] - 'a'] = ++tot;
			val[tot] = INF;
		}
		u = tr[u][s[i] - 'a'];
	}
	e[u]++;
	dep[u] = strlen(s + 1);
	val[u] = min(val[u], cost);
}
queue<int> q;
void build() {
	for (int i = 0; i < 26; i++)
		if (tr[0][i]) q.push(tr[0][i]);
	while (q.size()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < 26; i++) {
			if (tr[u][i])
				fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
			else
				tr[u][i] = tr[fail[u]][i];
		}
	}
}
ll d[maxn];
bool vis[maxn];
void query(char* s) {
	int u = 0; ll res = 0;
	fill(d + 1, d + strlen(s+1) + 1, inf);
	vis[0] = 1;
	for (int i = 1; s[i]; i++) {
		u = tr[u][s[i] - 'a'];
		for (int j = u; j; j = fail[j]) {
			if (e[j] && vis[i - dep[j]]) {
				d[i] = min(d[i], d[i - dep[j]] + val[j]);
				vis[i] = 1;
			}
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf(" %s", s + 1);
		scanf("%lld", &cost);
		ins(s);
	}
	build();
	scanf(" %s", s + 1);
	query(s);
	printf("%lld\n", d[strlen(s + 1)] == inf ? -1 : d[strlen(s + 1)]);
	return 0;
}